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