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