Branch data Line data Source code
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.
35 : : namespace 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 [ # # ][ # # ]: 1220 : 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 [ # # ][ # # ]: 1178 : VectorMap(const GraphType& graph) {
[ + - ][ + - ]
93 [ # # ][ # # ]: 589 : Parent::attach(graph.notifier(Item()));
[ # # ][ # # ]
[ # # ][ # # ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
94 [ # # ][ # # ]: 589 : container.resize(Parent::notifier()->maxId() + 1);
[ # # ][ # # ]
[ # # ][ # # ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
95 : 589 : }
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 [ # # ][ # # ]: 76 : VectorMap(const GraphType& graph, const Value& value) {
[ # # ][ # # ]
[ + - ]
102 [ # # ][ # # ]: 38 : Parent::attach(graph.notifier(Item()));
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ + - ][ + - ]
[ + - ]
103 [ # # ][ # # ]: 38 : container.resize(Parent::notifier()->maxId() + 1, value);
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ + - ][ + - ]
[ + - ]
104 : 38 : }
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 : 13438 : Reference operator[](const Key& key) {
153 : 13438 : 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 : 94 : ConstReference operator[](const Key& key) const {
161 : 94 : 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 : 4703 : void set(const Key& key, const Value& value) {
169 : 4703 : (*this)[key] = value;
170 : 4703 : }
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 : 463 : virtual void add(const Key& key) {
179 : 463 : int id = Parent::notifier()->id(key);
180 [ + + + + : 463 : if (id >= int(container.size())) {
+ + # # #
# ]
181 : 332 : container.resize(id + 1);
182 : : }
183 : 463 : }
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 : 0 : virtual void add(const std::vector<Key>& keys) {
190 : 0 : int max = container.size() - 1;
191 [ # # ][ # # ]: 0 : for (int i = 0; i < int(keys.size()); ++i) {
[ # # ][ # # ]
[ # # ]
192 : 0 : int id = Parent::notifier()->id(keys[i]);
193 [ # # # # : 0 : if (id >= max) {
# # # # #
# ]
194 : 0 : max = id;
195 : : }
196 : : }
197 : 0 : container.resize(max + 1);
198 : 0 : }
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 : 159 : virtual void erase(const Key& key) {
205 : 159 : container[Parent::notifier()->id(key)] = Value();
206 : 159 : }
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 : 0 : virtual void erase(const std::vector<Key>& keys) {
213 [ # # ][ # # ]: 0 : for (int i = 0; i < int(keys.size()); ++i) {
[ # # ][ # # ]
[ # # ]
214 : 0 : container[Parent::notifier()->id(keys[i])] = Value();
215 : : }
216 : 0 : }
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 : 0 : virtual void build() {
223 : 0 : int size = Parent::notifier()->maxId() + 1;
224 : 0 : container.reserve(size);
225 : 0 : container.resize(size);
226 : 0 : }
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 : 0 : virtual void clear() {
233 : 0 : container.clear();
234 : 0 : }
235 : :
236 : : private:
237 : :
238 : : Container container;
239 : :
240 : : };
241 : :
242 : : }
243 : :
244 : : #endif
|
