correction of SubGraphWrapper bug.
7 #include <hugo/map_iterator.h>
8 #include <hugo/map_bits.h>
12 ///\brief Graph maps that construates and destruates
13 ///their elements dynamically.
18 /// \addtogroup graphmaps
21 /** The ArrayMap template class is graph map structure what
22 * automatically updates the map when a key is added to or erased from
23 * the map. This map factory uses the allocators to implement
24 * the container functionality.
26 * The template parameter is the MapRegistry that the maps
27 * will belong to and the ValueType.
30 template <typename MapRegistry, typename Value>
31 class ArrayMap : public MapRegistry::MapBase {
35 /// The graph type of the maps.
36 typedef typename MapRegistry::Graph Graph;
37 /// The key type of the maps.
38 typedef typename MapRegistry::KeyType KeyType;
39 /// The iterator to iterate on the keys.
40 typedef typename MapRegistry::KeyIt KeyIt;
42 /// The MapBase of the Map which imlements the core regisitry function.
43 typedef typename MapRegistry::MapBase MapBase;
48 /// The value type of the map.
49 typedef Value ValueType;
50 /// The reference type of the map;
51 typedef Value& ReferenceType;
52 /// The pointer type of the map;
53 typedef Value* PointerType;
55 /// The const value type of the map.
56 typedef const Value ConstValueType;
57 /// The const reference type of the map;
58 typedef const Value& ConstReferenceType;
59 /// The pointer type of the map;
60 typedef const Value* ConstPointerType;
63 typedef std::allocator<Value> Allocator;
66 /** Default constructor for the map.
68 ArrayMap() : values(0), capacity(0) {}
70 /** Graph and Registry initialized map constructor.
72 ArrayMap(const Graph& g, MapRegistry& r) : MapBase(g, r) {
74 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
75 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
76 allocator.construct(&(values[id]), Value());
80 /** Constructor to use default value to initialize the map.
82 ArrayMap(const Graph& g, MapRegistry& r, const Value& v)
85 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
86 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
87 allocator.construct(&(values[id]), v);
91 /** Constructor to copy a map of the same map type.
93 ArrayMap(const ArrayMap& copy) : MapBase(*copy.graph, *copy.registry) {
94 capacity = copy.capacity;
95 if (capacity == 0) return;
96 values = allocator.allocate(capacity);
97 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
98 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
99 allocator.construct(&(values[id]), copy.values[id]);
103 /** Constructor to copy a map of an other map type.
105 template <typename CMap> ArrayMap(const CMap& copy)
106 : MapBase(copy), capacity(0), values(0) {
107 if (MapBase::getGraph()) {
109 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
115 /** Assign operator to copy a map of the same map type.
117 ArrayMap& operator=(const ArrayMap& copy) {
118 if (© == this) return *this;
121 allocator.deallocate(values, capacity);
123 capacity = copy.capacity;
124 if (capacity == 0) return *this;
125 values = allocator.allocate(capacity);
126 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
127 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
128 allocator.construct(&(values[id]), copy.values[id]);
133 /** Assign operator to copy a map an other map type.
135 template <typename CMap> ArrayMap& operator=(const CMap& copy) {
138 allocator.deallocate(values, capacity);
140 MapBase::operator=(copy);
141 if (MapBase::getGraph()) {
143 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
150 /** The destructor of the map.
152 virtual ~ArrayMap() {
155 allocator.deallocate(values, capacity);
161 * The subscript operator. The map can be subscripted by the
162 * actual keys of the graph.
164 ReferenceType operator[](const KeyType& key) {
165 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
170 * The const subscript operator. The map can be subscripted by the
171 * actual keys of the graph.
173 ConstReferenceType operator[](const KeyType& key) const {
174 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
178 /** Setter function of the map. Equivalent with map[key] = val.
179 * This is a compatibility feature with the not dereferable maps.
181 void set(const KeyType& key, const ValueType& val) {
182 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
186 /** Add a new key to the map. It called by the map registry.
188 void add(const KeyType& key) {
189 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
190 if (id >= capacity) {
191 int new_capacity = (capacity == 0 ? 1 : capacity);
192 while (new_capacity <= id) {
195 Value* new_values = allocator.allocate(new_capacity);;
196 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
197 int jd = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
199 allocator.construct(&(new_values[jd]), values[jd]);
200 allocator.destroy(&(values[jd]));
203 if (capacity != 0) allocator.deallocate(values, capacity);
205 capacity = new_capacity;
207 allocator.construct(&(values[id]), Value());
210 /** Erase a key from the map. It called by the map registry.
212 void erase(const KeyType& key) {
213 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
214 allocator.destroy(&(values[id]));
217 /** Clear the data structure.
222 allocator.deallocate(values, capacity);
227 /// The stl compatible pair iterator of the map.
228 typedef MapIterator<ArrayMap> Iterator;
229 /// The stl compatible const pair iterator of the map.
230 typedef MapConstIterator<ArrayMap> ConstIterator;
232 /** Returns the begin iterator of the map.
235 return Iterator(*this, KeyIt(*MapBase::getGraph()));
238 /** Returns the end iterator of the map.
241 return Iterator(*this, INVALID);
244 /** Returns the begin ConstIterator of the map.
246 ConstIterator begin() const {
247 return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
250 /** Returns the end const_iterator of the map.
252 ConstIterator end() const {
253 return ConstIterator(*this, INVALID);
256 /// The KeySet of the Map.
257 typedef MapConstKeySet<ArrayMap> ConstKeySet;
259 /// KeySet getter function.
260 ConstKeySet keySet() const {
261 return ConstKeySet(*this);
264 /// The ConstValueSet of the Map.
265 typedef MapConstValueSet<ArrayMap> ConstValueSet;
267 /// ConstValueSet getter function.
268 ConstValueSet valueSet() const {
269 return ConstValueSet(*this);
272 /// The ValueSet of the Map.
273 typedef MapValueSet<ArrayMap> ValueSet;
275 /// ValueSet getter function.
276 ValueSet valueSet() {
277 return ValueSet(*this);
282 void allocate_memory() {
283 int max_id = KeyInfo<Graph, KeyIt>::maxId(*MapBase::getGraph());
290 while (capacity <= max_id) {
293 values = allocator.allocate(capacity);
301 // STL compatibility typedefs.
302 typedef Iterator iterator;
303 typedef ConstIterator const_iterator;
304 typedef typename Iterator::PairValueType value_type;
305 typedef typename Iterator::KeyType key_type;
306 typedef typename Iterator::ValueType data_type;
307 typedef typename Iterator::PairReferenceType reference;
308 typedef typename Iterator::PairPointerType pointer;
309 typedef typename ConstIterator::PairReferenceType const_reference;
310 typedef typename ConstIterator::PairPointerType const_pointer;
311 typedef int difference_type;