COIN-OR::LEMON - Graph Library

source: lemon/lemon/bits/array_map.h

Last change on this file was 1270:dceba191c00d, checked in by Alpar Juttner <alpar@…>, 11 years ago

Apply unify-sources.sh to the source tree

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