COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/vector_map.h @ 978:175cf8c3a994

Last change on this file since 978:175cf8c3a994 was 978:175cf8c3a994, checked in by Mihaly Barasz, 15 years ago

"make check" pass under gcc-3.4.3

File size: 7.6 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#include <algorithm>
22
23#include <lemon/alteration_observer_registry.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 Registry The AlterationObserverRegistry that will notify this map.
41  /// \param IdMap The IdMap type of the graph items.
42  /// \param Value The value type of the map.
43  ///
44  /// \author Balazs Dezso
45       
46
47  template <typename _Graph,
48            typename _Item,
49            typename _IdMap,
50            typename _Value>
51  class VectorMap : public AlterationObserverRegistry<_Item>::ObserverBase {
52  public:
53               
54    /// The graph type of the map.
55    typedef _Graph Graph;
56    /// The key type of the map.
57    typedef _Item KeyType;
58    /// The id map type of the map.
59    typedef _IdMap IdMap;
60    /// The registry type of the map.
61    typedef AlterationObserverRegistry<_Item> Registry;
62    /// The value type of the map.
63    typedef _Value Value;
64
65    /// The map type.
66    typedef VectorMap Map;
67    /// The base class of the map.
68    typedef typename Registry::ObserverBase Parent;
69
70  private:
71               
72    /// The container type of the map.
73    typedef std::vector<Value> Container;       
74
75  public:
76
77    /// The value type of the map.
78    typedef Value ValueType;
79    /// The reference type of the map;
80    typedef typename Container::reference ReferenceType;
81    /// The pointer type of the map;
82    typedef typename Container::pointer PointerType;
83
84    /// The const value type of the map.
85    typedef const Value ConstValueType;
86    /// The const reference type of the map;
87    typedef typename Container::const_reference ConstReferenceType;
88    /// The pointer type of the map;
89    typedef typename Container::const_pointer ConstPointerType;
90
91    /// Constructor to attach the new map into the registry.
92
93    /// It construates a map and attachs it into the registry.
94    /// It adds all the items of the graph to the map.
95     
96    VectorMap(const Graph& _g, Registry& _r) : graph(&_g) {
97      attach(_r);
98      build();
99    }
100
101    /// Constructor uses given value to initialize the map.
102
103    /// It construates a map uses a given value to initialize the map.
104    /// It adds all the items of the graph to the map.
105     
106    VectorMap(const Graph& g, Registry& r, const Value& v) : graph(&g) {
107      attach(r);
108      container.resize(IdMap(*graph).maxId() + 1, v);
109    }
110
111    VectorMap(const VectorMap& copy) : graph(copy.getGraph()) {
112      if (copy.attached()) {
113        attach(*copy.getRegistry());
114        container = copy.container;
115      }
116    }
117
118    using Parent::attach;
119    using Parent::detach;
120    using Parent::attached;
121
122    /** Assign operator to copy a map of the same map type.
123     */
124    VectorMap& operator=(const VectorMap& copy) {
125      if (&copy == this) return *this;
126     
127      if (graph != copy.graph) {
128        if (attached()) {
129          detach();
130        }
131        if (copy.attached()) {
132          attach(*copy.getRegistry());
133        }
134      }
135      container = copy.container;
136
137      return *this;
138    }
139
140
141    virtual ~VectorMap() {
142      if (attached()) {
143        detach();
144      }
145    }
146
147    const Graph* getGraph() const {
148      return graph;
149    }
150
151    /// The subcript operator.
152
153    /// The subscript operator. The map can be subscripted by the
154    /// actual items of the graph.
155     
156    ReferenceType operator[](const KeyType& key) {
157      return container[IdMap(*graph)[key]];
158    }
159               
160    /// The const subcript operator.
161
162    /// The const subscript operator. The map can be subscripted by the
163    /// actual items of the graph.
164     
165    ConstReferenceType operator[](const KeyType& key) const {
166      return container[IdMap(*graph)[key]];
167    }
168
169
170    /// The setter function of the map.
171
172    /// It the same as operator[](key) = value expression.
173    ///
174     
175    void set(const KeyType& key, const ValueType& value) {
176      (*this)[key] = value;
177    }
178
179    /// Adds a new key to the map.
180               
181    /// It adds a new key to the map. It called by the observer registry
182    /// and it overrides the add() member function of the observer base.
183     
184    void add(const KeyType& key) {
185      int id = IdMap(*graph)[key];
186      if (id >= (int)container.size()) {
187        container.resize(id + 1);
188      }
189    }
190
191    /// Erases a key from the map.
192               
193    /// Erase a key from the map. It called by the observer registry
194    /// and it overrides the erase() member function of the observer base.     
195    void erase(const KeyType&) {}
196
197    /// Buildes the map.
198               
199    /// It buildes the map. It called by the observer registry
200    /// and it overrides the build() member function of the observer base.
201
202    void build() {
203      container.resize(IdMap(*graph).maxId() + 1);
204    }
205
206    /// Clear the map.
207
208    /// It erase all items from the map. It called by the observer registry
209    /// and it overrides the clear() member function of the observer base.     
210    void clear() {
211      container.clear();
212    }
213
214  private:
215               
216    Container container;
217    const Graph *graph;
218
219  };
220
221
222  template <typename _Base>
223  class VectorMappableGraphExtender : public _Base {
224  public:
225
226    typedef VectorMappableGraphExtender<_Base> Graph;
227    typedef _Base Parent;
228
229    typedef typename Parent::Node Node;
230    typedef typename Parent::NodeIt NodeIt;
231    typedef typename Parent::NodeIdMap NodeIdMap;
232    typedef typename Parent::NodeObserverRegistry NodeObserverRegistry;
233
234    typedef typename Parent::Edge Edge;
235    typedef typename Parent::EdgeIt EdgeIt;
236    typedef typename Parent::EdgeIdMap EdgeIdMap;
237    typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry;
238
239   
240
241    template <typename _Value>
242    class NodeMap : public VectorMap<Graph, Node, NodeIdMap, _Value> {
243    public:
244      typedef VectorMappableGraphExtender<_Base> Graph;
245
246      typedef typename Graph::Node Node;
247      typedef typename Graph::NodeIdMap NodeIdMap;
248
249      typedef VectorMap<Graph, Node, NodeIdMap, _Value> Parent;
250
251      typedef typename Parent::Graph Graph;
252      typedef typename Parent::Value Value;
253
254      NodeMap(const Graph& g)
255        : Parent(g, g.getNodeObserverRegistry()) {}
256      NodeMap(const Graph& g, const Value& v)
257        : Parent(g, g.getNodeObserverRegistry(), v) {}
258
259    };
260
261    template <typename _Value>
262    class EdgeMap : public VectorMap<Graph, Edge, EdgeIdMap, _Value> {
263    public:
264      typedef VectorMappableGraphExtender<_Base> Graph;
265
266      typedef typename Graph::Edge Edge;
267      typedef typename Graph::EdgeIdMap EdgeIdMap;
268
269      typedef VectorMap<Graph, Edge, EdgeIdMap, _Value> Parent;
270
271      typedef typename Parent::Graph Graph;
272      typedef typename Parent::Value Value;
273
274      EdgeMap(const Graph& g)
275        : Parent(g, g.getEdgeObserverRegistry()) {}
276      EdgeMap(const Graph& g, const Value& v)
277        : Parent(g, g.getEdgeObserverRegistry(), v) {}
278
279    };
280   
281  };
282 
283  /// @}
284 
285}
286
287#endif
Note: See TracBrowser for help on using the repository browser.