COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/bits/array_map.h @ 1359:1581f961cfaa

Last change on this file since 1359:1581f961cfaa was 1359:1581f961cfaa, checked in by Alpar Juttner, 19 years ago

Correct the english name of EGRES.

File size: 9.3 KB
RevLine 
[906]1/* -*- C++ -*-
[921]2 * src/lemon/array_map.h - Part of LEMON, a generic C++ optimization library
[906]3 *
[1164]4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
[1359]5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
[906]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
[921]17#ifndef LEMON_ARRAY_MAP_H
18#define LEMON_ARRAY_MAP_H
[822]19
20#include <memory>
[1307]21#include <lemon/bits/map_iterator.h>
[822]22
23///\ingroup graphmaps
24///\file
25///\brief Graph maps that construates and destruates
26///their elements dynamically.
27
[921]28namespace lemon {
[822]29
30
31  /// \addtogroup graphmaps
32  /// @{
33       
34  /** The ArrayMap template class is graph map structure what
35   *  automatically updates the map when a key is added to or erased from
36   *  the map. This map factory uses the allocators to implement
37   *  the container functionality.
38   *
[1267]39   *  The template parameter is the AlterationNotifier that the maps
[987]40   *  will belong to and the Value.
[822]41   */
42
[946]43  template <typename _Graph,
44            typename _Item,
45            typename _Value>
[1039]46  class ArrayMap : public AlterationNotifier<_Item>::ObserverBase {
[897]47
[1267]48    typedef _Item Item;
[822]49  public:
50               
51    /// The graph type of the maps.
[946]52    typedef _Graph Graph;
[822]53    /// The key type of the maps.
[987]54    typedef _Item Key;
[946]55
[1039]56    typedef AlterationNotifier<_Item> Registry;
[946]57
[822]58    /// The MapBase of the Map which imlements the core regisitry function.
[946]59    typedef typename Registry::ObserverBase Parent;
[822]60               
61    /// The value type of the map.
[987]62    typedef _Value Value;
[822]63
64
[946]65  private:
[822]66    typedef std::allocator<Value> Allocator;
67
[946]68
69  public:
70
[822]71    /** Graph and Registry initialized map constructor.
72     */
[980]73    ArrayMap(const Graph& _g) : graph(&_g) {
[1267]74      Item it;
75      attach(_g.getNotifier(Item()));
[822]76      allocate_memory();
[1267]77      for (graph->first(it); it != INVALID; graph->next(it)) {
[980]78        int id = graph->id(it);;
[822]79        allocator.construct(&(values[id]), Value());
80      }                                                         
81    }
82
[946]83    /// Constructor to use default value to initialize the map.
84
85    /// It constrates a map and initialize all of the the map.
86
[980]87    ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) {
[1267]88      Item it;
[1039]89      attach(_g.getNotifier(_Item()));
[822]90      allocate_memory();
[1267]91      for (graph->first(it); it != INVALID; graph->next(it)) {
[980]92        int id = graph->id(it);;
[946]93        allocator.construct(&(values[id]), _v);
[822]94      }                                                         
95    }
96
97    /** Constructor to copy a map of the same map type.
98     */
[946]99    ArrayMap(const ArrayMap& copy) {
100      if (copy.attached()) {
101        attach(*copy.getRegistry());
102      }
[822]103      capacity = copy.capacity;
104      if (capacity == 0) return;
105      values = allocator.allocate(capacity);
[1267]106      Item it;
107      for (graph->first(it); it != INVALID; graph->next(it)) {
[980]108        int id = graph->id(it);;
[891]109        allocator.construct(&(values[id]), copy.values[id]);
[822]110      }
111    }
112
[978]113    using Parent::attach;
114    using Parent::detach;
115    using Parent::attached;
116
[822]117    /** Assign operator to copy a map of the same map type.
118     */
119    ArrayMap& operator=(const ArrayMap& copy) {
120      if (&copy == this) return *this;
[897]121     
[946]122      if (graph != copy.graph) {
123        if (attached()) {
124          clear();
125          detach();
[897]126        }
[946]127        if (copy.attached()) {
128          attach(*copy.getRegistry());
129        }
[897]130        capacity = copy.capacity;
131        if (capacity == 0) return *this;
132        values = allocator.allocate(capacity);     
[822]133      }
[891]134
[1267]135      Item it;
136      for (graph->first(it); it != INVALID; graph->next(it)) {
[980]137        int id = graph->id(it);;
[822]138        allocator.construct(&(values[id]), copy.values[id]);
139      }
[891]140
[822]141      return *this;
142    }
143
144    /** The destructor of the map.
145     */
[946]146    virtual ~ArrayMap() {     
147      if (attached()) {
148        clear();
149        detach();
[822]150      }
151    }
152       
153       
154    /**
155     * The subscript operator. The map can be subscripted by the
156     * actual keys of the graph.
157     */
[1267]158    Value& operator[](const Key& key) {
[980]159      int id = graph->id(key);
[822]160      return values[id];
161    }
162               
163    /**
164     * The const subscript operator. The map can be subscripted by the
165     * actual keys of the graph.
166     */
[1267]167    const Value& operator[](const Key& key) const {
[980]168      int id = graph->id(key);
[822]169      return values[id];
170    }
171       
172    /** Setter function of the map. Equivalent with map[key] = val.
173     *  This is a compatibility feature with the not dereferable maps.
174     */
[987]175    void set(const Key& key, const Value& val) {
[946]176      (*this)[key] = val;
[822]177    }
178               
179    /** Add a new key to the map. It called by the map registry.
180     */
[987]181    void add(const Key& key) {
[980]182      int id = graph->id(key);
[822]183      if (id >= capacity) {
184        int new_capacity = (capacity == 0 ? 1 : capacity);
185        while (new_capacity <= id) {
186          new_capacity <<= 1;
187        }
[946]188        Value* new_values = allocator.allocate(new_capacity);
[1267]189        Item it;
190        for (graph->first(it); it != INVALID; graph->next(it)) {
[980]191          int jd = graph->id(it);;
[822]192          if (id != jd) {
193            allocator.construct(&(new_values[jd]), values[jd]);
194            allocator.destroy(&(values[jd]));
195          }
196        }
197        if (capacity != 0) allocator.deallocate(values, capacity);
198        values = new_values;
199        capacity = new_capacity;
200      }
201      allocator.construct(&(values[id]), Value());
202    }
203               
204    /** Erase a key from the map. It called by the map registry.
205     */
[987]206    void erase(const Key& key) {
[980]207      int id = graph->id(key);
[822]208      allocator.destroy(&(values[id]));
209    }
210
[946]211    void build() {
212      allocate_memory();
[1267]213      Item it;
214      for (graph->first(it); it != INVALID; graph->next(it)) {
[980]215        int id = graph->id(it);;
[946]216        allocator.construct(&(values[id]), Value());
217      }                                                         
218    }
219
[822]220    void clear() {     
221      if (capacity != 0) {
[1267]222        Item it;
223        for (graph->first(it); it != INVALID; graph->next(it)) {
[980]224          int id = graph->id(it);;
[946]225          allocator.destroy(&(values[id]));
226        }                                                               
[822]227        allocator.deallocate(values, capacity);
228        capacity = 0;
229      }
230    }
231
[1271]232    const Graph* getGraph() {
233      return graph;
234    }
235
[946]236//     /// The stl compatible pair iterator of the map.
237//     typedef MapIterator<ArrayMap> Iterator;
238//     /// The stl compatible const pair iterator of the map.
239//     typedef MapConstIterator<ArrayMap> ConstIterator;
[822]240
[946]241//     /** Returns the begin iterator of the map.
242//      */
243//     Iterator begin() {
244//       return Iterator(*this, KeyIt(*MapBase::getGraph()));
245//     }
[822]246
[946]247//     /** Returns the end iterator of the map.
248//      */
249//     Iterator end() {
250//       return Iterator(*this, INVALID);
251//     }
[822]252
[946]253//     /** Returns the begin ConstIterator of the map.
254//      */
255//     ConstIterator begin() const {
256//       return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
257//     }
[822]258
[946]259//     /** Returns the end const_iterator of the map.
260//      */
261//     ConstIterator end() const {
262//       return ConstIterator(*this, INVALID);
263//     }
[822]264
[946]265//     /// The KeySet of the Map.
266//     typedef MapConstKeySet<ArrayMap> ConstKeySet;
[830]267
[946]268//     /// KeySet getter function.
269//     ConstKeySet keySet() const {
270//       return ConstKeySet(*this);
271//     }
[830]272
[946]273//     /// The ConstValueSet of the Map.
274//     typedef MapConstValueSet<ArrayMap> ConstValueSet;
[830]275
[946]276//     /// ConstValueSet getter function.
277//     ConstValueSet valueSet() const {
278//       return ConstValueSet(*this);
279//     }
[830]280
[946]281//     /// The ValueSet of the Map.
282//     typedef MapValueSet<ArrayMap> ValueSet;
[830]283
[946]284//     /// ValueSet getter function.
285//     ValueSet valueSet() {
286//       return ValueSet(*this);
287//     }
[830]288
[822]289  private:
290     
291    void allocate_memory() {
[980]292      int max_id = graph->maxId(_Item());
[822]293      if (max_id == -1) {
294        capacity = 0;
295        values = 0;
296        return;
297      }
298      capacity = 1;
299      while (capacity <= max_id) {
300        capacity <<= 1;
301      }
302      values = allocator.allocate(capacity);   
303    }     
304
[946]305    const Graph* graph;
[822]306    int capacity;
307    Value* values;
308    Allocator allocator;
[844]309
[822]310  };           
311
[946]312  template <typename _Base>
313  class ArrayMappableGraphExtender : public _Base {
314  public:
315
316    typedef ArrayMappableGraphExtender<_Base> Graph;
317    typedef _Base Parent;
318
319    typedef typename Parent::Node Node;
320    typedef typename Parent::NodeIt NodeIt;
[1039]321    typedef typename Parent::NodeNotifier NodeObserverRegistry;
[946]322
323    typedef typename Parent::Edge Edge;
324    typedef typename Parent::EdgeIt EdgeIt;
[1039]325    typedef typename Parent::EdgeNotifier EdgeObserverRegistry;
[946]326
327   
328
329    template <typename _Value>
[1267]330    class NodeMap
331      : public IterableMapExtender<ArrayMap<Graph, Node, _Value> > {
[946]332    public:
333      typedef ArrayMappableGraphExtender<_Base> Graph;
334
335      typedef typename Graph::Node Node;
336      typedef typename Graph::NodeIt NodeIt;
337
[1267]338      typedef IterableMapExtender<ArrayMap<Graph, Node, _Value> > Parent;
[946]339
[979]340      //typedef typename Parent::Graph Graph;
[946]341      typedef typename Parent::Value Value;
342
343      NodeMap(const Graph& g)
[980]344        : Parent(g) {}
[946]345      NodeMap(const Graph& g, const Value& v)
[980]346        : Parent(g, v) {}
[946]347
348    };
349
350    template <typename _Value>
[1267]351    class EdgeMap
352      : public IterableMapExtender<ArrayMap<Graph, Edge, _Value> > {
[946]353    public:
354      typedef ArrayMappableGraphExtender<_Base> Graph;
355
356      typedef typename Graph::Edge Edge;
357      typedef typename Graph::EdgeIt EdgeIt;
358
[1267]359      typedef IterableMapExtender<ArrayMap<Graph, Edge, _Value> > Parent;
[946]360
[979]361      //typedef typename Parent::Graph Graph;
[946]362      typedef typename Parent::Value Value;
363
364      EdgeMap(const Graph& g)
[980]365        : Parent(g) {}
[946]366      EdgeMap(const Graph& g, const Value& v)
[980]367        : Parent(g, v) {}
[946]368
369    };
370   
371  };
372
[822]373/// @}
374
375}
376
[921]377#endif //LEMON_ARRAY_MAP_H
Note: See TracBrowser for help on using the repository browser.