1 /* -*- C++ -*- |
1 /* -*- C++ -*- |
2 * src/lemon/array_map.h - Part of LEMON, a generic C++ optimization library |
2 * src/lemon/bits/array_map.h - Part of LEMON, a generic C++ optimization library |
3 * |
3 * |
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
5 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
5 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
6 * |
6 * |
7 * Permission to use, modify and distribute this software is granted |
7 * Permission to use, modify and distribute this software is granted |
29 |
29 |
30 |
30 |
31 /// \addtogroup graphmaps |
31 /// \addtogroup graphmaps |
32 /// @{ |
32 /// @{ |
33 |
33 |
34 /** The ArrayMap template class is graph map structure what |
34 /// The ArrayMap template class is graph map structure what |
35 * automatically updates the map when a key is added to or erased from |
35 /// automatically updates the map when a key is added to or erased from |
36 * the map. This map factory uses the allocators to implement |
36 /// the map. This map factory uses the allocators to implement |
37 * the container functionality. |
37 /// the container functionality. |
38 * |
38 /// |
39 * The template parameter is the AlterationNotifier that the maps |
39 /// The template parameter is the AlterationNotifier that the maps |
40 * will belong to and the Value. |
40 /// will belong to and the Value. |
41 */ |
41 |
42 |
42 |
43 template <typename _Graph, |
43 template <typename _Graph, |
44 typename _Item, |
44 typename _Item, |
45 typename _Value> |
45 typename _Value> |
46 class ArrayMap : public AlterationNotifier<_Item>::ObserverBase { |
46 class ArrayMap : public AlterationNotifier<_Item>::ObserverBase { |
66 typedef std::allocator<Value> Allocator; |
66 typedef std::allocator<Value> Allocator; |
67 |
67 |
68 |
68 |
69 public: |
69 public: |
70 |
70 |
71 /** Graph and Registry initialized map constructor. |
71 /// Graph and Registry initialized map constructor. |
72 */ |
72 |
73 ArrayMap(const Graph& _g) : graph(&_g) { |
73 ArrayMap(const Graph& _g) : graph(&_g) { |
74 Item it; |
74 Item it; |
75 attach(_g.getNotifier(Item())); |
75 attach(_g.getNotifier(Item())); |
76 allocate_memory(); |
76 allocate_memory(); |
77 for (graph->first(it); it != INVALID; graph->next(it)) { |
77 for (graph->first(it); it != INVALID; graph->next(it)) { |
92 int id = graph->id(it);; |
92 int id = graph->id(it);; |
93 allocator.construct(&(values[id]), _v); |
93 allocator.construct(&(values[id]), _v); |
94 } |
94 } |
95 } |
95 } |
96 |
96 |
97 /** Constructor to copy a map of the same map type. |
97 /// Constructor to copy a map of the same map type. |
98 */ |
98 |
99 ArrayMap(const ArrayMap& copy) : Parent() { |
99 ArrayMap(const ArrayMap& copy) : Parent() { |
100 if (copy.attached()) { |
100 if (copy.attached()) { |
101 attach(*copy.getRegistry()); |
101 attach(*copy.getRegistry()); |
102 } |
102 } |
103 capacity = copy.capacity; |
103 capacity = copy.capacity; |
112 |
112 |
113 using Parent::attach; |
113 using Parent::attach; |
114 using Parent::detach; |
114 using Parent::detach; |
115 using Parent::attached; |
115 using Parent::attached; |
116 |
116 |
117 /** Assign operator to copy a map of the same map type. |
117 /// Assign operator to copy a map of the same map type. |
118 */ |
118 |
119 ArrayMap& operator=(const ArrayMap& copy) { |
119 ArrayMap& operator=(const ArrayMap& copy) { |
120 if (© == this) return *this; |
120 if (© == this) return *this; |
121 |
121 |
122 if (graph != copy.graph) { |
122 if (graph != copy.graph) { |
123 if (attached()) { |
123 if (attached()) { |
139 } |
139 } |
140 |
140 |
141 return *this; |
141 return *this; |
142 } |
142 } |
143 |
143 |
144 /** The destructor of the map. |
144 /// The destructor of the map. |
145 */ |
145 |
146 virtual ~ArrayMap() { |
146 virtual ~ArrayMap() { |
147 if (attached()) { |
147 if (attached()) { |
148 clear(); |
148 clear(); |
149 detach(); |
149 detach(); |
150 } |
150 } |
151 } |
151 } |
152 |
152 |
153 |
153 |
154 /** |
154 ///The subscript operator. The map can be subscripted by the |
155 * The subscript operator. The map can be subscripted by the |
155 ///actual keys of the graph. |
156 * actual keys of the graph. |
156 |
157 */ |
|
158 Value& operator[](const Key& key) { |
157 Value& operator[](const Key& key) { |
159 int id = graph->id(key); |
158 int id = graph->id(key); |
160 return values[id]; |
159 return values[id]; |
161 } |
160 } |
162 |
161 |
163 /** |
162 |
164 * The const subscript operator. The map can be subscripted by the |
163 ///The const subscript operator. The map can be subscripted by the |
165 * actual keys of the graph. |
164 ///actual keys of the graph. |
166 */ |
165 |
167 const Value& operator[](const Key& key) const { |
166 const Value& operator[](const Key& key) const { |
168 int id = graph->id(key); |
167 int id = graph->id(key); |
169 return values[id]; |
168 return values[id]; |
170 } |
169 } |
171 |
170 |
172 /** Setter function of the map. Equivalent with map[key] = val. |
171 /// Setter function of the map. Equivalent with map[key] = val. |
173 * This is a compatibility feature with the not dereferable maps. |
172 /// This is a compatibility feature with the not dereferable maps. |
174 */ |
173 |
175 void set(const Key& key, const Value& val) { |
174 void set(const Key& key, const Value& val) { |
176 (*this)[key] = val; |
175 (*this)[key] = val; |
177 } |
176 } |
178 |
177 |
179 /** Add a new key to the map. It called by the map registry. |
178 /// Add a new key to the map. It called by the map registry. |
180 */ |
179 |
181 void add(const Key& key) { |
180 void add(const Key& key) { |
182 int id = graph->id(key); |
181 int id = graph->id(key); |
183 if (id >= capacity) { |
182 if (id >= capacity) { |
184 int new_capacity = (capacity == 0 ? 1 : capacity); |
183 int new_capacity = (capacity == 0 ? 1 : capacity); |
185 while (new_capacity <= id) { |
184 while (new_capacity <= id) { |
198 values = new_values; |
197 values = new_values; |
199 capacity = new_capacity; |
198 capacity = new_capacity; |
200 } |
199 } |
201 allocator.construct(&(values[id]), Value()); |
200 allocator.construct(&(values[id]), Value()); |
202 } |
201 } |
203 |
202 |
204 /** Erase a key from the map. It called by the map registry. |
203 void add(const std::vector<Key>& keys) { |
205 */ |
204 int max_id = -1; |
|
205 for (int i = 0; i < (int)keys.size(); ++i) { |
|
206 int id = graph->id(keys[i]); |
|
207 if (id > max_id) { |
|
208 max_id = id; |
|
209 } |
|
210 } |
|
211 if (max_id >= capacity) { |
|
212 int new_capacity = (capacity == 0 ? 1 : capacity); |
|
213 while (new_capacity <= max_id) { |
|
214 new_capacity <<= 1; |
|
215 } |
|
216 Value* new_values = allocator.allocate(new_capacity); |
|
217 Item it; |
|
218 for (graph->first(it); it != INVALID; graph->next(it)) { |
|
219 int id = graph->id(it); |
|
220 bool found = false; |
|
221 for (int i = 0; i < (int)keys.size(); ++i) { |
|
222 int jd = graph->id(keys[i]); |
|
223 if (id == jd) { |
|
224 found = true; |
|
225 break; |
|
226 } |
|
227 } |
|
228 if (found) continue; |
|
229 allocator.construct(&(new_values[id]), values[id]); |
|
230 allocator.destroy(&(values[id])); |
|
231 } |
|
232 if (capacity != 0) allocator.deallocate(values, capacity); |
|
233 values = new_values; |
|
234 capacity = new_capacity; |
|
235 } |
|
236 for (int i = 0; i < (int)keys.size(); ++i) { |
|
237 int id = graph->id(keys[i]); |
|
238 allocator.construct(&(values[id]), Value()); |
|
239 } |
|
240 } |
|
241 |
|
242 /// Erase a key from the map. It called by the map registry. |
|
243 |
206 void erase(const Key& key) { |
244 void erase(const Key& key) { |
207 int id = graph->id(key); |
245 int id = graph->id(key); |
208 allocator.destroy(&(values[id])); |
246 allocator.destroy(&(values[id])); |
|
247 } |
|
248 |
|
249 void erase(const std::vector<Key>& keys) { |
|
250 for (int i = 0; i < (int)keys.size(); ++i) { |
|
251 int id = graph->id(keys[i]); |
|
252 allocator.destroy(&(values[id])); |
|
253 } |
209 } |
254 } |
210 |
255 |
211 void build() { |
256 void build() { |
212 allocate_memory(); |
257 allocate_memory(); |
213 Item it; |
258 Item it; |
219 |
264 |
220 void clear() { |
265 void clear() { |
221 if (capacity != 0) { |
266 if (capacity != 0) { |
222 Item it; |
267 Item it; |
223 for (graph->first(it); it != INVALID; graph->next(it)) { |
268 for (graph->first(it); it != INVALID; graph->next(it)) { |
224 int id = graph->id(it);; |
269 int id = graph->id(it); |
225 allocator.destroy(&(values[id])); |
270 allocator.destroy(&(values[id])); |
226 } |
271 } |
227 allocator.deallocate(values, capacity); |
272 allocator.deallocate(values, capacity); |
228 capacity = 0; |
273 capacity = 0; |
229 } |
274 } |
230 } |
275 } |
231 |
276 |
232 const Graph* getGraph() { |
277 const Graph* getGraph() { |
233 return graph; |
278 return graph; |
234 } |
279 } |
235 |
|
236 // /// The stl compatible pair iterator of the map. |
|
237 // typedef MapIterator<ArrayMap> Iterator; |
|
238 // /// The stl compatible const pair iterator of the map. |
|
239 // typedef MapConstIterator<ArrayMap> ConstIterator; |
|
240 |
|
241 // /** Returns the begin iterator of the map. |
|
242 // */ |
|
243 // Iterator begin() { |
|
244 // return Iterator(*this, KeyIt(*MapBase::getGraph())); |
|
245 // } |
|
246 |
|
247 // /** Returns the end iterator of the map. |
|
248 // */ |
|
249 // Iterator end() { |
|
250 // return Iterator(*this, INVALID); |
|
251 // } |
|
252 |
|
253 // /** Returns the begin ConstIterator of the map. |
|
254 // */ |
|
255 // ConstIterator begin() const { |
|
256 // return ConstIterator(*this, KeyIt(*MapBase::getGraph())); |
|
257 // } |
|
258 |
|
259 // /** Returns the end const_iterator of the map. |
|
260 // */ |
|
261 // ConstIterator end() const { |
|
262 // return ConstIterator(*this, INVALID); |
|
263 // } |
|
264 |
|
265 // /// The KeySet of the Map. |
|
266 // typedef MapConstKeySet<ArrayMap> ConstKeySet; |
|
267 |
|
268 // /// KeySet getter function. |
|
269 // ConstKeySet keySet() const { |
|
270 // return ConstKeySet(*this); |
|
271 // } |
|
272 |
|
273 // /// The ConstValueSet of the Map. |
|
274 // typedef MapConstValueSet<ArrayMap> ConstValueSet; |
|
275 |
|
276 // /// ConstValueSet getter function. |
|
277 // ConstValueSet valueSet() const { |
|
278 // return ConstValueSet(*this); |
|
279 // } |
|
280 |
|
281 // /// The ValueSet of the Map. |
|
282 // typedef MapValueSet<ArrayMap> ValueSet; |
|
283 |
|
284 // /// ValueSet getter function. |
|
285 // ValueSet valueSet() { |
|
286 // return ValueSet(*this); |
|
287 // } |
|
288 |
280 |
289 private: |
281 private: |
290 |
282 |
291 void allocate_memory() { |
283 void allocate_memory() { |
292 int max_id = graph->maxId(_Item()); |
284 int max_id = graph->maxId(_Item()); |