1 /* -*- C++ -*- |
|
2 * src/lemon/array_map.h - Part of LEMON, a generic C++ optimization library |
|
3 * |
|
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
5 * (Egervary Combinatorial Optimization Research Group, 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/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) { |
|
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 /** |
|
155 * The subscript operator. The map can be subscripted by the |
|
156 * actual keys of the graph. |
|
157 */ |
|
158 Value& operator[](const Key& key) { |
|
159 int id = graph->id(key); |
|
160 return values[id]; |
|
161 } |
|
162 |
|
163 /** |
|
164 * The const subscript operator. The map can be subscripted by the |
|
165 * actual keys of the graph. |
|
166 */ |
|
167 const Value& operator[](const Key& key) const { |
|
168 int id = graph->id(key); |
|
169 return values[id]; |
|
170 } |
|
171 |
|
172 /** Setter function of the map. Equivalent with map[key] = val. |
|
173 * This is a compatibility feature with the not dereferable maps. |
|
174 */ |
|
175 void set(const Key& key, const Value& val) { |
|
176 (*this)[key] = val; |
|
177 } |
|
178 |
|
179 /** Add a new key to the map. It called by the map registry. |
|
180 */ |
|
181 void add(const Key& key) { |
|
182 int id = graph->id(key); |
|
183 if (id >= capacity) { |
|
184 int new_capacity = (capacity == 0 ? 1 : capacity); |
|
185 while (new_capacity <= id) { |
|
186 new_capacity <<= 1; |
|
187 } |
|
188 Value* new_values = allocator.allocate(new_capacity); |
|
189 Item it; |
|
190 for (graph->first(it); it != INVALID; graph->next(it)) { |
|
191 int jd = graph->id(it);; |
|
192 if (id != jd) { |
|
193 allocator.construct(&(new_values[jd]), values[jd]); |
|
194 allocator.destroy(&(values[jd])); |
|
195 } |
|
196 } |
|
197 if (capacity != 0) allocator.deallocate(values, capacity); |
|
198 values = new_values; |
|
199 capacity = new_capacity; |
|
200 } |
|
201 allocator.construct(&(values[id]), Value()); |
|
202 } |
|
203 |
|
204 /** Erase a key from the map. It called by the map registry. |
|
205 */ |
|
206 void erase(const Key& key) { |
|
207 int id = graph->id(key); |
|
208 allocator.destroy(&(values[id])); |
|
209 } |
|
210 |
|
211 void build() { |
|
212 allocate_memory(); |
|
213 Item it; |
|
214 for (graph->first(it); it != INVALID; graph->next(it)) { |
|
215 int id = graph->id(it);; |
|
216 allocator.construct(&(values[id]), Value()); |
|
217 } |
|
218 } |
|
219 |
|
220 void clear() { |
|
221 if (capacity != 0) { |
|
222 Item it; |
|
223 for (graph->first(it); it != INVALID; graph->next(it)) { |
|
224 int id = graph->id(it);; |
|
225 allocator.destroy(&(values[id])); |
|
226 } |
|
227 allocator.deallocate(values, capacity); |
|
228 capacity = 0; |
|
229 } |
|
230 } |
|
231 |
|
232 const Graph* getGraph() { |
|
233 return graph; |
|
234 } |
|
235 |
|
236 // /// The stl compatible pair iterator of the map. |
|
237 // typedef MapIterator<ArrayMap> Iterator; |
|
238 // /// The stl compatible const pair iterator of the map. |
|
239 // typedef MapConstIterator<ArrayMap> ConstIterator; |
|
240 |
|
241 // /** Returns the begin iterator of the map. |
|
242 // */ |
|
243 // Iterator begin() { |
|
244 // return Iterator(*this, KeyIt(*MapBase::getGraph())); |
|
245 // } |
|
246 |
|
247 // /** Returns the end iterator of the map. |
|
248 // */ |
|
249 // Iterator end() { |
|
250 // return Iterator(*this, INVALID); |
|
251 // } |
|
252 |
|
253 // /** Returns the begin ConstIterator of the map. |
|
254 // */ |
|
255 // ConstIterator begin() const { |
|
256 // return ConstIterator(*this, KeyIt(*MapBase::getGraph())); |
|
257 // } |
|
258 |
|
259 // /** Returns the end const_iterator of the map. |
|
260 // */ |
|
261 // ConstIterator end() const { |
|
262 // return ConstIterator(*this, INVALID); |
|
263 // } |
|
264 |
|
265 // /// The KeySet of the Map. |
|
266 // typedef MapConstKeySet<ArrayMap> ConstKeySet; |
|
267 |
|
268 // /// KeySet getter function. |
|
269 // ConstKeySet keySet() const { |
|
270 // return ConstKeySet(*this); |
|
271 // } |
|
272 |
|
273 // /// The ConstValueSet of the Map. |
|
274 // typedef MapConstValueSet<ArrayMap> ConstValueSet; |
|
275 |
|
276 // /// ConstValueSet getter function. |
|
277 // ConstValueSet valueSet() const { |
|
278 // return ConstValueSet(*this); |
|
279 // } |
|
280 |
|
281 // /// The ValueSet of the Map. |
|
282 // typedef MapValueSet<ArrayMap> ValueSet; |
|
283 |
|
284 // /// ValueSet getter function. |
|
285 // ValueSet valueSet() { |
|
286 // return ValueSet(*this); |
|
287 // } |
|
288 |
|
289 private: |
|
290 |
|
291 void allocate_memory() { |
|
292 int max_id = graph->maxId(_Item()); |
|
293 if (max_id == -1) { |
|
294 capacity = 0; |
|
295 values = 0; |
|
296 return; |
|
297 } |
|
298 capacity = 1; |
|
299 while (capacity <= max_id) { |
|
300 capacity <<= 1; |
|
301 } |
|
302 values = allocator.allocate(capacity); |
|
303 } |
|
304 |
|
305 const Graph* graph; |
|
306 int capacity; |
|
307 Value* values; |
|
308 Allocator allocator; |
|
309 |
|
310 }; |
|
311 |
|
312 template <typename _Base> |
|
313 class ArrayMappableGraphExtender : public _Base { |
|
314 public: |
|
315 |
|
316 typedef ArrayMappableGraphExtender<_Base> Graph; |
|
317 typedef _Base Parent; |
|
318 |
|
319 typedef typename Parent::Node Node; |
|
320 typedef typename Parent::NodeIt NodeIt; |
|
321 typedef typename Parent::NodeNotifier NodeObserverRegistry; |
|
322 |
|
323 typedef typename Parent::Edge Edge; |
|
324 typedef typename Parent::EdgeIt EdgeIt; |
|
325 typedef typename Parent::EdgeNotifier EdgeObserverRegistry; |
|
326 |
|
327 |
|
328 |
|
329 template <typename _Value> |
|
330 class NodeMap |
|
331 : public IterableMapExtender<ArrayMap<Graph, Node, _Value> > { |
|
332 public: |
|
333 typedef ArrayMappableGraphExtender<_Base> Graph; |
|
334 |
|
335 typedef typename Graph::Node Node; |
|
336 typedef typename Graph::NodeIt NodeIt; |
|
337 |
|
338 typedef IterableMapExtender<ArrayMap<Graph, Node, _Value> > Parent; |
|
339 |
|
340 //typedef typename Parent::Graph Graph; |
|
341 typedef typename Parent::Value Value; |
|
342 |
|
343 NodeMap(const Graph& g) |
|
344 : Parent(g) {} |
|
345 NodeMap(const Graph& g, const Value& v) |
|
346 : Parent(g, v) {} |
|
347 |
|
348 }; |
|
349 |
|
350 template <typename _Value> |
|
351 class EdgeMap |
|
352 : public IterableMapExtender<ArrayMap<Graph, Edge, _Value> > { |
|
353 public: |
|
354 typedef ArrayMappableGraphExtender<_Base> Graph; |
|
355 |
|
356 typedef typename Graph::Edge Edge; |
|
357 typedef typename Graph::EdgeIt EdgeIt; |
|
358 |
|
359 typedef IterableMapExtender<ArrayMap<Graph, Edge, _Value> > Parent; |
|
360 |
|
361 //typedef typename Parent::Graph Graph; |
|
362 typedef typename Parent::Value Value; |
|
363 |
|
364 EdgeMap(const Graph& g) |
|
365 : Parent(g) {} |
|
366 EdgeMap(const Graph& g, const Value& v) |
|
367 : Parent(g, v) {} |
|
368 |
|
369 }; |
|
370 |
|
371 }; |
|
372 |
|
373 /// @} |
|
374 |
|
375 } |
|
376 |
|
377 #endif //LEMON_ARRAY_MAP_H |
|