COIN-OR::LEMON - Graph Library

source: lemon/lemon/bits/vector_map.h @ 77:2de55e4f57a7

Last change on this file since 77:2de55e4f57a7 was 57:c1acf0018c0a, checked in by Balazs Dezso <deba@…>, 17 years ago

Port ListDigraph? and ListGraph? from svn -r 3433
Details:

  • port Digraph and Graph concepts
  • port ListDigraph? and ListGraph?
  • port Basic graph constructing tools
  • port Digraph and Graph tests
File size: 7.3 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_BITS_VECTOR_MAP_H
20#define LEMON_BITS_VECTOR_MAP_H
21
22#include <vector>
23#include <algorithm>
24
25#include <lemon/bits/traits.h>
26#include <lemon/bits/utility.h>
27
28#include <lemon/bits/alteration_notifier.h>
29
30#include <lemon/concept_check.h>
31#include <lemon/concepts/maps.h>
32
33///\ingroup graphbits
34///
35///\file
36///\brief Vector based graph maps.
37namespace lemon {
38
39  /// \ingroup graphbits
40  ///
41  /// \brief Graph map based on the std::vector storage.
42  ///
43  /// The VectorMap template class is graph map structure what
44  /// automatically updates the map when a key is added to or erased from
45  /// the map. This map type uses the std::vector to store the values.
46  ///
47  /// \param Notifier The AlterationNotifier that will notify this map.
48  /// \param Item The item type of the graph items.
49  /// \param Value The value type of the map.
50  ///
51  /// \author Balazs Dezso     
52  template <typename _Graph, typename _Item, typename _Value>
53  class VectorMap
54    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
55  private:
56               
57    /// The container type of the map.
58    typedef std::vector<_Value> Container;     
59
60  public:
61
62    /// The graph type of the map.
63    typedef _Graph Graph;
64    /// The item type of the map.
65    typedef _Item Item;
66    /// The reference map tag.
67    typedef True ReferenceMapTag;
68
69    /// The key type of the map.
70    typedef _Item Key;
71    /// The value type of the map.
72    typedef _Value Value;
73
74    /// The notifier type.
75    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
76
77    /// The map type.
78    typedef VectorMap Map;
79    /// The base class of the map.
80    typedef typename Notifier::ObserverBase Parent;
81
82    /// The reference type of the map;
83    typedef typename Container::reference Reference;
84    /// The const reference type of the map;
85    typedef typename Container::const_reference ConstReference;
86
87
88    /// \brief Constructor to attach the new map into the notifier.
89    ///
90    /// It constructs a map and attachs it into the notifier.
91    /// It adds all the items of the graph to the map.
92    VectorMap(const Graph& graph) {
93      Parent::attach(graph.notifier(Item()));
94      container.resize(Parent::notifier()->maxId() + 1);
95    }
96
97    /// \brief Constructor uses given value to initialize the map.
98    ///
99    /// It constructs a map uses a given value to initialize the map.
100    /// It adds all the items of the graph to the map.
101    VectorMap(const Graph& graph, const Value& value) {
102      Parent::attach(graph.notifier(Item()));
103      container.resize(Parent::notifier()->maxId() + 1, value);
104    }
105
106    /// \brief Copy constructor
107    ///
108    /// Copy constructor.
109    VectorMap(const VectorMap& _copy) : Parent() {
110      if (_copy.attached()) {
111        Parent::attach(*_copy.notifier());
112        container = _copy.container;
113      }
114    }
115
116    /// \brief Assign operator.
117    ///
118    /// This operator assigns for each item in the map the
119    /// value mapped to the same item in the copied map. 
120    /// The parameter map should be indiced with the same
121    /// itemset because this assign operator does not change
122    /// the container of the map.
123    VectorMap& operator=(const VectorMap& cmap) {
124      return operator=<VectorMap>(cmap);
125    }
126
127
128    /// \brief Template assign operator.
129    ///
130    /// The given parameter should be conform to the ReadMap
131    /// concecpt and could be indiced by the current item set of
132    /// the NodeMap. In this case the value for each item
133    /// is assigned by the value of the given ReadMap.
134    template <typename CMap>
135    VectorMap& operator=(const CMap& cmap) {
136      checkConcept<concepts::ReadMap<Key, _Value>, CMap>();
137      const typename Parent::Notifier* nf = Parent::notifier();
138      Item it;
139      for (nf->first(it); it != INVALID; nf->next(it)) {
140        set(it, cmap[it]);
141      }
142      return *this;
143    }
144   
145  public:
146
147    /// \brief The subcript operator.
148    ///
149    /// The subscript operator. The map can be subscripted by the
150    /// actual items of the graph.     
151    Reference operator[](const Key& key) {
152      return container[Parent::notifier()->id(key)];
153    }
154               
155    /// \brief The const subcript operator.
156    ///
157    /// The const subscript operator. The map can be subscripted by the
158    /// actual items of the graph.
159    ConstReference operator[](const Key& key) const {
160      return container[Parent::notifier()->id(key)];
161    }
162
163
164    /// \brief The setter function of the map.
165    ///
166    /// It the same as operator[](key) = value expression.
167    void set(const Key& key, const Value& value) {
168      (*this)[key] = value;
169    }
170
171  protected:
172
173    /// \brief Adds a new key to the map.
174    ///         
175    /// It adds a new key to the map. It called by the observer notifier
176    /// and it overrides the add() member function of the observer base.     
177    virtual void add(const Key& key) {
178      int id = Parent::notifier()->id(key);
179      if (id >= int(container.size())) {
180        container.resize(id + 1);
181      }
182    }
183
184    /// \brief Adds more new keys to the map.
185    ///         
186    /// It adds more new keys to the map. It called by the observer notifier
187    /// and it overrides the add() member function of the observer base.     
188    virtual void add(const std::vector<Key>& keys) {
189      int max = container.size() - 1;
190      for (int i = 0; i < int(keys.size()); ++i) {
191        int id = Parent::notifier()->id(keys[i]);
192        if (id >= max) {
193          max = id;
194        }
195      }
196      container.resize(max + 1);
197    }
198
199    /// \brief Erase a key from the map.
200    ///
201    /// Erase a key from the map. It called by the observer notifier
202    /// and it overrides the erase() member function of the observer base.     
203    virtual void erase(const Key& key) {
204      container[Parent::notifier()->id(key)] = Value();
205    }
206
207    /// \brief Erase more keys from the map.
208    ///
209    /// Erase more keys from the map. It called by the observer notifier
210    /// and it overrides the erase() member function of the observer base.     
211    virtual void erase(const std::vector<Key>& keys) {
212      for (int i = 0; i < int(keys.size()); ++i) {
213        container[Parent::notifier()->id(keys[i])] = Value();
214      }
215    }
216   
217    /// \brief Buildes the map.
218    ///
219    /// It buildes the map. It called by the observer notifier
220    /// and it overrides the build() member function of the observer base.
221    virtual void build() {
222      int size = Parent::notifier()->maxId() + 1;
223      container.reserve(size);
224      container.resize(size);
225    }
226
227    /// \brief Clear the map.
228    ///
229    /// It erase all items from the map. It called by the observer notifier
230    /// and it overrides the clear() member function of the observer base.     
231    virtual void clear() {
232      container.clear();
233    }
234   
235  private:
236               
237    Container container;
238
239  };
240
241}
242
243#endif
Note: See TracBrowser for help on using the repository browser.