34 |
34 |
35 // \ingroup graphbits |
35 // \ingroup graphbits |
36 // |
36 // |
37 // \brief Graph map based on the array storage. |
37 // \brief Graph map based on the array storage. |
38 // |
38 // |
39 // The ArrayMap template class is graph map structure what |
39 // The ArrayMap template class is graph map structure that automatically |
40 // automatically updates the map when a key is added to or erased from |
40 // updates the map when a key is added to or erased from the graph. |
41 // the map. This map uses the allocators to implement |
41 // This map uses the allocators to implement the container functionality. |
42 // the container functionality. |
|
43 // |
42 // |
44 // The template parameters are the Graph the current Item type and |
43 // The template parameters are the Graph, the current Item type and |
45 // the Value type of the map. |
44 // the Value type of the map. |
46 template <typename _Graph, typename _Item, typename _Value> |
45 template <typename _Graph, typename _Item, typename _Value> |
47 class ArrayMap |
46 class ArrayMap |
48 : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase { |
47 : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase { |
49 public: |
48 public: |
50 // The graph type of the maps. |
49 // The graph type. |
51 typedef _Graph Graph; |
50 typedef _Graph Graph; |
52 // The item type of the map. |
51 // The item type. |
53 typedef _Item Item; |
52 typedef _Item Item; |
54 // The reference map tag. |
53 // The reference map tag. |
55 typedef True ReferenceMapTag; |
54 typedef True ReferenceMapTag; |
56 |
55 |
57 // The key type of the maps. |
56 // The key type of the map. |
58 typedef _Item Key; |
57 typedef _Item Key; |
59 // The value type of the map. |
58 // The value type of the map. |
60 typedef _Value Value; |
59 typedef _Value Value; |
61 |
60 |
62 // The const reference type of the map. |
61 // The const reference type of the map. |
198 |
197 |
199 protected: |
198 protected: |
200 |
199 |
201 // \brief Adds a new key to the map. |
200 // \brief Adds a new key to the map. |
202 // |
201 // |
203 // It adds a new key to the map. It called by the observer notifier |
202 // It adds a new key to the map. It is called by the observer notifier |
204 // and it overrides the add() member function of the observer base. |
203 // and it overrides the add() member function of the observer base. |
205 virtual void add(const Key& key) { |
204 virtual void add(const Key& key) { |
206 Notifier* nf = Parent::notifier(); |
205 Notifier* nf = Parent::notifier(); |
207 int id = nf->id(key); |
206 int id = nf->id(key); |
208 if (id >= capacity) { |
207 if (id >= capacity) { |
226 allocator.construct(&(values[id]), Value()); |
225 allocator.construct(&(values[id]), Value()); |
227 } |
226 } |
228 |
227 |
229 // \brief Adds more new keys to the map. |
228 // \brief Adds more new keys to the map. |
230 // |
229 // |
231 // It adds more new keys to the map. It called by the observer notifier |
230 // It adds more new keys to the map. It is called by the observer notifier |
232 // and it overrides the add() member function of the observer base. |
231 // and it overrides the add() member function of the observer base. |
233 virtual void add(const std::vector<Key>& keys) { |
232 virtual void add(const std::vector<Key>& keys) { |
234 Notifier* nf = Parent::notifier(); |
233 Notifier* nf = Parent::notifier(); |
235 int max_id = -1; |
234 int max_id = -1; |
236 for (int i = 0; i < int(keys.size()); ++i) { |
235 for (int i = 0; i < int(keys.size()); ++i) { |
270 } |
269 } |
271 } |
270 } |
272 |
271 |
273 // \brief Erase a key from the map. |
272 // \brief Erase a key from the map. |
274 // |
273 // |
275 // Erase a key from the map. It called by the observer notifier |
274 // Erase a key from the map. It is called by the observer notifier |
276 // and it overrides the erase() member function of the observer base. |
275 // and it overrides the erase() member function of the observer base. |
277 virtual void erase(const Key& key) { |
276 virtual void erase(const Key& key) { |
278 int id = Parent::notifier()->id(key); |
277 int id = Parent::notifier()->id(key); |
279 allocator.destroy(&(values[id])); |
278 allocator.destroy(&(values[id])); |
280 } |
279 } |
281 |
280 |
282 // \brief Erase more keys from the map. |
281 // \brief Erase more keys from the map. |
283 // |
282 // |
284 // Erase more keys from the map. It called by the observer notifier |
283 // Erase more keys from the map. It is called by the observer notifier |
285 // and it overrides the erase() member function of the observer base. |
284 // and it overrides the erase() member function of the observer base. |
286 virtual void erase(const std::vector<Key>& keys) { |
285 virtual void erase(const std::vector<Key>& keys) { |
287 for (int i = 0; i < int(keys.size()); ++i) { |
286 for (int i = 0; i < int(keys.size()); ++i) { |
288 int id = Parent::notifier()->id(keys[i]); |
287 int id = Parent::notifier()->id(keys[i]); |
289 allocator.destroy(&(values[id])); |
288 allocator.destroy(&(values[id])); |
290 } |
289 } |
291 } |
290 } |
292 |
291 |
293 // \brief Buildes the map. |
292 // \brief Builds the map. |
294 // |
293 // |
295 // It buildes the map. It called by the observer notifier |
294 // It builds the map. It is called by the observer notifier |
296 // and it overrides the build() member function of the observer base. |
295 // and it overrides the build() member function of the observer base. |
297 virtual void build() { |
296 virtual void build() { |
298 Notifier* nf = Parent::notifier(); |
297 Notifier* nf = Parent::notifier(); |
299 allocate_memory(); |
298 allocate_memory(); |
300 Item it; |
299 Item it; |
304 } |
303 } |
305 } |
304 } |
306 |
305 |
307 // \brief Clear the map. |
306 // \brief Clear the map. |
308 // |
307 // |
309 // It erase all items from the map. It called by the observer notifier |
308 // It erase all items from the map. It is called by the observer notifier |
310 // and it overrides the clear() member function of the observer base. |
309 // and it overrides the clear() member function of the observer base. |
311 virtual void clear() { |
310 virtual void clear() { |
312 Notifier* nf = Parent::notifier(); |
311 Notifier* nf = Parent::notifier(); |
313 if (capacity != 0) { |
312 if (capacity != 0) { |
314 Item it; |
313 Item it; |