COIN-OR::LEMON - Graph Library

source: lemon/lemon/bits/vector_map.h @ 969:6dd226d3dcba

Last change on this file since 969:6dd226d3dcba was 664:4137ef9aacc6, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Fix and uniform the usage of Graph and Parent typedefs (#268)

  • Rename Graph typedefs to GraphType? in the implementation of graph maps and MapExtender? to prevent conflicts (especially using VS). They are not public.
  • Make Parent typedefs private in all classes.
  • Replace Digraph with Graph in some places (fix faulty renamings of the script).
  • Use Graph and Digraph typedefs (more) consequently.
File size: 7.1 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2009
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/core.h>
26#include <lemon/bits/alteration_notifier.h>
27
28#include <lemon/concept_check.h>
29#include <lemon/concepts/maps.h>
30
31//\ingroup graphbits
32//
33//\file
34//\brief Vector based graph maps.
35namespace lemon {
36
37  // \ingroup graphbits
38  //
39  // \brief Graph map based on the std::vector storage.
40  //
41  // The VectorMap template class is graph map structure that automatically
42  // updates the map when a key is added to or erased from the graph.
43  // This map type uses std::vector to store the values.
44  //
45  // \tparam _Graph The graph this map is attached to.
46  // \tparam _Item The item type of the graph items.
47  // \tparam _Value The value type of the map.
48  template <typename _Graph, typename _Item, typename _Value>
49  class VectorMap
50    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
51  private:
52
53    // The container type of the map.
54    typedef std::vector<_Value> Container;
55
56  public:
57
58    // The graph type of the map.
59    typedef _Graph GraphType;
60    // The item type of the map.
61    typedef _Item Item;
62    // The reference map tag.
63    typedef True ReferenceMapTag;
64
65    // The key type of the map.
66    typedef _Item Key;
67    // The value type of the map.
68    typedef _Value Value;
69
70    // The notifier type.
71    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
72
73    // The map type.
74    typedef VectorMap Map;
75
76    // The reference type of the map;
77    typedef typename Container::reference Reference;
78    // The const reference type of the map;
79    typedef typename Container::const_reference ConstReference;
80
81  private:
82
83    // The base class of the map.
84    typedef typename Notifier::ObserverBase Parent;
85
86  public:
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 GraphType& 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 GraphType& graph, const Value& value) {
102      Parent::attach(graph.notifier(Item()));
103      container.resize(Parent::notifier()->maxId() + 1, value);
104    }
105
106  private:
107    // \brief Copy constructor
108    //
109    // Copy constructor.
110    VectorMap(const VectorMap& _copy) : Parent() {
111      if (_copy.attached()) {
112        Parent::attach(*_copy.notifier());
113        container = _copy.container;
114      }
115    }
116
117    // \brief Assign operator.
118    //
119    // This operator assigns for each item in the map the
120    // value mapped to the same item in the copied map.
121    // The parameter map should be indiced with the same
122    // itemset because this assign operator does not change
123    // the container of the map.
124    VectorMap& operator=(const VectorMap& cmap) {
125      return operator=<VectorMap>(cmap);
126    }
127
128
129    // \brief Template assign operator.
130    //
131    // The given parameter should conform to the ReadMap
132    // concecpt and could be indiced by the current item set of
133    // the NodeMap. In this case the value for each item
134    // is assigned by the value of the given ReadMap.
135    template <typename CMap>
136    VectorMap& operator=(const CMap& cmap) {
137      checkConcept<concepts::ReadMap<Key, _Value>, CMap>();
138      const typename Parent::Notifier* nf = Parent::notifier();
139      Item it;
140      for (nf->first(it); it != INVALID; nf->next(it)) {
141        set(it, cmap[it]);
142      }
143      return *this;
144    }
145
146  public:
147
148    // \brief The subcript operator.
149    //
150    // The subscript operator. The map can be subscripted by the
151    // actual items of the graph.
152    Reference operator[](const Key& key) {
153      return container[Parent::notifier()->id(key)];
154    }
155
156    // \brief The const subcript operator.
157    //
158    // The const subscript operator. The map can be subscripted by the
159    // actual items of the graph.
160    ConstReference operator[](const Key& key) const {
161      return container[Parent::notifier()->id(key)];
162    }
163
164
165    // \brief The setter function of the map.
166    //
167    // It the same as operator[](key) = value expression.
168    void set(const Key& key, const Value& value) {
169      (*this)[key] = value;
170    }
171
172  protected:
173
174    // \brief Adds a new key to the map.
175    //
176    // It adds a new key to the map. It is called by the observer notifier
177    // and it overrides the add() member function of the observer base.
178    virtual void add(const Key& key) {
179      int id = Parent::notifier()->id(key);
180      if (id >= int(container.size())) {
181        container.resize(id + 1);
182      }
183    }
184
185    // \brief Adds more new keys to the map.
186    //
187    // It adds more new keys to the map. It is called by the observer notifier
188    // and it overrides the add() member function of the observer base.
189    virtual void add(const std::vector<Key>& keys) {
190      int max = container.size() - 1;
191      for (int i = 0; i < int(keys.size()); ++i) {
192        int id = Parent::notifier()->id(keys[i]);
193        if (id >= max) {
194          max = id;
195        }
196      }
197      container.resize(max + 1);
198    }
199
200    // \brief Erase a key from the map.
201    //
202    // Erase a key from the map. It is called by the observer notifier
203    // and it overrides the erase() member function of the observer base.
204    virtual void erase(const Key& key) {
205      container[Parent::notifier()->id(key)] = Value();
206    }
207
208    // \brief Erase more keys from the map.
209    //
210    // It erases more keys from the map. It is called by the observer notifier
211    // and it overrides the erase() member function of the observer base.
212    virtual void erase(const std::vector<Key>& keys) {
213      for (int i = 0; i < int(keys.size()); ++i) {
214        container[Parent::notifier()->id(keys[i])] = Value();
215      }
216    }
217
218    // \brief Build the map.
219    //
220    // It builds the map. It is called by the observer notifier
221    // and it overrides the build() member function of the observer base.
222    virtual void build() {
223      int size = Parent::notifier()->maxId() + 1;
224      container.reserve(size);
225      container.resize(size);
226    }
227
228    // \brief Clear the map.
229    //
230    // It erases all items from the map. It is called by the observer notifier
231    // and it overrides the clear() member function of the observer base.
232    virtual void clear() {
233      container.clear();
234    }
235
236  private:
237
238    Container container;
239
240  };
241
242}
243
244#endif
Note: See TracBrowser for help on using the repository browser.