33 /** The ArrayMap template class is graph map structure what |
34 /** The ArrayMap template class is graph map structure what |
34 * automatically updates the map when a key is added to or erased from |
35 * automatically updates the map when a key is added to or erased from |
35 * the map. This map factory uses the allocators to implement |
36 * the map. This map factory uses the allocators to implement |
36 * the container functionality. |
37 * the container functionality. |
37 * |
38 * |
38 * The template parameter is the MapRegistry that the maps |
39 * The template parameter is the AlterationNotifier that the maps |
39 * will belong to and the Value. |
40 * will belong to and the Value. |
40 */ |
41 */ |
41 |
42 |
42 template <typename _Graph, |
43 template <typename _Graph, |
43 typename _Item, |
44 typename _Item, |
44 typename _ItemIt, |
|
45 typename _Value> |
45 typename _Value> |
46 class ArrayMap : public AlterationNotifier<_Item>::ObserverBase { |
46 class ArrayMap : public AlterationNotifier<_Item>::ObserverBase { |
47 |
47 |
|
48 typedef _Item Item; |
48 public: |
49 public: |
49 |
50 |
50 /// The graph type of the maps. |
51 /// The graph type of the maps. |
51 typedef _Graph Graph; |
52 typedef _Graph Graph; |
52 /// The key type of the maps. |
53 /// The key type of the maps. |
53 typedef _Item Key; |
54 typedef _Item Key; |
54 |
55 |
55 typedef AlterationNotifier<_Item> Registry; |
56 typedef AlterationNotifier<_Item> Registry; |
56 |
57 |
57 private: |
|
58 /// The iterator to iterate on the keys. |
|
59 typedef _ItemIt KeyIt; |
|
60 |
|
61 /// The MapBase of the Map which imlements the core regisitry function. |
58 /// The MapBase of the Map which imlements the core regisitry function. |
62 typedef typename Registry::ObserverBase Parent; |
59 typedef typename Registry::ObserverBase Parent; |
63 |
60 |
64 |
|
65 public: |
|
66 |
|
67 /// The value type of the map. |
61 /// The value type of the map. |
68 typedef _Value Value; |
62 typedef _Value Value; |
69 /// The reference type of the map; |
|
70 typedef Value& Reference; |
|
71 /// The pointer type of the map; |
|
72 typedef Value* Pointer; |
|
73 |
|
74 /// The const value type of the map. |
|
75 typedef const Value ConstValue; |
|
76 /// The const reference type of the map; |
|
77 typedef const Value& ConstReference; |
|
78 /// The pointer type of the map; |
|
79 typedef const Value* ConstPointer; |
|
80 |
63 |
81 |
64 |
82 private: |
65 private: |
83 typedef std::allocator<Value> Allocator; |
66 typedef std::allocator<Value> Allocator; |
84 |
67 |
86 public: |
69 public: |
87 |
70 |
88 /** Graph and Registry initialized map constructor. |
71 /** Graph and Registry initialized map constructor. |
89 */ |
72 */ |
90 ArrayMap(const Graph& _g) : graph(&_g) { |
73 ArrayMap(const Graph& _g) : graph(&_g) { |
|
74 Item it; |
|
75 attach(_g.getNotifier(Item())); |
|
76 allocate_memory(); |
|
77 for (graph->first(it); it != INVALID; graph->next(it)) { |
|
78 int id = graph->id(it);; |
|
79 allocator.construct(&(values[id]), Value()); |
|
80 } |
|
81 } |
|
82 |
|
83 /// Constructor to use default value to initialize the map. |
|
84 |
|
85 /// It constrates a map and initialize all of the the map. |
|
86 |
|
87 ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) { |
|
88 Item it; |
91 attach(_g.getNotifier(_Item())); |
89 attach(_g.getNotifier(_Item())); |
92 allocate_memory(); |
90 allocate_memory(); |
93 for (KeyIt it(*graph); it != INVALID; ++it) { |
91 for (graph->first(it); it != INVALID; graph->next(it)) { |
94 int id = graph->id(it);; |
|
95 allocator.construct(&(values[id]), Value()); |
|
96 } |
|
97 } |
|
98 |
|
99 /// Constructor to use default value to initialize the map. |
|
100 |
|
101 /// It constrates a map and initialize all of the the map. |
|
102 |
|
103 ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) { |
|
104 attach(_g.getNotifier(_Item())); |
|
105 allocate_memory(); |
|
106 for (KeyIt it(*graph); it != INVALID; ++it) { |
|
107 int id = graph->id(it);; |
92 int id = graph->id(it);; |
108 allocator.construct(&(values[id]), _v); |
93 allocator.construct(&(values[id]), _v); |
109 } |
94 } |
110 } |
95 } |
111 |
96 |
116 attach(*copy.getRegistry()); |
101 attach(*copy.getRegistry()); |
117 } |
102 } |
118 capacity = copy.capacity; |
103 capacity = copy.capacity; |
119 if (capacity == 0) return; |
104 if (capacity == 0) return; |
120 values = allocator.allocate(capacity); |
105 values = allocator.allocate(capacity); |
121 for (KeyIt it(*graph); it != INVALID; ++it) { |
106 Item it; |
|
107 for (graph->first(it); it != INVALID; graph->next(it)) { |
122 int id = graph->id(it);; |
108 int id = graph->id(it);; |
123 allocator.construct(&(values[id]), copy.values[id]); |
109 allocator.construct(&(values[id]), copy.values[id]); |
124 } |
110 } |
125 } |
111 } |
126 |
112 |
144 capacity = copy.capacity; |
130 capacity = copy.capacity; |
145 if (capacity == 0) return *this; |
131 if (capacity == 0) return *this; |
146 values = allocator.allocate(capacity); |
132 values = allocator.allocate(capacity); |
147 } |
133 } |
148 |
134 |
149 for (KeyIt it(*graph); it != INVALID; ++it) { |
135 Item it; |
|
136 for (graph->first(it); it != INVALID; graph->next(it)) { |
150 int id = graph->id(it);; |
137 int id = graph->id(it);; |
151 allocator.construct(&(values[id]), copy.values[id]); |
138 allocator.construct(&(values[id]), copy.values[id]); |
152 } |
139 } |
153 |
140 |
154 return *this; |
141 return *this; |
166 |
153 |
167 /** |
154 /** |
168 * The subscript operator. The map can be subscripted by the |
155 * The subscript operator. The map can be subscripted by the |
169 * actual keys of the graph. |
156 * actual keys of the graph. |
170 */ |
157 */ |
171 Reference operator[](const Key& key) { |
158 Value& operator[](const Key& key) { |
172 int id = graph->id(key); |
159 int id = graph->id(key); |
173 return values[id]; |
160 return values[id]; |
174 } |
161 } |
175 |
162 |
176 /** |
163 /** |
177 * The const subscript operator. The map can be subscripted by the |
164 * The const subscript operator. The map can be subscripted by the |
178 * actual keys of the graph. |
165 * actual keys of the graph. |
179 */ |
166 */ |
180 ConstReference operator[](const Key& key) const { |
167 const Value& operator[](const Key& key) const { |
181 int id = graph->id(key); |
168 int id = graph->id(key); |
182 return values[id]; |
169 return values[id]; |
183 } |
170 } |
184 |
171 |
185 /** Setter function of the map. Equivalent with map[key] = val. |
172 /** Setter function of the map. Equivalent with map[key] = val. |
197 int new_capacity = (capacity == 0 ? 1 : capacity); |
184 int new_capacity = (capacity == 0 ? 1 : capacity); |
198 while (new_capacity <= id) { |
185 while (new_capacity <= id) { |
199 new_capacity <<= 1; |
186 new_capacity <<= 1; |
200 } |
187 } |
201 Value* new_values = allocator.allocate(new_capacity); |
188 Value* new_values = allocator.allocate(new_capacity); |
202 for (KeyIt it(*graph); it != INVALID; ++it) { |
189 Item it; |
|
190 for (graph->first(it); it != INVALID; graph->next(it)) { |
203 int jd = graph->id(it);; |
191 int jd = graph->id(it);; |
204 if (id != jd) { |
192 if (id != jd) { |
205 allocator.construct(&(new_values[jd]), values[jd]); |
193 allocator.construct(&(new_values[jd]), values[jd]); |
206 allocator.destroy(&(values[jd])); |
194 allocator.destroy(&(values[jd])); |
207 } |
195 } |
220 allocator.destroy(&(values[id])); |
208 allocator.destroy(&(values[id])); |
221 } |
209 } |
222 |
210 |
223 void build() { |
211 void build() { |
224 allocate_memory(); |
212 allocate_memory(); |
225 for (KeyIt it(*graph); it != INVALID; ++it) { |
213 Item it; |
|
214 for (graph->first(it); it != INVALID; graph->next(it)) { |
226 int id = graph->id(it);; |
215 int id = graph->id(it);; |
227 allocator.construct(&(values[id]), Value()); |
216 allocator.construct(&(values[id]), Value()); |
228 } |
217 } |
229 } |
218 } |
230 |
219 |
231 void clear() { |
220 void clear() { |
232 if (capacity != 0) { |
221 if (capacity != 0) { |
233 for (KeyIt it(*graph); it != INVALID; ++it) { |
222 Item it; |
|
223 for (graph->first(it); it != INVALID; graph->next(it)) { |
234 int id = graph->id(it);; |
224 int id = graph->id(it);; |
235 allocator.destroy(&(values[id])); |
225 allocator.destroy(&(values[id])); |
236 } |
226 } |
237 allocator.deallocate(values, capacity); |
227 allocator.deallocate(values, capacity); |
238 capacity = 0; |
228 capacity = 0; |
311 const Graph* graph; |
301 const Graph* graph; |
312 int capacity; |
302 int capacity; |
313 Value* values; |
303 Value* values; |
314 Allocator allocator; |
304 Allocator allocator; |
315 |
305 |
316 public: |
|
317 // // STL compatibility typedefs. |
|
318 // typedef Iterator iterator; |
|
319 // typedef ConstIterator const_iterator; |
|
320 // typedef typename Iterator::PairValue value_type; |
|
321 // typedef typename Iterator::Key key_type; |
|
322 // typedef typename Iterator::Value data_type; |
|
323 // typedef typename Iterator::PairReference reference; |
|
324 // typedef typename Iterator::PairPointer pointer; |
|
325 // typedef typename ConstIterator::PairReference const_reference; |
|
326 // typedef typename ConstIterator::PairPointer const_pointer; |
|
327 // typedef int difference_type; |
|
328 }; |
306 }; |
329 |
307 |
330 template <typename _Base> |
308 template <typename _Base> |
331 class ArrayMappableGraphExtender : public _Base { |
309 class ArrayMappableGraphExtender : public _Base { |
332 public: |
310 public: |
343 typedef typename Parent::EdgeNotifier EdgeObserverRegistry; |
321 typedef typename Parent::EdgeNotifier EdgeObserverRegistry; |
344 |
322 |
345 |
323 |
346 |
324 |
347 template <typename _Value> |
325 template <typename _Value> |
348 class NodeMap : public ArrayMap<Graph, Node, NodeIt, _Value> { |
326 class NodeMap |
|
327 : public IterableMapExtender<ArrayMap<Graph, Node, _Value> > { |
349 public: |
328 public: |
350 typedef ArrayMappableGraphExtender<_Base> Graph; |
329 typedef ArrayMappableGraphExtender<_Base> Graph; |
351 |
330 |
352 typedef typename Graph::Node Node; |
331 typedef typename Graph::Node Node; |
353 typedef typename Graph::NodeIt NodeIt; |
332 typedef typename Graph::NodeIt NodeIt; |
354 |
333 |
355 typedef ArrayMap<Graph, Node, NodeIt, _Value> Parent; |
334 typedef IterableMapExtender<ArrayMap<Graph, Node, _Value> > Parent; |
356 |
335 |
357 //typedef typename Parent::Graph Graph; |
336 //typedef typename Parent::Graph Graph; |
358 typedef typename Parent::Value Value; |
337 typedef typename Parent::Value Value; |
359 |
338 |
360 NodeMap(const Graph& g) |
339 NodeMap(const Graph& g) |
363 : Parent(g, v) {} |
342 : Parent(g, v) {} |
364 |
343 |
365 }; |
344 }; |
366 |
345 |
367 template <typename _Value> |
346 template <typename _Value> |
368 class EdgeMap : public ArrayMap<Graph, Edge, EdgeIt, _Value> { |
347 class EdgeMap |
|
348 : public IterableMapExtender<ArrayMap<Graph, Edge, _Value> > { |
369 public: |
349 public: |
370 typedef ArrayMappableGraphExtender<_Base> Graph; |
350 typedef ArrayMappableGraphExtender<_Base> Graph; |
371 |
351 |
372 typedef typename Graph::Edge Edge; |
352 typedef typename Graph::Edge Edge; |
373 typedef typename Graph::EdgeIt EdgeIt; |
353 typedef typename Graph::EdgeIt EdgeIt; |
374 |
354 |
375 typedef ArrayMap<Graph, Edge, EdgeIt, _Value> Parent; |
355 typedef IterableMapExtender<ArrayMap<Graph, Edge, _Value> > Parent; |
376 |
356 |
377 //typedef typename Parent::Graph Graph; |
357 //typedef typename Parent::Graph Graph; |
378 typedef typename Parent::Value Value; |
358 typedef typename Parent::Value Value; |
379 |
359 |
380 EdgeMap(const Graph& g) |
360 EdgeMap(const Graph& g) |