COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/vector_map.h @ 2031:080d51024ac5

Last change on this file since 2031:080d51024ac5 was 2031:080d51024ac5, checked in by Balazs Dezso, 18 years ago

Correcting the structure of the graph's and adaptor's map.
The template assign operators and map iterators can be used for adaptors also.

Some bugfix in the adaptors

New class SwapBpUGraphAdaptor which swaps the two nodeset of the graph.

File size: 7.4 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 factory uses the allocators to implement
46  /// the container functionality. This map factory
47  /// uses the std::vector to implement the container function.
48  ///
49  /// \param Notifier The AlterationNotifier that will notify this map.
50  /// \param Item The item type of the graph items.
51  /// \param Value The value type of the map.
52  ///
53  /// \author Balazs Dezso     
54  template <typename _Graph, typename _Item, typename _Value>
55  class VectorMap
56    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
57  private:
58               
59    /// The container type of the map.
60    typedef std::vector<_Value> Container;     
61
62  public:
63
64    /// The graph type of the map.
65    typedef _Graph Graph;
66    /// The item type of the map.
67    typedef _Item Item;
68    /// The reference map tag.
69    typedef True ReferenceMapTag;
70
71    /// The key type of the map.
72    typedef _Item Key;
73    /// The value type of the map.
74    typedef _Value Value;
75
76    /// The notifier type.
77    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
78
79    /// The map type.
80    typedef VectorMap Map;
81    /// The base class of the map.
82    typedef typename Notifier::ObserverBase Parent;
83
84    /// The reference type of the map;
85    typedef typename Container::reference Reference;
86    /// The const reference type of the map;
87    typedef typename Container::const_reference ConstReference;
88
89
90    /// \brief Constructor to attach the new map into the notifier.
91    ///
92    /// It constructs a map and attachs it into the notifier.
93    /// It adds all the items of the graph to the map.
94    VectorMap(const Graph& graph) {
95      Parent::attach(graph.getNotifier(Item()));
96      container.resize(Parent::getNotifier()->maxId() + 1);
97    }
98
99    /// \brief Constructor uses given value to initialize the map.
100    ///
101    /// It constructs a map uses a given value to initialize the map.
102    /// It adds all the items of the graph to the map.
103    VectorMap(const Graph& graph, const Value& value) {
104      Parent::attach(graph.getNotifier(Item()));
105      container.resize(Parent::getNotifier()->maxId() + 1, value);
106    }
107
108    /// \brief Copy constructor
109    ///
110    /// Copy constructor.
111    VectorMap(const VectorMap& _copy) : Parent() {
112      if (_copy.attached()) {
113        Parent::attach(*_copy.getNotifier());
114        container = _copy.container;
115      }
116    }
117
118    /// \brief Assign operator.
119    ///
120    /// This operator assigns for each item in the map the
121    /// value mapped to the same item in the copied map. 
122    /// The parameter map should be indiced with the same
123    /// itemset because this assign operator does not change
124    /// the container of the map.
125    VectorMap& operator=(const VectorMap& cmap) {
126      return operator=<VectorMap>(cmap);
127    }
128
129
130    /// \brief Template assign operator.
131    ///
132    /// The given parameter should be conform to the ReadMap
133    /// concecpt and could be indiced by the current item set of
134    /// the NodeMap. In this case the value for each item
135    /// is assigned by the value of the given ReadMap.
136    template <typename CMap>
137    VectorMap& operator=(const CMap& cmap) {
138      checkConcept<concept::ReadMap<Key, _Value>, CMap>();
139      const typename Parent::Notifier* notifier = Parent::getNotifier();
140      Item it;
141      for (notifier->first(it); it != INVALID; notifier->next(it)) {
142        set(it, cmap[it]);
143      }
144      return *this;
145    }
146   
147  public:
148
149    /// \brief The subcript operator.
150    ///
151    /// The subscript operator. The map can be subscripted by the
152    /// actual items of the graph.     
153    Reference operator[](const Key& key) {
154      return container[Parent::getNotifier()->id(key)];
155    }
156               
157    /// \brief The const subcript operator.
158    ///
159    /// The const subscript operator. The map can be subscripted by the
160    /// actual items of the graph.
161    ConstReference operator[](const Key& key) const {
162      return container[Parent::getNotifier()->id(key)];
163    }
164
165
166    /// \brief The setter function of the map.
167    ///
168    /// It the same as operator[](key) = value expression.
169    void set(const Key& key, const Value& value) {
170      (*this)[key] = value;
171    }
172
173  protected:
174
175    /// \brief Adds a new key to the map.
176    ///         
177    /// It adds a new key to the map. It called by the observer notifier
178    /// and it overrides the add() member function of the observer base.     
179    virtual void add(const Key& key) {
180      int id = Parent::getNotifier()->id(key);
181      if (id >= (int)container.size()) {
182        container.resize(id + 1);
183      }
184    }
185
186    /// \brief Adds more new keys to the map.
187    ///         
188    /// It adds more new keys to the map. It called by the observer notifier
189    /// and it overrides the add() member function of the observer base.     
190    virtual void add(const std::vector<Key>& keys) {
191      int max = container.size() - 1;
192      for (int i = 0; i < (int)keys.size(); ++i) {
193        int id = Parent::getNotifier()->id(keys[i]);
194        if (id >= max) {
195          max = id;
196        }
197      }
198      container.resize(max + 1);
199    }
200
201    /// \brief Erase a key from the map.
202    ///
203    /// Erase a key from the map. It called by the observer notifier
204    /// and it overrides the erase() member function of the observer base.     
205    virtual void erase(const Key& key) {
206      container[Parent::getNotifier()->id(key)] = Value();
207    }
208
209    /// \brief Erase more keys from the map.
210    ///
211    /// Erase more keys from the map. It called by the observer notifier
212    /// and it overrides the erase() member function of the observer base.     
213    virtual void erase(const std::vector<Key>& keys) {
214      for (int i = 0; i < (int)keys.size(); ++i) {
215        container[Parent::getNotifier()->id(keys[i])] = Value();
216      }
217    }
218   
219    /// \brief Buildes the map.
220    ///
221    /// It buildes the map. It called by the observer notifier
222    /// and it overrides the build() member function of the observer base.
223    virtual void build() {
224      int size = Parent::getNotifier()->maxId() + 1;
225      container.reserve(size);
226      container.resize(size);
227    }
228
229    /// \brief Clear the map.
230    ///
231    /// It erase all items from the map. It called by the observer notifier
232    /// and it overrides the clear() member function of the observer base.     
233    virtual void clear() {
234      container.clear();
235    }
236   
237  private:
238               
239    Container container;
240
241  };
242
243}
244
245#endif
Note: See TracBrowser for help on using the repository browser.