1 // -*- c++ -*- |
|
2 #ifndef VECTOR_MAP_H |
|
3 #define VECTOR_MAP_H |
|
4 |
|
5 #include <vector> |
|
6 |
|
7 #include "extended_pair.h" |
|
8 |
|
9 namespace lemon { |
|
10 |
|
11 /** The VectorMapFactory template class is a factory class |
|
12 * to create maps for the edge and nodes. This map factory |
|
13 * use the std::vector to implement the container function. |
|
14 * |
|
15 * The template parameter is the MapRegistry that the maps |
|
16 * will belong to. |
|
17 */ |
|
18 |
|
19 template <typename MapRegistry> |
|
20 class VectorMapFactory { |
|
21 public: |
|
22 |
|
23 /// The graph type of the maps. |
|
24 typedef typename MapRegistry::Graph Graph; |
|
25 /// The key type of the maps. |
|
26 typedef typename MapRegistry::Key Key; |
|
27 /// The iterator to iterate on the keys. |
|
28 typedef typename MapRegistry::KeyIt KeyIt; |
|
29 |
|
30 /// The MapBase of the Map which imlements the core regisitry function. |
|
31 typedef typename MapRegistry::MapBase MapBase; |
|
32 |
|
33 |
|
34 /** The template Map type. |
|
35 */ |
|
36 template <typename V> |
|
37 class Map : public MapBase { |
|
38 public: |
|
39 |
|
40 /// The value type of the map. |
|
41 typedef V Value; |
|
42 |
|
43 typedef std::vector<Value> Container; |
|
44 |
|
45 /** Default constructor for the map. |
|
46 */ |
|
47 Map() {} |
|
48 |
|
49 /** Graph and Registry initialized map constructor. |
|
50 */ |
|
51 Map(const Graph& g, MapRegistry& r) : MapBase(g, r) { |
|
52 init(); |
|
53 } |
|
54 |
|
55 /** Constructor to use default value to initialize the map. |
|
56 */ |
|
57 Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) { |
|
58 for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) { |
|
59 int id = getGraph->id(it); |
|
60 if (id >= container.size) { |
|
61 container.resize(id + 1); |
|
62 } |
|
63 set(it, v); |
|
64 } |
|
65 } |
|
66 |
|
67 /** Constructor to copy a map of an other map type. |
|
68 */ |
|
69 template <typename CMap> Map(const CMap& copy) : MapBase(copy) { |
|
70 if (getGraph()) { |
|
71 for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) { |
|
72 int id = getGraph->id(it); |
|
73 if (id >= container.size) { |
|
74 container.resize(id + 1); |
|
75 } |
|
76 set(it, copy[it]); |
|
77 } |
|
78 } |
|
79 } |
|
80 |
|
81 /** Assign operator to copy a map an other map type. |
|
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 for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) { |
|
90 int id = getGraph->id(it); |
|
91 if (id >= container.size) { |
|
92 container.resize(id + 1); |
|
93 } |
|
94 set(it, copy[it]); |
|
95 } |
|
96 } |
|
97 } |
|
98 |
|
99 /** The destructor of the map. |
|
100 */ |
|
101 virtual ~Map() { |
|
102 } |
|
103 |
|
104 /** |
|
105 * The subscript operator. The map can be subscripted by the |
|
106 * actual keys of the graph. |
|
107 */ |
|
108 typename Container::reference operator[](const Key& key) { |
|
109 int id = getGraph()->id(key); |
|
110 return container[id]; |
|
111 } |
|
112 |
|
113 /** |
|
114 * The const subscript operator. The map can be subscripted by the |
|
115 * actual keys of the graph. |
|
116 */ |
|
117 typename Container::const_reference operator[](const Key& key) const { |
|
118 int id = getGraph()->id(key); |
|
119 return container[id]; |
|
120 } |
|
121 |
|
122 /** Setter function of the map. Equivalent with map[key] = val. |
|
123 * This is a compatibility feature with the not dereferable maps. |
|
124 */ |
|
125 void set(const Key& key, const Value& val) { |
|
126 int id = getGraph()->id(key); |
|
127 container[id] = val; |
|
128 } |
|
129 |
|
130 /** Add a new key to the map. It called by the map registry. |
|
131 */ |
|
132 void add(const Key& key) { |
|
133 int id = getGraph()->id(key); |
|
134 if (id >= container.size()) { |
|
135 container.resize(id + 1); |
|
136 } |
|
137 } |
|
138 |
|
139 /** Erease a key from the map. It called by the map registry. |
|
140 */ |
|
141 void erase(const Key& key) {} |
|
142 |
|
143 /** Compatible iterator with the stl maps' iterators. |
|
144 * It iterates on pairs of a key and a value. |
|
145 */ |
|
146 class iterator { |
|
147 friend class Map; |
|
148 friend class const_iterator; |
|
149 private: |
|
150 |
|
151 /** Private constructor to initalize the the iterators returned |
|
152 * by the begin() and end(). |
|
153 */ |
|
154 iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {} |
|
155 |
|
156 public: |
|
157 |
|
158 /** Default constructor. |
|
159 */ |
|
160 iterator() {} |
|
161 |
|
162 typedef extended_pair<const Key&, const Key&, |
|
163 Value&, Value&> Reference; |
|
164 |
|
165 /** Dereference operator for map. |
|
166 */ |
|
167 Reference operator*() { |
|
168 return Reference(it, (*map)[it]); |
|
169 } |
|
170 |
|
171 class Pointer { |
|
172 friend class iterator; |
|
173 private: |
|
174 Reference data; |
|
175 Pointer(const Key& key, Value& val) : data(key, val) {} |
|
176 public: |
|
177 Reference* operator->() {return &data;} |
|
178 }; |
|
179 |
|
180 /** Arrow operator for map. |
|
181 */ |
|
182 Pointer operator->() { |
|
183 return Pointer(it, ((*map)[it])); |
|
184 } |
|
185 |
|
186 /** The pre increment operator of the map. |
|
187 */ |
|
188 iterator& operator++() { |
|
189 map->getGraph()->next(it); |
|
190 return *this; |
|
191 } |
|
192 |
|
193 /** The post increment operator of the map. |
|
194 */ |
|
195 iterator operator++(int) { |
|
196 iterator tmp(it); |
|
197 map.getGraph()->next(it); |
|
198 return tmp; |
|
199 } |
|
200 |
|
201 /** The equality operator of the map. |
|
202 */ |
|
203 bool operator==(const_iterator p_it) { |
|
204 return p_it.it == it; |
|
205 } |
|
206 |
|
207 /** The not-equality operator of the map. |
|
208 */ |
|
209 bool operator!=(const_iterator p_it) { |
|
210 return !(*this == p_it); |
|
211 } |
|
212 |
|
213 |
|
214 private: |
|
215 Map* map; |
|
216 KeyIt it; |
|
217 }; |
|
218 |
|
219 /** Returns the begin iterator of the map. |
|
220 */ |
|
221 iterator begin() { |
|
222 return iterator(*this, KeyIt(*getGraph())); |
|
223 } |
|
224 |
|
225 /** Returns the end iterator of the map. |
|
226 */ |
|
227 iterator end() { |
|
228 return iterator(*this, INVALID); |
|
229 } |
|
230 |
|
231 class const_iterator { |
|
232 friend class Map; |
|
233 friend class iterator; |
|
234 private: |
|
235 |
|
236 /** Private constructor to initalize the the iterators returned |
|
237 * by the begin() and end(). |
|
238 */ |
|
239 const_iterator (const Map& pmap, const KeyIt& pit) |
|
240 : map(&pmap), it(pit) {} |
|
241 |
|
242 public: |
|
243 |
|
244 /** Default constructor. |
|
245 */ |
|
246 const_iterator() {} |
|
247 |
|
248 /** Constructor to convert iterator to const_iterator. |
|
249 */ |
|
250 const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {} |
|
251 |
|
252 typedef extended_pair<const Key&, const Key&, |
|
253 const Value&, const Value&> Reference; |
|
254 |
|
255 /** Dereference operator for map. |
|
256 */ |
|
257 Reference operator*() { |
|
258 return Reference(it, (*map)[it]); |
|
259 } |
|
260 |
|
261 |
|
262 class Pointer { |
|
263 friend class const_iterator; |
|
264 private: |
|
265 Reference data; |
|
266 Pointer(const Key& key, const Value& val) : data(key, val) {} |
|
267 public: |
|
268 Reference* operator->() {return &data;} |
|
269 }; |
|
270 |
|
271 /** Arrow operator for map. |
|
272 */ |
|
273 Pointer operator->() { |
|
274 return Pointer(it, ((*map)[it])); |
|
275 } |
|
276 |
|
277 /** The pre increment operator of the map. |
|
278 */ |
|
279 const_iterator& operator++() { |
|
280 map->getGraph()->next(it); |
|
281 return *this; |
|
282 } |
|
283 |
|
284 /** The post increment operator of the map. |
|
285 */ |
|
286 const_iterator operator++(int) { |
|
287 const_iterator tmp(it); |
|
288 map->getGraph()->next(it); |
|
289 return tmp; |
|
290 } |
|
291 |
|
292 /** The equality operator of the map. |
|
293 */ |
|
294 bool operator==(const_iterator p_it) { |
|
295 return p_it.it == it; |
|
296 } |
|
297 |
|
298 /** The not-equality operator of the map. |
|
299 */ |
|
300 bool operator!=(const_iterator p_it) { |
|
301 return !(*this == p_it); |
|
302 } |
|
303 |
|
304 |
|
305 private: |
|
306 const Map* map; |
|
307 KeyIt it; |
|
308 }; |
|
309 |
|
310 /** Returns the begin const_iterator of the map. |
|
311 */ |
|
312 const_iterator begin() const { |
|
313 return const_iterator(*this, KeyIt(*getGraph())); |
|
314 } |
|
315 |
|
316 /** Returns the end const_iterator of the map. |
|
317 */ |
|
318 const_iterator end() const { |
|
319 return const_iterator(*this, INVALID); |
|
320 } |
|
321 |
|
322 private: |
|
323 |
|
324 Container container; |
|
325 |
|
326 }; |
|
327 |
|
328 }; |
|
329 |
|
330 } |
|
331 |
|
332 #endif |
|