75 typedef const Value& ConstReferenceType; |
84 typedef const Value& ConstReferenceType; |
76 /// The pointer type of the map; |
85 /// The pointer type of the map; |
77 typedef const Value* ConstPointerType; |
86 typedef const Value* ConstPointerType; |
78 |
87 |
79 |
88 |
|
89 private: |
80 typedef std::allocator<Value> Allocator; |
90 typedef std::allocator<Value> Allocator; |
81 |
91 |
82 |
92 |
|
93 public: |
|
94 |
83 /** Graph and Registry initialized map constructor. |
95 /** Graph and Registry initialized map constructor. |
84 */ |
96 */ |
85 ArrayMap(const Graph& g, MapRegistry& r) : MapBase(g, r) { |
97 ArrayMap(const Graph& _g, Registry& _r) : graph(&_g) { |
|
98 attach(_r); |
86 allocate_memory(); |
99 allocate_memory(); |
87 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { |
100 for (KeyIt it(*graph); it != INVALID; ++it) { |
88 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it); |
101 int id = IdMap(*graph)[it]; |
89 allocator.construct(&(values[id]), Value()); |
102 allocator.construct(&(values[id]), Value()); |
90 } |
103 } |
91 } |
104 } |
92 |
105 |
93 /** Constructor to use default value to initialize the map. |
106 /// Constructor to use default value to initialize the map. |
94 */ |
107 |
95 ArrayMap(const Graph& g, MapRegistry& r, const Value& v) |
108 /// It constrates a map and initialize all of the the map. |
96 : MapBase(g, r) { |
109 |
|
110 ArrayMap(const Graph& _g, Registry& _r, const Value& _v) : graph(&_g) { |
|
111 attach(_r); |
97 allocate_memory(); |
112 allocate_memory(); |
98 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { |
113 for (KeyIt it(*graph); it != INVALID; ++it) { |
99 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it); |
114 int id = IdMap(*graph)[it]; |
100 allocator.construct(&(values[id]), v); |
115 allocator.construct(&(values[id]), _v); |
101 } |
116 } |
102 } |
117 } |
103 |
118 |
104 /** Constructor to copy a map of the same map type. |
119 /** Constructor to copy a map of the same map type. |
105 */ |
120 */ |
106 ArrayMap(const ArrayMap& copy) : MapBase(copy) { |
121 ArrayMap(const ArrayMap& copy) { |
|
122 if (copy.attached()) { |
|
123 attach(*copy.getRegistry()); |
|
124 } |
107 capacity = copy.capacity; |
125 capacity = copy.capacity; |
108 if (capacity == 0) return; |
126 if (capacity == 0) return; |
109 values = allocator.allocate(capacity); |
127 values = allocator.allocate(capacity); |
110 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { |
128 for (KeyIt it(*graph); it != INVALID; ++it) { |
111 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it); |
129 int id = IdMap(*graph)[it]; |
112 allocator.construct(&(values[id]), copy.values[id]); |
|
113 } |
|
114 } |
|
115 |
|
116 /** Constructor to copy a map of an other map type. |
|
117 */ |
|
118 template <typename TT> |
|
119 ArrayMap(const ArrayMap<MapRegistry, TT>& copy) |
|
120 : MapBase(copy) { |
|
121 capacity = copy.capacity; |
|
122 if (capacity == 0) return; |
|
123 values = allocator.allocate(capacity); |
|
124 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { |
|
125 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it); |
|
126 allocator.construct(&(values[id]), copy.values[id]); |
130 allocator.construct(&(values[id]), copy.values[id]); |
127 } |
131 } |
128 } |
132 } |
129 |
133 |
130 /** Assign operator to copy a map of the same map type. |
134 /** Assign operator to copy a map of the same map type. |
131 */ |
135 */ |
132 ArrayMap& operator=(const ArrayMap& copy) { |
136 ArrayMap& operator=(const ArrayMap& copy) { |
133 if (© == this) return *this; |
137 if (© == this) return *this; |
134 |
138 |
135 if (MapBase::getGraph() != copy.getGraph()) { |
139 if (graph != copy.graph) { |
136 if (capacity != 0) { |
140 if (attached()) { |
137 MapBase::destroy(); |
141 clear(); |
138 allocator.deallocate(values, capacity); |
142 detach(); |
139 } |
143 } |
140 |
144 if (copy.attached()) { |
141 MapBase::operator=(copy); |
145 attach(*copy.getRegistry()); |
|
146 } |
142 capacity = copy.capacity; |
147 capacity = copy.capacity; |
143 if (capacity == 0) return *this; |
148 if (capacity == 0) return *this; |
144 values = allocator.allocate(capacity); |
149 values = allocator.allocate(capacity); |
145 } |
150 } |
146 |
151 |
147 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { |
152 for (KeyIt it(*graph); it != INVALID; ++it) { |
148 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it); |
153 int id = IdMap(*graph)[it]; |
149 allocator.construct(&(values[id]), copy.values[id]); |
154 allocator.construct(&(values[id]), copy.values[id]); |
150 } |
155 } |
151 |
156 |
152 return *this; |
157 return *this; |
153 } |
158 } |
154 |
159 |
155 /** Assign operator to copy a map of an other map type. |
|
156 */ |
|
157 template <typename TT> |
|
158 ArrayMap& operator=(const ArrayMap<MapRegistry, TT>& copy) { |
|
159 |
|
160 if (MapBase::getGraph() != copy.getGraph()) { |
|
161 if (capacity != 0) { |
|
162 MapBase::destroy(); |
|
163 allocator.deallocate(values, capacity); |
|
164 } |
|
165 |
|
166 MapBase::operator=(copy); |
|
167 |
|
168 capacity = copy.capacity; |
|
169 if (capacity == 0) return *this; |
|
170 values = allocator.allocate(capacity); |
|
171 } |
|
172 |
|
173 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { |
|
174 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it); |
|
175 allocator.construct(&(values[id]), copy.values[id]); |
|
176 } |
|
177 |
|
178 return *this; |
|
179 } |
|
180 |
|
181 /** The destructor of the map. |
160 /** The destructor of the map. |
182 */ |
161 */ |
183 virtual ~ArrayMap() { |
162 virtual ~ArrayMap() { |
184 if (capacity != 0) { |
163 if (attached()) { |
185 MapBase::destroy(); |
164 clear(); |
186 allocator.deallocate(values, capacity); |
165 detach(); |
187 } |
166 } |
188 } |
167 } |
189 |
168 |
190 |
169 |
191 /** |
170 /** |
192 * The subscript operator. The map can be subscripted by the |
171 * The subscript operator. The map can be subscripted by the |
193 * actual keys of the graph. |
172 * actual keys of the graph. |
194 */ |
173 */ |
195 ReferenceType operator[](const KeyType& key) { |
174 ReferenceType operator[](const KeyType& key) { |
196 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key); |
175 int id = IdMap(*graph)[key]; |
197 return values[id]; |
176 return values[id]; |
198 } |
177 } |
199 |
178 |
200 /** |
179 /** |
201 * The const subscript operator. The map can be subscripted by the |
180 * The const subscript operator. The map can be subscripted by the |
202 * actual keys of the graph. |
181 * actual keys of the graph. |
203 */ |
182 */ |
204 ConstReferenceType operator[](const KeyType& key) const { |
183 ConstReferenceType operator[](const KeyType& key) const { |
205 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key); |
184 int id = IdMap(*graph)[key]; |
206 return values[id]; |
185 return values[id]; |
207 } |
186 } |
208 |
187 |
209 /** Setter function of the map. Equivalent with map[key] = val. |
188 /** Setter function of the map. Equivalent with map[key] = val. |
210 * This is a compatibility feature with the not dereferable maps. |
189 * This is a compatibility feature with the not dereferable maps. |
211 */ |
190 */ |
212 void set(const KeyType& key, const ValueType& val) { |
191 void set(const KeyType& key, const ValueType& val) { |
213 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key); |
192 (*this)[key] = val; |
214 values[id] = val; |
|
215 } |
193 } |
216 |
194 |
217 /** Add a new key to the map. It called by the map registry. |
195 /** Add a new key to the map. It called by the map registry. |
218 */ |
196 */ |
219 void add(const KeyType& key) { |
197 void add(const KeyType& key) { |
220 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key); |
198 int id = IdMap(*graph)[key]; |
221 if (id >= capacity) { |
199 if (id >= capacity) { |
222 int new_capacity = (capacity == 0 ? 1 : capacity); |
200 int new_capacity = (capacity == 0 ? 1 : capacity); |
223 while (new_capacity <= id) { |
201 while (new_capacity <= id) { |
224 new_capacity <<= 1; |
202 new_capacity <<= 1; |
225 } |
203 } |
226 Value* new_values = allocator.allocate(new_capacity);; |
204 Value* new_values = allocator.allocate(new_capacity); |
227 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { |
205 for (KeyIt it(*graph); it != INVALID; ++it) { |
228 int jd = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it); |
206 int jd = IdMap(*graph)[it]; |
229 if (id != jd) { |
207 if (id != jd) { |
230 allocator.construct(&(new_values[jd]), values[jd]); |
208 allocator.construct(&(new_values[jd]), values[jd]); |
231 allocator.destroy(&(values[jd])); |
209 allocator.destroy(&(values[jd])); |
232 } |
210 } |
233 } |
211 } |
239 } |
217 } |
240 |
218 |
241 /** Erase a key from the map. It called by the map registry. |
219 /** Erase a key from the map. It called by the map registry. |
242 */ |
220 */ |
243 void erase(const KeyType& key) { |
221 void erase(const KeyType& key) { |
244 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key); |
222 int id = IdMap(*graph)[key]; |
245 allocator.destroy(&(values[id])); |
223 allocator.destroy(&(values[id])); |
246 } |
224 } |
247 |
225 |
248 /** Clear the data structure. |
226 void build() { |
249 */ |
227 allocate_memory(); |
|
228 for (KeyIt it(*graph); it != INVALID; ++it) { |
|
229 int id = IdMap(*graph)[it]; |
|
230 allocator.construct(&(values[id]), Value()); |
|
231 } |
|
232 } |
|
233 |
250 void clear() { |
234 void clear() { |
251 if (capacity != 0) { |
235 if (capacity != 0) { |
252 MapBase::destroy(); |
236 for (KeyIt it(*graph); it != INVALID; ++it) { |
|
237 int id = IdMap(*graph)[it]; |
|
238 allocator.destroy(&(values[id])); |
|
239 } |
253 allocator.deallocate(values, capacity); |
240 allocator.deallocate(values, capacity); |
254 capacity = 0; |
241 capacity = 0; |
255 } |
242 } |
256 } |
243 } |
257 |
244 |
258 /// The stl compatible pair iterator of the map. |
245 // /// The stl compatible pair iterator of the map. |
259 typedef MapIterator<ArrayMap> Iterator; |
246 // typedef MapIterator<ArrayMap> Iterator; |
260 /// The stl compatible const pair iterator of the map. |
247 // /// The stl compatible const pair iterator of the map. |
261 typedef MapConstIterator<ArrayMap> ConstIterator; |
248 // typedef MapConstIterator<ArrayMap> ConstIterator; |
262 |
249 |
263 /** Returns the begin iterator of the map. |
250 // /** Returns the begin iterator of the map. |
264 */ |
251 // */ |
265 Iterator begin() { |
252 // Iterator begin() { |
266 return Iterator(*this, KeyIt(*MapBase::getGraph())); |
253 // return Iterator(*this, KeyIt(*MapBase::getGraph())); |
267 } |
254 // } |
268 |
255 |
269 /** Returns the end iterator of the map. |
256 // /** Returns the end iterator of the map. |
270 */ |
257 // */ |
271 Iterator end() { |
258 // Iterator end() { |
272 return Iterator(*this, INVALID); |
259 // return Iterator(*this, INVALID); |
273 } |
260 // } |
274 |
261 |
275 /** Returns the begin ConstIterator of the map. |
262 // /** Returns the begin ConstIterator of the map. |
276 */ |
263 // */ |
277 ConstIterator begin() const { |
264 // ConstIterator begin() const { |
278 return ConstIterator(*this, KeyIt(*MapBase::getGraph())); |
265 // return ConstIterator(*this, KeyIt(*MapBase::getGraph())); |
279 } |
266 // } |
280 |
267 |
281 /** Returns the end const_iterator of the map. |
268 // /** Returns the end const_iterator of the map. |
282 */ |
269 // */ |
283 ConstIterator end() const { |
270 // ConstIterator end() const { |
284 return ConstIterator(*this, INVALID); |
271 // return ConstIterator(*this, INVALID); |
285 } |
272 // } |
286 |
273 |
287 /// The KeySet of the Map. |
274 // /// The KeySet of the Map. |
288 typedef MapConstKeySet<ArrayMap> ConstKeySet; |
275 // typedef MapConstKeySet<ArrayMap> ConstKeySet; |
289 |
276 |
290 /// KeySet getter function. |
277 // /// KeySet getter function. |
291 ConstKeySet keySet() const { |
278 // ConstKeySet keySet() const { |
292 return ConstKeySet(*this); |
279 // return ConstKeySet(*this); |
293 } |
280 // } |
294 |
281 |
295 /// The ConstValueSet of the Map. |
282 // /// The ConstValueSet of the Map. |
296 typedef MapConstValueSet<ArrayMap> ConstValueSet; |
283 // typedef MapConstValueSet<ArrayMap> ConstValueSet; |
297 |
284 |
298 /// ConstValueSet getter function. |
285 // /// ConstValueSet getter function. |
299 ConstValueSet valueSet() const { |
286 // ConstValueSet valueSet() const { |
300 return ConstValueSet(*this); |
287 // return ConstValueSet(*this); |
301 } |
288 // } |
302 |
289 |
303 /// The ValueSet of the Map. |
290 // /// The ValueSet of the Map. |
304 typedef MapValueSet<ArrayMap> ValueSet; |
291 // typedef MapValueSet<ArrayMap> ValueSet; |
305 |
292 |
306 /// ValueSet getter function. |
293 // /// ValueSet getter function. |
307 ValueSet valueSet() { |
294 // ValueSet valueSet() { |
308 return ValueSet(*this); |
295 // return ValueSet(*this); |
309 } |
296 // } |
310 |
297 |
311 private: |
298 private: |
312 |
299 |
313 void allocate_memory() { |
300 void allocate_memory() { |
314 int max_id = KeyInfo<Graph, KeyIt>::maxId(*MapBase::getGraph()); |
301 int max_id = IdMap(*graph).maxId(); |
315 if (max_id == -1) { |
302 if (max_id == -1) { |
316 capacity = 0; |
303 capacity = 0; |
317 values = 0; |
304 values = 0; |
318 return; |
305 return; |
319 } |
306 } |
322 capacity <<= 1; |
309 capacity <<= 1; |
323 } |
310 } |
324 values = allocator.allocate(capacity); |
311 values = allocator.allocate(capacity); |
325 } |
312 } |
326 |
313 |
|
314 const Graph* graph; |
327 int capacity; |
315 int capacity; |
328 Value* values; |
316 Value* values; |
329 Allocator allocator; |
317 Allocator allocator; |
330 |
318 |
331 public: |
319 public: |
332 // STL compatibility typedefs. |
320 // // STL compatibility typedefs. |
333 typedef Iterator iterator; |
321 // typedef Iterator iterator; |
334 typedef ConstIterator const_iterator; |
322 // typedef ConstIterator const_iterator; |
335 typedef typename Iterator::PairValueType value_type; |
323 // typedef typename Iterator::PairValueType value_type; |
336 typedef typename Iterator::KeyType key_type; |
324 // typedef typename Iterator::KeyType key_type; |
337 typedef typename Iterator::ValueType data_type; |
325 // typedef typename Iterator::ValueType data_type; |
338 typedef typename Iterator::PairReferenceType reference; |
326 // typedef typename Iterator::PairReferenceType reference; |
339 typedef typename Iterator::PairPointerType pointer; |
327 // typedef typename Iterator::PairPointerType pointer; |
340 typedef typename ConstIterator::PairReferenceType const_reference; |
328 // typedef typename ConstIterator::PairReferenceType const_reference; |
341 typedef typename ConstIterator::PairPointerType const_pointer; |
329 // typedef typename ConstIterator::PairPointerType const_pointer; |
342 typedef int difference_type; |
330 // typedef int difference_type; |
343 }; |
331 }; |
344 |
332 |
|
333 template <typename _Base> |
|
334 class ArrayMappableGraphExtender : public _Base { |
|
335 public: |
|
336 |
|
337 typedef ArrayMappableGraphExtender<_Base> Graph; |
|
338 typedef _Base Parent; |
|
339 |
|
340 typedef typename Parent::Node Node; |
|
341 typedef typename Parent::NodeIt NodeIt; |
|
342 typedef typename Parent::NodeIdMap NodeIdMap; |
|
343 typedef typename Parent::NodeObserverRegistry NodeObserverRegistry; |
|
344 |
|
345 typedef typename Parent::Edge Edge; |
|
346 typedef typename Parent::EdgeIt EdgeIt; |
|
347 typedef typename Parent::EdgeIdMap EdgeIdMap; |
|
348 typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry; |
|
349 |
|
350 |
|
351 |
|
352 template <typename _Value> |
|
353 class NodeMap : public ArrayMap<Graph, Node, NodeIt, NodeIdMap, _Value> { |
|
354 public: |
|
355 typedef ArrayMappableGraphExtender<_Base> Graph; |
|
356 |
|
357 typedef typename Graph::Node Node; |
|
358 typedef typename Graph::NodeIt NodeIt; |
|
359 typedef typename Graph::NodeIdMap NodeIdMap; |
|
360 |
|
361 typedef ArrayMap<Graph, Node, NodeIt, NodeIdMap, _Value> Parent; |
|
362 |
|
363 typedef typename Parent::Graph Graph; |
|
364 typedef typename Parent::Value Value; |
|
365 |
|
366 NodeMap(const Graph& g) |
|
367 : Parent(g, g.getNodeObserverRegistry()) {} |
|
368 NodeMap(const Graph& g, const Value& v) |
|
369 : Parent(g, g.getNodeObserverRegistry(), v) {} |
|
370 |
|
371 }; |
|
372 |
|
373 template <typename _Value> |
|
374 class EdgeMap : public ArrayMap<Graph, Edge, EdgeIt, EdgeIdMap, _Value> { |
|
375 public: |
|
376 typedef ArrayMappableGraphExtender<_Base> Graph; |
|
377 |
|
378 typedef typename Graph::Edge Edge; |
|
379 typedef typename Graph::EdgeIt EdgeIt; |
|
380 typedef typename Graph::EdgeIdMap EdgeIdMap; |
|
381 |
|
382 typedef ArrayMap<Graph, Edge, EdgeIt, EdgeIdMap, _Value> Parent; |
|
383 |
|
384 typedef typename Parent::Graph Graph; |
|
385 typedef typename Parent::Value Value; |
|
386 |
|
387 EdgeMap(const Graph& g) |
|
388 : Parent(g, g.getEdgeObserverRegistry()) {} |
|
389 EdgeMap(const Graph& g, const Value& v) |
|
390 : Parent(g, g.getEdgeObserverRegistry(), v) {} |
|
391 |
|
392 }; |
|
393 |
|
394 }; |
|
395 |
345 /// @} |
396 /// @} |
346 |
397 |
347 } |
398 } |
348 |
399 |
349 #endif //LEMON_ARRAY_MAP_H |
400 #endif //LEMON_ARRAY_MAP_H |