COIN-OR::LEMON - Graph Library

Changeset 209:765619b7cbb2 in lemon-1.2 for lemon/bits/array_map.h


Ignore:
Timestamp:
07/13/08 20:51:02 (11 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Phase:
public
Message:

Apply unify-sources.sh to the source tree

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/bits/array_map.h

    r107 r209  
    1 /* -*- C++ -*-
    2  *
    3  * This file is a part of LEMON, a generic C++ optimization library
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2 *
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
     
    3939  /// The ArrayMap template class is graph map structure what
    4040  /// automatically updates the map when a key is added to or erased from
    41   /// the map. This map uses the allocators to implement 
     41  /// the map. This map uses the allocators to implement
    4242  /// the container functionality.
    4343  ///
     
    4545  /// the Value type of the map.
    4646  template <typename _Graph, typename _Item, typename _Value>
    47   class ArrayMap 
     47  class ArrayMap
    4848    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
    4949  public:
    50     /// The graph type of the maps. 
     50    /// The graph type of the maps.
    5151    typedef _Graph Graph;
    5252    /// The item type of the map.
     
    7070    /// The MapBase of the Map which imlements the core regisitry function.
    7171    typedef typename Notifier::ObserverBase Parent;
    72                
     72
    7373  private:
    7474    typedef std::allocator<Value> Allocator;
     
    8585      Item it;
    8686      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. 
     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.
    9595    ArrayMap(const Graph& graph, const Value& value) {
    9696      Parent::attach(graph.notifier(Item()));
     
    9999      Item it;
    100100      for (nf->first(it); it != INVALID; nf->next(it)) {
    101         int id = nf->id(it);;
    102         allocator.construct(&(values[id]), value);
    103       }                                                         
     101        int id = nf->id(it);;
     102        allocator.construct(&(values[id]), value);
     103      }
    104104    }
    105105
    106106    /// \brief Constructor to copy a map of the same map type.
    107107    ///
    108     /// Constructor to copy a map of the same map type.     
     108    /// Constructor to copy a map of the same map type.
    109109    ArrayMap(const ArrayMap& copy) : Parent() {
    110110      if (copy.attached()) {
    111         attach(*copy.notifier());
     111        attach(*copy.notifier());
    112112      }
    113113      capacity = copy.capacity;
     
    117117      Item it;
    118118      for (nf->first(it); it != INVALID; nf->next(it)) {
    119         int id = nf->id(it);;
    120         allocator.construct(&(values[id]), copy.values[id]);
     119        int id = nf->id(it);;
     120        allocator.construct(&(values[id]), copy.values[id]);
    121121      }
    122122    }
     
    125125    ///
    126126    /// This operator assigns for each item in the map the
    127     /// value mapped to the same item in the copied map. 
     127    /// value mapped to the same item in the copied map.
    128128    /// The parameter map should be indiced with the same
    129129    /// itemset because this assign operator does not change
    130     /// the container of the map. 
     130    /// the container of the map.
    131131    ArrayMap& operator=(const ArrayMap& cmap) {
    132132      return operator=<ArrayMap>(cmap);
     
    139139    /// concecpt and could be indiced by the current item set of
    140140    /// the NodeMap. In this case the value for each item
    141     /// is assigned by the value of the given ReadMap. 
     141    /// is assigned by the value of the given ReadMap.
    142142    template <typename CMap>
    143143    ArrayMap& operator=(const CMap& cmap) {
     
    152152
    153153    /// \brief The destructor of the map.
    154     ///     
     154    ///
    155155    /// The destructor of the map.
    156     virtual ~ArrayMap() {     
     156    virtual ~ArrayMap() {
    157157      if (attached()) {
    158         clear();
    159         detach();
    160       }
    161     }
    162                
     158        clear();
     159        detach();
     160      }
     161    }
     162
    163163  protected:
    164164
     
    169169  public:
    170170
    171     /// \brief The subscript operator. 
     171    /// \brief The subscript operator.
    172172    ///
    173173    /// The subscript operator. The map can be subscripted by the
    174     /// actual keys of the graph. 
     174    /// actual keys of the graph.
    175175    Value& operator[](const Key& key) {
    176176      int id = Parent::notifier()->id(key);
    177177      return values[id];
    178     } 
    179                
     178    }
     179
    180180    /// \brief The const subscript operator.
    181181    ///
    182182    /// The const subscript operator. The map can be subscripted by the
    183     /// actual keys of the graph. 
     183    /// actual keys of the graph.
    184184    const Value& operator[](const Key& key) const {
    185185      int id = Parent::notifier()->id(key);
     
    188188
    189189    /// \brief Setter function of the map.
    190     /// 
     190    ///
    191191    /// Setter function of the map. Equivalent with map[key] = val.
    192192    /// This is a compatibility feature with the not dereferable maps.
     
    198198
    199199    /// \brief Adds a new key to the map.
    200     ///         
     200    ///
    201201    /// It adds a new key to the map. It called by the observer notifier
    202     /// and it overrides the add() member function of the observer base.     
     202    /// and it overrides the add() member function of the observer base.
    203203    virtual void add(const Key& key) {
    204204      Notifier* nf = Parent::notifier();
    205205      int id = nf->id(key);
    206206      if (id >= capacity) {
    207         int new_capacity = (capacity == 0 ? 1 : capacity);
    208         while (new_capacity <= id) {
    209           new_capacity <<= 1;
    210         }
    211         Value* new_values = allocator.allocate(new_capacity);
    212         Item it;
    213         for (nf->first(it); it != INVALID; nf->next(it)) {
    214           int jd = nf->id(it);;
    215           if (id != jd) {
    216             allocator.construct(&(new_values[jd]), values[jd]);
    217             allocator.destroy(&(values[jd]));
    218           }
    219         }
    220         if (capacity != 0) allocator.deallocate(values, capacity);
    221         values = new_values;
    222         capacity = new_capacity;
     207        int new_capacity = (capacity == 0 ? 1 : capacity);
     208        while (new_capacity <= id) {
     209          new_capacity <<= 1;
     210        }
     211        Value* new_values = allocator.allocate(new_capacity);
     212        Item it;
     213        for (nf->first(it); it != INVALID; nf->next(it)) {
     214          int jd = nf->id(it);;
     215          if (id != jd) {
     216            allocator.construct(&(new_values[jd]), values[jd]);
     217            allocator.destroy(&(values[jd]));
     218          }
     219        }
     220        if (capacity != 0) allocator.deallocate(values, capacity);
     221        values = new_values;
     222        capacity = new_capacity;
    223223      }
    224224      allocator.construct(&(values[id]), Value());
     
    226226
    227227    /// \brief Adds more new keys to the map.
    228     ///         
     228    ///
    229229    /// It adds more new keys to the map. It called by the observer notifier
    230     /// and it overrides the add() member function of the observer base.     
     230    /// and it overrides the add() member function of the observer base.
    231231    virtual void add(const std::vector<Key>& keys) {
    232232      Notifier* nf = Parent::notifier();
    233233      int max_id = -1;
    234234      for (int i = 0; i < int(keys.size()); ++i) {
    235         int id = nf->id(keys[i]);
    236         if (id > max_id) {
    237           max_id = id;
    238         }
     235        int id = nf->id(keys[i]);
     236        if (id > max_id) {
     237          max_id = id;
     238        }
    239239      }
    240240      if (max_id >= capacity) {
    241         int new_capacity = (capacity == 0 ? 1 : capacity);
    242         while (new_capacity <= max_id) {
    243           new_capacity <<= 1;
    244         }
    245         Value* new_values = allocator.allocate(new_capacity);
    246         Item it;
    247         for (nf->first(it); it != INVALID; nf->next(it)) {
    248           int id = nf->id(it);
    249           bool found = false;
    250           for (int i = 0; i < int(keys.size()); ++i) {
    251             int jd = nf->id(keys[i]);
    252             if (id == jd) {
    253               found = true;
    254               break;
    255             }
    256           }
    257           if (found) continue;
    258           allocator.construct(&(new_values[id]), values[id]);
    259           allocator.destroy(&(values[id]));
    260         }
    261         if (capacity != 0) allocator.deallocate(values, capacity);
    262         values = new_values;
    263         capacity = new_capacity;
     241        int new_capacity = (capacity == 0 ? 1 : capacity);
     242        while (new_capacity <= max_id) {
     243          new_capacity <<= 1;
     244        }
     245        Value* new_values = allocator.allocate(new_capacity);
     246        Item it;
     247        for (nf->first(it); it != INVALID; nf->next(it)) {
     248          int id = nf->id(it);
     249          bool found = false;
     250          for (int i = 0; i < int(keys.size()); ++i) {
     251            int jd = nf->id(keys[i]);
     252            if (id == jd) {
     253              found = true;
     254              break;
     255            }
     256          }
     257          if (found) continue;
     258          allocator.construct(&(new_values[id]), values[id]);
     259          allocator.destroy(&(values[id]));
     260        }
     261        if (capacity != 0) allocator.deallocate(values, capacity);
     262        values = new_values;
     263        capacity = new_capacity;
    264264      }
    265265      for (int i = 0; i < int(keys.size()); ++i) {
    266         int id = nf->id(keys[i]);
    267         allocator.construct(&(values[id]), Value());
    268       }
    269     }
    270                
     266        int id = nf->id(keys[i]);
     267        allocator.construct(&(values[id]), Value());
     268      }
     269    }
     270
    271271    /// \brief Erase a key from the map.
    272272    ///
    273273    /// Erase a key from the map. It called by the observer notifier
    274     /// and it overrides the erase() member function of the observer base.     
     274    /// and it overrides the erase() member function of the observer base.
    275275    virtual void erase(const Key& key) {
    276276      int id = Parent::notifier()->id(key);
     
    281281    ///
    282282    /// Erase more keys from the map. It called by the observer notifier
    283     /// and it overrides the erase() member function of the observer base.     
     283    /// and it overrides the erase() member function of the observer base.
    284284    virtual void erase(const std::vector<Key>& keys) {
    285285      for (int i = 0; i < int(keys.size()); ++i) {
    286         int id = Parent::notifier()->id(keys[i]);
    287         allocator.destroy(&(values[id]));
     286        int id = Parent::notifier()->id(keys[i]);
     287        allocator.destroy(&(values[id]));
    288288      }
    289289    }
    290290
    291291    /// \brief Buildes the map.
    292     /// 
     292    ///
    293293    /// It buildes the map. It called by the observer notifier
    294     /// and it overrides the build() member function of the observer base. 
     294    /// and it overrides the build() member function of the observer base.
    295295    virtual void build() {
    296296      Notifier* nf = Parent::notifier();
     
    298298      Item it;
    299299      for (nf->first(it); it != INVALID; nf->next(it)) {
    300         int id = nf->id(it);;
    301         allocator.construct(&(values[id]), Value());
    302       }                                                         
     300        int id = nf->id(it);;
     301        allocator.construct(&(values[id]), Value());
     302      }
    303303    }
    304304
     
    306306    ///
    307307    /// It erase all items from the map. It called by the observer notifier
    308     /// and it overrides the clear() member function of the observer base.     
    309     virtual void clear() {     
     308    /// and it overrides the clear() member function of the observer base.
     309    virtual void clear() {
    310310      Notifier* nf = Parent::notifier();
    311311      if (capacity != 0) {
    312         Item it;
    313         for (nf->first(it); it != INVALID; nf->next(it)) {
    314           int id = nf->id(it);
    315           allocator.destroy(&(values[id]));
    316         }                                                               
    317         allocator.deallocate(values, capacity);
    318         capacity = 0;
     312        Item it;
     313        for (nf->first(it); it != INVALID; nf->next(it)) {
     314          int id = nf->id(it);
     315          allocator.destroy(&(values[id]));
     316        }
     317        allocator.deallocate(values, capacity);
     318        capacity = 0;
    319319      }
    320320    }
    321321
    322322  private:
    323      
     323
    324324    void allocate_memory() {
    325325      int max_id = Parent::notifier()->maxId();
    326326      if (max_id == -1) {
    327         capacity = 0;
    328         values = 0;
    329         return;
     327        capacity = 0;
     328        values = 0;
     329        return;
    330330      }
    331331      capacity = 1;
    332332      while (capacity <= max_id) {
    333         capacity <<= 1;
    334       }
    335       values = allocator.allocate(capacity);   
    336     }     
     333        capacity <<= 1;
     334      }
     335      values = allocator.allocate(capacity);
     336    }
    337337
    338338    int capacity;
     
    340340    Allocator allocator;
    341341
    342   };           
     342  };
    343343
    344344}
    345345
    346 #endif 
     346#endif
Note: See TracChangeset for help on using the changeset viewer.