COIN-OR::LEMON - Graph Library

Changeset 1999:2ff283124dfc in lemon-0.x for lemon/bits/vector_map.h


Ignore:
Timestamp:
03/06/06 11:28:37 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2609
Message:

Clarifing alteration observing system
It is directly connected now to a container

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/bits/vector_map.h

    r1996 r1999  
    1717 */
    1818
    19 #ifndef LEMON_VECTOR_MAP_H
    20 #define LEMON_VECTOR_MAP_H
     19#ifndef LEMON_BITS_VECTOR_MAP_H
     20#define LEMON_BITS_VECTOR_MAP_H
    2121
    2222#include <vector>
    2323#include <algorithm>
    2424
     25#include <lemon/bits/traits.h>
    2526#include <lemon/bits/utility.h>
    26 #include <lemon/bits/map_extender.h>
     27
    2728#include <lemon/bits/alteration_notifier.h>
    28 #include <lemon/concept_check.h>
    29 #include <lemon/concept/maps.h>
    30 
    31 /// \ingroup graphbits
     29
     30///\ingroup graphbits
    3231///
    3332///\file
    3433///\brief Vector based graph maps.
    35 
    3634namespace lemon {
    3735
     
    4139  ///
    4240  /// The VectorMap template class is graph map structure what
    43   /// automatically indates the map when a key is added to or erased from
     41  /// automatically updates the map when a key is added to or erased from
    4442  /// the map. This map factory uses the allocators to implement
    4543  /// the container functionality. This map factory
    4644  /// uses the std::vector to implement the container function.
    4745  ///
    48   /// \param Registry The AlterationNotifier that will notify this map.
     46  /// \param Notifier The AlterationNotifier that will notify this map.
    4947  /// \param Item The item type of the graph items.
    5048  /// \param Value The value type of the map.
    5149  ///
    52   /// \author Balazs Dezso
    53        
    54   template <
    55     typename _Graph,
    56     typename _Item,   
    57     typename _Value
    58     >
    59   class VectorMap : public AlterationNotifier<_Item>::ObserverBase {
     50  /// \author Balazs Dezso     
     51  template <typename _Graph, typename _Item, typename _Value>
     52  class VectorMap
     53    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
    6054  private:
    6155               
     
    6761    /// The graph type of the map.
    6862    typedef _Graph Graph;
     63    /// The item type of the map.
     64    typedef _Item Item;
    6965    /// The reference map tag.
    7066    typedef True ReferenceMapTag;
     
    7571    typedef _Value Value;
    7672
    77     typedef AlterationNotifier<_Item> Registry;
     73    /// The notifier type.
     74    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
    7875
    7976    /// The map type.
    8077    typedef VectorMap Map;
    8178    /// The base class of the map.
    82     typedef typename Registry::ObserverBase Parent;
     79    typedef typename Notifier::ObserverBase Parent;
    8380
    8481    /// The reference type of the map;
    8582    typedef typename Container::reference Reference;
    86     /// The pointer type of the map;
    87     typedef typename Container::pointer Pointer;
    88 
    89     /// The const value type of the map.
    90     typedef const Value ConstValue;
    9183    /// The const reference type of the map;
    9284    typedef typename Container::const_reference ConstReference;
    93     /// The pointer type of the map;
    94     typedef typename Container::const_pointer ConstPointer;
    95 
    96 
    97     /// \brief Constructor to attach the new map into the registry.
    98     ///
    99     /// It constructs a map and attachs it into the registry.
     85
     86
     87    /// \brief Constructor to attach the new map into the notifier.
     88    ///
     89    /// It constructs a map and attachs it into the notifier.
    10090    /// It adds all the items of the graph to the map.
    101     VectorMap(const Graph& _g) : graph(&_g) {
    102       attach(_g.getNotifier(_Item()));
    103       build();
     91    VectorMap(const Graph& graph) {
     92      Parent::attach(graph.getNotifier(Item()));
     93      container.resize(Parent::getNotifier()->maxId() + 1);
    10494    }
    10595
     
    10898    /// It constructs a map uses a given value to initialize the map.
    10999    /// It adds all the items of the graph to the map.
    110     VectorMap(const Graph& _g, const Value& _v) : graph(&_g) {
    111       attach(_g.getNotifier(_Item()));
    112       container.resize(graph->maxId(_Item()) + 1, _v);
     100    VectorMap(const Graph& graph, const Value& value) {
     101      Parent::attach(graph.getNotifier(Item()));
     102      container.resize(Parent::getNotifier()->maxId() + 1, value);
    113103    }
    114104
     
    116106    ///
    117107    /// Copy constructor.
    118     VectorMap(const VectorMap& _copy)
    119       : Parent(), graph(_copy.getGraph()) {
     108    VectorMap(const VectorMap& _copy) : Parent() {
    120109      if (_copy.attached()) {
    121         attach(*_copy.getRegistry());
     110        Parent::attach(*_copy.getNotifier());
    122111        container = _copy.container;
    123112      }
    124113    }
    125114
    126     /// \brief Destrcutor
    127     ///
    128     /// Destructor.
    129     virtual ~VectorMap() {
    130       if (attached()) {
    131         detach();
    132       }
    133     }
    134 
    135 
    136115  private:
    137116
    138117    VectorMap& operator=(const VectorMap&);
    139 
    140   protected:
    141 
    142     using Parent::attach;
    143     using Parent::detach;
    144     using Parent::attached;
    145 
    146     const Graph* getGraph() const {
    147       return graph;
    148     }
    149118
    150119  public:
     
    155124    /// actual items of the graph.     
    156125    Reference operator[](const Key& key) {
    157       return container[graph->id(key)];
     126      return container[Parent::getNotifier()->id(key)];
    158127    }
    159128               
     
    163132    /// actual items of the graph.
    164133    ConstReference operator[](const Key& key) const {
    165       return container[graph->id(key)];
     134      return container[Parent::getNotifier()->id(key)];
    166135    }
    167136
     
    178147    /// \brief Adds a new key to the map.
    179148    ///         
    180     /// It adds a new key to the map. It called by the observer registry
     149    /// It adds a new key to the map. It called by the observer notifier
    181150    /// and it overrides the add() member function of the observer base.     
    182151    virtual void add(const Key& key) {
    183       int id = graph->id(key);
     152      int id = Parent::getNotifier()->id(key);
    184153      if (id >= (int)container.size()) {
    185154        container.resize(id + 1);
     
    189158    /// \brief Adds more new keys to the map.
    190159    ///         
    191     /// It adds more new keys to the map. It called by the observer registry
     160    /// It adds more new keys to the map. It called by the observer notifier
    192161    /// and it overrides the add() member function of the observer base.     
    193162    virtual void add(const std::vector<Key>& keys) {
     163      int max = container.size() - 1;
    194164      for (int i = 0; i < (int)keys.size(); ++i) {
    195         add(keys[i]);
    196       }
     165        int id = Parent::getNotifier()->id(keys[i]);
     166        if (id >= max) {
     167          max = id;
     168        }
     169      }
     170      container.resize(max + 1);
    197171    }
    198172
    199173    /// \brief Erase a key from the map.
    200174    ///
    201     /// Erase a key from the map. It called by the observer registry
     175    /// Erase a key from the map. It called by the observer notifier
    202176    /// and it overrides the erase() member function of the observer base.     
    203     virtual void erase(const Key&) {}
     177    virtual void erase(const Key& key) {
     178      container[Parent::getNotifier()->id(key)] = Value();
     179    }
    204180
    205181    /// \brief Erase more keys from the map.
    206182    ///
    207     /// Erase more keys from the map. It called by the observer registry
     183    /// Erase more keys from the map. It called by the observer notifier
    208184    /// and it overrides the erase() member function of the observer base.     
    209     virtual void erase(const std::vector<Key>&) {}
     185    virtual void erase(const std::vector<Key>& keys) {
     186      for (int i = 0; i < (int)keys.size(); ++i) {
     187        container[Parent::getNotifier()->id(keys[i])] = Value();
     188      }
     189    }
    210190   
    211191    /// \brief Buildes the map.
    212192    ///
    213     /// It buildes the map. It called by the observer registry
     193    /// It buildes the map. It called by the observer notifier
    214194    /// and it overrides the build() member function of the observer base.
    215195    virtual void build() {
    216       container.resize(graph->maxId(_Item()) + 1);
     196      int size = Parent::getNotifier()->maxId() + 1;
     197      container.reserve(size);
     198      container.resize(size);
    217199    }
    218200
    219201    /// \brief Clear the map.
    220202    ///
    221     /// It erase all items from the map. It called by the observer registry
     203    /// It erase all items from the map. It called by the observer notifier
    222204    /// and it overrides the clear() member function of the observer base.     
    223205    virtual void clear() {
     
    228210               
    229211    Container container;
    230     const Graph *graph;
    231212
    232213  };
Note: See TracChangeset for help on using the changeset viewer.