COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/vector_map.h @ 2202:09cbc87cb4ab

Last change on this file since 2202:09cbc87cb4ab was 2202:09cbc87cb4ab, checked in by Balazs Dezso, 13 years ago

New map type based on array map for debugging purpose

It checks multiple allocation and deallocation of map values and
some consistency.

todo:
clarification of debugging concepts
assertions - exceptions - debug
revision of attic/debug.h

motto:
testing is at least so important as coding

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-2006
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/concept/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.getNotifier(Item()));
94      container.resize(Parent::getNotifier()->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.getNotifier(Item()));
103      container.resize(Parent::getNotifier()->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.getNotifier());
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<concept::ReadMap<Key, _Value>, CMap>();
137      const typename Parent::Notifier* notifier = Parent::getNotifier();
138      Item it;
139      for (notifier->first(it); it != INVALID; notifier->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::getNotifier()->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::getNotifier()->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::getNotifier()->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::getNotifier()->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::getNotifier()->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::getNotifier()->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::getNotifier()->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.