29 namespace lemon { |
29 namespace lemon { |
30 |
30 |
31 /// \addtogroup graphmaps |
31 /// \addtogroup graphmaps |
32 /// @{ |
32 /// @{ |
33 |
33 |
34 /** The ArrayMap 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 * The template parameter is the MapRegistry that the maps |
40 * \param MapRegistry The MapRegistry that the maps will belong to. |
41 * will belong to and the ValueType. |
41 * \param Value The value type of the map. |
42 * |
42 * |
43 * \todo It should use a faster initialization using the maxNodeId() or |
43 * \author Balazs Dezso |
44 * maxEdgeId() function of the graph instead of iterating through each |
|
45 * edge/node. |
|
46 */ |
44 */ |
47 |
45 |
48 template <typename MapRegistry, typename Value> |
46 template <typename MapRegistry, typename Value> |
49 class VectorMap : public MapRegistry::MapBase { |
47 class VectorMap : public MapRegistry::MapBase { |
50 template <typename MR, typename T> friend class VectorMap; |
48 template <typename MR, typename T> friend class VectorMap; |
82 /// The const reference type of the map; |
80 /// The const reference type of the map; |
83 typedef typename Container::const_reference ConstReferenceType; |
81 typedef typename Container::const_reference ConstReferenceType; |
84 /// The pointer type of the map; |
82 /// The pointer type of the map; |
85 typedef typename Container::const_pointer ConstPointerType; |
83 typedef typename Container::const_pointer ConstPointerType; |
86 |
84 |
87 /** Graph and Registry initialized map constructor. |
85 /// Constructor to attach the new map into a registry. |
|
86 |
|
87 /** Constructor to attach the new map into a registry. |
|
88 * It adds all the nodes or edges of the graph to the map. |
88 */ |
89 */ |
89 VectorMap(const Graph& g, MapRegistry& r) |
90 VectorMap(const Graph& g, MapRegistry& r) |
90 : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1) {} |
91 : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1) {} |
91 |
92 |
92 /** Constructor to use default value to initialize the map. |
93 /// Constructor uses given value to initialize the map. |
|
94 |
|
95 /** Constructor uses given value to initialize the map. |
|
96 * It adds all the nodes or edges of the graph to the map. |
93 */ |
97 */ |
94 VectorMap(const Graph& g, MapRegistry& r, const Value& v) |
98 VectorMap(const Graph& g, MapRegistry& r, const Value& v) |
95 : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1, v) {} |
99 : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1, v) {} |
96 |
100 |
|
101 /// Assign operator to copy a map of an other map type. |
|
102 |
97 /** Assign operator to copy a map of an other map type. |
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. |
98 */ |
106 */ |
99 template <typename TT> |
107 template <typename TT> |
100 VectorMap(const VectorMap<MapRegistry, TT>& c) |
108 VectorMap(const VectorMap<MapRegistry, TT>& c) |
101 : MapBase(c), container(c.container.size()) { |
109 : MapBase(c), container(c.container.size()) { |
102 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { |
110 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { |
103 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it); |
111 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it); |
104 container[id] = c.container[id]; |
112 container[id] = c.container[id]; |
105 } |
113 } |
106 } |
114 } |
107 |
115 |
|
116 /// Assign operator to copy a map of an other map type. |
|
117 |
108 /** Assign operator to copy a map of an other map type. |
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. |
109 */ |
121 */ |
110 template <typename TT> |
122 template <typename TT> |
111 VectorMap& operator=(const VectorMap<MapRegistry, TT>& c) { |
123 VectorMap& operator=(const VectorMap<MapRegistry, TT>& c) { |
112 if (MapBase::getGraph() != c.getGraph()) { |
124 if (MapBase::getGraph() != c.getGraph()) { |
113 MapBase::operator=(c); |
125 MapBase::operator=(c); |
117 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it); |
129 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it); |
118 container[id] = c.container[id]; |
130 container[id] = c.container[id]; |
119 } |
131 } |
120 return *this; |
132 return *this; |
121 } |
133 } |
|
134 |
|
135 /// The subcript operator. |
|
136 |
122 /** |
137 /** |
123 * The subscript operator. The map can be subscripted by the |
138 * The subscript operator. The map can be subscripted by the |
124 * actual keys of the graph. |
139 * actual keys of the graph. |
125 */ |
140 */ |
126 ReferenceType operator[](const KeyType& key) { |
141 ReferenceType operator[](const KeyType& key) { |
127 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key); |
142 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key); |
128 return container[id]; |
143 return container[id]; |
129 } |
144 } |
130 |
145 |
|
146 /// The const subcript operator. |
|
147 |
131 /** |
148 /** |
132 * The const subscript operator. The map can be subscripted by the |
149 * The const subscript operator. The map can be subscripted by the |
133 * actual keys of the graph. |
150 * actual keys of the graph. |
134 */ |
151 */ |
135 ConstReferenceType operator[](const KeyType& key) const { |
152 ConstReferenceType operator[](const KeyType& key) const { |
136 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key); |
153 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key); |
137 return container[id]; |
154 return container[id]; |
138 } |
155 } |
139 |
156 |
|
157 ///Setter function of the map. |
|
158 |
140 /** Setter function of the map. Equivalent with map[key] = val. |
159 /** Setter function of the map. Equivalent with map[key] = val. |
141 * This is a compatibility feature with the not dereferable maps. |
160 * This is a compatibility feature with the not dereferable maps. |
142 */ |
161 */ |
143 void set(const KeyType& key, const ValueType& val) { |
162 void set(const KeyType& key, const ValueType& val) { |
144 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key); |
163 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key); |
145 container[id] = val; |
164 container[id] = val; |
146 } |
165 } |
147 |
166 /// Adds a new key to the map. |
148 /** Add a new key to the map. It called by the map registry. |
167 |
|
168 /** Adds a new key to the map. It called by the map registry |
|
169 * and it overrides the \ref MapRegistry::MapBase MapBase's |
|
170 * add() member function. |
149 */ |
171 */ |
150 void add(const KeyType& key) { |
172 void add(const KeyType& key) { |
151 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key); |
173 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key); |
152 if (id >= (int)container.size()) { |
174 if (id >= (int)container.size()) { |
153 container.resize(id + 1); |
175 container.resize(id + 1); |
154 } |
176 } |
155 } |
177 } |
156 |
178 |
157 /** Erase a key from the map. It called by the map registry. |
179 /// Erases a key from the map. |
|
180 |
|
181 /** Erase a key from the map. It called by the map registry |
|
182 * and it overrides the \ref MapRegistry::MapBase MapBase's |
|
183 * erase() member function. |
158 */ |
184 */ |
159 void erase(const KeyType& key) {} |
185 void erase(const KeyType& key) {} |
160 |
186 |
161 /** Clear the data structure. |
187 /// Makes empty the map. |
162 */ |
188 |
|
189 /** Makes empty the map. It called by the map registry |
|
190 * and it overrides the \ref MapRegistry::MapBase MapBase's |
|
191 * clear() member function. |
|
192 */ |
|
193 |
163 void clear() { |
194 void clear() { |
164 container.clear(); |
195 container.clear(); |
165 } |
196 } |
166 |
197 |
167 /// The stl compatible pair iterator of the map. |
198 /// The stl compatible pair iterator of the map. |