1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/lemon/vector_map.h Wed Sep 29 15:30:04 2004 +0000
1.3 @@ -0,0 +1,243 @@
1.4 +/* -*- C++ -*-
1.5 + * src/lemon/vector_map.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2004 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 +
1.25 +#include <lemon/map_iterator.h>
1.26 +#include <lemon/map_bits.h>
1.27 +
1.28 +///\ingroup graphmaps
1.29 +///\file
1.30 +///\brief Vector based graph maps.
1.31 +
1.32 +namespace lemon {
1.33 +
1.34 + /// \addtogroup graphmaps
1.35 + /// @{
1.36 +
1.37 + /** The ArrayMap template class is graph map structure what
1.38 + * automatically updates the map when a key is added to or erased from
1.39 + * the map. This map factory uses the allocators to implement
1.40 + * the container functionality. This map factory
1.41 + * uses the std::vector to implement the container function.
1.42 + *
1.43 + * The template parameter is the MapRegistry that the maps
1.44 + * will belong to and the ValueType.
1.45 + *
1.46 + * \todo It should use a faster initialization using the maxNodeId() or
1.47 + * maxEdgeId() function of the graph instead of iterating through each
1.48 + * edge/node.
1.49 + */
1.50 +
1.51 + template <typename MapRegistry, typename Value>
1.52 + class VectorMap : public MapRegistry::MapBase {
1.53 + template <typename MR, typename T> friend class VectorMap;
1.54 + public:
1.55 +
1.56 + /// The graph type of the maps.
1.57 + typedef typename MapRegistry::Graph Graph;
1.58 + /// The key type of the maps.
1.59 + typedef typename MapRegistry::KeyType KeyType;
1.60 + /// The iterator to iterate on the keys.
1.61 + typedef typename MapRegistry::KeyIt KeyIt;
1.62 +
1.63 + /// The map type.
1.64 + typedef VectorMap Map;
1.65 + /// The MapBase of the Map which implements the core regisitry function.
1.66 + typedef typename MapRegistry::MapBase MapBase;
1.67 +
1.68 + private:
1.69 +
1.70 + /// The container type of the map.
1.71 + typedef std::vector<Value> Container;
1.72 +
1.73 + public:
1.74 +
1.75 +
1.76 + /// The value type of the map.
1.77 + typedef Value ValueType;
1.78 + /// The reference type of the map;
1.79 + typedef typename Container::reference ReferenceType;
1.80 + /// The pointer type of the map;
1.81 + typedef typename Container::pointer PointerType;
1.82 +
1.83 + /// The const value type of the map.
1.84 + typedef const Value ConstValueType;
1.85 + /// The const reference type of the map;
1.86 + typedef typename Container::const_reference ConstReferenceType;
1.87 + /// The pointer type of the map;
1.88 + typedef typename Container::const_pointer ConstPointerType;
1.89 +
1.90 + /** Graph and Registry initialized map constructor.
1.91 + */
1.92 + VectorMap(const Graph& g, MapRegistry& r)
1.93 + : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1) {}
1.94 +
1.95 + /** Constructor to use default value to initialize the map.
1.96 + */
1.97 + VectorMap(const Graph& g, MapRegistry& r, const Value& v)
1.98 + : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1, v) {}
1.99 +
1.100 + /** Assign operator to copy a map of an other map type.
1.101 + */
1.102 + template <typename TT>
1.103 + VectorMap(const VectorMap<MapRegistry, TT>& c)
1.104 + : MapBase(c), container(c.container.size()) {
1.105 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.106 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
1.107 + container[id] = c.container[id];
1.108 + }
1.109 + }
1.110 +
1.111 + /** Assign operator to copy a map of an other map type.
1.112 + */
1.113 + template <typename TT>
1.114 + VectorMap& operator=(const VectorMap<MapRegistry, TT>& c) {
1.115 + if (MapBase::getGraph() != c.getGraph()) {
1.116 + MapBase::operator=(c);
1.117 + container.resize(c.container.size());
1.118 + }
1.119 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.120 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
1.121 + container[id] = c.container[id];
1.122 + }
1.123 + return *this;
1.124 + }
1.125 + /**
1.126 + * The subscript operator. The map can be subscripted by the
1.127 + * actual keys of the graph.
1.128 + */
1.129 + ReferenceType operator[](const KeyType& key) {
1.130 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
1.131 + return container[id];
1.132 + }
1.133 +
1.134 + /**
1.135 + * The const subscript operator. The map can be subscripted by the
1.136 + * actual keys of the graph.
1.137 + */
1.138 + ConstReferenceType operator[](const KeyType& key) const {
1.139 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
1.140 + return container[id];
1.141 + }
1.142 +
1.143 + /** Setter function of the map. Equivalent with map[key] = val.
1.144 + * This is a compatibility feature with the not dereferable maps.
1.145 + */
1.146 + void set(const KeyType& key, const ValueType& val) {
1.147 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
1.148 + container[id] = val;
1.149 + }
1.150 +
1.151 + /** Add a new key to the map. It called by the map registry.
1.152 + */
1.153 + void add(const KeyType& key) {
1.154 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
1.155 + if (id >= (int)container.size()) {
1.156 + container.resize(id + 1);
1.157 + }
1.158 + }
1.159 +
1.160 + /** Erase a key from the map. It called by the map registry.
1.161 + */
1.162 + void erase(const KeyType& key) {}
1.163 +
1.164 + /** Clear the data structure.
1.165 + */
1.166 + void clear() {
1.167 + container.clear();
1.168 + }
1.169 +
1.170 + /// The stl compatible pair iterator of the map.
1.171 + typedef MapIterator<VectorMap> Iterator;
1.172 + /// The stl compatible const pair iterator of the map.
1.173 + typedef MapConstIterator<VectorMap> ConstIterator;
1.174 +
1.175 + /** Returns the begin iterator of the map.
1.176 + */
1.177 + Iterator begin() {
1.178 + return Iterator(*this, KeyIt(*MapBase::getGraph()));
1.179 + }
1.180 +
1.181 + /** Returns the end iterator of the map.
1.182 + */
1.183 + Iterator end() {
1.184 + return Iterator(*this, INVALID);
1.185 + }
1.186 +
1.187 + /** Returns the begin ConstIterator of the map.
1.188 + */
1.189 + ConstIterator begin() const {
1.190 + return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
1.191 + }
1.192 +
1.193 + /** Returns the end const_iterator of the map.
1.194 + */
1.195 + ConstIterator end() const {
1.196 + return ConstIterator(*this, INVALID);
1.197 + }
1.198 +
1.199 + /// The KeySet of the Map.
1.200 + typedef MapConstKeySet<VectorMap> ConstKeySet;
1.201 +
1.202 + /// KeySet getter function.
1.203 + ConstKeySet keySet() const {
1.204 + return ConstKeySet(*this);
1.205 + }
1.206 +
1.207 + /// The ConstValueSet of the Map.
1.208 + typedef MapConstValueSet<VectorMap> ConstValueSet;
1.209 +
1.210 + /// ConstValueSet getter function.
1.211 + ConstValueSet valueSet() const {
1.212 + return ConstValueSet(*this);
1.213 + }
1.214 +
1.215 + /// The ValueSet of the Map.
1.216 + typedef MapValueSet<VectorMap> ValueSet;
1.217 +
1.218 + /// ValueSet getter function.
1.219 + ValueSet valueSet() {
1.220 + return ValueSet(*this);
1.221 + }
1.222 +
1.223 +
1.224 + private:
1.225 +
1.226 + Container container;
1.227 +
1.228 + public:
1.229 + // STL compatibility typedefs.
1.230 + typedef Iterator iterator;
1.231 + typedef ConstIterator const_iterator;
1.232 + typedef typename Iterator::PairValueType value_type;
1.233 + typedef typename Iterator::KeyType key_type;
1.234 + typedef typename Iterator::ValueType data_type;
1.235 + typedef typename Iterator::PairReferenceType reference;
1.236 + typedef typename Iterator::PairPointerType pointer;
1.237 + typedef typename ConstIterator::PairReferenceType const_reference;
1.238 + typedef typename ConstIterator::PairPointerType const_pointer;
1.239 + typedef int difference_type;
1.240 + };
1.241 +
1.242 + /// @}
1.243 +
1.244 +}
1.245 +
1.246 +#endif