16 |
16 |
17 #ifndef LEMON_VECTOR_MAP_H |
17 #ifndef LEMON_VECTOR_MAP_H |
18 #define LEMON_VECTOR_MAP_H |
18 #define LEMON_VECTOR_MAP_H |
19 |
19 |
20 #include <vector> |
20 #include <vector> |
21 |
21 #include <algorithm> |
22 #include <lemon/map_iterator.h> |
22 |
23 #include <lemon/map_bits.h> |
23 #include <lemon/alteration_observer_registry.h> |
24 |
24 |
25 ///\ingroup graphmaps |
25 ///\ingroup graphmaps |
26 ///\file |
26 ///\file |
27 ///\brief Vector based graph maps. |
27 ///\brief Vector based graph maps. |
28 |
28 |
29 namespace lemon { |
29 namespace lemon { |
30 |
30 |
31 /// \addtogroup graphmaps |
31 /// \addtogroup graphmaps |
32 /// @{ |
32 /// @{ |
33 |
33 |
34 /** The VectorMap template class is graph map structure what |
34 /// The VectorMap template class is graph map structure what |
35 * automatically updates the map when a key is added to or erased from |
35 /// automatically updates the map when a key is added to or erased from |
36 * the map. This map factory uses the allocators to implement |
36 /// the map. This map factory uses the allocators to implement |
37 * the container functionality. This map factory |
37 /// the container functionality. This map factory |
38 * uses the std::vector to implement the container function. |
38 /// uses the std::vector to implement the container function. |
39 * |
39 /// |
40 * \param MapRegistry The MapRegistry that the maps will belong to. |
40 /// \param Registry The AlterationObserverRegistry that will notify this map. |
41 * \param Value The value type of the map. |
41 /// \param IdMap The IdMap type of the graph items. |
42 * |
42 /// \param Value The value type of the map. |
43 * \author Balazs Dezso |
43 /// |
44 */ |
44 /// \author Balazs Dezso |
45 |
45 |
46 template <typename MapRegistry, typename Value> |
46 |
47 class VectorMap : public MapRegistry::MapBase { |
47 template <typename _Graph, |
48 template <typename MR, typename T> friend class VectorMap; |
48 typename _Item, |
|
49 typename _IdMap, |
|
50 typename _Value> |
|
51 class VectorMap : public AlterationObserverRegistry<_Item>::ObserverBase { |
49 public: |
52 public: |
50 |
53 |
51 /// The graph type of the maps. |
54 /// The graph type of the map. |
52 typedef typename MapRegistry::Graph Graph; |
55 typedef _Graph Graph; |
53 /// The key type of the maps. |
56 /// The key type of the map. |
54 typedef typename MapRegistry::KeyType KeyType; |
57 typedef _Item KeyType; |
55 /// The iterator to iterate on the keys. |
58 /// The id map type of the map. |
56 typedef typename MapRegistry::KeyIt KeyIt; |
59 typedef _IdMap IdMap; |
|
60 /// The registry type of the map. |
|
61 typedef AlterationObserverRegistry<_Item> Registry; |
|
62 /// The value type of the map. |
|
63 typedef _Value Value; |
57 |
64 |
58 /// The map type. |
65 /// The map type. |
59 typedef VectorMap Map; |
66 typedef VectorMap Map; |
60 /// The MapBase of the Map which implements the core regisitry function. |
67 /// The base class of the map. |
61 typedef typename MapRegistry::MapBase MapBase; |
68 typedef typename Registry::ObserverBase Parent; |
62 |
69 |
63 private: |
70 private: |
64 |
71 |
65 /// The container type of the map. |
72 /// The container type of the map. |
66 typedef std::vector<Value> Container; |
73 typedef std::vector<Value> Container; |
67 |
74 |
68 public: |
75 public: |
69 |
|
70 |
76 |
71 /// The value type of the map. |
77 /// The value type of the map. |
72 typedef Value ValueType; |
78 typedef Value ValueType; |
73 /// The reference type of the map; |
79 /// The reference type of the map; |
74 typedef typename Container::reference ReferenceType; |
80 typedef typename Container::reference ReferenceType; |
80 /// The const reference type of the map; |
86 /// The const reference type of the map; |
81 typedef typename Container::const_reference ConstReferenceType; |
87 typedef typename Container::const_reference ConstReferenceType; |
82 /// The pointer type of the map; |
88 /// The pointer type of the map; |
83 typedef typename Container::const_pointer ConstPointerType; |
89 typedef typename Container::const_pointer ConstPointerType; |
84 |
90 |
85 /// Constructor to attach the new map into a registry. |
91 /// Constructor to attach the new map into the registry. |
86 |
92 |
87 /** Constructor to attach the new map into a registry. |
93 /// It construates a map and attachs it into the registry. |
88 * It adds all the nodes or edges of the graph to the map. |
94 /// It adds all the items of the graph to the map. |
|
95 |
|
96 VectorMap(const Graph& _g, Registry& _r) : graph(&_g) { |
|
97 attach(_r); |
|
98 build(); |
|
99 } |
|
100 |
|
101 /// Constructor uses given value to initialize the map. |
|
102 |
|
103 /// It construates a map uses a given value to initialize the map. |
|
104 /// It adds all the items of the graph to the map. |
|
105 |
|
106 VectorMap(const Graph& g, Registry& r, const Value& v) : graph(&g) { |
|
107 attach(r); |
|
108 container.resize(IdMap(*graph).maxId() + 1, v); |
|
109 } |
|
110 |
|
111 VectorMap(const VectorMap& copy) : graph(copy.getGraph()) { |
|
112 if (copy.attached()) { |
|
113 attach(*copy.getRegistry()); |
|
114 container = copy.container; |
|
115 } |
|
116 } |
|
117 |
|
118 |
|
119 /** Assign operator to copy a map of the same map type. |
89 */ |
120 */ |
90 VectorMap(const Graph& g, MapRegistry& r) |
121 VectorMap& operator=(const VectorMap& copy) { |
91 : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1) {} |
122 if (© == this) return *this; |
92 |
123 |
93 /// Constructor uses given value to initialize the map. |
124 if (graph != copy.graph) { |
94 |
125 if (attached()) { |
95 /** Constructor uses given value to initialize the map. |
126 detach(); |
96 * It adds all the nodes or edges of the graph to the map. |
127 } |
97 */ |
128 if (copy.attached()) { |
98 VectorMap(const Graph& g, MapRegistry& r, const Value& v) |
129 attach(*copy.getRegistry()); |
99 : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1, v) {} |
130 } |
100 |
131 } |
101 /// Assign operator to copy a map of an other map type. |
132 container = copy.container; |
102 |
133 |
103 /** Assign operator to copy a map of an other map type. |
|
104 * This map's value type must be assignable by the other |
|
105 * map type's value type. |
|
106 */ |
|
107 template <typename TT> |
|
108 VectorMap(const VectorMap<MapRegistry, TT>& c) |
|
109 : MapBase(c), container(c.container.size()) { |
|
110 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { |
|
111 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it); |
|
112 container[id] = c.container[id]; |
|
113 } |
|
114 } |
|
115 |
|
116 /// Assign operator to copy a map of an other map type. |
|
117 |
|
118 /** Assign operator to copy a map of an other map type. |
|
119 * This map's value type must be assignable by the other |
|
120 * map type's value type. |
|
121 */ |
|
122 template <typename TT> |
|
123 VectorMap& operator=(const VectorMap<MapRegistry, TT>& c) { |
|
124 if (MapBase::getGraph() != c.getGraph()) { |
|
125 MapBase::operator=(c); |
|
126 container.resize(c.container.size()); |
|
127 } |
|
128 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { |
|
129 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it); |
|
130 container[id] = c.container[id]; |
|
131 } |
|
132 return *this; |
134 return *this; |
133 } |
135 } |
134 |
136 |
|
137 |
|
138 virtual ~VectorMap() { |
|
139 if (attached()) { |
|
140 detach(); |
|
141 } |
|
142 } |
|
143 |
|
144 const Graph* getGraph() const { |
|
145 return graph; |
|
146 } |
|
147 |
135 /// The subcript operator. |
148 /// The subcript operator. |
136 |
149 |
137 /** |
150 /// The subscript operator. The map can be subscripted by the |
138 * The subscript operator. The map can be subscripted by the |
151 /// actual items of the graph. |
139 * actual keys of the graph. |
152 |
140 */ |
|
141 ReferenceType operator[](const KeyType& key) { |
153 ReferenceType operator[](const KeyType& key) { |
142 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key); |
154 return container[IdMap(*graph)[key]]; |
143 return container[id]; |
|
144 } |
155 } |
145 |
156 |
146 /// The const subcript operator. |
157 /// The const subcript operator. |
147 |
158 |
148 /** |
159 /// The const subscript operator. The map can be subscripted by the |
149 * The const subscript operator. The map can be subscripted by the |
160 /// actual items of the graph. |
150 * actual keys of the graph. |
161 |
151 */ |
|
152 ConstReferenceType operator[](const KeyType& key) const { |
162 ConstReferenceType operator[](const KeyType& key) const { |
153 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key); |
163 return container[IdMap(*graph)[key]]; |
154 return container[id]; |
164 } |
155 } |
165 |
156 |
166 |
157 ///Setter function of the map. |
167 /// The setter function of the map. |
158 |
168 |
159 /** Setter function of the map. Equivalent with map[key] = val. |
169 /// It the same as operator[](key) = value expression. |
160 * This is a compatibility feature with the not dereferable maps. |
170 /// |
161 */ |
171 |
162 void set(const KeyType& key, const ValueType& val) { |
172 void set(const KeyType& key, const ValueType& value) { |
163 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key); |
173 (*this)[key] = value; |
164 container[id] = val; |
174 } |
165 } |
175 |
166 /// Adds a new key to the map. |
176 /// Adds a new key to the map. |
167 |
177 |
168 /** Adds a new key to the map. It called by the map registry |
178 /// It adds a new key to the map. It called by the observer registry |
169 * and it overrides the \ref MapRegistry::MapBase MapBase's |
179 /// and it overrides the add() member function of the observer base. |
170 * add() member function. |
180 |
171 */ |
|
172 void add(const KeyType& key) { |
181 void add(const KeyType& key) { |
173 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key); |
182 int id = IdMap(*graph)[key]; |
174 if (id >= (int)container.size()) { |
183 if (id >= (int)container.size()) { |
175 container.resize(id + 1); |
184 container.resize(id + 1); |
176 } |
185 } |
177 } |
186 } |
178 |
187 |
179 /// Erases a key from the map. |
188 /// Erases a key from the map. |
180 |
189 |
181 /** Erase a key from the map. It called by the map registry |
190 /// Erase a key from the map. It called by the observer registry |
182 * and it overrides the \ref MapRegistry::MapBase MapBase's |
191 /// and it overrides the erase() member function of the observer base. |
183 * erase() member function. |
|
184 */ |
|
185 void erase(const KeyType& key) {} |
192 void erase(const KeyType& key) {} |
186 |
193 |
187 /// Makes empty the map. |
194 /// Buildes the map. |
188 |
195 |
189 /** Makes empty the map. It called by the map registry |
196 /// It buildes the map. It called by the observer registry |
190 * and it overrides the \ref MapRegistry::MapBase MapBase's |
197 /// and it overrides the build() member function of the observer base. |
191 * clear() member function. |
198 |
192 */ |
199 void build() { |
193 |
200 container.resize(IdMap(*graph).maxId() + 1); |
|
201 } |
|
202 |
|
203 /// Clear the map. |
|
204 |
|
205 /// It erase all items from the map. It called by the observer registry |
|
206 /// and it overrides the clear() member function of the observer base. |
194 void clear() { |
207 void clear() { |
195 container.clear(); |
208 container.clear(); |
196 } |
209 } |
197 |
210 |
198 /// The stl compatible pair iterator of the map. |
|
199 typedef MapIterator<VectorMap> Iterator; |
|
200 /// The stl compatible const pair iterator of the map. |
|
201 typedef MapConstIterator<VectorMap> ConstIterator; |
|
202 |
|
203 /** Returns the begin iterator of the map. |
|
204 */ |
|
205 Iterator begin() { |
|
206 return Iterator(*this, KeyIt(*MapBase::getGraph())); |
|
207 } |
|
208 |
|
209 /** Returns the end iterator of the map. |
|
210 */ |
|
211 Iterator end() { |
|
212 return Iterator(*this, INVALID); |
|
213 } |
|
214 |
|
215 /** Returns the begin ConstIterator of the map. |
|
216 */ |
|
217 ConstIterator begin() const { |
|
218 return ConstIterator(*this, KeyIt(*MapBase::getGraph())); |
|
219 } |
|
220 |
|
221 /** Returns the end const_iterator of the map. |
|
222 */ |
|
223 ConstIterator end() const { |
|
224 return ConstIterator(*this, INVALID); |
|
225 } |
|
226 |
|
227 /// The KeySet of the Map. |
|
228 typedef MapConstKeySet<VectorMap> ConstKeySet; |
|
229 |
|
230 /// KeySet getter function. |
|
231 ConstKeySet keySet() const { |
|
232 return ConstKeySet(*this); |
|
233 } |
|
234 |
|
235 /// The ConstValueSet of the Map. |
|
236 typedef MapConstValueSet<VectorMap> ConstValueSet; |
|
237 |
|
238 /// ConstValueSet getter function. |
|
239 ConstValueSet valueSet() const { |
|
240 return ConstValueSet(*this); |
|
241 } |
|
242 |
|
243 /// The ValueSet of the Map. |
|
244 typedef MapValueSet<VectorMap> ValueSet; |
|
245 |
|
246 /// ValueSet getter function. |
|
247 ValueSet valueSet() { |
|
248 return ValueSet(*this); |
|
249 } |
|
250 |
|
251 |
|
252 private: |
211 private: |
253 |
212 |
254 Container container; |
213 Container container; |
255 |
214 const Graph *graph; |
|
215 |
|
216 }; |
|
217 |
|
218 |
|
219 template <typename _Base> |
|
220 class VectorMappableGraphExtender : public _Base { |
256 public: |
221 public: |
257 // STL compatibility typedefs. |
222 |
258 typedef Iterator iterator; |
223 typedef VectorMappableGraphExtender<_Base> Graph; |
259 typedef ConstIterator const_iterator; |
224 typedef _Base Parent; |
260 typedef typename Iterator::PairValueType value_type; |
225 |
261 typedef typename Iterator::KeyType key_type; |
226 typedef typename Parent::Node Node; |
262 typedef typename Iterator::ValueType data_type; |
227 typedef typename Parent::NodeIt NodeIt; |
263 typedef typename Iterator::PairReferenceType reference; |
228 typedef typename Parent::NodeIdMap NodeIdMap; |
264 typedef typename Iterator::PairPointerType pointer; |
229 typedef typename Parent::NodeObserverRegistry NodeObserverRegistry; |
265 typedef typename ConstIterator::PairReferenceType const_reference; |
230 |
266 typedef typename ConstIterator::PairPointerType const_pointer; |
231 typedef typename Parent::Edge Edge; |
267 typedef int difference_type; |
232 typedef typename Parent::EdgeIt EdgeIt; |
|
233 typedef typename Parent::EdgeIdMap EdgeIdMap; |
|
234 typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry; |
|
235 |
|
236 |
|
237 |
|
238 template <typename _Value> |
|
239 class NodeMap : public VectorMap<Graph, Node, NodeIdMap, _Value> { |
|
240 public: |
|
241 typedef VectorMappableGraphExtender<_Base> Graph; |
|
242 |
|
243 typedef typename Graph::Node Node; |
|
244 typedef typename Graph::NodeIdMap NodeIdMap; |
|
245 |
|
246 typedef VectorMap<Graph, Node, NodeIdMap, _Value> Parent; |
|
247 |
|
248 typedef typename Parent::Graph Graph; |
|
249 typedef typename Parent::Value Value; |
|
250 |
|
251 NodeMap(const Graph& g) |
|
252 : Parent(g, g.getNodeObserverRegistry()) {} |
|
253 NodeMap(const Graph& g, const Value& v) |
|
254 : Parent(g, g.getNodeObserverRegistry(), v) {} |
|
255 |
|
256 }; |
|
257 |
|
258 template <typename _Value> |
|
259 class EdgeMap : public VectorMap<Graph, Edge, EdgeIdMap, _Value> { |
|
260 public: |
|
261 typedef VectorMappableGraphExtender<_Base> Graph; |
|
262 |
|
263 typedef typename Graph::Edge Edge; |
|
264 typedef typename Graph::EdgeIdMap EdgeIdMap; |
|
265 |
|
266 typedef VectorMap<Graph, Edge, EdgeIdMap, _Value> Parent; |
|
267 |
|
268 typedef typename Parent::Graph Graph; |
|
269 typedef typename Parent::Value Value; |
|
270 |
|
271 EdgeMap(const Graph& g) |
|
272 : Parent(g, g.getEdgeObserverRegistry()) {} |
|
273 EdgeMap(const Graph& g, const Value& v) |
|
274 : Parent(g, g.getEdgeObserverRegistry(), v) {} |
|
275 |
|
276 }; |
|
277 |
268 }; |
278 }; |
269 |
279 |
270 /// @} |
280 /// @} |
271 |
281 |
272 } |
282 } |