COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/vector_map.h @ 2000:ebcc93ead7da

Last change on this file since 2000:ebcc93ead7da was 1999:2ff283124dfc, checked in by Balazs Dezso, 14 years ago

Clarifing alteration observing system
It is directly connected now to a container

File size: 6.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///\ingroup graphbits
31///
32///\file
33///\brief Vector based graph maps.
34namespace lemon {
35
36  /// \ingroup graphbits
37  ///
38  /// \brief Graph map based on the std::vector storage.
39  ///
40  /// The VectorMap template class is graph map structure what
41  /// automatically updates the map when a key is added to or erased from
42  /// the map. This map factory uses the allocators to implement
43  /// the container functionality. This map factory
44  /// uses the std::vector to implement the container function.
45  ///
46  /// \param Notifier The AlterationNotifier that will notify this map.
47  /// \param Item The item type of the graph items.
48  /// \param Value The value type of the map.
49  ///
50  /// \author Balazs Dezso     
51  template <typename _Graph, typename _Item, typename _Value>
52  class VectorMap
53    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
54  private:
55               
56    /// The container type of the map.
57    typedef std::vector<_Value> Container;     
58
59  public:
60
61    /// The graph type of the map.
62    typedef _Graph Graph;
63    /// The item type of the map.
64    typedef _Item Item;
65    /// The reference map tag.
66    typedef True ReferenceMapTag;
67
68    /// The key type of the map.
69    typedef _Item Key;
70    /// The value type of the map.
71    typedef _Value Value;
72
73    /// The notifier type.
74    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
75
76    /// The map type.
77    typedef VectorMap Map;
78    /// The base class of the map.
79    typedef typename Notifier::ObserverBase Parent;
80
81    /// The reference type of the map;
82    typedef typename Container::reference Reference;
83    /// The const reference type of the map;
84    typedef typename Container::const_reference ConstReference;
85
86
87    /// \brief Constructor to attach the new map into the notifier.
88    ///
89    /// It constructs a map and attachs it into the notifier.
90    /// It adds all the items of the graph to the map.
91    VectorMap(const Graph& graph) {
92      Parent::attach(graph.getNotifier(Item()));
93      container.resize(Parent::getNotifier()->maxId() + 1);
94    }
95
96    /// \brief Constructor uses given value to initialize the map.
97    ///
98    /// It constructs a map uses a given value to initialize the map.
99    /// It adds all the items of the graph to the map.
100    VectorMap(const Graph& graph, const Value& value) {
101      Parent::attach(graph.getNotifier(Item()));
102      container.resize(Parent::getNotifier()->maxId() + 1, value);
103    }
104
105    /// \brief Copy constructor
106    ///
107    /// Copy constructor.
108    VectorMap(const VectorMap& _copy) : Parent() {
109      if (_copy.attached()) {
110        Parent::attach(*_copy.getNotifier());
111        container = _copy.container;
112      }
113    }
114
115  private:
116
117    VectorMap& operator=(const VectorMap&);
118
119  public:
120
121    /// \brief The subcript operator.
122    ///
123    /// The subscript operator. The map can be subscripted by the
124    /// actual items of the graph.     
125    Reference operator[](const Key& key) {
126      return container[Parent::getNotifier()->id(key)];
127    }
128               
129    /// \brief The const subcript operator.
130    ///
131    /// The const subscript operator. The map can be subscripted by the
132    /// actual items of the graph.
133    ConstReference operator[](const Key& key) const {
134      return container[Parent::getNotifier()->id(key)];
135    }
136
137
138    /// \brief The setter function of the map.
139    ///
140    /// It the same as operator[](key) = value expression.
141    void set(const Key& key, const Value& value) {
142      (*this)[key] = value;
143    }
144
145  protected:
146
147    /// \brief Adds a new key to the map.
148    ///         
149    /// It adds a new key to the map. It called by the observer notifier
150    /// and it overrides the add() member function of the observer base.     
151    virtual void add(const Key& key) {
152      int id = Parent::getNotifier()->id(key);
153      if (id >= (int)container.size()) {
154        container.resize(id + 1);
155      }
156    }
157
158    /// \brief Adds more new keys to the map.
159    ///         
160    /// It adds more new keys to the map. It called by the observer notifier
161    /// and it overrides the add() member function of the observer base.     
162    virtual void add(const std::vector<Key>& keys) {
163      int max = container.size() - 1;
164      for (int i = 0; i < (int)keys.size(); ++i) {
165        int id = Parent::getNotifier()->id(keys[i]);
166        if (id >= max) {
167          max = id;
168        }
169      }
170      container.resize(max + 1);
171    }
172
173    /// \brief Erase a key from the map.
174    ///
175    /// Erase a key from the map. It called by the observer notifier
176    /// and it overrides the erase() member function of the observer base.     
177    virtual void erase(const Key& key) {
178      container[Parent::getNotifier()->id(key)] = Value();
179    }
180
181    /// \brief Erase more keys from the map.
182    ///
183    /// Erase more keys from the map. It called by the observer notifier
184    /// and it overrides the erase() member function of the observer base.     
185    virtual void erase(const std::vector<Key>& keys) {
186      for (int i = 0; i < (int)keys.size(); ++i) {
187        container[Parent::getNotifier()->id(keys[i])] = Value();
188      }
189    }
190   
191    /// \brief Buildes the map.
192    ///
193    /// It buildes the map. It called by the observer notifier
194    /// and it overrides the build() member function of the observer base.
195    virtual void build() {
196      int size = Parent::getNotifier()->maxId() + 1;
197      container.reserve(size);
198      container.resize(size);
199    }
200
201    /// \brief Clear the map.
202    ///
203    /// It erase all items from the map. It called by the observer notifier
204    /// and it overrides the clear() member function of the observer base.     
205    virtual void clear() {
206      container.clear();
207    }
208   
209  private:
210               
211    Container container;
212
213  };
214
215}
216
217#endif
Note: See TracBrowser for help on using the repository browser.