COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/bits/array_map.h @ 482:879c55700cd4

Last change on this file since 482:879c55700cd4 was 314:2cc60866a0c9, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Doc reorganization + improvements

  • Reorganize several tools (move them to other modules).
  • Add new module for map concepts.
  • Remove the doc of all tools in lemon/bits.
  • Improvements in groups.dox.
  • Fix some doxygen warnings.
File size: 10.2 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2008
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#include <lemon/concept_check.h>
27#include <lemon/concepts/maps.h>
28
29// \ingroup graphbits
30// \file
31// \brief Graph map based on the array storage.
32
33namespace lemon {
34
35  // \ingroup graphbits
36  //
37  // \brief Graph map based on the array storage.
38  //
39  // The ArrayMap template class is graph map structure what
40  // automatically updates 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 parameters are the Graph the current Item type and
45  // the Value type of the map.
46  template <typename _Graph, typename _Item, typename _Value>
47  class ArrayMap
48    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
49  public:
50    // The graph type of the maps.
51    typedef _Graph Graph;
52    // The item type of the map.
53    typedef _Item Item;
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
62    // The const reference type of the map.
63    typedef const _Value& ConstReference;
64    // The reference type of the map.
65    typedef _Value& Reference;
66
67    // The notifier type.
68    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
69
70    // The MapBase of the Map which imlements the core regisitry function.
71    typedef typename Notifier::ObserverBase Parent;
72
73  private:
74    typedef std::allocator<Value> Allocator;
75
76  public:
77
78    // \brief Graph initialized map constructor.
79    //
80    // Graph initialized map constructor.
81    explicit ArrayMap(const Graph& graph) {
82      Parent::attach(graph.notifier(Item()));
83      allocate_memory();
84      Notifier* nf = Parent::notifier();
85      Item it;
86      for (nf->first(it); it != INVALID; nf->next(it)) {
87        int id = nf->id(it);;
88        allocator.construct(&(values[id]), Value());
89      }
90    }
91
92    // \brief Constructor to use default value to initialize the map.
93    //
94    // It constructs a map and initialize all of the the map.
95    ArrayMap(const Graph& graph, const Value& value) {
96      Parent::attach(graph.notifier(Item()));
97      allocate_memory();
98      Notifier* nf = Parent::notifier();
99      Item it;
100      for (nf->first(it); it != INVALID; nf->next(it)) {
101        int id = nf->id(it);;
102        allocator.construct(&(values[id]), value);
103      }
104    }
105
106  private:
107    // \brief Constructor to copy a map of the same map type.
108    //
109    // Constructor to copy a map of the same map type.
110    ArrayMap(const ArrayMap& copy) : Parent() {
111      if (copy.attached()) {
112        attach(*copy.notifier());
113      }
114      capacity = copy.capacity;
115      if (capacity == 0) return;
116      values = allocator.allocate(capacity);
117      Notifier* nf = Parent::notifier();
118      Item it;
119      for (nf->first(it); it != INVALID; nf->next(it)) {
120        int id = nf->id(it);;
121        allocator.construct(&(values[id]), copy.values[id]);
122      }
123    }
124
125    // \brief Assign operator.
126    //
127    // This operator assigns for each item in the map the
128    // value mapped to the same item in the copied map.
129    // The parameter map should be indiced with the same
130    // itemset because this assign operator does not change
131    // the container of the map.
132    ArrayMap& operator=(const ArrayMap& cmap) {
133      return operator=<ArrayMap>(cmap);
134    }
135
136
137    // \brief Template assign operator.
138    //
139    // The given parameter should be conform to the ReadMap
140    // concecpt and could be indiced by the current item set of
141    // the NodeMap. In this case the value for each item
142    // is assigned by the value of the given ReadMap.
143    template <typename CMap>
144    ArrayMap& operator=(const CMap& cmap) {
145      checkConcept<concepts::ReadMap<Key, _Value>, CMap>();
146      const typename Parent::Notifier* nf = Parent::notifier();
147      Item it;
148      for (nf->first(it); it != INVALID; nf->next(it)) {
149        set(it, cmap[it]);
150      }
151      return *this;
152    }
153
154  public:
155    // \brief The destructor of the map.
156    //
157    // The destructor of the map.
158    virtual ~ArrayMap() {
159      if (attached()) {
160        clear();
161        detach();
162      }
163    }
164
165  protected:
166
167    using Parent::attach;
168    using Parent::detach;
169    using Parent::attached;
170
171  public:
172
173    // \brief The subscript operator.
174    //
175    // The subscript operator. The map can be subscripted by the
176    // actual keys of the graph.
177    Value& operator[](const Key& key) {
178      int id = Parent::notifier()->id(key);
179      return values[id];
180    }
181
182    // \brief The const subscript operator.
183    //
184    // The const subscript operator. The map can be subscripted by the
185    // actual keys of the graph.
186    const Value& operator[](const Key& key) const {
187      int id = Parent::notifier()->id(key);
188      return values[id];
189    }
190
191    // \brief Setter function of the map.
192    //
193    // Setter function of the map. Equivalent with map[key] = val.
194    // This is a compatibility feature with the not dereferable maps.
195    void set(const Key& key, const Value& val) {
196      (*this)[key] = val;
197    }
198
199  protected:
200
201    // \brief Adds a new key to the map.
202    //
203    // It adds a new key to the map. It called by the observer notifier
204    // and it overrides the add() member function of the observer base.
205    virtual void add(const Key& key) {
206      Notifier* nf = Parent::notifier();
207      int id = nf->id(key);
208      if (id >= capacity) {
209        int new_capacity = (capacity == 0 ? 1 : capacity);
210        while (new_capacity <= id) {
211          new_capacity <<= 1;
212        }
213        Value* new_values = allocator.allocate(new_capacity);
214        Item it;
215        for (nf->first(it); it != INVALID; nf->next(it)) {
216          int jd = nf->id(it);;
217          if (id != jd) {
218            allocator.construct(&(new_values[jd]), values[jd]);
219            allocator.destroy(&(values[jd]));
220          }
221        }
222        if (capacity != 0) allocator.deallocate(values, capacity);
223        values = new_values;
224        capacity = new_capacity;
225      }
226      allocator.construct(&(values[id]), Value());
227    }
228
229    // \brief Adds more new keys to the map.
230    //
231    // It adds more new keys to the map. It called by the observer notifier
232    // and it overrides the add() member function of the observer base.
233    virtual void add(const std::vector<Key>& keys) {
234      Notifier* nf = Parent::notifier();
235      int max_id = -1;
236      for (int i = 0; i < int(keys.size()); ++i) {
237        int id = nf->id(keys[i]);
238        if (id > max_id) {
239          max_id = id;
240        }
241      }
242      if (max_id >= capacity) {
243        int new_capacity = (capacity == 0 ? 1 : capacity);
244        while (new_capacity <= max_id) {
245          new_capacity <<= 1;
246        }
247        Value* new_values = allocator.allocate(new_capacity);
248        Item it;
249        for (nf->first(it); it != INVALID; nf->next(it)) {
250          int id = nf->id(it);
251          bool found = false;
252          for (int i = 0; i < int(keys.size()); ++i) {
253            int jd = nf->id(keys[i]);
254            if (id == jd) {
255              found = true;
256              break;
257            }
258          }
259          if (found) continue;
260          allocator.construct(&(new_values[id]), values[id]);
261          allocator.destroy(&(values[id]));
262        }
263        if (capacity != 0) allocator.deallocate(values, capacity);
264        values = new_values;
265        capacity = new_capacity;
266      }
267      for (int i = 0; i < int(keys.size()); ++i) {
268        int id = nf->id(keys[i]);
269        allocator.construct(&(values[id]), Value());
270      }
271    }
272
273    // \brief Erase a key from the map.
274    //
275    // Erase a key from the map. It called by the observer notifier
276    // and it overrides the erase() member function of the observer base.
277    virtual void erase(const Key& key) {
278      int id = Parent::notifier()->id(key);
279      allocator.destroy(&(values[id]));
280    }
281
282    // \brief Erase more keys from the map.
283    //
284    // Erase more keys from the map. It called by the observer notifier
285    // and it overrides the erase() member function of the observer base.
286    virtual void erase(const std::vector<Key>& keys) {
287      for (int i = 0; i < int(keys.size()); ++i) {
288        int id = Parent::notifier()->id(keys[i]);
289        allocator.destroy(&(values[id]));
290      }
291    }
292
293    // \brief Buildes the map.
294    //
295    // It buildes the map. It called by the observer notifier
296    // and it overrides the build() member function of the observer base.
297    virtual void build() {
298      Notifier* nf = Parent::notifier();
299      allocate_memory();
300      Item it;
301      for (nf->first(it); it != INVALID; nf->next(it)) {
302        int id = nf->id(it);;
303        allocator.construct(&(values[id]), Value());
304      }
305    }
306
307    // \brief Clear the map.
308    //
309    // It erase all items from the map. It called by the observer notifier
310    // and it overrides the clear() member function of the observer base.
311    virtual void clear() {
312      Notifier* nf = Parent::notifier();
313      if (capacity != 0) {
314        Item it;
315        for (nf->first(it); it != INVALID; nf->next(it)) {
316          int id = nf->id(it);
317          allocator.destroy(&(values[id]));
318        }
319        allocator.deallocate(values, capacity);
320        capacity = 0;
321      }
322    }
323
324  private:
325
326    void allocate_memory() {
327      int max_id = Parent::notifier()->maxId();
328      if (max_id == -1) {
329        capacity = 0;
330        values = 0;
331        return;
332      }
333      capacity = 1;
334      while (capacity <= max_id) {
335        capacity <<= 1;
336      }
337      values = allocator.allocate(capacity);
338    }
339
340    int capacity;
341    Value* values;
342    Allocator allocator;
343
344  };
345
346}
347
348#endif
Note: See TracBrowser for help on using the repository browser.