1.1 --- a/src/lemon/bits/vector_map.h Sat May 21 21:04:57 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,288 +0,0 @@
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 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