COIN-OR::LEMON - Graph Library

Changeset 1414:01d9d6bc1284 in lemon-0.x for src/lemon/bits/array_map.h


Ignore:
Timestamp:
05/14/05 19:20:40 (15 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1884
Message:

Handling simultan edge adding.
Fixed bug: directed edge maps for undir graphs

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/bits/array_map.h

    r1374 r1414  
    11/* -*- C++ -*-
    2  * src/lemon/array_map.h - Part of LEMON, a generic C++ optimization library
     2 * src/lemon/bits/array_map.h - Part of LEMON, a generic C++ optimization library
    33 *
    44 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     
    3232  /// @{
    3333       
    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    *
    39    * The template parameter is the AlterationNotifier that the maps
    40    * will belong to and the Value.
    41    */
     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  ///
     39  /// The template parameter is the AlterationNotifier that the maps
     40  /// will belong to and the Value.
     41   
    4242
    4343  template <typename _Graph,
     
    6969  public:
    7070
    71     /** Graph and Registry initialized map constructor.
    72      */
     71    /// Graph and Registry initialized map constructor.
     72     
    7373    ArrayMap(const Graph& _g) : graph(&_g) {
    7474      Item it;
     
    9595    }
    9696
    97     /** Constructor to copy a map of the same map type.
    98      */
     97    /// Constructor to copy a map of the same map type.
     98     
    9999    ArrayMap(const ArrayMap& copy) : Parent() {
    100100      if (copy.attached()) {
     
    115115    using Parent::attached;
    116116
    117     /** Assign operator to copy a map of the same map type.
    118      */
     117    /// Assign operator to copy a map of the same map type.
     118     
    119119    ArrayMap& operator=(const ArrayMap& copy) {
    120120      if (&copy == this) return *this;
     
    142142    }
    143143
    144     /** The destructor of the map.
    145      */
     144    /// The destructor of the map.
     145     
    146146    virtual ~ArrayMap() {     
    147147      if (attached()) {
     
    152152       
    153153       
    154     /**
    155      * The subscript operator. The map can be subscripted by the
    156      * actual keys of the graph.
    157      */
     154    ///The subscript operator. The map can be subscripted by the
     155    ///actual keys of the graph.
     156     
    158157    Value& operator[](const Key& key) {
    159158      int id = graph->id(key);
     
    161160    }
    162161               
    163     /**
    164      * The const subscript operator. The map can be subscripted by the
    165      * actual keys of the graph.
    166      */
     162
     163    ///The const subscript operator. The map can be subscripted by the
     164    ///actual keys of the graph.
     165     
    167166    const Value& operator[](const Key& key) const {
    168167      int id = graph->id(key);
     
    170169    }
    171170       
    172     /** Setter function of the map. Equivalent with map[key] = val.
    173      * This is a compatibility feature with the not dereferable maps.
    174      */
     171    /// Setter function of the map. Equivalent with map[key] = val.
     172    /// This is a compatibility feature with the not dereferable maps.
     173     
    175174    void set(const Key& key, const Value& val) {
    176175      (*this)[key] = val;
    177176    }
    178177               
    179     /** Add a new key to the map. It called by the map registry.
    180      */
     178    /// Add a new key to the map. It called by the map registry.
     179     
    181180    void add(const Key& key) {
    182181      int id = graph->id(key);
     
    201200      allocator.construct(&(values[id]), Value());
    202201    }
    203                
    204     /** Erase a key from the map. It called by the map registry.
    205      */
     202
     203    void add(const std::vector<Key>& keys) {
     204      int max_id = -1;
     205      for (int i = 0; i < (int)keys.size(); ++i) {
     206        int id = graph->id(keys[i]);
     207        if (id > max_id) {
     208          max_id = id;
     209        }
     210      }
     211      if (max_id >= capacity) {
     212        int new_capacity = (capacity == 0 ? 1 : capacity);
     213        while (new_capacity <= max_id) {
     214          new_capacity <<= 1;
     215        }
     216        Value* new_values = allocator.allocate(new_capacity);
     217        Item it;
     218        for (graph->first(it); it != INVALID; graph->next(it)) {
     219          int id = graph->id(it);
     220          bool found = false;
     221          for (int i = 0; i < (int)keys.size(); ++i) {
     222            int jd = graph->id(keys[i]);
     223            if (id == jd) {
     224              found = true;
     225              break;
     226            }
     227          }
     228          if (found) continue;
     229          allocator.construct(&(new_values[id]), values[id]);
     230          allocator.destroy(&(values[id]));
     231        }
     232        if (capacity != 0) allocator.deallocate(values, capacity);
     233        values = new_values;
     234        capacity = new_capacity;
     235      }
     236      for (int i = 0; i < (int)keys.size(); ++i) {
     237        int id = graph->id(keys[i]);
     238        allocator.construct(&(values[id]), Value());
     239      }
     240    }
     241               
     242    /// Erase a key from the map. It called by the map registry.
     243     
    206244    void erase(const Key& key) {
    207245      int id = graph->id(key);
    208246      allocator.destroy(&(values[id]));
     247    }
     248
     249    void erase(const std::vector<Key>& keys) {
     250      for (int i = 0; i < (int)keys.size(); ++i) {
     251        int id = graph->id(keys[i]);
     252        allocator.destroy(&(values[id]));
     253      }
    209254    }
    210255
     
    222267        Item it;
    223268        for (graph->first(it); it != INVALID; graph->next(it)) {
    224           int id = graph->id(it);;
     269          int id = graph->id(it);
    225270          allocator.destroy(&(values[id]));
    226271        }                                                               
     
    233278      return graph;
    234279    }
    235 
    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;
    240 
    241 //     /** Returns the begin iterator of the map.
    242 //      */
    243 //     Iterator begin() {
    244 //       return Iterator(*this, KeyIt(*MapBase::getGraph()));
    245 //     }
    246 
    247 //     /** Returns the end iterator of the map.
    248 //      */
    249 //     Iterator end() {
    250 //       return Iterator(*this, INVALID);
    251 //     }
    252 
    253 //     /** Returns the begin ConstIterator of the map.
    254 //      */
    255 //     ConstIterator begin() const {
    256 //       return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
    257 //     }
    258 
    259 //     /** Returns the end const_iterator of the map.
    260 //      */
    261 //     ConstIterator end() const {
    262 //       return ConstIterator(*this, INVALID);
    263 //     }
    264 
    265 //     /// The KeySet of the Map.
    266 //     typedef MapConstKeySet<ArrayMap> ConstKeySet;
    267 
    268 //     /// KeySet getter function.
    269 //     ConstKeySet keySet() const {
    270 //       return ConstKeySet(*this);
    271 //     }
    272 
    273 //     /// The ConstValueSet of the Map.
    274 //     typedef MapConstValueSet<ArrayMap> ConstValueSet;
    275 
    276 //     /// ConstValueSet getter function.
    277 //     ConstValueSet valueSet() const {
    278 //       return ConstValueSet(*this);
    279 //     }
    280 
    281 //     /// The ValueSet of the Map.
    282 //     typedef MapValueSet<ArrayMap> ValueSet;
    283 
    284 //     /// ValueSet getter function.
    285 //     ValueSet valueSet() {
    286 //       return ValueSet(*this);
    287 //     }
    288280
    289281  private:
Note: See TracChangeset for help on using the changeset viewer.