24 #include <lemon/bits/traits.h> |
24 #include <lemon/bits/traits.h> |
25 #include <lemon/bits/alteration_notifier.h> |
25 #include <lemon/bits/alteration_notifier.h> |
26 #include <lemon/concept_check.h> |
26 #include <lemon/concept_check.h> |
27 #include <lemon/concepts/maps.h> |
27 #include <lemon/concepts/maps.h> |
28 |
28 |
29 /// \ingroup graphbits |
29 // \ingroup graphbits |
30 /// \file |
30 // \file |
31 /// \brief Graph map based on the array storage. |
31 // \brief Graph map based on the array storage. |
32 |
32 |
33 namespace lemon { |
33 namespace lemon { |
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 what |
40 /// automatically updates the map when a key is added to or erased from |
40 // automatically updates the map when a key is added to or erased from |
41 /// the map. This map uses the allocators to implement |
41 // the map. This map uses the allocators to implement |
42 /// the container functionality. |
42 // the container functionality. |
43 /// |
43 // |
44 /// The template parameters are the Graph the current Item type and |
44 // The template parameters are the Graph the current Item type and |
45 /// the Value type of the map. |
45 // the Value type of the map. |
46 template <typename _Graph, typename _Item, typename _Value> |
46 template <typename _Graph, typename _Item, typename _Value> |
47 class ArrayMap |
47 class ArrayMap |
48 : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase { |
48 : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase { |
49 public: |
49 public: |
50 /// The graph type of the maps. |
50 // The graph type of the maps. |
51 typedef _Graph Graph; |
51 typedef _Graph Graph; |
52 /// The item type of the map. |
52 // The item type of the map. |
53 typedef _Item Item; |
53 typedef _Item Item; |
54 /// The reference map tag. |
54 // The reference map tag. |
55 typedef True ReferenceMapTag; |
55 typedef True ReferenceMapTag; |
56 |
56 |
57 /// The key type of the maps. |
57 // The key type of the maps. |
58 typedef _Item Key; |
58 typedef _Item Key; |
59 /// The value type of the map. |
59 // The value type of the map. |
60 typedef _Value Value; |
60 typedef _Value Value; |
61 |
61 |
62 /// The const reference type of the map. |
62 // The const reference type of the map. |
63 typedef const _Value& ConstReference; |
63 typedef const _Value& ConstReference; |
64 /// The reference type of the map. |
64 // The reference type of the map. |
65 typedef _Value& Reference; |
65 typedef _Value& Reference; |
66 |
66 |
67 /// The notifier type. |
67 // The notifier type. |
68 typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier; |
68 typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier; |
69 |
69 |
70 /// The MapBase of the Map which imlements the core regisitry function. |
70 // The MapBase of the Map which imlements the core regisitry function. |
71 typedef typename Notifier::ObserverBase Parent; |
71 typedef typename Notifier::ObserverBase Parent; |
72 |
72 |
73 private: |
73 private: |
74 typedef std::allocator<Value> Allocator; |
74 typedef std::allocator<Value> Allocator; |
75 |
75 |
76 public: |
76 public: |
77 |
77 |
78 /// \brief Graph initialized map constructor. |
78 // \brief Graph initialized map constructor. |
79 /// |
79 // |
80 /// Graph initialized map constructor. |
80 // Graph initialized map constructor. |
81 explicit ArrayMap(const Graph& graph) { |
81 explicit ArrayMap(const Graph& graph) { |
82 Parent::attach(graph.notifier(Item())); |
82 Parent::attach(graph.notifier(Item())); |
83 allocate_memory(); |
83 allocate_memory(); |
84 Notifier* nf = Parent::notifier(); |
84 Notifier* nf = Parent::notifier(); |
85 Item it; |
85 Item it; |
120 int id = nf->id(it);; |
120 int id = nf->id(it);; |
121 allocator.construct(&(values[id]), copy.values[id]); |
121 allocator.construct(&(values[id]), copy.values[id]); |
122 } |
122 } |
123 } |
123 } |
124 |
124 |
125 /// \brief Assign operator. |
125 // \brief Assign operator. |
126 /// |
126 // |
127 /// This operator assigns for each item in the map the |
127 // This operator assigns for each item in the map the |
128 /// value mapped to the same item in the copied map. |
128 // value mapped to the same item in the copied map. |
129 /// The parameter map should be indiced with the same |
129 // The parameter map should be indiced with the same |
130 /// itemset because this assign operator does not change |
130 // itemset because this assign operator does not change |
131 /// the container of the map. |
131 // the container of the map. |
132 ArrayMap& operator=(const ArrayMap& cmap) { |
132 ArrayMap& operator=(const ArrayMap& cmap) { |
133 return operator=<ArrayMap>(cmap); |
133 return operator=<ArrayMap>(cmap); |
134 } |
134 } |
135 |
135 |
136 |
136 |
137 /// \brief Template assign operator. |
137 // \brief Template assign operator. |
138 /// |
138 // |
139 /// The given parameter should be conform to the ReadMap |
139 // The given parameter should be conform to the ReadMap |
140 /// concecpt and could be indiced by the current item set of |
140 // concecpt and could be indiced by the current item set of |
141 /// the NodeMap. In this case the value for each item |
141 // the NodeMap. In this case the value for each item |
142 /// is assigned by the value of the given ReadMap. |
142 // is assigned by the value of the given ReadMap. |
143 template <typename CMap> |
143 template <typename CMap> |
144 ArrayMap& operator=(const CMap& cmap) { |
144 ArrayMap& operator=(const CMap& cmap) { |
145 checkConcept<concepts::ReadMap<Key, _Value>, CMap>(); |
145 checkConcept<concepts::ReadMap<Key, _Value>, CMap>(); |
146 const typename Parent::Notifier* nf = Parent::notifier(); |
146 const typename Parent::Notifier* nf = Parent::notifier(); |
147 Item it; |
147 Item it; |
168 using Parent::detach; |
168 using Parent::detach; |
169 using Parent::attached; |
169 using Parent::attached; |
170 |
170 |
171 public: |
171 public: |
172 |
172 |
173 /// \brief The subscript operator. |
173 // \brief The subscript operator. |
174 /// |
174 // |
175 /// The subscript operator. The map can be subscripted by the |
175 // The subscript operator. The map can be subscripted by the |
176 /// actual keys of the graph. |
176 // actual keys of the graph. |
177 Value& operator[](const Key& key) { |
177 Value& operator[](const Key& key) { |
178 int id = Parent::notifier()->id(key); |
178 int id = Parent::notifier()->id(key); |
179 return values[id]; |
179 return values[id]; |
180 } |
180 } |
181 |
181 |
182 /// \brief The const subscript operator. |
182 // \brief The const subscript operator. |
183 /// |
183 // |
184 /// The const subscript operator. The map can be subscripted by the |
184 // The const subscript operator. The map can be subscripted by the |
185 /// actual keys of the graph. |
185 // actual keys of the graph. |
186 const Value& operator[](const Key& key) const { |
186 const Value& operator[](const Key& key) const { |
187 int id = Parent::notifier()->id(key); |
187 int id = Parent::notifier()->id(key); |
188 return values[id]; |
188 return values[id]; |
189 } |
189 } |
190 |
190 |
191 /// \brief Setter function of the map. |
191 // \brief Setter function of the map. |
192 /// |
192 // |
193 /// Setter function of the map. Equivalent with map[key] = val. |
193 // Setter function of the map. Equivalent with map[key] = val. |
194 /// This is a compatibility feature with the not dereferable maps. |
194 // This is a compatibility feature with the not dereferable maps. |
195 void set(const Key& key, const Value& val) { |
195 void set(const Key& key, const Value& val) { |
196 (*this)[key] = val; |
196 (*this)[key] = val; |
197 } |
197 } |
198 |
198 |
199 protected: |
199 protected: |
200 |
200 |
201 /// \brief Adds a new key to the map. |
201 // \brief Adds a new key to the map. |
202 /// |
202 // |
203 /// It adds a new key to the map. It called by the observer notifier |
203 // It adds a new key to the map. It called by the observer notifier |
204 /// and it overrides the add() member function of the observer base. |
204 // and it overrides the add() member function of the observer base. |
205 virtual void add(const Key& key) { |
205 virtual void add(const Key& key) { |
206 Notifier* nf = Parent::notifier(); |
206 Notifier* nf = Parent::notifier(); |
207 int id = nf->id(key); |
207 int id = nf->id(key); |
208 if (id >= capacity) { |
208 if (id >= capacity) { |
209 int new_capacity = (capacity == 0 ? 1 : capacity); |
209 int new_capacity = (capacity == 0 ? 1 : capacity); |
224 capacity = new_capacity; |
224 capacity = new_capacity; |
225 } |
225 } |
226 allocator.construct(&(values[id]), Value()); |
226 allocator.construct(&(values[id]), Value()); |
227 } |
227 } |
228 |
228 |
229 /// \brief Adds more new keys to the map. |
229 // \brief Adds more new keys to the map. |
230 /// |
230 // |
231 /// It adds more new keys to the map. It called by the observer notifier |
231 // It adds more new keys to the map. It called by the observer notifier |
232 /// and it overrides the add() member function of the observer base. |
232 // and it overrides the add() member function of the observer base. |
233 virtual void add(const std::vector<Key>& keys) { |
233 virtual void add(const std::vector<Key>& keys) { |
234 Notifier* nf = Parent::notifier(); |
234 Notifier* nf = Parent::notifier(); |
235 int max_id = -1; |
235 int max_id = -1; |
236 for (int i = 0; i < int(keys.size()); ++i) { |
236 for (int i = 0; i < int(keys.size()); ++i) { |
237 int id = nf->id(keys[i]); |
237 int id = nf->id(keys[i]); |
268 int id = nf->id(keys[i]); |
268 int id = nf->id(keys[i]); |
269 allocator.construct(&(values[id]), Value()); |
269 allocator.construct(&(values[id]), Value()); |
270 } |
270 } |
271 } |
271 } |
272 |
272 |
273 /// \brief Erase a key from the map. |
273 // \brief Erase a key from the map. |
274 /// |
274 // |
275 /// Erase a key from the map. It called by the observer notifier |
275 // Erase a key from the map. It called by the observer notifier |
276 /// and it overrides the erase() member function of the observer base. |
276 // and it overrides the erase() member function of the observer base. |
277 virtual void erase(const Key& key) { |
277 virtual void erase(const Key& key) { |
278 int id = Parent::notifier()->id(key); |
278 int id = Parent::notifier()->id(key); |
279 allocator.destroy(&(values[id])); |
279 allocator.destroy(&(values[id])); |
280 } |
280 } |
281 |
281 |
282 /// \brief Erase more keys from the map. |
282 // \brief Erase more keys from the map. |
283 /// |
283 // |
284 /// Erase more keys from the map. It called by the observer notifier |
284 // Erase more keys from the map. It called by the observer notifier |
285 /// and it overrides the erase() member function of the observer base. |
285 // and it overrides the erase() member function of the observer base. |
286 virtual void erase(const std::vector<Key>& keys) { |
286 virtual void erase(const std::vector<Key>& keys) { |
287 for (int i = 0; i < int(keys.size()); ++i) { |
287 for (int i = 0; i < int(keys.size()); ++i) { |
288 int id = Parent::notifier()->id(keys[i]); |
288 int id = Parent::notifier()->id(keys[i]); |
289 allocator.destroy(&(values[id])); |
289 allocator.destroy(&(values[id])); |
290 } |
290 } |
291 } |
291 } |
292 |
292 |
293 /// \brief Buildes the map. |
293 // \brief Buildes the map. |
294 /// |
294 // |
295 /// It buildes the map. It called by the observer notifier |
295 // It buildes the map. It called by the observer notifier |
296 /// and it overrides the build() member function of the observer base. |
296 // and it overrides the build() member function of the observer base. |
297 virtual void build() { |
297 virtual void build() { |
298 Notifier* nf = Parent::notifier(); |
298 Notifier* nf = Parent::notifier(); |
299 allocate_memory(); |
299 allocate_memory(); |
300 Item it; |
300 Item it; |
301 for (nf->first(it); it != INVALID; nf->next(it)) { |
301 for (nf->first(it); it != INVALID; nf->next(it)) { |
302 int id = nf->id(it);; |
302 int id = nf->id(it);; |
303 allocator.construct(&(values[id]), Value()); |
303 allocator.construct(&(values[id]), Value()); |
304 } |
304 } |
305 } |
305 } |
306 |
306 |
307 /// \brief Clear the map. |
307 // \brief Clear the map. |
308 /// |
308 // |
309 /// It erase all items from the map. It called by the observer notifier |
309 // It erase all items from the map. It called by the observer notifier |
310 /// and it overrides the clear() member function of the observer base. |
310 // and it overrides the clear() member function of the observer base. |
311 virtual void clear() { |
311 virtual void clear() { |
312 Notifier* nf = Parent::notifier(); |
312 Notifier* nf = Parent::notifier(); |
313 if (capacity != 0) { |
313 if (capacity != 0) { |
314 Item it; |
314 Item it; |
315 for (nf->first(it); it != INVALID; nf->next(it)) { |
315 for (nf->first(it); it != INVALID; nf->next(it)) { |