COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/array_map.h @ 1993:2115143eceea

Last change on this file since 1993:2115143eceea was 1956:a055123339d5, checked in by Alpar Juttner, 18 years ago

Unified copyright notices

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