COIN-OR::LEMON - Graph Library

source: lemon/lemon/bits/array_map.h @ 582:6a17a722b50e

Last change on this file since 582:6a17a722b50e was 525:9605e051942f, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Various doc improvements

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