The graph_factory branch (@ 1321) has been merged to trunk.
2 * src/lemon/array_map.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #ifndef LEMON_ARRAY_MAP_H
18 #define LEMON_ARRAY_MAP_H
22 #include <lemon/map_iterator.h>
26 ///\brief Graph maps that construates and destruates
27 ///their elements dynamically.
32 /// \addtogroup graphmaps
35 /** The ArrayMap template class is graph map structure what
36 * automatically updates the map when a key is added to or erased from
37 * the map. This map factory uses the allocators to implement
38 * the container functionality.
40 * The template parameter is the MapRegistry that the maps
41 * will belong to and the ValueType.
44 template <typename _Graph,
49 class ArrayMap : public AlterationObserverRegistry<_Item>::ObserverBase {
53 /// The graph type of the maps.
55 /// The key type of the maps.
56 typedef _Item KeyType;
58 typedef AlterationObserverRegistry<_Item> Registry;
61 /// The iterator to iterate on the keys.
62 typedef _ItemIt KeyIt;
68 /// The MapBase of the Map which imlements the core regisitry function.
69 typedef typename Registry::ObserverBase Parent;
74 /// The value type of the map.
75 typedef Value ValueType;
76 /// The reference type of the map;
77 typedef Value& ReferenceType;
78 /// The pointer type of the map;
79 typedef Value* PointerType;
81 /// The const value type of the map.
82 typedef const Value ConstValueType;
83 /// The const reference type of the map;
84 typedef const Value& ConstReferenceType;
85 /// The pointer type of the map;
86 typedef const Value* ConstPointerType;
90 typedef std::allocator<Value> Allocator;
95 /** Graph and Registry initialized map constructor.
97 ArrayMap(const Graph& _g, Registry& _r) : graph(&_g) {
100 for (KeyIt it(*graph); it != INVALID; ++it) {
101 int id = IdMap(*graph)[it];
102 allocator.construct(&(values[id]), Value());
106 /// Constructor to use default value to initialize the map.
108 /// It constrates a map and initialize all of the the map.
110 ArrayMap(const Graph& _g, Registry& _r, const Value& _v) : graph(&_g) {
113 for (KeyIt it(*graph); it != INVALID; ++it) {
114 int id = IdMap(*graph)[it];
115 allocator.construct(&(values[id]), _v);
119 /** Constructor to copy a map of the same map type.
121 ArrayMap(const ArrayMap& copy) {
122 if (copy.attached()) {
123 attach(*copy.getRegistry());
125 capacity = copy.capacity;
126 if (capacity == 0) return;
127 values = allocator.allocate(capacity);
128 for (KeyIt it(*graph); it != INVALID; ++it) {
129 int id = IdMap(*graph)[it];
130 allocator.construct(&(values[id]), copy.values[id]);
134 /** Assign operator to copy a map of the same map type.
136 ArrayMap& operator=(const ArrayMap& copy) {
137 if (© == this) return *this;
139 if (graph != copy.graph) {
144 if (copy.attached()) {
145 attach(*copy.getRegistry());
147 capacity = copy.capacity;
148 if (capacity == 0) return *this;
149 values = allocator.allocate(capacity);
152 for (KeyIt it(*graph); it != INVALID; ++it) {
153 int id = IdMap(*graph)[it];
154 allocator.construct(&(values[id]), copy.values[id]);
160 /** The destructor of the map.
162 virtual ~ArrayMap() {
171 * The subscript operator. The map can be subscripted by the
172 * actual keys of the graph.
174 ReferenceType operator[](const KeyType& key) {
175 int id = IdMap(*graph)[key];
180 * The const subscript operator. The map can be subscripted by the
181 * actual keys of the graph.
183 ConstReferenceType operator[](const KeyType& key) const {
184 int id = IdMap(*graph)[key];
188 /** Setter function of the map. Equivalent with map[key] = val.
189 * This is a compatibility feature with the not dereferable maps.
191 void set(const KeyType& key, const ValueType& val) {
195 /** Add a new key to the map. It called by the map registry.
197 void add(const KeyType& key) {
198 int id = IdMap(*graph)[key];
199 if (id >= capacity) {
200 int new_capacity = (capacity == 0 ? 1 : capacity);
201 while (new_capacity <= id) {
204 Value* new_values = allocator.allocate(new_capacity);
205 for (KeyIt it(*graph); it != INVALID; ++it) {
206 int jd = IdMap(*graph)[it];
208 allocator.construct(&(new_values[jd]), values[jd]);
209 allocator.destroy(&(values[jd]));
212 if (capacity != 0) allocator.deallocate(values, capacity);
214 capacity = new_capacity;
216 allocator.construct(&(values[id]), Value());
219 /** Erase a key from the map. It called by the map registry.
221 void erase(const KeyType& key) {
222 int id = IdMap(*graph)[key];
223 allocator.destroy(&(values[id]));
228 for (KeyIt it(*graph); it != INVALID; ++it) {
229 int id = IdMap(*graph)[it];
230 allocator.construct(&(values[id]), Value());
236 for (KeyIt it(*graph); it != INVALID; ++it) {
237 int id = IdMap(*graph)[it];
238 allocator.destroy(&(values[id]));
240 allocator.deallocate(values, capacity);
245 // /// The stl compatible pair iterator of the map.
246 // typedef MapIterator<ArrayMap> Iterator;
247 // /// The stl compatible const pair iterator of the map.
248 // typedef MapConstIterator<ArrayMap> ConstIterator;
250 // /** Returns the begin iterator of the map.
252 // Iterator begin() {
253 // return Iterator(*this, KeyIt(*MapBase::getGraph()));
256 // /** Returns the end iterator of the map.
259 // return Iterator(*this, INVALID);
262 // /** Returns the begin ConstIterator of the map.
264 // ConstIterator begin() const {
265 // return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
268 // /** Returns the end const_iterator of the map.
270 // ConstIterator end() const {
271 // return ConstIterator(*this, INVALID);
274 // /// The KeySet of the Map.
275 // typedef MapConstKeySet<ArrayMap> ConstKeySet;
277 // /// KeySet getter function.
278 // ConstKeySet keySet() const {
279 // return ConstKeySet(*this);
282 // /// The ConstValueSet of the Map.
283 // typedef MapConstValueSet<ArrayMap> ConstValueSet;
285 // /// ConstValueSet getter function.
286 // ConstValueSet valueSet() const {
287 // return ConstValueSet(*this);
290 // /// The ValueSet of the Map.
291 // typedef MapValueSet<ArrayMap> ValueSet;
293 // /// ValueSet getter function.
294 // ValueSet valueSet() {
295 // return ValueSet(*this);
300 void allocate_memory() {
301 int max_id = IdMap(*graph).maxId();
308 while (capacity <= max_id) {
311 values = allocator.allocate(capacity);
320 // // STL compatibility typedefs.
321 // typedef Iterator iterator;
322 // typedef ConstIterator const_iterator;
323 // typedef typename Iterator::PairValueType value_type;
324 // typedef typename Iterator::KeyType key_type;
325 // typedef typename Iterator::ValueType data_type;
326 // typedef typename Iterator::PairReferenceType reference;
327 // typedef typename Iterator::PairPointerType pointer;
328 // typedef typename ConstIterator::PairReferenceType const_reference;
329 // typedef typename ConstIterator::PairPointerType const_pointer;
330 // typedef int difference_type;
333 template <typename _Base>
334 class ArrayMappableGraphExtender : public _Base {
337 typedef ArrayMappableGraphExtender<_Base> Graph;
338 typedef _Base Parent;
340 typedef typename Parent::Node Node;
341 typedef typename Parent::NodeIt NodeIt;
342 typedef typename Parent::NodeIdMap NodeIdMap;
343 typedef typename Parent::NodeObserverRegistry NodeObserverRegistry;
345 typedef typename Parent::Edge Edge;
346 typedef typename Parent::EdgeIt EdgeIt;
347 typedef typename Parent::EdgeIdMap EdgeIdMap;
348 typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry;
352 template <typename _Value>
353 class NodeMap : public ArrayMap<Graph, Node, NodeIt, NodeIdMap, _Value> {
355 typedef ArrayMappableGraphExtender<_Base> Graph;
357 typedef typename Graph::Node Node;
358 typedef typename Graph::NodeIt NodeIt;
359 typedef typename Graph::NodeIdMap NodeIdMap;
361 typedef ArrayMap<Graph, Node, NodeIt, NodeIdMap, _Value> Parent;
363 typedef typename Parent::Graph Graph;
364 typedef typename Parent::Value Value;
366 NodeMap(const Graph& g)
367 : Parent(g, g.getNodeObserverRegistry()) {}
368 NodeMap(const Graph& g, const Value& v)
369 : Parent(g, g.getNodeObserverRegistry(), v) {}
373 template <typename _Value>
374 class EdgeMap : public ArrayMap<Graph, Edge, EdgeIt, EdgeIdMap, _Value> {
376 typedef ArrayMappableGraphExtender<_Base> Graph;
378 typedef typename Graph::Edge Edge;
379 typedef typename Graph::EdgeIt EdgeIt;
380 typedef typename Graph::EdgeIdMap EdgeIdMap;
382 typedef ArrayMap<Graph, Edge, EdgeIt, EdgeIdMap, _Value> Parent;
384 typedef typename Parent::Graph Graph;
385 typedef typename Parent::Value Value;
387 EdgeMap(const Graph& g)
388 : Parent(g, g.getEdgeObserverRegistry()) {}
389 EdgeMap(const Graph& g, const Value& v)
390 : Parent(g, g.getEdgeObserverRegistry(), v) {}
400 #endif //LEMON_ARRAY_MAP_H