1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/lemon/bits/vector_map.h Tue Apr 05 12:30:46 2005 +0000
1.3 @@ -0,0 +1,287 @@
1.4 +/* -*- C++ -*-
1.5 + * src/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 Combinatorial Optimization Research Group, 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) : graph(_copy.getGraph()) {
1.116 + if (_copy.attached()) {
1.117 + attach(*_copy.getRegistry());
1.118 + container = _copy.container;
1.119 + }
1.120 + }
1.121 +
1.122 + using Parent::attach;
1.123 + using Parent::detach;
1.124 + using Parent::attached;
1.125 +
1.126 + /** Assign operator to copy a map of the same map type.
1.127 + */
1.128 + VectorMap& operator=(const VectorMap& copy) {
1.129 + if (© == this) return *this;
1.130 +
1.131 + if (graph != copy.graph) {
1.132 + if (attached()) {
1.133 + detach();
1.134 + }
1.135 + if (copy.attached()) {
1.136 + attach(*copy.getRegistry());
1.137 + }
1.138 + }
1.139 + container = copy.container;
1.140 +
1.141 + return *this;
1.142 + }
1.143 +
1.144 +
1.145 + virtual ~VectorMap() {
1.146 + if (attached()) {
1.147 + detach();
1.148 + }
1.149 + }
1.150 +
1.151 + const Graph* getGraph() const {
1.152 + return graph;
1.153 + }
1.154 +
1.155 + /// The subcript operator.
1.156 +
1.157 + /// The subscript operator. The map can be subscripted by the
1.158 + /// actual items of the graph.
1.159 +
1.160 + Reference operator[](const Key& key) {
1.161 + return container[graph->id(key)];
1.162 + }
1.163 +
1.164 + /// The const subcript operator.
1.165 +
1.166 + /// The const subscript operator. The map can be subscripted by the
1.167 + /// actual items of the graph.
1.168 +
1.169 + ConstReference operator[](const Key& key) const {
1.170 + return container[graph->id(key)];
1.171 + }
1.172 +
1.173 +
1.174 + /// The setter function of the map.
1.175 +
1.176 + /// It the same as operator[](key) = value expression.
1.177 + ///
1.178 +
1.179 + void set(const Key& key, const Value& value) {
1.180 + (*this)[key] = value;
1.181 + }
1.182 +
1.183 + /// Adds a new key to the map.
1.184 +
1.185 + /// It adds a new key to the map. It called by the observer registry
1.186 + /// and it overrides the add() member function of the observer base.
1.187 +
1.188 + void add(const Key& key) {
1.189 + int id = graph->id(key);
1.190 + if (id >= (int)container.size()) {
1.191 + container.resize(id + 1);
1.192 + }
1.193 + }
1.194 +
1.195 + /// Erases a key from the map.
1.196 +
1.197 + /// Erase a key from the map. It called by the observer registry
1.198 + /// and it overrides the erase() member function of the observer base.
1.199 + void erase(const Key&) {}
1.200 +
1.201 + /// Buildes the map.
1.202 +
1.203 + /// It buildes the map. It called by the observer registry
1.204 + /// and it overrides the build() member function of the observer base.
1.205 +
1.206 + void build() {
1.207 + container.resize(graph->maxId(_Item()) + 1);
1.208 + }
1.209 +
1.210 + /// Clear the map.
1.211 +
1.212 + /// It erase all items from the map. It called by the observer registry
1.213 + /// and it overrides the clear() member function of the observer base.
1.214 + void clear() {
1.215 + container.clear();
1.216 + }
1.217 +
1.218 + private:
1.219 +
1.220 + Container container;
1.221 + const Graph *graph;
1.222 +
1.223 + };
1.224 +
1.225 +
1.226 + template <typename _Base>
1.227 + class VectorMappableGraphExtender : public _Base {
1.228 + public:
1.229 +
1.230 + typedef VectorMappableGraphExtender<_Base> Graph;
1.231 + typedef _Base Parent;
1.232 +
1.233 + typedef typename Parent::Node Node;
1.234 + typedef typename Parent::NodeIt NodeIt;
1.235 + typedef typename Parent::NodeIdMap NodeIdMap;
1.236 + typedef typename Parent::NodeNotifier NodeObserverRegistry;
1.237 +
1.238 + typedef typename Parent::Edge Edge;
1.239 + typedef typename Parent::EdgeIt EdgeIt;
1.240 + typedef typename Parent::EdgeIdMap EdgeIdMap;
1.241 + typedef typename Parent::EdgeNotifier EdgeObserverRegistry;
1.242 +
1.243 +
1.244 + template <typename _Value>
1.245 + class NodeMap :
1.246 + public IterableMapExtender<VectorMap<Graph, Node, _Value> > {
1.247 + public:
1.248 + typedef VectorMappableGraphExtender<_Base> Graph;
1.249 +
1.250 + typedef typename Graph::Node Node;
1.251 +
1.252 + typedef IterableMapExtender<VectorMap<Graph, Node, _Value> > Parent;
1.253 +
1.254 + //typedef typename Parent::Graph Graph;
1.255 + typedef typename Parent::Value Value;
1.256 +
1.257 + NodeMap(const Graph& g)
1.258 + : Parent(g) {}
1.259 + NodeMap(const Graph& g, const Value& v)
1.260 + : Parent(g, v) {}
1.261 +
1.262 + };
1.263 +
1.264 + template <typename _Value>
1.265 + class EdgeMap
1.266 + : public IterableMapExtender<VectorMap<Graph, Edge, _Value> > {
1.267 + public:
1.268 + typedef VectorMappableGraphExtender<_Base> Graph;
1.269 +
1.270 + typedef typename Graph::Edge Edge;
1.271 +
1.272 + typedef IterableMapExtender<VectorMap<Graph, Edge, _Value> > Parent;
1.273 +
1.274 + //typedef typename Parent::Graph Graph;
1.275 + typedef typename Parent::Value Value;
1.276 +
1.277 + EdgeMap(const Graph& g)
1.278 + : Parent(g) {}
1.279 + EdgeMap(const Graph& g, const Value& v)
1.280 + : Parent(g, v) {}
1.281 +
1.282 + };
1.283 +
1.284 + };
1.285 +
1.286 + /// @}
1.287 +
1.288 +}
1.289 +
1.290 +#endif