3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_BITS_VECTOR_MAP_H
20 #define LEMON_BITS_VECTOR_MAP_H
25 #include <lemon/bits/traits.h>
26 #include <lemon/bits/utility.h>
28 #include <lemon/bits/alteration_notifier.h>
30 #include <lemon/concept_check.h>
31 #include <lemon/concepts/maps.h>
36 ///\brief Vector based graph maps.
39 /// \ingroup graphbits
41 /// \brief Graph map based on the std::vector storage.
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.
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.
51 /// \author Balazs Dezso
52 template <typename _Graph, typename _Item, typename _Value>
54 : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
57 /// The container type of the map.
58 typedef std::vector<_Value> Container;
62 /// The graph type of the map.
64 /// The item type of the map.
66 /// The reference map tag.
67 typedef True ReferenceMapTag;
69 /// The key type of the map.
71 /// The value type of the map.
74 /// The notifier type.
75 typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
78 typedef VectorMap Map;
79 /// The base class of the map.
80 typedef typename Notifier::ObserverBase Parent;
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;
88 /// \brief Constructor to attach the new map into the notifier.
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);
97 /// \brief Constructor uses given value to initialize the map.
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);
106 /// \brief Copy constructor
108 /// Copy constructor.
109 VectorMap(const VectorMap& _copy) : Parent() {
110 if (_copy.attached()) {
111 Parent::attach(*_copy.notifier());
112 container = _copy.container;
116 /// \brief Assign operator.
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);
128 /// \brief Template assign operator.
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* notifier = Parent::notifier();
139 for (notifier->first(it); it != INVALID; notifier->next(it)) {
147 /// \brief The subcript operator.
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)];
155 /// \brief The const subcript operator.
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)];
164 /// \brief The setter function of the map.
166 /// It the same as operator[](key) = value expression.
167 void set(const Key& key, const Value& value) {
168 (*this)[key] = value;
173 /// \brief Adds a new key to the map.
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);
184 /// \brief Adds more new keys to the map.
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]);
196 container.resize(max + 1);
199 /// \brief Erase a key from the map.
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();
207 /// \brief Erase more keys from the map.
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();
217 /// \brief Buildes the map.
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);
227 /// \brief Clear the map.
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() {