COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/vector_map.h @ 873:f3a30fda2e49

Last change on this file since 873:f3a30fda2e49 was 844:9bf990cb066d, checked in by Balazs Dezso, 20 years ago

Bug fix in the symmetric maps.
Faster map initialization.
Iterators and Containers STL compatible.

File size: 6.6 KB
Line 
1// -*- c++ -*-
2#ifndef VECTOR_MAP_H
3#define VECTOR_MAP_H
4
5#include <vector>
6
7#include <hugo/map_iterator.h>
8#include <hugo/map_bits.h>
9
10///\ingroup graphmaps
11///\file
12///\brief Vector based graph maps.
13
14namespace hugo {
15 
16  /// \addtogroup graphmaps
17  /// @{
18 
19  /** The ArrayMap template class is graph map structure what
20   *  automatically updates the map when a key is added to or erased from
21   *  the map. This map factory uses the allocators to implement
22   *  the container functionality. This map factory
23   *  uses the std::vector to implement the container function.
24   *
25   *  The template parameter is the MapRegistry that the maps
26   *  will belong to and the ValueType.
27   *
28   * \todo It should use a faster initialization using the maxNodeId() or
29   * maxEdgeId() function of the graph instead of iterating through each
30   * edge/node.
31   */
32       
33  template <typename MapRegistry, typename Value>
34  class VectorMap : public MapRegistry::MapBase {
35  public:
36               
37    /// The graph type of the maps.
38    typedef typename MapRegistry::Graph Graph;
39    /// The key type of the maps.
40    typedef typename MapRegistry::KeyType KeyType;
41    /// The iterator to iterate on the keys.
42    typedef typename MapRegistry::KeyIt KeyIt;
43
44    /// The map type.
45    typedef VectorMap Map;
46    /// The MapBase of the Map which implements the core regisitry function.
47    typedef typename MapRegistry::MapBase MapBase;
48
49  private:
50               
51    /// The container type of the map.
52    typedef std::vector<Value> Container;       
53
54  public:
55
56
57    /// The value type of the map.
58    typedef Value ValueType;
59    /// The reference type of the map;
60    typedef typename Container::reference ReferenceType;
61    /// The pointer type of the map;
62    typedef typename Container::pointer PointerType;
63
64    /// The const value type of the map.
65    typedef const Value ConstValueType;
66    /// The const reference type of the map;
67    typedef typename Container::const_reference ConstReferenceType;
68    /// The pointer type of the map;
69    typedef typename Container::const_pointer ConstPointerType;
70
71    /** Default constructor for the map.
72     */
73    VectorMap() {}
74               
75    /** Graph and Registry initialized map constructor.
76     */
77    VectorMap(const Graph& g, MapRegistry& r)
78      : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1) {}
79
80    /** Constructor to use default value to initialize the map.
81     */
82    VectorMap(const Graph& g, MapRegistry& r, const Value& v)
83      : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1, v) {}
84
85    /** Constructor to copy a map of an other map type.
86     */
87    template <typename CMap> VectorMap(const CMap& copy) : MapBase(copy) {
88      if (MapBase::getGraph()) {
89        container.resize(KeyInfo<Graph, KeyIt>::maxId(*MapBase::getGraph())+1);
90        for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
91          set(it, copy[it]);
92        }
93      }
94    }
95
96    /** Assign operator to copy a map an other map type.
97     */
98    template <typename CMap> VectorMap& operator=(const CMap& copy) {
99      container.clear();
100      this->MapBase::operator=(copy);
101      if (MapBase::getGraph()) {
102        container.resize(KeyInfo<Graph, KeyIt>::maxId(*MapBase::getGraph())+1);
103        for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
104          set(it, copy[it]);
105        }
106      }
107      return *this;
108    }
109
110    /** The destructor of the map.
111     */
112    virtual ~VectorMap() {
113    }
114               
115    /**
116     * The subscript operator. The map can be subscripted by the
117     * actual keys of the graph.
118     */
119    ReferenceType operator[](const KeyType& key) {
120      int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
121      return container[id];
122    }
123               
124    /**
125     * The const subscript operator. The map can be subscripted by the
126     * actual keys of the graph.
127     */
128    ConstReferenceType operator[](const KeyType& key) const {
129      int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
130      return container[id];
131    }
132
133    /** Setter function of the map. Equivalent with map[key] = val.
134     *  This is a compatibility feature with the not dereferable maps.
135     */
136    void set(const KeyType& key, const ValueType& val) {
137      int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
138      container[id] = val;
139    }
140               
141    /** Add a new key to the map. It called by the map registry.
142     */
143    void add(const KeyType& key) {
144      int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
145      if (id >= (int)container.size()) {
146        container.resize(id + 1);
147      }
148    }
149               
150    /** Erase a key from the map. It called by the map registry.
151     */
152    void erase(const KeyType& key) {}
153
154    /** Clear the data structure.
155     */
156    void clear() {
157      container.clear();
158    }
159
160    /// The stl compatible pair iterator of the map.
161    typedef MapIterator<VectorMap> Iterator;
162    /// The stl compatible const pair iterator of the map.
163    typedef MapConstIterator<VectorMap> ConstIterator;
164
165    /** Returns the begin iterator of the map.
166     */
167    Iterator begin() {
168      return Iterator(*this, KeyIt(*MapBase::getGraph()));
169    }
170
171    /** Returns the end iterator of the map.
172     */
173    Iterator end() {
174      return Iterator(*this, INVALID);
175    }
176
177    /** Returns the begin ConstIterator of the map.
178     */
179    ConstIterator begin() const {
180      return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
181    }
182
183    /** Returns the end const_iterator of the map.
184     */
185    ConstIterator end() const {
186      return ConstIterator(*this, INVALID);
187    }
188
189    /// The KeySet of the Map.
190    typedef MapConstKeySet<VectorMap> ConstKeySet;
191
192    /// KeySet getter function.
193    ConstKeySet keySet() const {
194      return ConstKeySet(*this);
195    }
196
197    /// The ConstValueSet of the Map.
198    typedef MapConstValueSet<VectorMap> ConstValueSet;
199
200    /// ConstValueSet getter function.
201    ConstValueSet valueSet() const {
202      return ConstValueSet(*this);
203    }
204
205    /// The ValueSet of the Map.
206    typedef MapValueSet<VectorMap> ValueSet;
207
208    /// ValueSet getter function.
209    ValueSet valueSet() {
210      return ValueSet(*this);
211    }
212
213
214  private:
215               
216    Container container;
217
218  public:
219    // STL  compatibility typedefs.
220    typedef Iterator iterator;
221    typedef ConstIterator const_iterator;
222    typedef typename Iterator::PairValueType value_type;
223    typedef typename Iterator::KeyType key_type;
224    typedef typename Iterator::ValueType data_type;
225    typedef typename Iterator::PairReferenceType reference;
226    typedef typename Iterator::PairPointerType pointer;
227    typedef typename ConstIterator::PairReferenceType const_reference;
228    typedef typename ConstIterator::PairPointerType const_pointer;
229    typedef int difference_type;               
230  };
231 
232  /// @}
233 
234}
235
236#endif
Note: See TracBrowser for help on using the repository browser.