17 #ifndef LEMON_ARRAY_MAP_H |
17 #ifndef LEMON_ARRAY_MAP_H |
18 #define LEMON_ARRAY_MAP_H |
18 #define LEMON_ARRAY_MAP_H |
19 |
19 |
20 #include <memory> |
20 #include <memory> |
21 #include <lemon/bits/map_iterator.h> |
21 #include <lemon/bits/map_iterator.h> |
22 |
22 #include <lemon/concept_check.h> |
23 ///\ingroup graphmapfactory |
23 #include <lemon/concept/maps.h> |
24 ///\file |
24 |
25 ///\brief Graph maps that construates and destruates |
25 /// \ingroup graphmapfactory |
26 ///their elements dynamically. |
26 /// \file |
|
27 /// \brief Graph maps that construct and destruct |
|
28 /// their elements dynamically. |
27 |
29 |
28 namespace lemon { |
30 namespace lemon { |
29 |
31 |
30 |
32 /// \ingroup graphmapfactory |
31 /// \addtogroup graphmapfactory |
33 /// |
32 /// @{ |
34 /// \brief Graph map based on the array storage. |
33 |
35 /// |
34 /// The ArrayMap template class is graph map structure what |
36 /// The ArrayMap template class is graph map structure what |
35 /// automatically updates the map when a key is added to or erased from |
37 /// automatically updates the map when a key is added to or erased from |
36 /// the map. This map factory uses the allocators to implement |
38 /// the map. This map uses the allocators to implement |
37 /// the container functionality. |
39 /// the container functionality. |
38 /// |
40 /// |
39 /// The template parameter is the AlterationNotifier that the maps |
41 /// The template parameter is the AlterationNotifier that the maps |
40 /// will belong to and the Value. |
42 /// will belong to and the Value. |
41 |
|
42 |
43 |
43 template <typename _Graph, |
44 template <typename _Graph, |
44 typename _Item, |
45 typename _Item, |
45 typename _Value> |
46 typename _Value> |
46 class ArrayMap : public AlterationNotifier<_Item>::ObserverBase { |
47 class ArrayMap : public AlterationNotifier<_Item>::ObserverBase { |
108 int id = graph->id(it);; |
108 int id = graph->id(it);; |
109 allocator.construct(&(values[id]), copy.values[id]); |
109 allocator.construct(&(values[id]), copy.values[id]); |
110 } |
110 } |
111 } |
111 } |
112 |
112 |
113 using Parent::attach; |
113 /// \brief The destructor of the map. |
114 using Parent::detach; |
114 /// |
115 using Parent::attached; |
|
116 |
|
117 /// Assign operator to copy a map of the same map type. |
|
118 |
|
119 ArrayMap& operator=(const ArrayMap& copy) { |
|
120 if (© == this) return *this; |
|
121 |
|
122 if (graph != copy.graph) { |
|
123 if (attached()) { |
|
124 clear(); |
|
125 detach(); |
|
126 } |
|
127 if (copy.attached()) { |
|
128 attach(*copy.getRegistry()); |
|
129 } |
|
130 capacity = copy.capacity; |
|
131 if (capacity == 0) return *this; |
|
132 values = allocator.allocate(capacity); |
|
133 } |
|
134 |
|
135 Item it; |
|
136 for (graph->first(it); it != INVALID; graph->next(it)) { |
|
137 int id = graph->id(it);; |
|
138 allocator.construct(&(values[id]), copy.values[id]); |
|
139 } |
|
140 |
|
141 return *this; |
|
142 } |
|
143 |
|
144 /// The destructor of the map. |
115 /// The destructor of the map. |
145 |
|
146 virtual ~ArrayMap() { |
116 virtual ~ArrayMap() { |
147 if (attached()) { |
117 if (attached()) { |
148 clear(); |
118 clear(); |
149 detach(); |
119 detach(); |
150 } |
120 } |
151 } |
121 } |
152 |
122 |
153 |
123 private: |
|
124 |
|
125 ArrayMap& operator=(const ArrayMap&); |
|
126 |
|
127 protected: |
|
128 |
|
129 using Parent::attach; |
|
130 using Parent::detach; |
|
131 using Parent::attached; |
|
132 |
|
133 const Graph* getGraph() { |
|
134 return graph; |
|
135 } |
|
136 |
|
137 |
|
138 public: |
|
139 |
154 ///The subscript operator. The map can be subscripted by the |
140 ///The subscript operator. The map can be subscripted by the |
155 ///actual keys of the graph. |
141 ///actual keys of the graph. |
156 |
142 |
157 Value& operator[](const Key& key) { |
143 Value& operator[](const Key& key) { |
158 int id = graph->id(key); |
144 int id = graph->id(key); |
172 /// This is a compatibility feature with the not dereferable maps. |
158 /// This is a compatibility feature with the not dereferable maps. |
173 |
159 |
174 void set(const Key& key, const Value& val) { |
160 void set(const Key& key, const Value& val) { |
175 (*this)[key] = val; |
161 (*this)[key] = val; |
176 } |
162 } |
177 |
163 |
|
164 protected: |
|
165 |
178 /// Add a new key to the map. It called by the map registry. |
166 /// Add a new key to the map. It called by the map registry. |
179 |
167 |
180 void add(const Key& key) { |
168 void add(const Key& key) { |
181 int id = graph->id(key); |
169 int id = graph->id(key); |
182 if (id >= capacity) { |
170 if (id >= capacity) { |
299 Value* values; |
283 Value* values; |
300 Allocator allocator; |
284 Allocator allocator; |
301 |
285 |
302 }; |
286 }; |
303 |
287 |
304 template <typename _Base> |
|
305 class ArrayMappableGraphExtender : public _Base { |
|
306 public: |
|
307 |
|
308 typedef ArrayMappableGraphExtender<_Base> Graph; |
|
309 typedef _Base Parent; |
|
310 |
|
311 typedef typename Parent::Node Node; |
|
312 typedef typename Parent::NodeIt NodeIt; |
|
313 typedef typename Parent::NodeNotifier NodeObserverRegistry; |
|
314 |
|
315 typedef typename Parent::Edge Edge; |
|
316 typedef typename Parent::EdgeIt EdgeIt; |
|
317 typedef typename Parent::EdgeNotifier EdgeObserverRegistry; |
|
318 |
|
319 |
|
320 |
|
321 template <typename _Value> |
|
322 class NodeMap |
|
323 : public IterableMapExtender<ArrayMap<Graph, Node, _Value> > { |
|
324 public: |
|
325 typedef ArrayMappableGraphExtender<_Base> Graph; |
|
326 |
|
327 typedef typename Graph::Node Node; |
|
328 typedef typename Graph::NodeIt NodeIt; |
|
329 |
|
330 typedef IterableMapExtender<ArrayMap<Graph, Node, _Value> > Parent; |
|
331 |
|
332 //typedef typename Parent::Graph Graph; |
|
333 typedef typename Parent::Value Value; |
|
334 |
|
335 NodeMap(const Graph& g) |
|
336 : Parent(g) {} |
|
337 NodeMap(const Graph& g, const Value& v) |
|
338 : Parent(g, v) {} |
|
339 |
|
340 }; |
|
341 |
|
342 template <typename _Value> |
|
343 class EdgeMap |
|
344 : public IterableMapExtender<ArrayMap<Graph, Edge, _Value> > { |
|
345 public: |
|
346 typedef ArrayMappableGraphExtender<_Base> Graph; |
|
347 |
|
348 typedef typename Graph::Edge Edge; |
|
349 typedef typename Graph::EdgeIt EdgeIt; |
|
350 |
|
351 typedef IterableMapExtender<ArrayMap<Graph, Edge, _Value> > Parent; |
|
352 |
|
353 //typedef typename Parent::Graph Graph; |
|
354 typedef typename Parent::Value Value; |
|
355 |
|
356 EdgeMap(const Graph& g) |
|
357 : Parent(g) {} |
|
358 EdgeMap(const Graph& g, const Value& v) |
|
359 : Parent(g, v) {} |
|
360 |
|
361 }; |
|
362 |
|
363 }; |
|
364 |
|
365 /// @} |
|
366 |
|
367 } |
288 } |
368 |
289 |
369 #endif //LEMON_ARRAY_MAP_H |
290 #endif //LEMON_ARRAY_MAP_H |