COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/array_map.h @ 1284:b941d044f87b

Last change on this file since 1284:b941d044f87b was 1271:40e5d0d44a65, checked in by Balazs Dezso, 15 years ago

Some bug fix

File size: 9.3 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/array_map.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 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#include <lemon/map_iterator.h>
22
23///\ingroup graphmaps
24///\file
25///\brief Graph maps that construates and destruates
26///their elements dynamically.
27
28namespace lemon {
29
30
31  /// \addtogroup graphmaps
32  /// @{
33       
34  /** The ArrayMap template class is graph map structure what
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
37   *  the container functionality.
38   *
39   *  The template parameter is the AlterationNotifier that the maps
40   *  will belong to and the Value.
41   */
42
43  template <typename _Graph,
44            typename _Item,
45            typename _Value>
46  class ArrayMap : public AlterationNotifier<_Item>::ObserverBase {
47
48    typedef _Item Item;
49  public:
50               
51    /// The graph type of the maps.
52    typedef _Graph Graph;
53    /// The key type of the maps.
54    typedef _Item Key;
55
56    typedef AlterationNotifier<_Item> Registry;
57
58    /// The MapBase of the Map which imlements the core regisitry function.
59    typedef typename Registry::ObserverBase Parent;
60               
61    /// The value type of the map.
62    typedef _Value Value;
63
64
65  private:
66    typedef std::allocator<Value> Allocator;
67
68
69  public:
70
71    /** Graph and Registry initialized map constructor.
72     */
73    ArrayMap(const Graph& _g) : graph(&_g) {
74      Item it;
75      attach(_g.getNotifier(Item()));
76      allocate_memory();
77      for (graph->first(it); it != INVALID; graph->next(it)) {
78        int id = graph->id(it);;
79        allocator.construct(&(values[id]), Value());
80      }                                                         
81    }
82
83    /// Constructor to use default value to initialize the map.
84
85    /// It constrates a map and initialize all of the the map.
86
87    ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) {
88      Item it;
89      attach(_g.getNotifier(_Item()));
90      allocate_memory();
91      for (graph->first(it); it != INVALID; graph->next(it)) {
92        int id = graph->id(it);;
93        allocator.construct(&(values[id]), _v);
94      }                                                         
95    }
96
97    /** Constructor to copy a map of the same map type.
98     */
99    ArrayMap(const ArrayMap& copy) {
100      if (copy.attached()) {
101        attach(*copy.getRegistry());
102      }
103      capacity = copy.capacity;
104      if (capacity == 0) return;
105      values = allocator.allocate(capacity);
106      Item it;
107      for (graph->first(it); it != INVALID; graph->next(it)) {
108        int id = graph->id(it);;
109        allocator.construct(&(values[id]), copy.values[id]);
110      }
111    }
112
113    using Parent::attach;
114    using Parent::detach;
115    using Parent::attached;
116
117    /** Assign operator to copy a map of the same map type.
118     */
119    ArrayMap& operator=(const ArrayMap& copy) {
120      if (&copy == this) return *this;
121     
122      if (graph != copy.graph) {
123        if (attached()) {
124          clear();
125          detach();
126        }
127        if (copy.attached()) {
128          attach(*copy.getRegistry());
129        }
130        capacity = copy.capacity;
131        if (capacity == 0) return *this;
132        values = allocator.allocate(capacity);     
133      }
134
135      Item it;
136      for (graph->first(it); it != INVALID; graph->next(it)) {
137        int id = graph->id(it);;
138        allocator.construct(&(values[id]), copy.values[id]);
139      }
140
141      return *this;
142    }
143
144    /** The destructor of the map.
145     */
146    virtual ~ArrayMap() {     
147      if (attached()) {
148        clear();
149        detach();
150      }
151    }
152       
153       
154    /**
155     * The subscript operator. The map can be subscripted by the
156     * actual keys of the graph.
157     */
158    Value& operator[](const Key& key) {
159      int id = graph->id(key);
160      return values[id];
161    }
162               
163    /**
164     * The const subscript operator. The map can be subscripted by the
165     * actual keys of the graph.
166     */
167    const Value& operator[](const Key& key) const {
168      int id = graph->id(key);
169      return values[id];
170    }
171       
172    /** Setter function of the map. Equivalent with map[key] = val.
173     *  This is a compatibility feature with the not dereferable maps.
174     */
175    void set(const Key& key, const Value& val) {
176      (*this)[key] = val;
177    }
178               
179    /** Add a new key to the map. It called by the map registry.
180     */
181    void add(const Key& key) {
182      int id = graph->id(key);
183      if (id >= capacity) {
184        int new_capacity = (capacity == 0 ? 1 : capacity);
185        while (new_capacity <= id) {
186          new_capacity <<= 1;
187        }
188        Value* new_values = allocator.allocate(new_capacity);
189        Item it;
190        for (graph->first(it); it != INVALID; graph->next(it)) {
191          int jd = graph->id(it);;
192          if (id != jd) {
193            allocator.construct(&(new_values[jd]), values[jd]);
194            allocator.destroy(&(values[jd]));
195          }
196        }
197        if (capacity != 0) allocator.deallocate(values, capacity);
198        values = new_values;
199        capacity = new_capacity;
200      }
201      allocator.construct(&(values[id]), Value());
202    }
203               
204    /** Erase a key from the map. It called by the map registry.
205     */
206    void erase(const Key& key) {
207      int id = graph->id(key);
208      allocator.destroy(&(values[id]));
209    }
210
211    void build() {
212      allocate_memory();
213      Item it;
214      for (graph->first(it); it != INVALID; graph->next(it)) {
215        int id = graph->id(it);;
216        allocator.construct(&(values[id]), Value());
217      }                                                         
218    }
219
220    void clear() {     
221      if (capacity != 0) {
222        Item it;
223        for (graph->first(it); it != INVALID; graph->next(it)) {
224          int id = graph->id(it);;
225          allocator.destroy(&(values[id]));
226        }                                                               
227        allocator.deallocate(values, capacity);
228        capacity = 0;
229      }
230    }
231
232    const Graph* getGraph() {
233      return graph;
234    }
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
289  private:
290     
291    void allocate_memory() {
292      int max_id = graph->maxId(_Item());
293      if (max_id == -1) {
294        capacity = 0;
295        values = 0;
296        return;
297      }
298      capacity = 1;
299      while (capacity <= max_id) {
300        capacity <<= 1;
301      }
302      values = allocator.allocate(capacity);   
303    }     
304
305    const Graph* graph;
306    int capacity;
307    Value* values;
308    Allocator allocator;
309
310  };           
311
312  template <typename _Base>
313  class ArrayMappableGraphExtender : public _Base {
314  public:
315
316    typedef ArrayMappableGraphExtender<_Base> Graph;
317    typedef _Base Parent;
318
319    typedef typename Parent::Node Node;
320    typedef typename Parent::NodeIt NodeIt;
321    typedef typename Parent::NodeNotifier NodeObserverRegistry;
322
323    typedef typename Parent::Edge Edge;
324    typedef typename Parent::EdgeIt EdgeIt;
325    typedef typename Parent::EdgeNotifier EdgeObserverRegistry;
326
327   
328
329    template <typename _Value>
330    class NodeMap
331      : public IterableMapExtender<ArrayMap<Graph, Node, _Value> > {
332    public:
333      typedef ArrayMappableGraphExtender<_Base> Graph;
334
335      typedef typename Graph::Node Node;
336      typedef typename Graph::NodeIt NodeIt;
337
338      typedef IterableMapExtender<ArrayMap<Graph, Node, _Value> > Parent;
339
340      //typedef typename Parent::Graph Graph;
341      typedef typename Parent::Value Value;
342
343      NodeMap(const Graph& g)
344        : Parent(g) {}
345      NodeMap(const Graph& g, const Value& v)
346        : Parent(g, v) {}
347
348    };
349
350    template <typename _Value>
351    class EdgeMap
352      : public IterableMapExtender<ArrayMap<Graph, Edge, _Value> > {
353    public:
354      typedef ArrayMappableGraphExtender<_Base> Graph;
355
356      typedef typename Graph::Edge Edge;
357      typedef typename Graph::EdgeIt EdgeIt;
358
359      typedef IterableMapExtender<ArrayMap<Graph, Edge, _Value> > Parent;
360
361      //typedef typename Parent::Graph Graph;
362      typedef typename Parent::Value Value;
363
364      EdgeMap(const Graph& g)
365        : Parent(g) {}
366      EdgeMap(const Graph& g, const Value& v)
367        : Parent(g, v) {}
368
369    };
370   
371  };
372
373/// @}
374
375}
376
377#endif //LEMON_ARRAY_MAP_H
Note: See TracBrowser for help on using the repository browser.