1 /* -*- C++ -*- |
|
2 * src/lemon/bits/array_map.h - Part of LEMON, a generic C++ optimization library |
|
3 * |
|
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
5 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
6 * |
|
7 * Permission to use, modify and distribute this software is granted |
|
8 * provided that this copyright notice appears in all copies. For |
|
9 * precise terms see the accompanying LICENSE file. |
|
10 * |
|
11 * This software is provided "AS IS" with no warranty of any kind, |
|
12 * express or implied, and with no claim as to its suitability for any |
|
13 * purpose. |
|
14 * |
|
15 */ |
|
16 |
|
17 #ifndef LEMON_ARRAY_MAP_H |
|
18 #define LEMON_ARRAY_MAP_H |
|
19 |
|
20 #include <memory> |
|
21 #include <lemon/bits/map_iterator.h> |
|
22 |
|
23 ///\ingroup graphmaps |
|
24 ///\file |
|
25 ///\brief Graph maps that construates and destruates |
|
26 ///their elements dynamically. |
|
27 |
|
28 namespace lemon { |
|
29 |
|
30 |
|
31 /// \addtogroup graphmaps |
|
32 /// @{ |
|
33 |
|
34 /// The ArrayMap template class is graph map structure what |
|
35 /// automatically updates the map when a key is added to or erased from |
|
36 /// the map. This map factory uses the allocators to implement |
|
37 /// the container functionality. |
|
38 /// |
|
39 /// The template parameter is the AlterationNotifier that the maps |
|
40 /// will belong to and the Value. |
|
41 |
|
42 |
|
43 template <typename _Graph, |
|
44 typename _Item, |
|
45 typename _Value> |
|
46 class ArrayMap : public AlterationNotifier<_Item>::ObserverBase { |
|
47 |
|
48 typedef _Item Item; |
|
49 public: |
|
50 |
|
51 /// The graph type of the maps. |
|
52 typedef _Graph Graph; |
|
53 /// The key type of the maps. |
|
54 typedef _Item Key; |
|
55 |
|
56 typedef AlterationNotifier<_Item> Registry; |
|
57 |
|
58 /// The MapBase of the Map which imlements the core regisitry function. |
|
59 typedef typename Registry::ObserverBase Parent; |
|
60 |
|
61 /// The value type of the map. |
|
62 typedef _Value Value; |
|
63 |
|
64 |
|
65 private: |
|
66 typedef std::allocator<Value> Allocator; |
|
67 |
|
68 |
|
69 public: |
|
70 |
|
71 /// Graph and Registry initialized map constructor. |
|
72 |
|
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; |
|
89 attach(_g.getNotifier(_Item())); |
|
90 allocate_memory(); |
|
91 for (graph->first(it); it != INVALID; graph->next(it)) { |
|
92 int id = graph->id(it);; |
|
93 allocator.construct(&(values[id]), _v); |
|
94 } |
|
95 } |
|
96 |
|
97 /// Constructor to copy a map of the same map type. |
|
98 |
|
99 ArrayMap(const ArrayMap& copy) : Parent() { |
|
100 if (copy.attached()) { |
|
101 attach(*copy.getRegistry()); |
|
102 } |
|
103 capacity = copy.capacity; |
|
104 if (capacity == 0) return; |
|
105 values = allocator.allocate(capacity); |
|
106 Item it; |
|
107 for (graph->first(it); it != INVALID; graph->next(it)) { |
|
108 int id = graph->id(it);; |
|
109 allocator.construct(&(values[id]), copy.values[id]); |
|
110 } |
|
111 } |
|
112 |
|
113 using Parent::attach; |
|
114 using Parent::detach; |
|
115 using Parent::attached; |
|
116 |
|
117 /// Assign operator to copy a map of the same map type. |
|
118 |
|
119 ArrayMap& operator=(const ArrayMap& copy) { |
|
120 if (© == this) return *this; |
|
121 |
|
122 if (graph != copy.graph) { |
|
123 if (attached()) { |
|
124 clear(); |
|
125 detach(); |
|
126 } |
|
127 if (copy.attached()) { |
|
128 attach(*copy.getRegistry()); |
|
129 } |
|
130 capacity = copy.capacity; |
|
131 if (capacity == 0) return *this; |
|
132 values = allocator.allocate(capacity); |
|
133 } |
|
134 |
|
135 Item it; |
|
136 for (graph->first(it); it != INVALID; graph->next(it)) { |
|
137 int id = graph->id(it);; |
|
138 allocator.construct(&(values[id]), copy.values[id]); |
|
139 } |
|
140 |
|
141 return *this; |
|
142 } |
|
143 |
|
144 /// The destructor of the map. |
|
145 |
|
146 virtual ~ArrayMap() { |
|
147 if (attached()) { |
|
148 clear(); |
|
149 detach(); |
|
150 } |
|
151 } |
|
152 |
|
153 |
|
154 ///The subscript operator. The map can be subscripted by the |
|
155 ///actual keys of the graph. |
|
156 |
|
157 Value& operator[](const Key& key) { |
|
158 int id = graph->id(key); |
|
159 return values[id]; |
|
160 } |
|
161 |
|
162 |
|
163 ///The const subscript operator. The map can be subscripted by the |
|
164 ///actual keys of the graph. |
|
165 |
|
166 const Value& operator[](const Key& key) const { |
|
167 int id = graph->id(key); |
|
168 return values[id]; |
|
169 } |
|
170 |
|
171 /// Setter function of the map. Equivalent with map[key] = val. |
|
172 /// This is a compatibility feature with the not dereferable maps. |
|
173 |
|
174 void set(const Key& key, const Value& val) { |
|
175 (*this)[key] = val; |
|
176 } |
|
177 |
|
178 /// Add a new key to the map. It called by the map registry. |
|
179 |
|
180 void add(const Key& key) { |
|
181 int id = graph->id(key); |
|
182 if (id >= capacity) { |
|
183 int new_capacity = (capacity == 0 ? 1 : capacity); |
|
184 while (new_capacity <= id) { |
|
185 new_capacity <<= 1; |
|
186 } |
|
187 Value* new_values = allocator.allocate(new_capacity); |
|
188 Item it; |
|
189 for (graph->first(it); it != INVALID; graph->next(it)) { |
|
190 int jd = graph->id(it);; |
|
191 if (id != jd) { |
|
192 allocator.construct(&(new_values[jd]), values[jd]); |
|
193 allocator.destroy(&(values[jd])); |
|
194 } |
|
195 } |
|
196 if (capacity != 0) allocator.deallocate(values, capacity); |
|
197 values = new_values; |
|
198 capacity = new_capacity; |
|
199 } |
|
200 allocator.construct(&(values[id]), Value()); |
|
201 } |
|
202 |
|
203 void add(const std::vector<Key>& keys) { |
|
204 int max_id = -1; |
|
205 for (int i = 0; i < (int)keys.size(); ++i) { |
|
206 int id = graph->id(keys[i]); |
|
207 if (id > max_id) { |
|
208 max_id = id; |
|
209 } |
|
210 } |
|
211 if (max_id >= capacity) { |
|
212 int new_capacity = (capacity == 0 ? 1 : capacity); |
|
213 while (new_capacity <= max_id) { |
|
214 new_capacity <<= 1; |
|
215 } |
|
216 Value* new_values = allocator.allocate(new_capacity); |
|
217 Item it; |
|
218 for (graph->first(it); it != INVALID; graph->next(it)) { |
|
219 int id = graph->id(it); |
|
220 bool found = false; |
|
221 for (int i = 0; i < (int)keys.size(); ++i) { |
|
222 int jd = graph->id(keys[i]); |
|
223 if (id == jd) { |
|
224 found = true; |
|
225 break; |
|
226 } |
|
227 } |
|
228 if (found) continue; |
|
229 allocator.construct(&(new_values[id]), values[id]); |
|
230 allocator.destroy(&(values[id])); |
|
231 } |
|
232 if (capacity != 0) allocator.deallocate(values, capacity); |
|
233 values = new_values; |
|
234 capacity = new_capacity; |
|
235 } |
|
236 for (int i = 0; i < (int)keys.size(); ++i) { |
|
237 int id = graph->id(keys[i]); |
|
238 allocator.construct(&(values[id]), Value()); |
|
239 } |
|
240 } |
|
241 |
|
242 /// Erase a key from the map. It called by the map registry. |
|
243 |
|
244 void erase(const Key& key) { |
|
245 int id = graph->id(key); |
|
246 allocator.destroy(&(values[id])); |
|
247 } |
|
248 |
|
249 void erase(const std::vector<Key>& keys) { |
|
250 for (int i = 0; i < (int)keys.size(); ++i) { |
|
251 int id = graph->id(keys[i]); |
|
252 allocator.destroy(&(values[id])); |
|
253 } |
|
254 } |
|
255 |
|
256 void build() { |
|
257 allocate_memory(); |
|
258 Item it; |
|
259 for (graph->first(it); it != INVALID; graph->next(it)) { |
|
260 int id = graph->id(it);; |
|
261 allocator.construct(&(values[id]), Value()); |
|
262 } |
|
263 } |
|
264 |
|
265 void clear() { |
|
266 if (capacity != 0) { |
|
267 Item it; |
|
268 for (graph->first(it); it != INVALID; graph->next(it)) { |
|
269 int id = graph->id(it); |
|
270 allocator.destroy(&(values[id])); |
|
271 } |
|
272 allocator.deallocate(values, capacity); |
|
273 capacity = 0; |
|
274 } |
|
275 } |
|
276 |
|
277 const Graph* getGraph() { |
|
278 return graph; |
|
279 } |
|
280 |
|
281 private: |
|
282 |
|
283 void allocate_memory() { |
|
284 int max_id = graph->maxId(_Item()); |
|
285 if (max_id == -1) { |
|
286 capacity = 0; |
|
287 values = 0; |
|
288 return; |
|
289 } |
|
290 capacity = 1; |
|
291 while (capacity <= max_id) { |
|
292 capacity <<= 1; |
|
293 } |
|
294 values = allocator.allocate(capacity); |
|
295 } |
|
296 |
|
297 const Graph* graph; |
|
298 int capacity; |
|
299 Value* values; |
|
300 Allocator allocator; |
|
301 |
|
302 }; |
|
303 |
|
304 template <typename _Base> |
|
305 class ArrayMappableGraphExtender : public _Base { |
|
306 public: |
|
307 |
|
308 typedef ArrayMappableGraphExtender<_Base> Graph; |
|
309 typedef _Base Parent; |
|
310 |
|
311 typedef typename Parent::Node Node; |
|
312 typedef typename Parent::NodeIt NodeIt; |
|
313 typedef typename Parent::NodeNotifier NodeObserverRegistry; |
|
314 |
|
315 typedef typename Parent::Edge Edge; |
|
316 typedef typename Parent::EdgeIt EdgeIt; |
|
317 typedef typename Parent::EdgeNotifier EdgeObserverRegistry; |
|
318 |
|
319 |
|
320 |
|
321 template <typename _Value> |
|
322 class NodeMap |
|
323 : public IterableMapExtender<ArrayMap<Graph, Node, _Value> > { |
|
324 public: |
|
325 typedef ArrayMappableGraphExtender<_Base> Graph; |
|
326 |
|
327 typedef typename Graph::Node Node; |
|
328 typedef typename Graph::NodeIt NodeIt; |
|
329 |
|
330 typedef IterableMapExtender<ArrayMap<Graph, Node, _Value> > Parent; |
|
331 |
|
332 //typedef typename Parent::Graph Graph; |
|
333 typedef typename Parent::Value Value; |
|
334 |
|
335 NodeMap(const Graph& g) |
|
336 : Parent(g) {} |
|
337 NodeMap(const Graph& g, const Value& v) |
|
338 : Parent(g, v) {} |
|
339 |
|
340 }; |
|
341 |
|
342 template <typename _Value> |
|
343 class EdgeMap |
|
344 : public IterableMapExtender<ArrayMap<Graph, Edge, _Value> > { |
|
345 public: |
|
346 typedef ArrayMappableGraphExtender<_Base> Graph; |
|
347 |
|
348 typedef typename Graph::Edge Edge; |
|
349 typedef typename Graph::EdgeIt EdgeIt; |
|
350 |
|
351 typedef IterableMapExtender<ArrayMap<Graph, Edge, _Value> > Parent; |
|
352 |
|
353 //typedef typename Parent::Graph Graph; |
|
354 typedef typename Parent::Value Value; |
|
355 |
|
356 EdgeMap(const Graph& g) |
|
357 : Parent(g) {} |
|
358 EdgeMap(const Graph& g, const Value& v) |
|
359 : Parent(g, v) {} |
|
360 |
|
361 }; |
|
362 |
|
363 }; |
|
364 |
|
365 /// @} |
|
366 |
|
367 } |
|
368 |
|
369 #endif //LEMON_ARRAY_MAP_H |
|