COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/array_map.h @ 1791:62e7d237e1fb

Last change on this file since 1791:62e7d237e1fb was 1719:674182524bd9, checked in by Balazs Dezso, 14 years ago

Traits moved to own file
Tag for reference maps
Possibility to handle proper the return type
of the operator[]() const -- value or reference

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