COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/vector_map.h @ 1284:b941d044f87b

Last change on this file since 1284:b941d044f87b was 1267:a93f94dbe3d3, checked in by Balazs Dezso, 15 years ago

First version of iterable maps.

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