COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/array_map.h @ 980:0f1044b7a3af

Last change on this file since 980:0f1044b7a3af was 980:0f1044b7a3af, checked in by Balazs Dezso, 16 years ago

maxNodeId() and maxEdgeId() changed to maxId(Node) and maxId(Edge)
getNodeObserverRegistry() and getEdgeObserverRegistry() changed to
getObserverRegistry(Node) and getObserverRegistry(Edge)

IdMappableGraphExtender? erased

File size: 10.2 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/array_map.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
6 *
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.
10 *
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
13 * purpose.
14 *
15 */
16
17#ifndef LEMON_ARRAY_MAP_H
18#define LEMON_ARRAY_MAP_H
19
20#include <memory>
21
22#include <lemon/map_iterator.h>
23
24///\ingroup graphmaps
25///\file
26///\brief Graph maps that construates and destruates
27///their elements dynamically.
28
29namespace lemon {
30
31
32  /// \addtogroup graphmaps
33  /// @{
34       
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.
39   *
40   *  The template parameter is the MapRegistry that the maps
41   *  will belong to and the ValueType.
42   */
43
44  template <typename _Graph,
45            typename _Item,
46            typename _ItemIt,
47            typename _Value>
48  class ArrayMap : public AlterationObserverRegistry<_Item>::ObserverBase {
49
50  public:
51               
52    /// The graph type of the maps.
53    typedef _Graph Graph;
54    /// The key type of the maps.
55    typedef _Item KeyType;
56
57    typedef AlterationObserverRegistry<_Item> Registry;
58
59  private:
60    /// The iterator to iterate on the keys.
61    typedef _ItemIt KeyIt;
62
63    typedef _Value Value;
64
65    /// The MapBase of the Map which imlements the core regisitry function.
66    typedef typename Registry::ObserverBase Parent;
67               
68   
69  public:
70
71    /// The value type of the map.
72    typedef Value ValueType;
73    /// The reference type of the map;
74    typedef Value& ReferenceType;
75    /// The pointer type of the map;
76    typedef Value* PointerType;
77
78    /// The const value type of the map.
79    typedef const Value ConstValueType;
80    /// The const reference type of the map;
81    typedef const Value& ConstReferenceType;
82    /// The pointer type of the map;
83    typedef const Value* ConstPointerType;
84
85
86  private:
87    typedef std::allocator<Value> Allocator;
88
89
90  public:
91
92    /** Graph and Registry initialized map constructor.
93     */
94    ArrayMap(const Graph& _g) : graph(&_g) {
95      attach(_g.getObserverRegistry(_Item()));
96      allocate_memory();
97      for (KeyIt it(*graph); it != INVALID; ++it) {
98        int id = graph->id(it);;
99        allocator.construct(&(values[id]), Value());
100      }                                                         
101    }
102
103    /// Constructor to use default value to initialize the map.
104
105    /// It constrates a map and initialize all of the the map.
106
107    ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) {
108      attach(_g.getObserverRegistry(_Item()));
109      allocate_memory();
110      for (KeyIt it(*graph); it != INVALID; ++it) {
111        int id = graph->id(it);;
112        allocator.construct(&(values[id]), _v);
113      }                                                         
114    }
115
116    /** Constructor to copy a map of the same map type.
117     */
118    ArrayMap(const ArrayMap& copy) {
119      if (copy.attached()) {
120        attach(*copy.getRegistry());
121      }
122      capacity = copy.capacity;
123      if (capacity == 0) return;
124      values = allocator.allocate(capacity);
125      for (KeyIt it(*graph); it != INVALID; ++it) {
126        int id = graph->id(it);;
127        allocator.construct(&(values[id]), copy.values[id]);
128      }
129    }
130
131    using Parent::attach;
132    using Parent::detach;
133    using Parent::attached;
134
135    /** Assign operator to copy a map of the same map type.
136     */
137    ArrayMap& operator=(const ArrayMap& copy) {
138      if (&copy == this) return *this;
139     
140      if (graph != copy.graph) {
141        if (attached()) {
142          clear();
143          detach();
144        }
145        if (copy.attached()) {
146          attach(*copy.getRegistry());
147        }
148        capacity = copy.capacity;
149        if (capacity == 0) return *this;
150        values = allocator.allocate(capacity);     
151      }
152
153      for (KeyIt it(*graph); it != INVALID; ++it) {
154        int id = graph->id(it);;
155        allocator.construct(&(values[id]), copy.values[id]);
156      }
157
158      return *this;
159    }
160
161    /** The destructor of the map.
162     */
163    virtual ~ArrayMap() {     
164      if (attached()) {
165        clear();
166        detach();
167      }
168    }
169       
170       
171    /**
172     * The subscript operator. The map can be subscripted by the
173     * actual keys of the graph.
174     */
175    ReferenceType operator[](const KeyType& key) {
176      int id = graph->id(key);
177      return values[id];
178    }
179               
180    /**
181     * The const subscript operator. The map can be subscripted by the
182     * actual keys of the graph.
183     */
184    ConstReferenceType operator[](const KeyType& key) const {
185      int id = graph->id(key);
186      return values[id];
187    }
188       
189    /** Setter function of the map. Equivalent with map[key] = val.
190     *  This is a compatibility feature with the not dereferable maps.
191     */
192    void set(const KeyType& key, const ValueType& val) {
193      (*this)[key] = val;
194    }
195               
196    /** Add a new key to the map. It called by the map registry.
197     */
198    void add(const KeyType& key) {
199      int id = graph->id(key);
200      if (id >= capacity) {
201        int new_capacity = (capacity == 0 ? 1 : capacity);
202        while (new_capacity <= id) {
203          new_capacity <<= 1;
204        }
205        Value* new_values = allocator.allocate(new_capacity);
206        for (KeyIt it(*graph); it != INVALID; ++it) {
207          int jd = graph->id(it);;
208          if (id != jd) {
209            allocator.construct(&(new_values[jd]), values[jd]);
210            allocator.destroy(&(values[jd]));
211          }
212        }
213        if (capacity != 0) allocator.deallocate(values, capacity);
214        values = new_values;
215        capacity = new_capacity;
216      }
217      allocator.construct(&(values[id]), Value());
218    }
219               
220    /** Erase a key from the map. It called by the map registry.
221     */
222    void erase(const KeyType& key) {
223      int id = graph->id(key);
224      allocator.destroy(&(values[id]));
225    }
226
227    void build() {
228      allocate_memory();
229      for (KeyIt it(*graph); it != INVALID; ++it) {
230        int id = graph->id(it);;
231        allocator.construct(&(values[id]), Value());
232      }                                                         
233    }
234
235    void clear() {     
236      if (capacity != 0) {
237        for (KeyIt it(*graph); it != INVALID; ++it) {
238          int id = graph->id(it);;
239          allocator.destroy(&(values[id]));
240        }                                                               
241        allocator.deallocate(values, capacity);
242        capacity = 0;
243      }
244    }
245
246//     /// The stl compatible pair iterator of the map.
247//     typedef MapIterator<ArrayMap> Iterator;
248//     /// The stl compatible const pair iterator of the map.
249//     typedef MapConstIterator<ArrayMap> ConstIterator;
250
251//     /** Returns the begin iterator of the map.
252//      */
253//     Iterator begin() {
254//       return Iterator(*this, KeyIt(*MapBase::getGraph()));
255//     }
256
257//     /** Returns the end iterator of the map.
258//      */
259//     Iterator end() {
260//       return Iterator(*this, INVALID);
261//     }
262
263//     /** Returns the begin ConstIterator of the map.
264//      */
265//     ConstIterator begin() const {
266//       return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
267//     }
268
269//     /** Returns the end const_iterator of the map.
270//      */
271//     ConstIterator end() const {
272//       return ConstIterator(*this, INVALID);
273//     }
274
275//     /// The KeySet of the Map.
276//     typedef MapConstKeySet<ArrayMap> ConstKeySet;
277
278//     /// KeySet getter function.
279//     ConstKeySet keySet() const {
280//       return ConstKeySet(*this);
281//     }
282
283//     /// The ConstValueSet of the Map.
284//     typedef MapConstValueSet<ArrayMap> ConstValueSet;
285
286//     /// ConstValueSet getter function.
287//     ConstValueSet valueSet() const {
288//       return ConstValueSet(*this);
289//     }
290
291//     /// The ValueSet of the Map.
292//     typedef MapValueSet<ArrayMap> ValueSet;
293
294//     /// ValueSet getter function.
295//     ValueSet valueSet() {
296//       return ValueSet(*this);
297//     }
298
299  private:
300     
301    void allocate_memory() {
302      int max_id = graph->maxId(_Item());
303      if (max_id == -1) {
304        capacity = 0;
305        values = 0;
306        return;
307      }
308      capacity = 1;
309      while (capacity <= max_id) {
310        capacity <<= 1;
311      }
312      values = allocator.allocate(capacity);   
313    }     
314
315    const Graph* graph;
316    int capacity;
317    Value* values;
318    Allocator allocator;
319
320  public:
321//     // STL  compatibility typedefs.
322//     typedef Iterator iterator;
323//     typedef ConstIterator const_iterator;
324//     typedef typename Iterator::PairValueType value_type;
325//     typedef typename Iterator::KeyType key_type;
326//     typedef typename Iterator::ValueType data_type;
327//     typedef typename Iterator::PairReferenceType reference;
328//     typedef typename Iterator::PairPointerType pointer;
329//     typedef typename ConstIterator::PairReferenceType const_reference;
330//     typedef typename ConstIterator::PairPointerType const_pointer;
331//     typedef int difference_type;             
332  };           
333
334  template <typename _Base>
335  class ArrayMappableGraphExtender : public _Base {
336  public:
337
338    typedef ArrayMappableGraphExtender<_Base> Graph;
339    typedef _Base Parent;
340
341    typedef typename Parent::Node Node;
342    typedef typename Parent::NodeIt NodeIt;
343    typedef typename Parent::NodeObserverRegistry NodeObserverRegistry;
344
345    typedef typename Parent::Edge Edge;
346    typedef typename Parent::EdgeIt EdgeIt;
347    typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry;
348
349   
350
351    template <typename _Value>
352    class NodeMap : public ArrayMap<Graph, Node, NodeIt, _Value> {
353    public:
354      typedef ArrayMappableGraphExtender<_Base> Graph;
355
356      typedef typename Graph::Node Node;
357      typedef typename Graph::NodeIt NodeIt;
358
359      typedef ArrayMap<Graph, Node, NodeIt, _Value> Parent;
360
361      //typedef typename Parent::Graph Graph;
362      typedef typename Parent::Value Value;
363
364      NodeMap(const Graph& g)
365        : Parent(g) {}
366      NodeMap(const Graph& g, const Value& v)
367        : Parent(g, v) {}
368
369    };
370
371    template <typename _Value>
372    class EdgeMap : public ArrayMap<Graph, Edge, EdgeIt, _Value> {
373    public:
374      typedef ArrayMappableGraphExtender<_Base> Graph;
375
376      typedef typename Graph::Edge Edge;
377      typedef typename Graph::EdgeIt EdgeIt;
378
379      typedef ArrayMap<Graph, Edge, EdgeIt, _Value> Parent;
380
381      //typedef typename Parent::Graph Graph;
382      typedef typename Parent::Value Value;
383
384      EdgeMap(const Graph& g)
385        : Parent(g) {}
386      EdgeMap(const Graph& g, const Value& v)
387        : Parent(g, v) {}
388
389    };
390   
391  };
392
393/// @}
394
395}
396
397#endif //LEMON_ARRAY_MAP_H
Note: See TracBrowser for help on using the repository browser.