18 |
18 |
19 #ifndef LEMON_BITS_ARRAY_MAP_H |
19 #ifndef LEMON_BITS_ARRAY_MAP_H |
20 #define LEMON_BITS_ARRAY_MAP_H |
20 #define LEMON_BITS_ARRAY_MAP_H |
21 |
21 |
22 #include <memory> |
22 #include <memory> |
23 #include <lemon/bits/map_extender.h> |
23 |
|
24 #include <lemon/bits/traits.h> |
24 #include <lemon/bits/alteration_notifier.h> |
25 #include <lemon/bits/alteration_notifier.h> |
25 #include <lemon/concept_check.h> |
|
26 #include <lemon/concept/maps.h> |
|
27 |
26 |
28 /// \ingroup graphbits |
27 /// \ingroup graphbits |
29 /// \file |
28 /// \file |
30 /// \brief Graph maps that construct and destruct |
29 /// \brief Graph map based on the array storage. |
31 /// their elements dynamically. |
|
32 |
30 |
33 namespace lemon { |
31 namespace lemon { |
34 |
32 |
35 /// \ingroup graphbits |
33 /// \ingroup graphbits |
36 /// |
34 /// |
37 /// \brief Graph map based on the array storage. |
35 /// \brief Graph map based on the array storage. |
38 /// |
36 /// |
39 /// The ArrayMap template class is graph map structure what |
37 /// The ArrayMap template class is graph map structure what |
40 /// automatically indates the map when a key is added to or erased from |
38 /// automatically updates the map when a key is added to or erased from |
41 /// the map. This map uses the allocators to implement |
39 /// the map. This map uses the allocators to implement |
42 /// the container functionality. |
40 /// the container functionality. |
43 /// |
41 /// |
44 /// The template parameter is the AlterationNotifier that the maps |
42 /// The template parameter is the Graph the current Item type and |
45 /// will belong to and the Value. |
43 /// the Value type of the map. |
46 |
44 template <typename _Graph, typename _Item, typename _Value> |
47 template <typename _Graph, |
45 class ArrayMap |
48 typename _Item, |
46 : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase { |
49 typename _Value> |
|
50 class ArrayMap : public AlterationNotifier<_Item>::ObserverBase { |
|
51 |
|
52 typedef _Item Item; |
|
53 public: |
47 public: |
54 /// The graph type of the maps. |
48 /// The graph type of the maps. |
55 typedef _Graph Graph; |
49 typedef _Graph Graph; |
|
50 /// The item type of the map. |
|
51 typedef _Item Item; |
56 /// The reference map tag. |
52 /// The reference map tag. |
57 typedef True ReferenceMapTag; |
53 typedef True ReferenceMapTag; |
58 |
54 |
59 /// The key type of the maps. |
55 /// The key type of the maps. |
60 typedef _Item Key; |
56 typedef _Item Key; |
61 /// The value type of the map. |
57 /// The value type of the map. |
62 typedef _Value Value; |
58 typedef _Value Value; |
|
59 |
63 /// The const reference type of the map. |
60 /// The const reference type of the map. |
64 typedef const _Value& ConstReference; |
61 typedef const _Value& ConstReference; |
65 /// The reference type of the map. |
62 /// The reference type of the map. |
66 typedef _Value& Reference; |
63 typedef _Value& Reference; |
67 |
64 |
68 typedef const Value ConstValue; |
65 /// The notifier type. |
69 typedef Value* Pointer; |
66 typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier; |
70 typedef const Value* ConstPointer; |
|
71 |
|
72 typedef AlterationNotifier<_Item> Registry; |
|
73 |
67 |
74 /// The MapBase of the Map which imlements the core regisitry function. |
68 /// The MapBase of the Map which imlements the core regisitry function. |
75 typedef typename Registry::ObserverBase Parent; |
69 typedef typename Notifier::ObserverBase Parent; |
76 |
70 |
77 |
|
78 |
|
79 private: |
71 private: |
80 typedef std::allocator<Value> Allocator; |
72 typedef std::allocator<Value> Allocator; |
81 |
73 |
82 |
|
83 public: |
74 public: |
84 |
75 |
85 /// \brief Graph initialized map constructor. |
76 /// \brief Graph initialized map constructor. |
86 /// |
77 /// |
87 /// Graph initialized map constructor. |
78 /// Graph initialized map constructor. |
88 ArrayMap(const Graph& _g) : graph(&_g) { |
79 ArrayMap(const Graph& graph) { |
|
80 Parent::attach(graph.getNotifier(Item())); |
|
81 allocate_memory(); |
|
82 Notifier* notifier = Parent::getNotifier(); |
89 Item it; |
83 Item it; |
90 attach(_g.getNotifier(Item())); |
84 for (notifier->first(it); it != INVALID; notifier->next(it)) { |
91 allocate_memory(); |
85 int id = notifier->id(it);; |
92 for (graph->first(it); it != INVALID; graph->next(it)) { |
|
93 int id = graph->id(it);; |
|
94 allocator.construct(&(values[id]), Value()); |
86 allocator.construct(&(values[id]), Value()); |
95 } |
87 } |
96 } |
88 } |
97 |
89 |
98 /// \brief Constructor to use default value to initialize the map. |
90 /// \brief Constructor to use default value to initialize the map. |
99 /// |
91 /// |
100 /// It constructs a map and initialize all of the the map. |
92 /// It constructs a map and initialize all of the the map. |
101 ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) { |
93 ArrayMap(const Graph& graph, const Value& value) { |
|
94 Parent::attach(graph.getNotifier(Item())); |
|
95 allocate_memory(); |
|
96 Notifier* notifier = Parent::getNotifier(); |
102 Item it; |
97 Item it; |
103 attach(_g.getNotifier(_Item())); |
98 for (notifier->first(it); it != INVALID; notifier->next(it)) { |
104 allocate_memory(); |
99 int id = notifier->id(it);; |
105 for (graph->first(it); it != INVALID; graph->next(it)) { |
100 allocator.construct(&(values[id]), value); |
106 int id = graph->id(it);; |
|
107 allocator.construct(&(values[id]), _v); |
|
108 } |
101 } |
109 } |
102 } |
110 |
103 |
111 /// \brief Constructor to copy a map of the same map type. |
104 /// \brief Constructor to copy a map of the same map type. |
112 /// |
105 /// |
113 /// Constructor to copy a map of the same map type. |
106 /// Constructor to copy a map of the same map type. |
114 ArrayMap(const ArrayMap& copy) : Parent(), graph(copy.graph) { |
107 ArrayMap(const ArrayMap& copy) : Parent() { |
115 if (copy.attached()) { |
108 if (copy.attached()) { |
116 attach(*copy.getRegistry()); |
109 attach(*copy.getNotifier()); |
117 } |
110 } |
118 capacity = copy.capacity; |
111 capacity = copy.capacity; |
119 if (capacity == 0) return; |
112 if (capacity == 0) return; |
120 values = allocator.allocate(capacity); |
113 values = allocator.allocate(capacity); |
|
114 Notifier* notifier = Parent::getNotifier(); |
121 Item it; |
115 Item it; |
122 for (graph->first(it); it != INVALID; graph->next(it)) { |
116 for (notifier->first(it); it != INVALID; notifier->next(it)) { |
123 int id = graph->id(it);; |
117 int id = notifier->id(it);; |
124 allocator.construct(&(values[id]), copy.values[id]); |
118 allocator.construct(&(values[id]), copy.values[id]); |
125 } |
119 } |
126 } |
120 } |
127 |
121 |
128 /// \brief The destructor of the map. |
122 /// \brief The destructor of the map. |
143 |
137 |
144 using Parent::attach; |
138 using Parent::attach; |
145 using Parent::detach; |
139 using Parent::detach; |
146 using Parent::attached; |
140 using Parent::attached; |
147 |
141 |
148 const Graph* getGraph() { |
|
149 return graph; |
|
150 } |
|
151 |
|
152 |
|
153 public: |
142 public: |
154 |
143 |
155 /// \brief The subscript operator. |
144 /// \brief The subscript operator. |
156 /// |
145 /// |
157 /// The subscript operator. The map can be subscripted by the |
146 /// The subscript operator. The map can be subscripted by the |
158 /// actual keys of the graph. |
147 /// actual keys of the graph. |
159 Value& operator[](const Key& key) { |
148 Value& operator[](const Key& key) { |
160 int id = graph->id(key); |
149 int id = Parent::getNotifier()->id(key); |
161 return values[id]; |
150 return values[id]; |
162 } |
151 } |
163 |
152 |
164 /// \brief The const subscript operator. |
153 /// \brief The const subscript operator. |
165 /// |
154 /// |
166 /// The const subscript operator. The map can be subscripted by the |
155 /// The const subscript operator. The map can be subscripted by the |
167 /// actual keys of the graph. |
156 /// actual keys of the graph. |
168 const Value& operator[](const Key& key) const { |
157 const Value& operator[](const Key& key) const { |
169 int id = graph->id(key); |
158 int id = Parent::getNotifier()->id(key); |
170 return values[id]; |
159 return values[id]; |
171 } |
160 } |
172 |
161 |
173 /// \brief Setter function of the map. |
162 /// \brief Setter function of the map. |
174 /// |
163 /// |
237 if (capacity != 0) allocator.deallocate(values, capacity); |
234 if (capacity != 0) allocator.deallocate(values, capacity); |
238 values = new_values; |
235 values = new_values; |
239 capacity = new_capacity; |
236 capacity = new_capacity; |
240 } |
237 } |
241 for (int i = 0; i < (int)keys.size(); ++i) { |
238 for (int i = 0; i < (int)keys.size(); ++i) { |
242 int id = graph->id(keys[i]); |
239 int id = notifier->id(keys[i]); |
243 allocator.construct(&(values[id]), Value()); |
240 allocator.construct(&(values[id]), Value()); |
244 } |
241 } |
245 } |
242 } |
246 |
243 |
247 /// Erase a key from the map. It called by the map registry. |
244 /// \brief Erase a key from the map. |
248 |
245 /// |
|
246 /// Erase a key from the map. It called by the observer notifier |
|
247 /// and it overrides the erase() member function of the observer base. |
249 virtual void erase(const Key& key) { |
248 virtual void erase(const Key& key) { |
250 int id = graph->id(key); |
249 int id = Parent::getNotifier()->id(key); |
251 allocator.destroy(&(values[id])); |
250 allocator.destroy(&(values[id])); |
252 } |
251 } |
253 |
252 |
|
253 /// \brief Erase more keys from the map. |
|
254 /// |
|
255 /// Erase more keys from the map. It called by the observer notifier |
|
256 /// and it overrides the erase() member function of the observer base. |
254 virtual void erase(const std::vector<Key>& keys) { |
257 virtual void erase(const std::vector<Key>& keys) { |
255 for (int i = 0; i < (int)keys.size(); ++i) { |
258 for (int i = 0; i < (int)keys.size(); ++i) { |
256 int id = graph->id(keys[i]); |
259 int id = Parent::getNotifier()->id(keys[i]); |
257 allocator.destroy(&(values[id])); |
260 allocator.destroy(&(values[id])); |
258 } |
261 } |
259 } |
262 } |
260 |
263 |
|
264 /// \brief Buildes the map. |
|
265 /// |
|
266 /// It buildes the map. It called by the observer notifier |
|
267 /// and it overrides the build() member function of the observer base. |
261 virtual void build() { |
268 virtual void build() { |
|
269 Notifier* notifier = Parent::getNotifier(); |
262 allocate_memory(); |
270 allocate_memory(); |
263 Item it; |
271 Item it; |
264 for (graph->first(it); it != INVALID; graph->next(it)) { |
272 for (notifier->first(it); it != INVALID; notifier->next(it)) { |
265 int id = graph->id(it);; |
273 int id = notifier->id(it);; |
266 allocator.construct(&(values[id]), Value()); |
274 allocator.construct(&(values[id]), Value()); |
267 } |
275 } |
268 } |
276 } |
269 |
277 |
|
278 /// \brief Clear the map. |
|
279 /// |
|
280 /// It erase all items from the map. It called by the observer notifier |
|
281 /// and it overrides the clear() member function of the observer base. |
270 virtual void clear() { |
282 virtual void clear() { |
|
283 Notifier* notifier = Parent::getNotifier(); |
271 if (capacity != 0) { |
284 if (capacity != 0) { |
272 Item it; |
285 Item it; |
273 for (graph->first(it); it != INVALID; graph->next(it)) { |
286 for (notifier->first(it); it != INVALID; notifier->next(it)) { |
274 int id = graph->id(it); |
287 int id = notifier->id(it); |
275 allocator.destroy(&(values[id])); |
288 allocator.destroy(&(values[id])); |
276 } |
289 } |
277 allocator.deallocate(values, capacity); |
290 allocator.deallocate(values, capacity); |
278 capacity = 0; |
291 capacity = 0; |
279 } |
292 } |
280 } |
293 } |
281 |
294 |
282 private: |
295 private: |
283 |
296 |
284 void allocate_memory() { |
297 void allocate_memory() { |
285 int max_id = graph->maxId(_Item()); |
298 int max_id = Parent::getNotifier()->maxId(); |
286 if (max_id == -1) { |
299 if (max_id == -1) { |
287 capacity = 0; |
300 capacity = 0; |
288 values = 0; |
301 values = 0; |
289 return; |
302 return; |
290 } |
303 } |