1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/bits/vector_map.h Mon May 23 04:48:14 2005 +0000
1.3 @@ -0,0 +1,288 @@
1.4 +/* -*- C++ -*-
1.5 + * lemon/vector_map.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +
1.20 +#ifndef LEMON_VECTOR_MAP_H
1.21 +#define LEMON_VECTOR_MAP_H
1.22 +
1.23 +#include <vector>
1.24 +#include <algorithm>
1.25 +
1.26 +#include <lemon/utility.h>
1.27 +#include <lemon/bits/map_iterator.h>
1.28 +#include <lemon/bits/alteration_notifier.h>
1.29 +
1.30 +///\ingroup graphmaps
1.31 +///\file
1.32 +///\brief Vector based graph maps.
1.33 +
1.34 +namespace lemon {
1.35 +
1.36 + /// \addtogroup graphmaps
1.37 + /// @{
1.38 +
1.39 + /// The VectorMap template class is graph map structure what
1.40 + /// automatically updates the map when a key is added to or erased from
1.41 + /// the map. This map factory uses the allocators to implement
1.42 + /// the container functionality. This map factory
1.43 + /// uses the std::vector to implement the container function.
1.44 + ///
1.45 + /// \param Registry The AlterationNotifier that will notify this map.
1.46 + /// \param IdMap The IdMap type of the graph items.
1.47 + /// \param Value The value type of the map.
1.48 + ///
1.49 + /// \author Balazs Dezso
1.50 +
1.51 +
1.52 + template <
1.53 + typename _Graph,
1.54 + typename _Item,
1.55 + typename _Value
1.56 + >
1.57 + class VectorMap : public AlterationNotifier<_Item>::ObserverBase {
1.58 + public:
1.59 +
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 Key;
1.64 + /// The id map type of the map.
1.65 + typedef AlterationNotifier<_Item> Registry;
1.66 + /// The value type of the map.
1.67 + typedef _Value Value;
1.68 +
1.69 + /// The map type.
1.70 + typedef VectorMap Map;
1.71 + /// The base class of the map.
1.72 + typedef typename Registry::ObserverBase Parent;
1.73 +
1.74 + private:
1.75 +
1.76 + /// The container type of the map.
1.77 + typedef std::vector<Value> Container;
1.78 +
1.79 + public:
1.80 +
1.81 + /// The reference type of the map;
1.82 + typedef typename Container::reference Reference;
1.83 + /// The pointer type of the map;
1.84 + typedef typename Container::pointer Pointer;
1.85 +
1.86 + /// The const value type of the map.
1.87 + typedef const Value ConstValue;
1.88 + /// The const reference type of the map;
1.89 + typedef typename Container::const_reference ConstReference;
1.90 + /// The pointer type of the map;
1.91 + typedef typename Container::const_pointer ConstPointer;
1.92 +
1.93 + typedef True FullTypeTag;
1.94 +
1.95 + /// Constructor to attach the new map into the registry.
1.96 +
1.97 + /// It construates a map and attachs it into the registry.
1.98 + /// It adds all the items of the graph to the map.
1.99 +
1.100 + VectorMap(const Graph& _g) : graph(&_g) {
1.101 + attach(_g.getNotifier(_Item()));
1.102 + build();
1.103 + }
1.104 +
1.105 + /// Constructor uses given value to initialize the map.
1.106 +
1.107 + /// It construates a map uses a given value to initialize the map.
1.108 + /// It adds all the items of the graph to the map.
1.109 +
1.110 + VectorMap(const Graph& _g, const Value& _v) : graph(&_g) {
1.111 + attach(_g.getNotifier(_Item()));
1.112 + container.resize(graph->maxId(_Item()) + 1, _v);
1.113 + }
1.114 +
1.115 + VectorMap(const VectorMap& _copy)
1.116 + : Parent(), graph(_copy.getGraph()) {
1.117 + if (_copy.attached()) {
1.118 + attach(*_copy.getRegistry());
1.119 + container = _copy.container;
1.120 + }
1.121 + }
1.122 +
1.123 + using Parent::attach;
1.124 + using Parent::detach;
1.125 + using Parent::attached;
1.126 +
1.127 + /** Assign operator to copy a map of the same map type.
1.128 + */
1.129 + VectorMap& operator=(const VectorMap& copy) {
1.130 + if (© == this) return *this;
1.131 +
1.132 + if (graph != copy.graph) {
1.133 + if (attached()) {
1.134 + detach();
1.135 + }
1.136 + if (copy.attached()) {
1.137 + attach(*copy.getRegistry());
1.138 + }
1.139 + }
1.140 + container = copy.container;
1.141 +
1.142 + return *this;
1.143 + }
1.144 +
1.145 +
1.146 + virtual ~VectorMap() {
1.147 + if (attached()) {
1.148 + detach();
1.149 + }
1.150 + }
1.151 +
1.152 + const Graph* getGraph() const {
1.153 + return graph;
1.154 + }
1.155 +
1.156 + /// The subcript operator.
1.157 +
1.158 + /// The subscript operator. The map can be subscripted by the
1.159 + /// actual items of the graph.
1.160 +
1.161 + Reference operator[](const Key& key) {
1.162 + return container[graph->id(key)];
1.163 + }
1.164 +
1.165 + /// The const subcript operator.
1.166 +
1.167 + /// The const subscript operator. The map can be subscripted by the
1.168 + /// actual items of the graph.
1.169 +
1.170 + ConstReference operator[](const Key& key) const {
1.171 + return container[graph->id(key)];
1.172 + }
1.173 +
1.174 +
1.175 + /// The setter function of the map.
1.176 +
1.177 + /// It the same as operator[](key) = value expression.
1.178 + ///
1.179 +
1.180 + void set(const Key& key, const Value& value) {
1.181 + (*this)[key] = value;
1.182 + }
1.183 +
1.184 + /// Adds a new key to the map.
1.185 +
1.186 + /// It adds a new key to the map. It called by the observer registry
1.187 + /// and it overrides the add() member function of the observer base.
1.188 +
1.189 + void add(const Key& key) {
1.190 + int id = graph->id(key);
1.191 + if (id >= (int)container.size()) {
1.192 + container.resize(id + 1);
1.193 + }
1.194 + }
1.195 +
1.196 + /// Erases a key from the map.
1.197 +
1.198 + /// Erase a key from the map. It called by the observer registry
1.199 + /// and it overrides the erase() member function of the observer base.
1.200 + void erase(const Key&) {}
1.201 +
1.202 + /// Buildes the map.
1.203 +
1.204 + /// It buildes the map. It called by the observer registry
1.205 + /// and it overrides the build() member function of the observer base.
1.206 +
1.207 + void build() {
1.208 + container.resize(graph->maxId(_Item()) + 1);
1.209 + }
1.210 +
1.211 + /// Clear the map.
1.212 +
1.213 + /// It erase all items from the map. It called by the observer registry
1.214 + /// and it overrides the clear() member function of the observer base.
1.215 + void clear() {
1.216 + container.clear();
1.217 + }
1.218 +
1.219 + private:
1.220 +
1.221 + Container container;
1.222 + const Graph *graph;
1.223 +
1.224 + };
1.225 +
1.226 +
1.227 + template <typename _Base>
1.228 + class VectorMappableGraphExtender : public _Base {
1.229 + public:
1.230 +
1.231 + typedef VectorMappableGraphExtender<_Base> Graph;
1.232 + typedef _Base Parent;
1.233 +
1.234 + typedef typename Parent::Node Node;
1.235 + typedef typename Parent::NodeIt NodeIt;
1.236 + typedef typename Parent::NodeIdMap NodeIdMap;
1.237 + typedef typename Parent::NodeNotifier NodeObserverRegistry;
1.238 +
1.239 + typedef typename Parent::Edge Edge;
1.240 + typedef typename Parent::EdgeIt EdgeIt;
1.241 + typedef typename Parent::EdgeIdMap EdgeIdMap;
1.242 + typedef typename Parent::EdgeNotifier EdgeObserverRegistry;
1.243 +
1.244 +
1.245 + template <typename _Value>
1.246 + class NodeMap :
1.247 + public IterableMapExtender<VectorMap<Graph, Node, _Value> > {
1.248 + public:
1.249 + typedef VectorMappableGraphExtender<_Base> Graph;
1.250 +
1.251 + typedef typename Graph::Node Node;
1.252 +
1.253 + typedef IterableMapExtender<VectorMap<Graph, Node, _Value> > Parent;
1.254 +
1.255 + //typedef typename Parent::Graph Graph;
1.256 + typedef typename Parent::Value Value;
1.257 +
1.258 + NodeMap(const Graph& g)
1.259 + : Parent(g) {}
1.260 + NodeMap(const Graph& g, const Value& v)
1.261 + : Parent(g, v) {}
1.262 +
1.263 + };
1.264 +
1.265 + template <typename _Value>
1.266 + class EdgeMap
1.267 + : public IterableMapExtender<VectorMap<Graph, Edge, _Value> > {
1.268 + public:
1.269 + typedef VectorMappableGraphExtender<_Base> Graph;
1.270 +
1.271 + typedef typename Graph::Edge Edge;
1.272 +
1.273 + typedef IterableMapExtender<VectorMap<Graph, Edge, _Value> > Parent;
1.274 +
1.275 + //typedef typename Parent::Graph Graph;
1.276 + typedef typename Parent::Value Value;
1.277 +
1.278 + EdgeMap(const Graph& g)
1.279 + : Parent(g) {}
1.280 + EdgeMap(const Graph& g, const Value& v)
1.281 + : Parent(g, v) {}
1.282 +
1.283 + };
1.284 +
1.285 + };
1.286 +
1.287 + /// @}
1.288 +
1.289 +}
1.290 +
1.291 +#endif