COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/array_map.h @ 1813:5c5d1574667d

Last change on this file since 1813:5c5d1574667d was 1813:5c5d1574667d, checked in by Balazs Dezso, 14 years ago

Bug fix

File size: 7.8 KB
Line 
1/* -*- C++ -*-
2 * lemon/bits/array_map.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, 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/bits/map_extender.h>
22#include <lemon/bits/alteration_notifier.h>
23#include <lemon/concept_check.h>
24#include <lemon/concept/maps.h>
25
26/// \ingroup graphmapfactory
27/// \file
28/// \brief Graph maps that construct and destruct
29/// their elements dynamically.
30
31namespace lemon {
32
33  /// \ingroup graphmapfactory
34  ///
35  /// \brief Graph map based on the array storage.
36  ///
37  /// The ArrayMap template class is graph map structure what
38  /// automatically updates the map when a key is added to or erased from
39  /// the map. This map uses the allocators to implement
40  /// the container functionality.
41  ///
42  /// The template parameter is the AlterationNotifier that the maps
43  /// will belong to and the Value.
44
45  template <typename _Graph,
46            typename _Item,
47            typename _Value>
48  class ArrayMap : public AlterationNotifier<_Item>::ObserverBase {
49
50    typedef _Item Item;
51  public:
52    /// The graph type of the maps.
53    typedef _Graph Graph;
54    /// The reference map tag.
55    typedef True ReferenceMapTag;
56
57    /// The key type of the maps.
58    typedef _Item Key;
59    /// The value type of the map.
60    typedef _Value Value;
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    typedef const Value ConstValue;
67    typedef Value* Pointer;
68    typedef const Value* ConstPointer;
69
70    typedef AlterationNotifier<_Item> Registry;
71
72    /// The MapBase of the Map which imlements the core regisitry function.
73    typedef typename Registry::ObserverBase Parent;
74               
75
76
77  private:
78    typedef std::allocator<Value> Allocator;
79
80
81  public:
82
83    /// \brief Graph initialized map constructor.
84    ///
85    /// Graph initialized map constructor.
86    ArrayMap(const Graph& _g) : graph(&_g) {
87      Item it;
88      attach(_g.getNotifier(Item()));
89      allocate_memory();
90      for (graph->first(it); it != INVALID; graph->next(it)) {
91        int id = graph->id(it);;
92        allocator.construct(&(values[id]), Value());
93      }                                                         
94    }
95
96    /// \brief Constructor to use default value to initialize the map.
97    ///
98    /// It constructs a map and initialize all of the the map.
99    ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) {
100      Item it;
101      attach(_g.getNotifier(_Item()));
102      allocate_memory();
103      for (graph->first(it); it != INVALID; graph->next(it)) {
104        int id = graph->id(it);;
105        allocator.construct(&(values[id]), _v);
106      }                                                         
107    }
108
109    /// \brief Constructor to copy a map of the same map type.
110    ///
111    /// Constructor to copy a map of the same map type.     
112    ArrayMap(const ArrayMap& copy) : Parent(), graph(copy.graph) {
113      if (copy.attached()) {
114        attach(*copy.getRegistry());
115      }
116      capacity = copy.capacity;
117      if (capacity == 0) return;
118      values = allocator.allocate(capacity);
119      Item it;
120      for (graph->first(it); it != INVALID; graph->next(it)) {
121        int id = graph->id(it);;
122        allocator.construct(&(values[id]), copy.values[id]);
123      }
124    }
125
126    /// \brief The destructor of the map.
127    ///     
128    /// The destructor of the map.
129    virtual ~ArrayMap() {     
130      if (attached()) {
131        clear();
132        detach();
133      }
134    }
135               
136  private:
137
138    ArrayMap& operator=(const ArrayMap&);
139
140  protected:
141
142    using Parent::attach;
143    using Parent::detach;
144    using Parent::attached;
145
146    const Graph* getGraph() {
147      return graph;
148    }
149
150
151  public:
152
153    /// \brief The subscript operator.
154    ///
155    /// The subscript operator. The map can be subscripted by the
156    /// actual keys of the graph.
157    Value& operator[](const Key& key) {
158      int id = graph->id(key);
159      return values[id];
160    }
161               
162    /// \brief The const subscript operator.
163    ///
164    /// The const subscript operator. The map can be subscripted by the
165    /// actual keys of the graph.
166    const Value& operator[](const Key& key) const {
167      int id = graph->id(key);
168      return values[id];
169    }
170
171    /// \brief Setter function of the map.
172    ///
173    /// Setter function of the map. Equivalent with map[key] = val.
174    /// This is a compatibility feature with the not dereferable maps.
175    void set(const Key& key, const Value& val) {
176      (*this)[key] = val;
177    }
178
179  protected:
180
181    /// Add a new key to the map. It called by the map registry.
182         
183    virtual void add(const Key& key) {
184      int id = graph->id(key);
185      if (id >= capacity) {
186        int new_capacity = (capacity == 0 ? 1 : capacity);
187        while (new_capacity <= id) {
188          new_capacity <<= 1;
189        }
190        Value* new_values = allocator.allocate(new_capacity);
191        Item it;
192        for (graph->first(it); it != INVALID; graph->next(it)) {
193          int jd = graph->id(it);;
194          if (id != jd) {
195            allocator.construct(&(new_values[jd]), values[jd]);
196            allocator.destroy(&(values[jd]));
197          }
198        }
199        if (capacity != 0) allocator.deallocate(values, capacity);
200        values = new_values;
201        capacity = new_capacity;
202      }
203      allocator.construct(&(values[id]), Value());
204    }
205
206    virtual void add(const std::vector<Key>& keys) {
207      int max_id = -1;
208      for (int i = 0; i < (int)keys.size(); ++i) {
209        int id = graph->id(keys[i]);
210        if (id > max_id) {
211          max_id = id;
212        }
213      }
214      if (max_id >= capacity) {
215        int new_capacity = (capacity == 0 ? 1 : capacity);
216        while (new_capacity <= max_id) {
217          new_capacity <<= 1;
218        }
219        Value* new_values = allocator.allocate(new_capacity);
220        Item it;
221        for (graph->first(it); it != INVALID; graph->next(it)) {
222          int id = graph->id(it);
223          bool found = false;
224          for (int i = 0; i < (int)keys.size(); ++i) {
225            int jd = graph->id(keys[i]);
226            if (id == jd) {
227              found = true;
228              break;
229            }
230          }
231          if (found) continue;
232          allocator.construct(&(new_values[id]), values[id]);
233          allocator.destroy(&(values[id]));
234        }
235        if (capacity != 0) allocator.deallocate(values, capacity);
236        values = new_values;
237        capacity = new_capacity;
238      }
239      for (int i = 0; i < (int)keys.size(); ++i) {
240        int id = graph->id(keys[i]);
241        allocator.construct(&(values[id]), Value());
242      }
243    }
244               
245    /// Erase a key from the map. It called by the map registry.
246     
247    virtual void erase(const Key& key) {
248      int id = graph->id(key);
249      allocator.destroy(&(values[id]));
250    }
251
252    virtual void erase(const std::vector<Key>& keys) {
253      for (int i = 0; i < (int)keys.size(); ++i) {
254        int id = graph->id(keys[i]);
255        allocator.destroy(&(values[id]));
256      }
257    }
258
259    virtual void build() {
260      allocate_memory();
261      Item it;
262      for (graph->first(it); it != INVALID; graph->next(it)) {
263        int id = graph->id(it);;
264        allocator.construct(&(values[id]), Value());
265      }                                                         
266    }
267
268    virtual void clear() {     
269      if (capacity != 0) {
270        Item it;
271        for (graph->first(it); it != INVALID; graph->next(it)) {
272          int id = graph->id(it);
273          allocator.destroy(&(values[id]));
274        }                                                               
275        allocator.deallocate(values, capacity);
276        capacity = 0;
277      }
278    }
279
280  private:
281     
282    void allocate_memory() {
283      int max_id = graph->maxId(_Item());
284      if (max_id == -1) {
285        capacity = 0;
286        values = 0;
287        return;
288      }
289      capacity = 1;
290      while (capacity <= max_id) {
291        capacity <<= 1;
292      }
293      values = allocator.allocate(capacity);   
294    }     
295
296    const Graph* graph;
297    int capacity;
298    Value* values;
299    Allocator allocator;
300
301  };           
302
303}
304
305#endif //LEMON_ARRAY_MAP_H
Note: See TracBrowser for help on using the repository browser.