COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/array_map.h @ 1703:eb90e3d6bddc

Last change on this file since 1703:eb90e3d6bddc was 1703:eb90e3d6bddc, checked in by Balazs Dezso, 14 years ago

Proper sized map type

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