1.1 --- a/src/lemon/vector_map.h Mon Oct 25 13:29:46 2004 +0000
1.2 +++ b/src/lemon/vector_map.h Wed Oct 27 22:38:50 2004 +0000
1.3 @@ -18,9 +18,9 @@
1.4 #define LEMON_VECTOR_MAP_H
1.5
1.6 #include <vector>
1.7 +#include <algorithm>
1.8
1.9 -#include <lemon/map_iterator.h>
1.10 -#include <lemon/map_bits.h>
1.11 +#include <lemon/alteration_observer_registry.h>
1.12
1.13 ///\ingroup graphmaps
1.14 ///\file
1.15 @@ -31,34 +31,41 @@
1.16 /// \addtogroup graphmaps
1.17 /// @{
1.18
1.19 - /** The VectorMap template class is graph map structure what
1.20 - * automatically updates the map when a key is added to or erased from
1.21 - * the map. This map factory uses the allocators to implement
1.22 - * the container functionality. This map factory
1.23 - * uses the std::vector to implement the container function.
1.24 - *
1.25 - * \param MapRegistry The MapRegistry that the maps will belong to.
1.26 - * \param Value The value type of the map.
1.27 - *
1.28 - * \author Balazs Dezso
1.29 - */
1.30 -
1.31 - template <typename MapRegistry, typename Value>
1.32 - class VectorMap : public MapRegistry::MapBase {
1.33 - template <typename MR, typename T> friend class VectorMap;
1.34 + /// The VectorMap template class is graph map structure what
1.35 + /// automatically updates the map when a key is added to or erased from
1.36 + /// the map. This map factory uses the allocators to implement
1.37 + /// the container functionality. This map factory
1.38 + /// uses the std::vector to implement the container function.
1.39 + ///
1.40 + /// \param Registry The AlterationObserverRegistry that will notify this map.
1.41 + /// \param IdMap The IdMap type of the graph items.
1.42 + /// \param Value The value type of the map.
1.43 + ///
1.44 + /// \author Balazs Dezso
1.45 +
1.46 +
1.47 + template <typename _Graph,
1.48 + typename _Item,
1.49 + typename _IdMap,
1.50 + typename _Value>
1.51 + class VectorMap : public AlterationObserverRegistry<_Item>::ObserverBase {
1.52 public:
1.53
1.54 - /// The graph type of the maps.
1.55 - typedef typename MapRegistry::Graph Graph;
1.56 - /// The key type of the maps.
1.57 - typedef typename MapRegistry::KeyType KeyType;
1.58 - /// The iterator to iterate on the keys.
1.59 - typedef typename MapRegistry::KeyIt KeyIt;
1.60 + /// The graph type of the map.
1.61 + typedef _Graph Graph;
1.62 + /// The key type of the map.
1.63 + typedef _Item KeyType;
1.64 + /// The id map type of the map.
1.65 + typedef _IdMap IdMap;
1.66 + /// The registry type of the map.
1.67 + typedef AlterationObserverRegistry<_Item> Registry;
1.68 + /// The value type of the map.
1.69 + typedef _Value Value;
1.70
1.71 /// The map type.
1.72 typedef VectorMap Map;
1.73 - /// The MapBase of the Map which implements the core regisitry function.
1.74 - typedef typename MapRegistry::MapBase MapBase;
1.75 + /// The base class of the map.
1.76 + typedef typename Registry::ObserverBase Parent;
1.77
1.78 private:
1.79
1.80 @@ -67,7 +74,6 @@
1.81
1.82 public:
1.83
1.84 -
1.85 /// The value type of the map.
1.86 typedef Value ValueType;
1.87 /// The reference type of the map;
1.88 @@ -82,95 +88,98 @@
1.89 /// The pointer type of the map;
1.90 typedef typename Container::const_pointer ConstPointerType;
1.91
1.92 - /// Constructor to attach the new map into a registry.
1.93 + /// Constructor to attach the new map into the registry.
1.94
1.95 - /** Constructor to attach the new map into a registry.
1.96 - * It adds all the nodes or edges of the graph to the map.
1.97 - */
1.98 - VectorMap(const Graph& g, MapRegistry& r)
1.99 - : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1) {}
1.100 + /// It construates a map and attachs it into the registry.
1.101 + /// It adds all the items of the graph to the map.
1.102 +
1.103 + VectorMap(const Graph& _g, Registry& _r) : graph(&_g) {
1.104 + attach(_r);
1.105 + build();
1.106 + }
1.107
1.108 /// Constructor uses given value to initialize the map.
1.109
1.110 - /** Constructor uses given value to initialize the map.
1.111 - * It adds all the nodes or edges of the graph to the map.
1.112 - */
1.113 - VectorMap(const Graph& g, MapRegistry& r, const Value& v)
1.114 - : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1, v) {}
1.115 + /// It construates a map uses a given value to initialize the map.
1.116 + /// It adds all the items of the graph to the map.
1.117 +
1.118 + VectorMap(const Graph& g, Registry& r, const Value& v) : graph(&g) {
1.119 + attach(r);
1.120 + container.resize(IdMap(*graph).maxId() + 1, v);
1.121 + }
1.122
1.123 - /// Assign operator to copy a map of an other map type.
1.124 -
1.125 - /** Assign operator to copy a map of an other map type.
1.126 - * This map's value type must be assignable by the other
1.127 - * map type's value type.
1.128 - */
1.129 - template <typename TT>
1.130 - VectorMap(const VectorMap<MapRegistry, TT>& c)
1.131 - : MapBase(c), container(c.container.size()) {
1.132 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.133 - int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
1.134 - container[id] = c.container[id];
1.135 + VectorMap(const VectorMap& copy) : graph(copy.getGraph()) {
1.136 + if (copy.attached()) {
1.137 + attach(*copy.getRegistry());
1.138 + container = copy.container;
1.139 }
1.140 }
1.141
1.142 - /// Assign operator to copy a map of an other map type.
1.143
1.144 - /** Assign operator to copy a map of an other map type.
1.145 - * This map's value type must be assignable by the other
1.146 - * map type's value type.
1.147 + /** Assign operator to copy a map of the same map type.
1.148 */
1.149 - template <typename TT>
1.150 - VectorMap& operator=(const VectorMap<MapRegistry, TT>& c) {
1.151 - if (MapBase::getGraph() != c.getGraph()) {
1.152 - MapBase::operator=(c);
1.153 - container.resize(c.container.size());
1.154 + VectorMap& operator=(const VectorMap& copy) {
1.155 + if (© == this) return *this;
1.156 +
1.157 + if (graph != copy.graph) {
1.158 + if (attached()) {
1.159 + detach();
1.160 + }
1.161 + if (copy.attached()) {
1.162 + attach(*copy.getRegistry());
1.163 + }
1.164 }
1.165 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.166 - int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
1.167 - container[id] = c.container[id];
1.168 + container = copy.container;
1.169 +
1.170 + return *this;
1.171 + }
1.172 +
1.173 +
1.174 + virtual ~VectorMap() {
1.175 + if (attached()) {
1.176 + detach();
1.177 }
1.178 - return *this;
1.179 + }
1.180 +
1.181 + const Graph* getGraph() const {
1.182 + return graph;
1.183 }
1.184
1.185 /// The subcript operator.
1.186
1.187 - /**
1.188 - * The subscript operator. The map can be subscripted by the
1.189 - * actual keys of the graph.
1.190 - */
1.191 + /// The subscript operator. The map can be subscripted by the
1.192 + /// actual items of the graph.
1.193 +
1.194 ReferenceType operator[](const KeyType& key) {
1.195 - int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
1.196 - return container[id];
1.197 + return container[IdMap(*graph)[key]];
1.198 }
1.199
1.200 /// The const subcript operator.
1.201
1.202 - /**
1.203 - * The const subscript operator. The map can be subscripted by the
1.204 - * actual keys of the graph.
1.205 - */
1.206 + /// The const subscript operator. The map can be subscripted by the
1.207 + /// actual items of the graph.
1.208 +
1.209 ConstReferenceType operator[](const KeyType& key) const {
1.210 - int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
1.211 - return container[id];
1.212 + return container[IdMap(*graph)[key]];
1.213 }
1.214
1.215 - ///Setter function of the map.
1.216
1.217 - /** Setter function of the map. Equivalent with map[key] = val.
1.218 - * This is a compatibility feature with the not dereferable maps.
1.219 - */
1.220 - void set(const KeyType& key, const ValueType& val) {
1.221 - int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
1.222 - container[id] = val;
1.223 + /// The setter function of the map.
1.224 +
1.225 + /// It the same as operator[](key) = value expression.
1.226 + ///
1.227 +
1.228 + void set(const KeyType& key, const ValueType& value) {
1.229 + (*this)[key] = value;
1.230 }
1.231 +
1.232 /// Adds a new key to the map.
1.233
1.234 - /** Adds a new key to the map. It called by the map registry
1.235 - * and it overrides the \ref MapRegistry::MapBase MapBase's
1.236 - * add() member function.
1.237 - */
1.238 + /// It adds a new key to the map. It called by the observer registry
1.239 + /// and it overrides the add() member function of the observer base.
1.240 +
1.241 void add(const KeyType& key) {
1.242 - int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
1.243 + int id = IdMap(*graph)[key];
1.244 if (id >= (int)container.size()) {
1.245 container.resize(id + 1);
1.246 }
1.247 @@ -178,93 +187,94 @@
1.248
1.249 /// Erases a key from the map.
1.250
1.251 - /** Erase a key from the map. It called by the map registry
1.252 - * and it overrides the \ref MapRegistry::MapBase MapBase's
1.253 - * erase() member function.
1.254 - */
1.255 + /// Erase a key from the map. It called by the observer registry
1.256 + /// and it overrides the erase() member function of the observer base.
1.257 void erase(const KeyType& key) {}
1.258
1.259 - /// Makes empty the map.
1.260 + /// Buildes the map.
1.261 +
1.262 + /// It buildes the map. It called by the observer registry
1.263 + /// and it overrides the build() member function of the observer base.
1.264
1.265 - /** Makes empty the map. It called by the map registry
1.266 - * and it overrides the \ref MapRegistry::MapBase MapBase's
1.267 - * clear() member function.
1.268 - */
1.269 + void build() {
1.270 + container.resize(IdMap(*graph).maxId() + 1);
1.271 + }
1.272
1.273 + /// Clear the map.
1.274 +
1.275 + /// It erase all items from the map. It called by the observer registry
1.276 + /// and it overrides the clear() member function of the observer base.
1.277 void clear() {
1.278 container.clear();
1.279 }
1.280
1.281 - /// The stl compatible pair iterator of the map.
1.282 - typedef MapIterator<VectorMap> Iterator;
1.283 - /// The stl compatible const pair iterator of the map.
1.284 - typedef MapConstIterator<VectorMap> ConstIterator;
1.285 -
1.286 - /** Returns the begin iterator of the map.
1.287 - */
1.288 - Iterator begin() {
1.289 - return Iterator(*this, KeyIt(*MapBase::getGraph()));
1.290 - }
1.291 -
1.292 - /** Returns the end iterator of the map.
1.293 - */
1.294 - Iterator end() {
1.295 - return Iterator(*this, INVALID);
1.296 - }
1.297 -
1.298 - /** Returns the begin ConstIterator of the map.
1.299 - */
1.300 - ConstIterator begin() const {
1.301 - return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
1.302 - }
1.303 -
1.304 - /** Returns the end const_iterator of the map.
1.305 - */
1.306 - ConstIterator end() const {
1.307 - return ConstIterator(*this, INVALID);
1.308 - }
1.309 -
1.310 - /// The KeySet of the Map.
1.311 - typedef MapConstKeySet<VectorMap> ConstKeySet;
1.312 -
1.313 - /// KeySet getter function.
1.314 - ConstKeySet keySet() const {
1.315 - return ConstKeySet(*this);
1.316 - }
1.317 -
1.318 - /// The ConstValueSet of the Map.
1.319 - typedef MapConstValueSet<VectorMap> ConstValueSet;
1.320 -
1.321 - /// ConstValueSet getter function.
1.322 - ConstValueSet valueSet() const {
1.323 - return ConstValueSet(*this);
1.324 - }
1.325 -
1.326 - /// The ValueSet of the Map.
1.327 - typedef MapValueSet<VectorMap> ValueSet;
1.328 -
1.329 - /// ValueSet getter function.
1.330 - ValueSet valueSet() {
1.331 - return ValueSet(*this);
1.332 - }
1.333 -
1.334 -
1.335 private:
1.336
1.337 Container container;
1.338 + const Graph *graph;
1.339
1.340 + };
1.341 +
1.342 +
1.343 + template <typename _Base>
1.344 + class VectorMappableGraphExtender : public _Base {
1.345 public:
1.346 - // STL compatibility typedefs.
1.347 - typedef Iterator iterator;
1.348 - typedef ConstIterator const_iterator;
1.349 - typedef typename Iterator::PairValueType value_type;
1.350 - typedef typename Iterator::KeyType key_type;
1.351 - typedef typename Iterator::ValueType data_type;
1.352 - typedef typename Iterator::PairReferenceType reference;
1.353 - typedef typename Iterator::PairPointerType pointer;
1.354 - typedef typename ConstIterator::PairReferenceType const_reference;
1.355 - typedef typename ConstIterator::PairPointerType const_pointer;
1.356 - typedef int difference_type;
1.357 +
1.358 + typedef VectorMappableGraphExtender<_Base> Graph;
1.359 + typedef _Base Parent;
1.360 +
1.361 + typedef typename Parent::Node Node;
1.362 + typedef typename Parent::NodeIt NodeIt;
1.363 + typedef typename Parent::NodeIdMap NodeIdMap;
1.364 + typedef typename Parent::NodeObserverRegistry NodeObserverRegistry;
1.365 +
1.366 + typedef typename Parent::Edge Edge;
1.367 + typedef typename Parent::EdgeIt EdgeIt;
1.368 + typedef typename Parent::EdgeIdMap EdgeIdMap;
1.369 + typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry;
1.370 +
1.371 +
1.372 +
1.373 + template <typename _Value>
1.374 + class NodeMap : public VectorMap<Graph, Node, NodeIdMap, _Value> {
1.375 + public:
1.376 + typedef VectorMappableGraphExtender<_Base> Graph;
1.377 +
1.378 + typedef typename Graph::Node Node;
1.379 + typedef typename Graph::NodeIdMap NodeIdMap;
1.380 +
1.381 + typedef VectorMap<Graph, Node, NodeIdMap, _Value> Parent;
1.382 +
1.383 + typedef typename Parent::Graph Graph;
1.384 + typedef typename Parent::Value Value;
1.385 +
1.386 + NodeMap(const Graph& g)
1.387 + : Parent(g, g.getNodeObserverRegistry()) {}
1.388 + NodeMap(const Graph& g, const Value& v)
1.389 + : Parent(g, g.getNodeObserverRegistry(), v) {}
1.390 +
1.391 + };
1.392 +
1.393 + template <typename _Value>
1.394 + class EdgeMap : public VectorMap<Graph, Edge, EdgeIdMap, _Value> {
1.395 + public:
1.396 + typedef VectorMappableGraphExtender<_Base> Graph;
1.397 +
1.398 + typedef typename Graph::Edge Edge;
1.399 + typedef typename Graph::EdgeIdMap EdgeIdMap;
1.400 +
1.401 + typedef VectorMap<Graph, Edge, EdgeIdMap, _Value> Parent;
1.402 +
1.403 + typedef typename Parent::Graph Graph;
1.404 + typedef typename Parent::Value Value;
1.405 +
1.406 + EdgeMap(const Graph& g)
1.407 + : Parent(g, g.getEdgeObserverRegistry()) {}
1.408 + EdgeMap(const Graph& g, const Value& v)
1.409 + : Parent(g, g.getEdgeObserverRegistry(), v) {}
1.410 +
1.411 + };
1.412 +
1.413 };
1.414
1.415 /// @}