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-2010
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_ARRAY_MAP_H
20 : : #define LEMON_BITS_ARRAY_MAP_H
21 : :
22 : : #include <memory>
23 : :
24 : : #include <lemon/bits/traits.h>
25 : : #include <lemon/bits/alteration_notifier.h>
26 : : #include <lemon/concept_check.h>
27 : : #include <lemon/concepts/maps.h>
28 : :
29 : : // \ingroup graphbits
30 : : // \file
31 : : // \brief Graph map based on the array storage.
32 : :
33 : : namespace lemon {
34 : :
35 : : // \ingroup graphbits
36 : : //
37 : : // \brief Graph map based on the array storage.
38 : : //
39 : : // The ArrayMap template class is graph map structure that automatically
40 : : // updates the map when a key is added to or erased from the graph.
41 : : // This map uses the allocators to implement the container functionality.
42 : : //
43 : : // The template parameters are the Graph, the current Item type and
44 : : // the Value type of the map.
45 : : template <typename _Graph, typename _Item, typename _Value>
46 : : class ArrayMap
47 : : : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
48 : : public:
49 : : // The graph type.
50 : : typedef _Graph GraphType;
51 : : // The item type.
52 : : typedef _Item Item;
53 : : // The reference map tag.
54 : : typedef True ReferenceMapTag;
55 : :
56 : : // The key type of the map.
57 : : typedef _Item Key;
58 : : // The value type of the map.
59 : : typedef _Value Value;
60 : :
61 : : // The const reference type of the map.
62 : : typedef const _Value& ConstReference;
63 : : // The reference type of the map.
64 : : typedef _Value& Reference;
65 : :
66 : : // The map type.
67 : : typedef ArrayMap Map;
68 : :
69 : : // The notifier type.
70 : : typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
71 : :
72 : : private:
73 : :
74 : : // The MapBase of the Map which imlements the core regisitry function.
75 : : typedef typename Notifier::ObserverBase Parent;
76 : :
77 : : typedef std::allocator<Value> Allocator;
78 : :
79 : : public:
80 : :
81 : : // \brief Graph initialized map constructor.
82 : : //
83 : : // Graph initialized map constructor.
84 : 712 : explicit ArrayMap(const GraphType& graph) {
85 [ # # ][ # # ]: 356 : Parent::attach(graph.notifier(Item()));
[ # # # # ]
[ # # ]
[ # # + - ]
[ + - ]
[ + - + - ]
[ + - ]
[ + - + - ]
[ + - ]
[ + - + - ]
[ + - ][ + - ]
86 [ # # ][ # # ]: 356 : allocate_memory();
[ + - ][ + - ]
[ + - ][ + - ]
87 [ # # ][ # # ]: 356 : Notifier* nf = Parent::notifier();
[ + - ][ + - ]
[ + - ][ + - ]
88 [ # # ][ # # ]: 356 : Item it;
[ + - ][ + - ]
[ + - ][ + - ]
89 [ # # ][ # # ]: 2601 : for (nf->first(it); it != INVALID; nf->next(it)) {
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + + ][ + - ]
[ + - ][ + - ]
[ + - ][ + + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + + ][ + - ]
[ + - ][ + - ]
[ + - ][ + + ]
90 [ # # ][ # # ]: 2245 : int id = nf->id(it);;
[ + - ][ + - ]
[ + - ][ + - ]
91 [ # # ][ # # ]: 2245 : allocator.construct(&(values[id]), Value());
[ # # ][ # # ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
92 : : }
93 : 356 : }
94 : :
95 : : // \brief Constructor to use default value to initialize the map.
96 : : //
97 : : // It constructs a map and initialize all of the the map.
98 : 0 : ArrayMap(const GraphType& graph, const Value& value) {
99 [ # # ][ # # ]: 0 : Parent::attach(graph.notifier(Item()));
[ # # # # ]
[ # # ][ # # ]
100 [ # # ][ # # ]: 0 : allocate_memory();
101 [ # # ][ # # ]: 0 : Notifier* nf = Parent::notifier();
102 [ # # ][ # # ]: 0 : Item it;
103 [ # # ][ # # ]: 0 : for (nf->first(it); it != INVALID; nf->next(it)) {
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
104 [ # # ][ # # ]: 0 : int id = nf->id(it);;
105 [ # # ][ # # ]: 0 : allocator.construct(&(values[id]), value);
106 : : }
107 : 0 : }
108 : :
109 : : private:
110 : : // \brief Constructor to copy a map of the same map type.
111 : : //
112 : : // Constructor to copy a map of the same map type.
113 : : ArrayMap(const ArrayMap& copy) : Parent() {
114 : : if (copy.attached()) {
115 : : attach(*copy.notifier());
116 : : }
117 : : capacity = copy.capacity;
118 : : if (capacity == 0) return;
119 : : values = allocator.allocate(capacity);
120 : : Notifier* nf = Parent::notifier();
121 : : Item it;
122 : : for (nf->first(it); it != INVALID; nf->next(it)) {
123 : : int id = nf->id(it);;
124 : : allocator.construct(&(values[id]), copy.values[id]);
125 : : }
126 : : }
127 : :
128 : : // \brief Assign operator.
129 : : //
130 : : // This operator assigns for each item in the map the
131 : : // value mapped to the same item in the copied map.
132 : : // The parameter map should be indiced with the same
133 : : // itemset because this assign operator does not change
134 : : // the container of the map.
135 : : ArrayMap& operator=(const ArrayMap& cmap) {
136 : : return operator=<ArrayMap>(cmap);
137 : : }
138 : :
139 : :
140 : : // \brief Template assign operator.
141 : : //
142 : : // The given parameter should conform to the ReadMap
143 : : // concecpt and could be indiced by the current item set of
144 : : // the NodeMap. In this case the value for each item
145 : : // is assigned by the value of the given ReadMap.
146 : : template <typename CMap>
147 : : ArrayMap& operator=(const CMap& cmap) {
148 : : checkConcept<concepts::ReadMap<Key, _Value>, CMap>();
149 : : const typename Parent::Notifier* nf = Parent::notifier();
150 : : Item it;
151 : : for (nf->first(it); it != INVALID; nf->next(it)) {
152 : : set(it, cmap[it]);
153 : : }
154 : : return *this;
155 : : }
156 : :
157 : : public:
158 : : // \brief The destructor of the map.
159 : : //
160 : : // The destructor of the map.
161 : 356 : virtual ~ArrayMap() {
162 [ # # ][ # # ]: 356 : if (attached()) {
[ + - ][ + - ]
[ + - ][ + - ]
163 : 356 : clear();
164 : 356 : detach();
165 : : }
166 [ # # ][ # # ]: 356 : }
[ - + ][ - + ]
[ - + ][ - + ]
167 : :
168 : : protected:
169 : :
170 : : using Parent::attach;
171 : : using Parent::detach;
172 : : using Parent::attached;
173 : :
174 : : public:
175 : :
176 : : // \brief The subscript operator.
177 : : //
178 : : // The subscript operator. The map can be subscripted by the
179 : : // actual keys of the graph.
180 : 4116 : Value& operator[](const Key& key) {
181 : 4116 : int id = Parent::notifier()->id(key);
182 : 4116 : return values[id];
183 : : }
184 : :
185 : : // \brief The const subscript operator.
186 : : //
187 : : // The const subscript operator. The map can be subscripted by the
188 : : // actual keys of the graph.
189 : 6735 : const Value& operator[](const Key& key) const {
190 : 6735 : int id = Parent::notifier()->id(key);
191 : 6735 : return values[id];
192 : : }
193 : :
194 : : // \brief Setter function of the map.
195 : : //
196 : : // Setter function of the map. Equivalent with map[key] = val.
197 : : // This is a compatibility feature with the not dereferable maps.
198 : 2832 : void set(const Key& key, const Value& val) {
199 : 2832 : (*this)[key] = val;
200 : 2832 : }
201 : :
202 : : protected:
203 : :
204 : : // \brief Adds a new key to the map.
205 : : //
206 : : // It adds a new key to the map. It is called by the observer notifier
207 : : // and it overrides the add() member function of the observer base.
208 : 109 : virtual void add(const Key& key) {
209 : 109 : Notifier* nf = Parent::notifier();
210 : 109 : int id = nf->id(key);
211 [ # # # # : 109 : if (id >= capacity) {
# # + + #
# # # ]
212 [ # # ][ # # ]: 18 : int new_capacity = (capacity == 0 ? 1 : capacity);
[ # # ][ + - ]
[ # # ][ # # ]
213 [ # # ][ # # ]: 36 : while (new_capacity <= id) {
[ # # ][ + + ]
[ # # ][ # # ]
214 : 18 : new_capacity <<= 1;
215 : : }
216 [ # # ][ # # ]: 18 : Value* new_values = allocator.allocate(new_capacity);
[ # # ][ + - ]
[ # # ][ # # ]
217 [ # # ][ # # ]: 18 : Item it;
[ # # ][ + - ]
[ # # ][ # # ]
218 [ # # ][ # # ]: 160 : for (nf->first(it); it != INVALID; nf->next(it)) {
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ + - ]
[ + - ][ + - ]
[ + - ][ + + ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
219 [ # # ][ # # ]: 142 : int jd = nf->id(it);;
[ # # ][ + - ]
[ # # ][ # # ]
220 [ # # ][ # # ]: 142 : if (id != jd) {
[ # # ][ + + ]
[ # # ][ # # ]
221 [ # # ][ # # ]: 124 : allocator.construct(&(new_values[jd]), values[jd]);
[ # # ][ + - ]
[ # # ][ # # ]
222 [ # # ][ # # ]: 124 : allocator.destroy(&(values[jd]));
[ # # ][ + - ]
[ # # ][ # # ]
223 : : }
224 : : }
225 [ # # ][ # # ]: 18 : if (capacity != 0) allocator.deallocate(values, capacity);
[ # # ][ # # ]
[ # # ][ # # ]
[ + - ][ + - ]
[ # # ][ # # ]
[ # # ][ # # ]
226 : 18 : values = new_values;
227 : 18 : capacity = new_capacity;
228 : : }
229 [ # # ][ # # ]: 109 : allocator.construct(&(values[id]), Value());
[ # # ][ + - ]
[ # # ][ # # ]
230 : 109 : }
231 : :
232 : : // \brief Adds more new keys to the map.
233 : : //
234 : : // It adds more new keys to the map. It is called by the observer notifier
235 : : // and it overrides the add() member function of the observer base.
236 : 0 : virtual void add(const std::vector<Key>& keys) {
237 : 0 : Notifier* nf = Parent::notifier();
238 : 0 : int max_id = -1;
239 [ # # ][ # # ]: 0 : for (int i = 0; i < int(keys.size()); ++i) {
[ # # ][ # # ]
[ # # ][ # # ]
240 : 0 : int id = nf->id(keys[i]);
241 [ # # # # : 0 : if (id > max_id) {
# # # # #
# # # ]
242 : 0 : max_id = id;
243 : : }
244 : : }
245 [ # # ][ # # ]: 0 : if (max_id >= capacity) {
[ # # ][ # # ]
[ # # ][ # # ]
246 [ # # ][ # # ]: 0 : int new_capacity = (capacity == 0 ? 1 : capacity);
[ # # ][ # # ]
[ # # ][ # # ]
247 [ # # ][ # # ]: 0 : while (new_capacity <= max_id) {
[ # # ][ # # ]
[ # # ][ # # ]
248 : 0 : new_capacity <<= 1;
249 : : }
250 [ # # ][ # # ]: 0 : Value* new_values = allocator.allocate(new_capacity);
[ # # ][ # # ]
[ # # ][ # # ]
251 [ # # ][ # # ]: 0 : Item it;
[ # # ][ # # ]
[ # # ][ # # ]
252 [ # # ][ # # ]: 0 : for (nf->first(it); it != INVALID; nf->next(it)) {
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
253 [ # # ][ # # ]: 0 : int id = nf->id(it);
[ # # ][ # # ]
[ # # ][ # # ]
254 : 0 : bool found = false;
255 [ # # ][ # # ]: 0 : for (int i = 0; i < int(keys.size()); ++i) {
[ # # ][ # # ]
[ # # ][ # # ]
256 [ # # ][ # # ]: 0 : int jd = nf->id(keys[i]);
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
257 [ # # ][ # # ]: 0 : if (id == jd) {
[ # # ][ # # ]
[ # # ][ # # ]
258 : 0 : found = true;
259 : 0 : break;
260 : : }
261 : : }
262 [ # # ][ # # ]: 0 : if (found) continue;
[ # # ][ # # ]
[ # # ][ # # ]
263 [ # # ][ # # ]: 0 : allocator.construct(&(new_values[id]), values[id]);
[ # # ][ # # ]
[ # # ][ # # ]
264 [ # # ][ # # ]: 0 : allocator.destroy(&(values[id]));
[ # # ][ # # ]
[ # # ][ # # ]
265 : : }
266 [ # # ][ # # ]: 0 : if (capacity != 0) allocator.deallocate(values, capacity);
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
267 : 0 : values = new_values;
268 : 0 : capacity = new_capacity;
269 : : }
270 [ # # ][ # # ]: 0 : for (int i = 0; i < int(keys.size()); ++i) {
[ # # ][ # # ]
[ # # ][ # # ]
271 : 0 : int id = nf->id(keys[i]);
272 [ # # # # ]: 0 : allocator.construct(&(values[id]), Value());
[ # # # #
# # # # ]
273 : : }
274 : 0 : }
275 : :
276 : : // \brief Erase a key from the map.
277 : : //
278 : : // Erase a key from the map. It is called by the observer notifier
279 : : // and it overrides the erase() member function of the observer base.
280 : 0 : virtual void erase(const Key& key) {
281 : 0 : int id = Parent::notifier()->id(key);
282 : 0 : allocator.destroy(&(values[id]));
283 : 0 : }
284 : :
285 : : // \brief Erase more keys from the map.
286 : : //
287 : : // Erase more keys from the map. It is called by the observer notifier
288 : : // and it overrides the erase() member function of the observer base.
289 : 0 : virtual void erase(const std::vector<Key>& keys) {
290 [ # # ][ # # ]: 0 : for (int i = 0; i < int(keys.size()); ++i) {
[ # # ][ # # ]
[ # # ][ # # ]
291 : 0 : int id = Parent::notifier()->id(keys[i]);
292 : 0 : allocator.destroy(&(values[id]));
293 : : }
294 : 0 : }
295 : :
296 : : // \brief Builds the map.
297 : : //
298 : : // It builds the map. It is called by the observer notifier
299 : : // and it overrides the build() member function of the observer base.
300 : 0 : virtual void build() {
301 [ # # ][ # # ]: 0 : Notifier* nf = Parent::notifier();
[ # # ][ # # ]
[ # # ][ # # ]
302 [ # # ][ # # ]: 0 : allocate_memory();
[ # # ][ # # ]
[ # # ][ # # ]
303 [ # # ][ # # ]: 0 : Item it;
[ # # ][ # # ]
[ # # ][ # # ]
304 [ # # ][ # # ]: 0 : for (nf->first(it); it != INVALID; nf->next(it)) {
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
305 [ # # ][ # # ]: 0 : int id = nf->id(it);;
[ # # ][ # # ]
[ # # ][ # # ]
306 [ # # ][ # # ]: 0 : allocator.construct(&(values[id]), Value());
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
307 : : }
308 : 0 : }
309 : :
310 : : // \brief Clear the map.
311 : : //
312 : : // It erase all items from the map. It is called by the observer notifier
313 : : // and it overrides the clear() member function of the observer base.
314 : 356 : virtual void clear() {
315 : 356 : Notifier* nf = Parent::notifier();
316 [ # # # # : 356 : if (capacity != 0) {
+ - + - +
- + - ]
317 [ # # ][ # # ]: 356 : Item it;
[ + - ][ + - ]
[ + - ][ + - ]
318 [ # # ][ # # ]: 2710 : for (nf->first(it); it != INVALID; nf->next(it)) {
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + + ][ + - ]
[ + - ][ + - ]
[ + - ][ + + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + + ][ + - ]
[ + - ][ + - ]
[ + - ][ + + ]
319 [ # # ][ # # ]: 2354 : int id = nf->id(it);
[ + - ][ + - ]
[ + - ][ + - ]
320 [ # # ][ # # ]: 2354 : allocator.destroy(&(values[id]));
[ + - ][ + - ]
[ + - ][ + - ]
321 : : }
322 [ # # ][ # # ]: 356 : allocator.deallocate(values, capacity);
[ + - ][ + - ]
[ + - ][ + - ]
323 : 356 : capacity = 0;
324 : : }
325 : 356 : }
326 : :
327 : : private:
328 : :
329 : 356 : void allocate_memory() {
330 : 356 : int max_id = Parent::notifier()->maxId();
331 [ # # # # : 356 : if (max_id == -1) {
- + - + -
+ - + ]
332 : 0 : capacity = 0;
333 : 0 : values = 0;
334 : 0 : return;
335 : : }
336 : 356 : capacity = 1;
337 [ # # ][ # # ]: 1364 : while (capacity <= max_id) {
[ + + ][ + + ]
[ + + ][ + + ]
338 : 1008 : capacity <<= 1;
339 : : }
340 : 356 : values = allocator.allocate(capacity);
341 : : }
342 : :
343 : : int capacity;
344 : : Value* values;
345 : : Allocator allocator;
346 : :
347 : : };
348 : :
349 : : }
350 : :
351 : : #endif
|
