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