1 // -*- c++ -*- |
|
2 #ifndef ARRAY_MAP_H |
|
3 #define ARRAY_MAP_H |
|
4 |
|
5 #include <memory> |
|
6 |
|
7 #include "extended_pair.h" |
|
8 |
|
9 namespace lemon { |
|
10 |
|
11 template <typename MapRegistry> class ArrayMapFactory { |
|
12 |
|
13 public: |
|
14 |
|
15 typedef typename MapRegistry::Graph Graph; |
|
16 typedef typename MapRegistry::Key Key; |
|
17 typedef typename MapRegistry::KeyIt KeyIt; |
|
18 |
|
19 typedef typename MapRegistry::MapBase MapBase; |
|
20 |
|
21 template <typename V, typename A = std::allocator<V> > |
|
22 class Map : public MapBase { |
|
23 |
|
24 public: |
|
25 |
|
26 typedef V Value; |
|
27 typedef A Allocator; |
|
28 |
|
29 |
|
30 Map() : values(0), capacity(0) {} |
|
31 |
|
32 Map(const Graph& g, MapRegistry& r) : MapBase(g, r) { |
|
33 allocate_memory(); |
|
34 for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) { |
|
35 int id = getGraph()->id(it); |
|
36 allocator.construct(&(values[id]), Value()); |
|
37 } |
|
38 } |
|
39 |
|
40 Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) { |
|
41 allocate_memory(); |
|
42 for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) { |
|
43 int id = getGraph()->id(it); |
|
44 allocator.construct(&(values[id]), v); |
|
45 } |
|
46 } |
|
47 |
|
48 Map(const Map& copy) : MapBase(*copy.graph, *copy.registry) { |
|
49 capacity = copy.capacity; |
|
50 if (capacity == 0) return; |
|
51 values = allocator.allocate(capacity); |
|
52 for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) { |
|
53 int id = getGraph()->id(it); |
|
54 allocator.construct(&(values[id]), copy.values[id]); |
|
55 } |
|
56 } |
|
57 |
|
58 template <typename CMap> Map(const CMap& copy) |
|
59 : capacity(0), values(0), MapBase(copy) { |
|
60 if (getGraph()) { |
|
61 allocate_memory(); |
|
62 for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) { |
|
63 set(it, copy[it]); |
|
64 } |
|
65 } |
|
66 } |
|
67 |
|
68 Map& operator=(const Map& copy) { |
|
69 if (© == this) return; |
|
70 if (capacity != 0) { |
|
71 destroy(); |
|
72 allocator.deallocate(values, capacity); |
|
73 } |
|
74 capacity = copy.capacity; |
|
75 if (capacity == 0) return; |
|
76 values = allocator.allocate(capacity); |
|
77 for (KeyIt it(getGraph()); getGraph()->valid(it); getGraph()->next(it)) { |
|
78 int id = getGraph()->id(it); |
|
79 allocator.construct(&(values[id]), copy.values[id]); |
|
80 } |
|
81 } |
|
82 |
|
83 template <typename CMap> Map& operator=(const CMap& copy) { |
|
84 if (getGraph()) { |
|
85 destroy(); |
|
86 } |
|
87 this->MapBase::operator=(copy); |
|
88 if (getGraph()) { |
|
89 allocate_memory(); |
|
90 for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) { |
|
91 set(it, copy[it]); |
|
92 } |
|
93 } |
|
94 } |
|
95 |
|
96 virtual ~Map() { |
|
97 if (capacity != 0) { |
|
98 destroy(); |
|
99 allocator.deallocate(values, capacity); |
|
100 } |
|
101 } |
|
102 |
|
103 |
|
104 Value& operator[](const Key& key) { |
|
105 int id = getGraph()->id(key); |
|
106 return values[id]; |
|
107 } |
|
108 |
|
109 const Value& operator[](const Key& key) const { |
|
110 int id = getGraph()->id(key); |
|
111 return values[id]; |
|
112 } |
|
113 |
|
114 const Value& get(const Key& key) const { |
|
115 int id = getGraph()->id(key); |
|
116 return values[id]; |
|
117 } |
|
118 |
|
119 void set(const Key& key, const Value& val) { |
|
120 int id = getGraph()->id(key); |
|
121 values[id] = val; |
|
122 } |
|
123 |
|
124 void add(const Key& key) { |
|
125 int id = getGraph()->id(key); |
|
126 if (id >= capacity) { |
|
127 int new_capacity = (capacity == 0 ? 1 : capacity); |
|
128 while (new_capacity <= id) { |
|
129 new_capacity <<= 1; |
|
130 } |
|
131 Value* new_values = allocator.allocate(new_capacity);; |
|
132 for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) { |
|
133 int jd = getGraph()->id(it); |
|
134 if (id != jd) { |
|
135 allocator.construct(&(new_values[jd]), values[jd]); |
|
136 allocator.destroy(&(values[jd])); |
|
137 } |
|
138 } |
|
139 if (capacity != 0) allocator.deallocate(values, capacity); |
|
140 values = new_values; |
|
141 capacity = new_capacity; |
|
142 } |
|
143 allocator.construct(&(values[id]), Value()); |
|
144 } |
|
145 |
|
146 void erase(const Key& key) { |
|
147 int id = getGraph()->id(key); |
|
148 allocator.destroy(&(values[id])); |
|
149 } |
|
150 |
|
151 class iterator { |
|
152 friend class Map; |
|
153 friend class const_iterator; |
|
154 private: |
|
155 |
|
156 /** Private constructor to initalize the the iterators returned |
|
157 * by the begin() and end(). |
|
158 */ |
|
159 iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {} |
|
160 |
|
161 public: |
|
162 |
|
163 /** Default constructor. |
|
164 */ |
|
165 iterator() {} |
|
166 |
|
167 typedef extended_pair<const Key&, const Key&, |
|
168 Value&, Value&> Reference; |
|
169 |
|
170 /** Dereference operator for map. |
|
171 */ |
|
172 Reference operator*() { |
|
173 return Reference(it, (*map)[it]); |
|
174 } |
|
175 |
|
176 class Pointer { |
|
177 friend class iterator; |
|
178 private: |
|
179 Reference data; |
|
180 Pointer(const Key& key, Value& val) : data(key, val) {} |
|
181 public: |
|
182 Reference* operator->() {return &data;} |
|
183 }; |
|
184 |
|
185 /** Arrow operator for map. |
|
186 */ |
|
187 Pointer operator->() { |
|
188 return Pointer(it, ((*map)[it])); |
|
189 } |
|
190 |
|
191 /** The pre increment operator of the map. |
|
192 */ |
|
193 iterator& operator++() { |
|
194 map->getGraph()->next(it); |
|
195 return *this; |
|
196 } |
|
197 |
|
198 /** The post increment operator of the map. |
|
199 */ |
|
200 iterator operator++(int) { |
|
201 iterator tmp(it); |
|
202 map.getGraph()->next(it); |
|
203 return tmp; |
|
204 } |
|
205 |
|
206 /** The equality operator of the map. |
|
207 */ |
|
208 bool operator==(const_iterator p_it) { |
|
209 return p_it.it == it; |
|
210 } |
|
211 |
|
212 /** The not-equality operator of the map. |
|
213 */ |
|
214 bool operator!=(const_iterator p_it) { |
|
215 return !(*this == p_it); |
|
216 } |
|
217 |
|
218 |
|
219 private: |
|
220 Map* map; |
|
221 KeyIt it; |
|
222 }; |
|
223 |
|
224 /** Returns the begin iterator of the map. |
|
225 */ |
|
226 iterator begin() { |
|
227 return iterator(*this, KeyIt(*getGraph())); |
|
228 } |
|
229 |
|
230 /** Returns the end iterator of the map. |
|
231 */ |
|
232 iterator end() { |
|
233 return iterator(*this, INVALID); |
|
234 } |
|
235 |
|
236 class const_iterator { |
|
237 friend class Map; |
|
238 friend class iterator; |
|
239 private: |
|
240 |
|
241 /** Private constructor to initalize the the iterators returned |
|
242 * by the begin() and end(). |
|
243 */ |
|
244 const_iterator (const Map& pmap, const KeyIt& pit) |
|
245 : map(&pmap), it(pit) {} |
|
246 |
|
247 public: |
|
248 |
|
249 /** Default constructor. |
|
250 */ |
|
251 const_iterator() {} |
|
252 |
|
253 /** Constructor to convert iterator to const_iterator. |
|
254 */ |
|
255 const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {} |
|
256 |
|
257 typedef extended_pair<const Key&, const Key&, |
|
258 const Value&, const Value&> Reference; |
|
259 |
|
260 /** Dereference operator for map. |
|
261 */ |
|
262 Reference operator*() { |
|
263 return Reference(it, (*map)[it]); |
|
264 } |
|
265 |
|
266 |
|
267 class Pointer { |
|
268 friend class const_iterator; |
|
269 private: |
|
270 Reference data; |
|
271 Pointer(const Key& key, const Value& val) : data(key, val) {} |
|
272 public: |
|
273 Reference* operator->() {return &data;} |
|
274 }; |
|
275 |
|
276 /** Arrow operator for map. |
|
277 */ |
|
278 Pointer operator->() { |
|
279 return Pointer(it, ((*map)[it])); |
|
280 } |
|
281 |
|
282 /** The pre increment operator of the map. |
|
283 */ |
|
284 const_iterator& operator++() { |
|
285 map->getGraph()->next(it); |
|
286 return *this; |
|
287 } |
|
288 |
|
289 /** The post increment operator of the map. |
|
290 */ |
|
291 const_iterator operator++(int) { |
|
292 const_iterator tmp(it); |
|
293 map->getGraph()->next(it); |
|
294 return tmp; |
|
295 } |
|
296 |
|
297 /** The equality operator of the map. |
|
298 */ |
|
299 bool operator==(const_iterator p_it) { |
|
300 return p_it.it == it; |
|
301 } |
|
302 |
|
303 /** The not-equality operator of the map. |
|
304 */ |
|
305 bool operator!=(const_iterator p_it) { |
|
306 return !(*this == p_it); |
|
307 } |
|
308 |
|
309 |
|
310 private: |
|
311 const Map* map; |
|
312 KeyIt it; |
|
313 }; |
|
314 |
|
315 /** Returns the begin const_iterator of the map. |
|
316 */ |
|
317 const_iterator begin() const { |
|
318 return const_iterator(*this, KeyIt(*getGraph())); |
|
319 } |
|
320 |
|
321 /** Returns the end const_iterator of the map. |
|
322 */ |
|
323 const_iterator end() const { |
|
324 return const_iterator(*this, INVALID); |
|
325 } |
|
326 |
|
327 private: |
|
328 |
|
329 void allocate_memory() { |
|
330 int max_id = -1; |
|
331 for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) { |
|
332 int id = getGraph()->id(it); |
|
333 if (id > max_id) { |
|
334 max_id = id; |
|
335 } |
|
336 } |
|
337 if (max_id == -1) { |
|
338 capacity = 0; |
|
339 values = 0; |
|
340 return; |
|
341 } |
|
342 capacity = 1; |
|
343 while (capacity <= max_id) { |
|
344 capacity <<= 1; |
|
345 } |
|
346 values = allocator.allocate(capacity); |
|
347 } |
|
348 int capacity; |
|
349 Value* values; |
|
350 Allocator allocator; |
|
351 }; |
|
352 }; |
|
353 } |
|
354 |
|
355 #endif |
|