COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/array_map.h @ 2000:ebcc93ead7da

Last change on this file since 2000:ebcc93ead7da was 1999:2ff283124dfc, checked in by Balazs Dezso, 14 years ago

Clarifing alteration observing system
It is directly connected now to a container

File size: 9.1 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_BITS_ARRAY_MAP_H
20#define LEMON_BITS_ARRAY_MAP_H
21
22#include <memory>
23
24#include <lemon/bits/traits.h>
25#include <lemon/bits/alteration_notifier.h>
26
27/// \ingroup graphbits
28/// \file
29/// \brief Graph map based on the array storage.
30
31namespace lemon {
32
33  /// \ingroup graphbits
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 Graph the current Item type and
43  /// the Value type of the map.
44  template <typename _Graph, typename _Item, typename _Value>
45  class ArrayMap
46    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
47  public:
48    /// The graph type of the maps.
49    typedef _Graph Graph;
50    /// The item type of the map.
51    typedef _Item Item;
52    /// The reference map tag.
53    typedef True ReferenceMapTag;
54
55    /// The key type of the maps.
56    typedef _Item Key;
57    /// The value type of the map.
58    typedef _Value Value;
59
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    /// The notifier type.
66    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
67
68    /// The MapBase of the Map which imlements the core regisitry function.
69    typedef typename Notifier::ObserverBase Parent;
70               
71  private:
72    typedef std::allocator<Value> Allocator;
73
74  public:
75
76    /// \brief Graph initialized map constructor.
77    ///
78    /// Graph initialized map constructor.
79    ArrayMap(const Graph& graph) {
80      Parent::attach(graph.getNotifier(Item()));
81      allocate_memory();
82      Notifier* notifier = Parent::getNotifier();
83      Item it;
84      for (notifier->first(it); it != INVALID; notifier->next(it)) {
85        int id = notifier->id(it);;
86        allocator.construct(&(values[id]), Value());
87      }                                                         
88    }
89
90    /// \brief Constructor to use default value to initialize the map.
91    ///
92    /// It constructs a map and initialize all of the the map.
93    ArrayMap(const Graph& graph, const Value& value) {
94      Parent::attach(graph.getNotifier(Item()));
95      allocate_memory();
96      Notifier* notifier = Parent::getNotifier();
97      Item it;
98      for (notifier->first(it); it != INVALID; notifier->next(it)) {
99        int id = notifier->id(it);;
100        allocator.construct(&(values[id]), value);
101      }                                                         
102    }
103
104    /// \brief Constructor to copy a map of the same map type.
105    ///
106    /// Constructor to copy a map of the same map type.     
107    ArrayMap(const ArrayMap& copy) : Parent() {
108      if (copy.attached()) {
109        attach(*copy.getNotifier());
110      }
111      capacity = copy.capacity;
112      if (capacity == 0) return;
113      values = allocator.allocate(capacity);
114      Notifier* notifier = Parent::getNotifier();
115      Item it;
116      for (notifier->first(it); it != INVALID; notifier->next(it)) {
117        int id = notifier->id(it);;
118        allocator.construct(&(values[id]), copy.values[id]);
119      }
120    }
121
122    /// \brief The destructor of the map.
123    ///     
124    /// The destructor of the map.
125    virtual ~ArrayMap() {     
126      if (attached()) {
127        clear();
128        detach();
129      }
130    }
131               
132  private:
133
134    ArrayMap& operator=(const ArrayMap&);
135
136  protected:
137
138    using Parent::attach;
139    using Parent::detach;
140    using Parent::attached;
141
142  public:
143
144    /// \brief The subscript operator.
145    ///
146    /// The subscript operator. The map can be subscripted by the
147    /// actual keys of the graph.
148    Value& operator[](const Key& key) {
149      int id = Parent::getNotifier()->id(key);
150      return values[id];
151    }
152               
153    /// \brief The const subscript operator.
154    ///
155    /// The const subscript operator. The map can be subscripted by the
156    /// actual keys of the graph.
157    const Value& operator[](const Key& key) const {
158      int id = Parent::getNotifier()->id(key);
159      return values[id];
160    }
161
162    /// \brief Setter function of the map.
163    ///
164    /// Setter function of the map. Equivalent with map[key] = val.
165    /// This is a compatibility feature with the not dereferable maps.
166    void set(const Key& key, const Value& val) {
167      (*this)[key] = val;
168    }
169
170  protected:
171
172    /// \brief Adds a new key to the map.
173    ///         
174    /// It adds a new key to the map. It called by the observer notifier
175    /// and it overrides the add() member function of the observer base.     
176    virtual void add(const Key& key) {
177      Notifier* notifier = Parent::getNotifier();
178      int id = notifier->id(key);
179      if (id >= capacity) {
180        int new_capacity = (capacity == 0 ? 1 : capacity);
181        while (new_capacity <= id) {
182          new_capacity <<= 1;
183        }
184        Value* new_values = allocator.allocate(new_capacity);
185        Item it;
186        for (notifier->first(it); it != INVALID; notifier->next(it)) {
187          int jd = notifier->id(it);;
188          if (id != jd) {
189            allocator.construct(&(new_values[jd]), values[jd]);
190            allocator.destroy(&(values[jd]));
191          }
192        }
193        if (capacity != 0) allocator.deallocate(values, capacity);
194        values = new_values;
195        capacity = new_capacity;
196      }
197      allocator.construct(&(values[id]), Value());
198    }
199
200    /// \brief Adds more new keys to the map.
201    ///         
202    /// It adds more new keys to the map. It called by the observer notifier
203    /// and it overrides the add() member function of the observer base.     
204    virtual void add(const std::vector<Key>& keys) {
205      Notifier* notifier = Parent::getNotifier();
206      int max_id = -1;
207      for (int i = 0; i < (int)keys.size(); ++i) {
208        int id = notifier->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 (notifier->first(it); it != INVALID; notifier->next(it)) {
221          int id = notifier->id(it);
222          bool found = false;
223          for (int i = 0; i < (int)keys.size(); ++i) {
224            int jd = notifier->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 = notifier->id(keys[i]);
240        allocator.construct(&(values[id]), Value());
241      }
242    }
243               
244    /// \brief Erase a key from the map.
245    ///
246    /// Erase a key from the map. It called by the observer notifier
247    /// and it overrides the erase() member function of the observer base.     
248    virtual void erase(const Key& key) {
249      int id = Parent::getNotifier()->id(key);
250      allocator.destroy(&(values[id]));
251    }
252
253    /// \brief Erase more keys from the map.
254    ///
255    /// Erase more keys from the map. It called by the observer notifier
256    /// and it overrides the erase() member function of the observer base.     
257    virtual void erase(const std::vector<Key>& keys) {
258      for (int i = 0; i < (int)keys.size(); ++i) {
259        int id = Parent::getNotifier()->id(keys[i]);
260        allocator.destroy(&(values[id]));
261      }
262    }
263
264    /// \brief Buildes the map.
265    ///
266    /// It buildes the map. It called by the observer notifier
267    /// and it overrides the build() member function of the observer base.
268    virtual void build() {
269      Notifier* notifier = Parent::getNotifier();
270      allocate_memory();
271      Item it;
272      for (notifier->first(it); it != INVALID; notifier->next(it)) {
273        int id = notifier->id(it);;
274        allocator.construct(&(values[id]), Value());
275      }                                                         
276    }
277
278    /// \brief Clear the map.
279    ///
280    /// It erase all items from the map. It called by the observer notifier
281    /// and it overrides the clear() member function of the observer base.     
282    virtual void clear() {     
283      Notifier* notifier = Parent::getNotifier();
284      if (capacity != 0) {
285        Item it;
286        for (notifier->first(it); it != INVALID; notifier->next(it)) {
287          int id = notifier->id(it);
288          allocator.destroy(&(values[id]));
289        }                                                               
290        allocator.deallocate(values, capacity);
291        capacity = 0;
292      }
293    }
294
295  private:
296     
297    void allocate_memory() {
298      int max_id = Parent::getNotifier()->maxId();
299      if (max_id == -1) {
300        capacity = 0;
301        values = 0;
302        return;
303      }
304      capacity = 1;
305      while (capacity <= max_id) {
306        capacity <<= 1;
307      }
308      values = allocator.allocate(capacity);   
309    }     
310
311    int capacity;
312    Value* values;
313    Allocator allocator;
314
315  };           
316
317}
318
319#endif
Note: See TracBrowser for help on using the repository browser.