COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/vector_map.h @ 938:70e2886211d5

Last change on this file since 938:70e2886211d5 was 937:d4e911acef3d, checked in by Balazs Dezso, 16 years ago

Revert backport changes -r1230.

File size: 8.1 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/vector_map.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef LEMON_VECTOR_MAP_H
18#define LEMON_VECTOR_MAP_H
19
20#include <vector>
21
22#include <lemon/map_iterator.h>
23#include <lemon/map_bits.h>
24
25///\ingroup graphmaps
26///\file
27///\brief Vector based graph maps.
28
29namespace lemon {
30 
31  /// \addtogroup graphmaps
32  /// @{
33 
34  /** The VectorMap template class is graph map structure what
35   *  automatically updates the map when a key is added to or erased from
36   *  the map. This map factory uses the allocators to implement
37   *  the container functionality. This map factory
38   *  uses the std::vector to implement the container function.
39   *
40   *  \param MapRegistry The MapRegistry that the maps will belong to.
41   *  \param Value The value type of the map.
42   *
43   *  \author Balazs Dezso
44   */
45       
46  template <typename MapRegistry, typename Value>
47  class VectorMap : public MapRegistry::MapBase {
48    template <typename MR, typename T> friend class VectorMap;
49  public:
50               
51    /// The graph type of the maps.
52    typedef typename MapRegistry::Graph Graph;
53    /// The key type of the maps.
54    typedef typename MapRegistry::KeyType KeyType;
55    /// The iterator to iterate on the keys.
56    typedef typename MapRegistry::KeyIt KeyIt;
57
58    /// The map type.
59    typedef VectorMap Map;
60    /// The MapBase of the Map which implements the core regisitry function.
61    typedef typename MapRegistry::MapBase MapBase;
62
63  private:
64               
65    /// The container type of the map.
66    typedef std::vector<Value> Container;       
67
68  public:
69
70
71    /// The value type of the map.
72    typedef Value ValueType;
73    /// The reference type of the map;
74    typedef typename Container::reference ReferenceType;
75    /// The pointer type of the map;
76    typedef typename Container::pointer PointerType;
77
78    /// The const value type of the map.
79    typedef const Value ConstValueType;
80    /// The const reference type of the map;
81    typedef typename Container::const_reference ConstReferenceType;
82    /// The pointer type of the map;
83    typedef typename Container::const_pointer ConstPointerType;
84
85    /// Constructor to attach the new map into a registry.
86
87    /** Constructor to attach the new map into a registry.
88     *  It adds all the nodes or edges of the graph to the map.
89     */
90    VectorMap(const Graph& g, MapRegistry& r)
91      : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1) {}
92
93    /// Constructor uses given value to initialize the map.
94
95    /** Constructor uses given value to initialize the map.
96     *  It adds all the nodes or edges of the graph to the map.
97     */
98    VectorMap(const Graph& g, MapRegistry& r, const Value& v)
99      : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1, v) {}
100
101    /// Assign operator to copy a map of an other map type.
102
103    /** Assign operator to copy a map of an other map type.
104     *  This map's value type must be assignable by the other
105     *  map type's value type.
106     */
107    template <typename TT>
108    VectorMap(const VectorMap<MapRegistry, TT>& c)
109      : MapBase(c), container(c.container.size()) {
110      for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
111        int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
112        container[id] = c.container[id];
113      }
114    }
115
116    /// Assign operator to copy a map of an other map type.
117
118    /** Assign operator to copy a map of an other map type.
119     *  This map's value type must be assignable by the other
120     *  map type's value type.
121     */
122    template <typename TT>
123    VectorMap& operator=(const VectorMap<MapRegistry, TT>& c) {
124      if (MapBase::getGraph() != c.getGraph()) {
125        MapBase::operator=(c);
126        container.resize(c.container.size());
127      }
128      for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
129        int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
130        container[id] = c.container[id];
131      }
132      return *this;
133    }
134
135    /// The subcript operator.
136
137    /**
138     * The subscript operator. The map can be subscripted by the
139     * actual keys of the graph.
140     */
141    ReferenceType operator[](const KeyType& key) {
142      int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
143      return container[id];
144    }
145               
146    /// The const subcript operator.
147
148    /**
149     * The const subscript operator. The map can be subscripted by the
150     * actual keys of the graph.
151     */
152    ConstReferenceType operator[](const KeyType& key) const {
153      int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
154      return container[id];
155    }
156
157    ///Setter function of the map.
158
159    /** Setter function of the map. Equivalent with map[key] = val.
160     *  This is a compatibility feature with the not dereferable maps.
161     */
162    void set(const KeyType& key, const ValueType& val) {
163      int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
164      container[id] = val;
165    }
166    /// Adds a new key to the map.
167               
168    /** Adds a new key to the map. It called by the map registry
169     *  and it overrides the \ref MapRegistry::MapBase MapBase's
170     *  add() member function.
171     */
172    void add(const KeyType& key) {
173      int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
174      if (id >= (int)container.size()) {
175        container.resize(id + 1);
176      }
177    }
178
179    /// Erases a key from the map.
180               
181    /** Erase a key from the map. It called by the map registry
182     *  and it overrides the \ref MapRegistry::MapBase MapBase's
183     *  erase() member function.
184     */
185    void erase(const KeyType& key) {}
186
187    /// Makes empty the map.
188
189    /** Makes empty the map. It called by the map registry
190     *  and it overrides the \ref MapRegistry::MapBase MapBase's
191     *  clear() member function.
192     */
193
194    void clear() {
195      container.clear();
196    }
197
198    /// The stl compatible pair iterator of the map.
199    typedef MapIterator<VectorMap> Iterator;
200    /// The stl compatible const pair iterator of the map.
201    typedef MapConstIterator<VectorMap> ConstIterator;
202
203    /** Returns the begin iterator of the map.
204     */
205    Iterator begin() {
206      return Iterator(*this, KeyIt(*MapBase::getGraph()));
207    }
208
209    /** Returns the end iterator of the map.
210     */
211    Iterator end() {
212      return Iterator(*this, INVALID);
213    }
214
215    /** Returns the begin ConstIterator of the map.
216     */
217    ConstIterator begin() const {
218      return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
219    }
220
221    /** Returns the end const_iterator of the map.
222     */
223    ConstIterator end() const {
224      return ConstIterator(*this, INVALID);
225    }
226
227    /// The KeySet of the Map.
228    typedef MapConstKeySet<VectorMap> ConstKeySet;
229
230    /// KeySet getter function.
231    ConstKeySet keySet() const {
232      return ConstKeySet(*this);
233    }
234
235    /// The ConstValueSet of the Map.
236    typedef MapConstValueSet<VectorMap> ConstValueSet;
237
238    /// ConstValueSet getter function.
239    ConstValueSet valueSet() const {
240      return ConstValueSet(*this);
241    }
242
243    /// The ValueSet of the Map.
244    typedef MapValueSet<VectorMap> ValueSet;
245
246    /// ValueSet getter function.
247    ValueSet valueSet() {
248      return ValueSet(*this);
249    }
250
251
252  private:
253               
254    Container container;
255
256  public:
257    // STL  compatibility typedefs.
258    typedef Iterator iterator;
259    typedef ConstIterator const_iterator;
260    typedef typename Iterator::PairValueType value_type;
261    typedef typename Iterator::KeyType key_type;
262    typedef typename Iterator::ValueType data_type;
263    typedef typename Iterator::PairReferenceType reference;
264    typedef typename Iterator::PairPointerType pointer;
265    typedef typename ConstIterator::PairReferenceType const_reference;
266    typedef typename ConstIterator::PairPointerType const_pointer;
267    typedef int difference_type;               
268  };
269 
270  /// @}
271 
272}
273
274#endif
Note: See TracBrowser for help on using the repository browser.