COIN-OR::LEMON - Graph Library

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


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

Location:
lemon/bits
Files:
1 added
1 deleted
7 edited

Legend:

Unmodified
Added
Removed
  • lemon/bits/alteration_notifier.h

    r1996 r1999  
    1717 */
    1818
    19 #ifndef LEMON_ALTERATION_NOTIFIER_H
    20 #define LEMON_ALTERATION_NOTIFIER_H
     19#ifndef LEMON_BITS_ALTERATION_NOTIFIER_H
     20#define LEMON_BITS_ALTERATION_NOTIFIER_H
    2121
    2222#include <vector>
    23 #include <algorithm>
     23
     24#include <lemon/bits/utility.h>
    2425
    2526///\ingroup graphbits
    2627///\file
    27 ///\brief Observer registry for graph alteration observers.
     28///\brief Observer notifier for graph alteration observers.
    2829
    2930namespace lemon {
    3031
    31   /// \addtogroup graphbits
    32   /// @{
    33 
    34   /// \brief Registry class to register objects observes alterations in
    35   /// the graph.
    36   ///
    37   /// This class is a registry for the objects which observe the
    38   /// alterations in a container. The alteration observers can be attached
    39   /// to and detached from the registry. The observers have to inherit
    40   /// from the \ref AlterationNotifier::ObserverBase and override
    41   /// the virtual functions in that.
    42   ///
    43   /// The most important application of the alteration observing is the
    44   /// dynamic map implementation.
    45   ///
    46   /// \param _Item The item type what the observers are observing, usually
    47   /// edge or node.
     32  /// \ingroup graphbits
     33  ///
     34  /// \brief Notifier class to notify observes about alterations in
     35  /// a container.
     36  ///
     37  /// The simple graph's can be refered as two containers, one node container
     38  /// and one edge container. But they are not standard containers they
     39  /// does not store values directly they are just key continars for more
     40  /// value containers which are the node and edge maps.
     41  ///
     42  /// The graph's node and edge sets can be changed as we add or erase
     43  /// nodes and edges in the graph. Lemon would like to handle easily
     44  /// that the node and edge maps should contain values for all nodes or
     45  /// edges. If we want to check on every indicing if the map contains
     46  /// the current indicing key that cause a drawback in the performance
     47  /// in the library. We use an other solution we notify all maps about
     48  /// an alteration in the graph, which cause only drawback on the
     49  /// alteration of the graph.
     50  ///
     51  /// This class provides an interface to the container. The \e first() and \e
     52  /// next() member functions make possible to iterate on the keys of the
     53  /// container. The \e id() function returns an integer id for each key.
     54  /// The \e maxId() function gives back an upper bound of the ids.
     55  ///
     56  /// For the proper functonality of this class, we should notify it
     57  /// about each alteration in the container. The alterations have four type
     58  /// as \e add(), \e erase(), \e build() and \e clear(). The \e add() and
     59  /// \e erase() signals that only one or few items added or erased to or
     60  /// from the graph. If all items are erased from the graph or from an empty
     61  /// graph a new graph is builded then it can be signaled with the
     62  /// clear() and build() members. Important rule that if we erase items
     63  /// from graph we should first signal the alteration and after that erase
     64  /// them from the container, on the other way on item addition we should
     65  /// first extend the container and just after that signal the alteration.
     66  ///
     67  /// The alteration can be observed with a class inherited from the
     68  /// \e ObserverBase nested class. The signals can be handled with
     69  /// overriding the virtual functions defined in the base class.
     70  /// The observer base can be attached to the notifier with the
     71  /// \e attach() member and can be detached with detach() function.
     72  ///
     73  /// Alteration observers try to be exception safe. This can be achived
     74  /// when the observers does not throw exception on \e erase() and
     75  /// \e clear(). Less strict condition is that the \e erase() should
     76  /// not throw exception after an \e add() with the same parameter and
     77  /// the \e clear() should not throw exception after a \e build().
     78  ///
     79  /// There are some place when the alteration observing is not completly
     80  /// reliable. If we want to carry out the node degree in the graph
     81  /// as in the \ref InDegMap and we use the reverseEdge that cause
     82  /// unreliable functionality. Because the alteration observing signals
     83  /// only erasing and adding but not the reversing it will stores bad
     84  /// degrees. The sub graph adaptors cannot signal the alterations because
     85  /// just a setting in the filter map can modify the graph and this cannot
     86  /// be watched in any way.
     87  ///
     88  /// \param _Container The container which is observed.
     89  /// \param _Item The item type which is obserbved.
    4890  ///
    4991  /// \author Balazs Dezso
    5092
    51   template <typename _Item>
     93  template <typename _Container, typename _Item>
    5294  class AlterationNotifier {
    5395  public:
     
    5597    typedef True Notifier;
    5698
     99    typedef _Container Container;
    57100    typedef _Item Item;
    58101
    59     /// ObserverBase is the base class for the observers.
    60        
     102    /// \brief ObserverBase is the base class for the observers.
     103    ///
    61104    /// ObserverBase is the abstract base class for the observers.
    62105    /// It will be notified about an item was inserted into or
     
    76119    class ObserverBase {
    77120    protected:
    78       typedef AlterationNotifier Registry;
     121      typedef AlterationNotifier Notifier;
    79122
    80123      friend class AlterationNotifier;
     
    84127      /// Default constructor for ObserverBase.
    85128      ///
    86       ObserverBase() : registry(0) {}
    87 
     129      ObserverBase() : notifier(0) {}
     130
     131      /// \brief Constructor which attach the observer into notifier.
     132      ///
     133      /// Constructor which attach the observer into notifier.
     134      ObserverBase(AlterationNotifier& _notifier) {
     135        attach(_notifier);
     136      }
     137
     138      /// \brief Constructor which attach the obserever to the same notifier.
     139      ///
     140      /// Constructor which attach the obserever to the same notifier as
     141      /// the other observer is attached to.
    88142      ObserverBase(const ObserverBase& copy) {
    89143        if (copy.attached()) {
    90           copy.getRegistry()->attach(*this);
     144          attach(*copy.getNotifier());
    91145        }
    92146      }
    93147       
    94       virtual ~ObserverBase() {}
     148      /// \brief Destructor
     149      virtual ~ObserverBase() {
     150        if (attached()) {
     151          detach();
     152        }
     153      }
    95154
    96155      /// \brief Attaches the observer into an AlterationNotifier.
     
    98157      /// This member attaches the observer into an AlterationNotifier.
    99158      ///
    100       void attach(AlterationNotifier& r) {
    101         registry = &r;
    102         registry->attach(*this);
     159      void attach(AlterationNotifier& _notifier) {
     160        notifier = &_notifier;
     161        notifier->attach(*this);
    103162      }
    104163
     
    108167      ///
    109168      void detach() {
    110         if (registry) {
    111           registry->detach(*this);
    112         }
    113       }
    114        
    115 
    116       /// Gives back a pointer to the registry what the map attached into.
    117 
    118       /// This function gives back a pointer to the registry what the map
     169        notifier->detach(*this);
     170      }
     171       
     172
     173      /// \brief Gives back a pointer to the notifier which the map
    119174      /// attached into.
    120175      ///
    121       Registry* getRegistry() const { return const_cast<Registry*>(registry); }
     176      /// This function gives back a pointer to the notifier which the map
     177      /// attached into.
     178      ///
     179      Notifier* getNotifier() const { return const_cast<Notifier*>(notifier); }
    122180     
    123       /// Gives back true when the observer is attached into a registry.
    124       bool attached() const { return registry != 0; }
     181      /// Gives back true when the observer is attached into a notifier.
     182      bool attached() const { return notifier != 0; }
    125183
    126184    private:
     
    130188    protected:
    131189     
    132       Registry* registry;
    133       int registry_index;
     190      Notifier* notifier;
     191      int notifier_index;
    134192
    135193      /// \brief The member function to notificate the observer about an
     
    150208
    151209      virtual void add(const std::vector<Item>& items) {
    152         for (int i = 0; i < (int)items.size(); ++i) {
    153           add(items[i]);
    154         }
     210        int i;
     211        try {
     212          for (i = 0; i < (int)items.size(); ++i) {
     213            add(items[i]);
     214          }
     215        } catch (...) {
     216          for (int j = 0; j < i; ++j) {
     217            add(items[j]);
     218          }         
     219          throw;
     220        }
    155221      }
    156222
     
    171237      /// subclasses.
    172238      virtual void erase(const std::vector<Item>& items) {
    173         for (int i = 0; i < (int)items.size(); ++i) {
    174           erase(items[i]);
    175         }
     239        for (int i = 0; i < (int)items.size(); ++i) {
     240          erase(items[i]);
     241        }
    176242      }
    177243
     
    183249      /// overrided in the subclasses.
    184250
    185       virtual void build() = 0;
     251      virtual void build() {
     252        Item it;
     253        try {
     254          for (notifier->first(it); it != INVALID; notifier->next(it)) {
     255            add(it);
     256          }
     257        } catch (...) {
     258          Item jt;
     259          for (notifier->first(jt); jt != it; notifier->next(jt)) {
     260            erase(jt);
     261          }
     262          throw;
     263        }
     264      }
    186265
    187266      /// \brief The member function to notificate the observer about all
     
    190269      /// The clear() member function notificates the observer about all
    191270      /// items are erased from the container. It have to be overrided in
    192       /// the subclasses.
    193      
    194       virtual void clear() = 0;
     271      /// the subclasses.     
     272      virtual void clear() {
     273        Item it;
     274        for (notifier->first(it); it != INVALID; notifier->next(it)) {
     275          erase(it);
     276        }
     277      }
    195278
    196279    };
    197280       
    198281  protected:
    199        
    200 
    201     typedef std::vector<ObserverBase*> Container;
    202 
    203     Container container;
     282
     283    const Container* container;
     284
     285    typedef std::vector<ObserverBase*> Observers;
     286    Observers observers;
    204287
    205288               
    206289  public:
    207290
    208     /// Default constructor.
    209        
     291    /// \brief Default constructor.
    210292    ///
    211293    /// The default constructor of the AlterationNotifier.
    212     /// It creates an empty registry.
    213     AlterationNotifier() {}
    214 
    215     /// Copy Constructor of the AlterationNotifier.
    216        
     294    /// It creates an empty notifier.
     295    AlterationNotifier()
     296      : container(0) {}
     297
     298    /// \brief Constructor.
     299    ///
     300    /// Constructor with the observed container parameter.
     301    AlterationNotifier(const Container& _container)
     302      : container(&_container) {}
     303
     304    /// \brief Copy Constructor of the AlterationNotifier.
     305    ///
    217306    /// Copy constructor of the AlterationNotifier.
    218     /// It creates only an empty registry because the copiable
    219     /// registry's observers have to be registered still into that registry.
    220     AlterationNotifier(const AlterationNotifier&) {}
    221 
    222     /// Assign operator.
     307    /// It creates only an empty notifier because the copiable
     308    /// notifier's observers have to be registered still into that notifier.
     309    AlterationNotifier(const AlterationNotifier& _notifier)
     310      : container(_notifier.container) {}
     311
     312    /// \brief Destructor.
     313    ///         
     314    /// Destructor of the AlterationNotifier.
     315    ///
     316    ~AlterationNotifier() {
     317      typename Observers::iterator it;
     318      for (it = observers.begin(); it != observers.end(); ++it) {
     319        (*it)->notifier = 0;
     320      }
     321    }
     322
     323    /// \brief Sets the container.
     324    ///
     325    /// Sets the container.
     326    void setContainer(const Container& _container) {
     327      container = &_container;
     328    }
     329
     330  protected:
     331
     332    AlterationNotifier& operator=(const AlterationNotifier&);
     333
     334  public:
     335
     336
     337
     338    /// \brief First item in the container.
     339    ///
     340    /// Returns the first item in the container. It is
     341    /// for start the iteration on the container.
     342    void first(Item& item) const {
     343      container->first(item);
     344    }
     345
     346    /// \brief Next item in the container.
     347    ///
     348    /// Returns the next item in the container. It is
     349    /// for iterate on the container.
     350    void next(Item& item) const {
     351      container->next(item);
     352    }
     353
     354    /// \brief Returns the id of the item.
     355    ///
     356    /// Returns the id of the item provided by the container.
     357    int id(const Item& item) const {
     358      return container->id(item);
     359    }
     360
     361    /// \brief Returns the maximum id of the container.
     362    ///
     363    /// Returns the maximum id of the container.
     364    int maxId() const {
     365      return container->maxId(Item());
     366    }
    223367               
    224     /// Assign operator for the AlterationNotifier.
    225     /// It makes the notifier only empty because the copiable
    226     /// notifier's observers have to be registered still into that registry.
    227     AlterationNotifier& operator=(const AlterationNotifier&) {
    228       typename Container::iterator it;
    229       for (it = container.begin(); it != container.end(); ++it) {
    230         (*it)->registry = 0;
    231       }
    232     }
    233 
    234     /// Destructor.
    235                                
    236     /// Destructor of the AlterationNotifier.
    237     ///
    238     ~AlterationNotifier() {
    239       typename Container::iterator it;
    240       for (it = container.begin(); it != container.end(); ++it) {
    241         (*it)->registry = 0;
    242       }
    243     }
    244        
    245        
    246368  protected:
    247369
    248370    void attach(ObserverBase& observer) {
    249       container.push_back(&observer);
    250       observer.registry = this;
    251       observer.registry_index = container.size()-1;
     371      observers.push_back(&observer);
     372      observer.notifier = this;
     373      observer.notifier_index = observers.size() - 1;
    252374    }
    253375
    254     void detach(ObserverBase& base) {
    255       container.back()->registry_index = base.registry_index;
    256       container[base.registry_index] = container.back();
    257       container.pop_back();
    258       base.registry = 0;
     376    void detach(ObserverBase& observer) {
     377      observers.back()->notifier_index = observer.notifier_index;
     378      observers[observer.notifier_index] = observers.back();
     379      observers.pop_back();
     380      observer.notifier = 0;
    259381    }
    260382
    261383  public:
    262384       
    263     /// \brief Notifies all the registered observers about an Item added to
    264     /// the container.
    265     ///
    266     /// It notifies all the registered observers about an Item added to
     385    /// \brief Notifies all the registed observers about an item added to
     386    /// the container.
     387    ///
     388    /// It notifies all the registed observers about an item added to
    267389    /// the container.
    268390    ///
    269391    void add(const Item& item) {
    270       typename Container::iterator it;
     392      typename Observers::iterator it;
    271393      try {
    272         for (it = container.begin(); it != container.end(); ++it) {
     394        for (it = observers.begin(); it != observers.end(); ++it) {
    273395          (*it)->add(item);
    274396        }
    275397      } catch (...) {
    276         typename Container::iterator jt;
    277         for (jt = container.begin(); jt != it; ++it) {
     398        typename Observers::iterator jt;
     399        for (jt = observers.begin(); jt != it; ++jt) {
    278400          (*it)->erase(item);
    279401        }
     
    282404    }   
    283405
    284     /// \brief Notifies all the registered observers about more Item added to
    285     /// the container.
    286     ///
    287     /// It notifies all the registered observers about more Item added to
     406    /// \brief Notifies all the registed observers about more item added to
     407    /// the container.
     408    ///
     409    /// It notifies all the registed observers about more item added to
    288410    /// the container.
    289411    ///
    290412    void add(const std::vector<Item>& items) {
    291       typename Container::iterator it;
     413      typename Observers::iterator it;
    292414      try {
    293         for (it = container.begin(); it != container.end(); ++it) {
     415        for (it = observers.begin(); it != observers.end(); ++it) {
    294416          (*it)->add(items);
    295417        }
    296418      } catch (...) {
    297         typename Container::iterator jt;
    298         for (jt = container.begin(); jt != it; ++it) {
     419        typename Observers::iterator jt;
     420        for (jt = observers.begin(); jt != it; ++jt) {
    299421          (*it)->erase(items);
    300422        }
     
    303425    }   
    304426
    305     /// \brief Notifies all the registered observers about an Item erased from
     427    /// \brief Notifies all the registed observers about an item erased from
    306428    /// the container.
    307429    ///
    308     /// It notifies all the registered observers about an Item erased from
     430    /// It notifies all the registed observers about an item erased from
    309431    /// the container.
    310432    ///
    311433    void erase(const Item& key) {
    312       typename Container::iterator it;
    313       for (it = container.begin(); it != container.end(); ++it) {
     434      typename Observers::iterator it;
     435      for (it = observers.begin(); it != observers.end(); ++it) {
    314436        (*it)->erase(key);
    315437      }
    316438    }
    317439
    318     /// \brief Notifies all the registered observers about more Item erased 
     440    /// \brief Notifies all the registed observers about more item erased 
    319441    /// from the container.
    320442    ///
    321     /// It notifies all the registered observers about more Item erased from
     443    /// It notifies all the registed observers about more item erased from
    322444    /// the container.
    323445    ///
    324446    void erase(const std::vector<Item>& items) {
    325       typename Container::iterator it;
    326       for (it = container.begin(); it != container.end(); ++it) {
     447      typename Observers::iterator it;
     448      for (it = observers.begin(); it != observers.end(); ++it) {
    327449        (*it)->erase(items);
    328450      }
    329451    }
    330452
    331     /// \brief Notifies all the registered observers about the container is
     453    /// \brief Notifies all the registed observers about the container is
    332454    /// built.
    333455    ///         
    334     /// Notifies all the registered observers about the container is built
     456    /// Notifies all the registed observers about the container is built
    335457    /// from an empty container.
    336458    void build() {
    337       typename Container::iterator it;
     459      typename Observers::iterator it;
    338460      try {
    339         for (it = container.begin(); it != container.end(); ++it) {
     461        for (it = observers.begin(); it != observers.end(); ++it) {
    340462          (*it)->build();
    341463        }
    342464      } catch (...) {
    343         typename Container::iterator jt;
    344         for (jt = container.begin(); jt != it; ++it) {
     465        typename Observers::iterator jt;
     466        for (jt = observers.begin(); jt != it; ++jt) {
    345467          (*it)->clear();
    346468        }
     
    350472
    351473
    352     /// \brief Notifies all the registered observers about all Items are
     474    /// \brief Notifies all the registed observers about all items are
    353475    /// erased.
    354476    ///
    355     /// Notifies all the registered observers about all Items are erased
     477    /// Notifies all the registed observers about all items are erased
    356478    /// from the container.
    357479    void clear() {
    358       typename Container::iterator it;
    359       for (it = container.begin(); it != container.end(); ++it) {
     480      typename Observers::iterator it;
     481      for (it = observers.begin(); it != observers.end(); ++it) {
    360482        (*it)->clear();
    361483      }
     
    363485  };
    364486
    365  
    366 /// @}
    367  
    368 
    369487}
    370488
  • lemon/bits/array_map.h

    r1996 r1999  
    2121
    2222#include <memory>
    23 #include <lemon/bits/map_extender.h>
     23
     24#include <lemon/bits/traits.h>
    2425#include <lemon/bits/alteration_notifier.h>
    25 #include <lemon/concept_check.h>
    26 #include <lemon/concept/maps.h>
    2726
    2827/// \ingroup graphbits
    2928/// \file
    30 /// \brief Graph maps that construct and destruct
    31 /// their elements dynamically.
     29/// \brief Graph map based on the array storage.
    3230
    3331namespace lemon {
     
    3836  ///
    3937  /// The ArrayMap template class is graph map structure what
    40   /// automatically indates the map when a key is added to or erased from
     38  /// automatically updates the map when a key is added to or erased from
    4139  /// the map. This map uses the allocators to implement
    4240  /// the container functionality.
    4341  ///
    44   /// The template parameter is the AlterationNotifier that the maps
    45   /// will belong to and the Value.
    46 
    47   template <typename _Graph,
    48             typename _Item,
    49             typename _Value>
    50   class ArrayMap : public AlterationNotifier<_Item>::ObserverBase {
    51 
    52     typedef _Item Item;
     42  /// The template parameter is the Graph the current Item type and
     43  /// the Value type of the map.
     44  template <typename _Graph, typename _Item, typename _Value>
     45  class ArrayMap
     46    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
    5347  public:
    5448    /// The graph type of the maps.
    5549    typedef _Graph Graph;
     50    /// The item type of the map.
     51    typedef _Item Item;
    5652    /// The reference map tag.
    5753    typedef True ReferenceMapTag;
     
    6157    /// The value type of the map.
    6258    typedef _Value Value;
     59
    6360    /// The const reference type of the map.
    6461    typedef const _Value& ConstReference;
     
    6663    typedef _Value& Reference;
    6764
    68     typedef const Value ConstValue;
    69     typedef Value* Pointer;
    70     typedef const Value* ConstPointer;
    71 
    72     typedef AlterationNotifier<_Item> Registry;
     65    /// The notifier type.
     66    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
    7367
    7468    /// The MapBase of the Map which imlements the core regisitry function.
    75     typedef typename Registry::ObserverBase Parent;
     69    typedef typename Notifier::ObserverBase Parent;
    7670               
    77 
    78 
    7971  private:
    8072    typedef std::allocator<Value> Allocator;
    8173
    82 
    8374  public:
    8475
     
    8677    ///
    8778    /// Graph initialized map constructor.
    88     ArrayMap(const Graph& _g) : graph(&_g) {
     79    ArrayMap(const Graph& graph) {
     80      Parent::attach(graph.getNotifier(Item()));
     81      allocate_memory();
     82      Notifier* notifier = Parent::getNotifier();
    8983      Item it;
    90       attach(_g.getNotifier(Item()));
    91       allocate_memory();
    92       for (graph->first(it); it != INVALID; graph->next(it)) {
    93         int id = graph->id(it);;
     84      for (notifier->first(it); it != INVALID; notifier->next(it)) {
     85        int id = notifier->id(it);;
    9486        allocator.construct(&(values[id]), Value());
    9587      }                                                         
     
    9991    ///
    10092    /// It constructs a map and initialize all of the the map.
    101     ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) {
     93    ArrayMap(const Graph& graph, const Value& value) {
     94      Parent::attach(graph.getNotifier(Item()));
     95      allocate_memory();
     96      Notifier* notifier = Parent::getNotifier();
    10297      Item it;
    103       attach(_g.getNotifier(_Item()));
    104       allocate_memory();
    105       for (graph->first(it); it != INVALID; graph->next(it)) {
    106         int id = graph->id(it);;
    107         allocator.construct(&(values[id]), _v);
     98      for (notifier->first(it); it != INVALID; notifier->next(it)) {
     99        int id = notifier->id(it);;
     100        allocator.construct(&(values[id]), value);
    108101      }                                                         
    109102    }
     
    112105    ///
    113106    /// Constructor to copy a map of the same map type.     
    114     ArrayMap(const ArrayMap& copy) : Parent(), graph(copy.graph) {
     107    ArrayMap(const ArrayMap& copy) : Parent() {
    115108      if (copy.attached()) {
    116         attach(*copy.getRegistry());
     109        attach(*copy.getNotifier());
    117110      }
    118111      capacity = copy.capacity;
    119112      if (capacity == 0) return;
    120113      values = allocator.allocate(capacity);
     114      Notifier* notifier = Parent::getNotifier();
    121115      Item it;
    122       for (graph->first(it); it != INVALID; graph->next(it)) {
    123         int id = graph->id(it);;
     116      for (notifier->first(it); it != INVALID; notifier->next(it)) {
     117        int id = notifier->id(it);;
    124118        allocator.construct(&(values[id]), copy.values[id]);
    125119      }
     
    146140    using Parent::attached;
    147141
    148     const Graph* getGraph() {
    149       return graph;
    150     }
    151 
    152 
    153142  public:
    154143
     
    158147    /// actual keys of the graph.
    159148    Value& operator[](const Key& key) {
    160       int id = graph->id(key);
     149      int id = Parent::getNotifier()->id(key);
    161150      return values[id];
    162151    }
     
    167156    /// actual keys of the graph.
    168157    const Value& operator[](const Key& key) const {
    169       int id = graph->id(key);
     158      int id = Parent::getNotifier()->id(key);
    170159      return values[id];
    171160    }
     
    181170  protected:
    182171
    183     /// Add a new key to the map. It called by the map registry.
    184          
     172    /// \brief Adds a new key to the map.
     173    ///         
     174    /// It adds a new key to the map. It called by the observer notifier
     175    /// and it overrides the add() member function of the observer base.     
    185176    virtual void add(const Key& key) {
    186       int id = graph->id(key);
     177      Notifier* notifier = Parent::getNotifier();
     178      int id = notifier->id(key);
    187179      if (id >= capacity) {
    188180        int new_capacity = (capacity == 0 ? 1 : capacity);
     
    192184        Value* new_values = allocator.allocate(new_capacity);
    193185        Item it;
    194         for (graph->first(it); it != INVALID; graph->next(it)) {
    195           int jd = graph->id(it);;
     186        for (notifier->first(it); it != INVALID; notifier->next(it)) {
     187          int jd = notifier->id(it);;
    196188          if (id != jd) {
    197189            allocator.construct(&(new_values[jd]), values[jd]);
     
    206198    }
    207199
     200    /// \brief Adds more new keys to the map.
     201    ///         
     202    /// It adds more new keys to the map. It called by the observer notifier
     203    /// and it overrides the add() member function of the observer base.     
    208204    virtual void add(const std::vector<Key>& keys) {
     205      Notifier* notifier = Parent::getNotifier();
    209206      int max_id = -1;
    210207      for (int i = 0; i < (int)keys.size(); ++i) {
    211         int id = graph->id(keys[i]);
     208        int id = notifier->id(keys[i]);
    212209        if (id > max_id) {
    213210          max_id = id;
     
    221218        Value* new_values = allocator.allocate(new_capacity);
    222219        Item it;
    223         for (graph->first(it); it != INVALID; graph->next(it)) {
    224           int id = graph->id(it);
     220        for (notifier->first(it); it != INVALID; notifier->next(it)) {
     221          int id = notifier->id(it);
    225222          bool found = false;
    226223          for (int i = 0; i < (int)keys.size(); ++i) {
    227             int jd = graph->id(keys[i]);
     224            int jd = notifier->id(keys[i]);
    228225            if (id == jd) {
    229226              found = true;
     
    240237      }
    241238      for (int i = 0; i < (int)keys.size(); ++i) {
    242         int id = graph->id(keys[i]);
     239        int id = notifier->id(keys[i]);
    243240        allocator.construct(&(values[id]), Value());
    244241      }
    245242    }
    246243               
    247     /// Erase a key from the map. It called by the map registry.
    248      
     244    /// \brief Erase a key from the map.
     245    ///
     246    /// Erase a key from the map. It called by the observer notifier
     247    /// and it overrides the erase() member function of the observer base.     
    249248    virtual void erase(const Key& key) {
    250       int id = graph->id(key);
     249      int id = Parent::getNotifier()->id(key);
    251250      allocator.destroy(&(values[id]));
    252251    }
    253252
     253    /// \brief Erase more keys from the map.
     254    ///
     255    /// Erase more keys from the map. It called by the observer notifier
     256    /// and it overrides the erase() member function of the observer base.     
    254257    virtual void erase(const std::vector<Key>& keys) {
    255258      for (int i = 0; i < (int)keys.size(); ++i) {
    256         int id = graph->id(keys[i]);
     259        int id = Parent::getNotifier()->id(keys[i]);
    257260        allocator.destroy(&(values[id]));
    258261      }
    259262    }
    260263
     264    /// \brief Buildes the map.
     265    ///
     266    /// It buildes the map. It called by the observer notifier
     267    /// and it overrides the build() member function of the observer base.
    261268    virtual void build() {
     269      Notifier* notifier = Parent::getNotifier();
    262270      allocate_memory();
    263271      Item it;
    264       for (graph->first(it); it != INVALID; graph->next(it)) {
    265         int id = graph->id(it);;
     272      for (notifier->first(it); it != INVALID; notifier->next(it)) {
     273        int id = notifier->id(it);;
    266274        allocator.construct(&(values[id]), Value());
    267275      }                                                         
    268276    }
    269277
     278    /// \brief Clear the map.
     279    ///
     280    /// It erase all items from the map. It called by the observer notifier
     281    /// and it overrides the clear() member function of the observer base.     
    270282    virtual void clear() {     
     283      Notifier* notifier = Parent::getNotifier();
    271284      if (capacity != 0) {
    272285        Item it;
    273         for (graph->first(it); it != INVALID; graph->next(it)) {
    274           int id = graph->id(it);
     286        for (notifier->first(it); it != INVALID; notifier->next(it)) {
     287          int id = notifier->id(it);
    275288          allocator.destroy(&(values[id]));
    276289        }                                                               
     
    283296     
    284297    void allocate_memory() {
    285       int max_id = graph->maxId(_Item());
     298      int max_id = Parent::getNotifier()->maxId();
    286299      if (max_id == -1) {
    287300        capacity = 0;
     
    296309    }     
    297310
    298     const Graph* graph;
    299311    int capacity;
    300312    Value* values;
  • lemon/bits/default_map.h

    r1996 r1999  
    1717 */
    1818
    19 #ifndef LEMON_DEFAULT_MAP_H
    20 #define LEMON_DEFAULT_MAP_H
     19#ifndef LEMON_BITS_DEFAULT_MAP_H
     20#define LEMON_BITS_DEFAULT_MAP_H
    2121
    2222
    2323#include <lemon/bits/array_map.h>
    2424#include <lemon/bits/vector_map.h>
    25 #include <lemon/bits/static_map.h>
    2625
    2726///\ingroup graphbits
    2827///\file
    29 ///\brief Graph maps that construct and destruct
    30 ///their elements dynamically.
     28///\brief Graph maps that construct and destruct their elements dynamically.
    3129
    3230namespace lemon {
     
    152150
    153151  /// \e
    154   template <
    155     typename _Graph,
    156     typename _Item,
    157     typename _Value>
     152  template <typename _Graph, typename _Item, typename _Value>
    158153  class DefaultMap
    159154    : public DefaultMapSelector<_Graph, _Item, _Value>::Map {
     
    165160    typedef typename Parent::Value Value;
    166161
    167     DefaultMap(const Graph& _g) : Parent(_g) {}
    168     DefaultMap(const Graph& _g, const Value& _v) : Parent(_g, _v) {}
     162    DefaultMap(const Graph& graph) : Parent(graph) {}
     163    DefaultMap(const Graph& graph, const Value& value)
     164      : Parent(graph, value) {}
    169165
    170166  };
  • lemon/bits/edge_set_extender.h

    r1996 r1999  
    7474
    7575    /// The edge observer registry.
    76     typedef AlterationNotifier<Edge> EdgeNotifier;
     76    typedef AlterationNotifier<EdgeSetExtender, Edge> EdgeNotifier;
    7777
    7878  protected:
     
    220220    template <typename _Value>
    221221    class EdgeMap
    222       : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
     222      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
    223223    public:
    224224      typedef EdgeSetExtender Graph;
    225       typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
     225      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    226226
    227227      EdgeMap(const Graph& _g)
     
    265265    }
    266266
     267    EdgeSetExtender() {
     268      edge_notifier.setContainer(*this);
     269    }
    267270
    268271    ~EdgeSetExtender() {
     
    331334    }
    332335
    333     typedef AlterationNotifier<Edge> EdgeNotifier;
    334     typedef AlterationNotifier<UEdge> UEdgeNotifier;
     336    typedef AlterationNotifier<UEdgeSetExtender, Edge> EdgeNotifier;
     337    typedef AlterationNotifier<UEdgeSetExtender, UEdge> UEdgeNotifier;
    335338
    336339
     
    538541    template <typename _Value>
    539542    class EdgeMap
    540       : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
     543      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
    541544    public:
    542545      typedef UEdgeSetExtender Graph;
    543       typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
     546      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    544547
    545548      EdgeMap(const Graph& _g)
     
    567570    template <typename _Value>
    568571    class UEdgeMap
    569       : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
     572      : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
    570573    public:
    571574      typedef UEdgeSetExtender Graph;
    572       typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
     575      typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
    573576
    574577      UEdgeMap(const Graph& _g)
     
    618621
    619622
     623    UEdgeSetExtender() {
     624      edge_notifier.setContainer(*this);
     625      uedge_notifier.setContainer(*this);
     626    }
     627
    620628    ~UEdgeSetExtender() {
    621       getNotifier(Edge()).clear();
    622       getNotifier(UEdge()).clear();
     629      uedge_notifier.clear();
     630      edge_notifier.clear();
    623631    }
    624632   
  • lemon/bits/graph_extender.h

    r1996 r1999  
    2323#include <lemon/error.h>
    2424
     25#include <lemon/bits/map_extender.h>
    2526#include <lemon/bits/default_map.h>
     27
     28#include <lemon/concept_check.h>
     29#include <lemon/concept/maps.h>
    2630
    2731///\ingroup graphbits
     
    7276    // Alterable extension
    7377
    74     typedef AlterationNotifier<Node> NodeNotifier;
    75     typedef AlterationNotifier<Edge> EdgeNotifier;
     78    typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
     79    typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;
    7680
    7781
     
    215219    template <typename _Value>
    216220    class NodeMap
    217       : public IterableMapExtender<DefaultMap<Graph, Node, _Value> > {
     221      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
    218222    public:
    219223      typedef GraphExtender Graph;
    220       typedef IterableMapExtender<DefaultMap<Graph, Node, _Value> > Parent;
    221 
    222       NodeMap(const Graph& _g)
    223         : Parent(_g) {}
    224       NodeMap(const Graph& _g, const _Value& _v)
    225         : Parent(_g, _v) {}
     224      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
     225
     226      NodeMap(const Graph& graph)
     227        : Parent(graph) {}
     228      NodeMap(const Graph& graph, const _Value& value)
     229        : Parent(graph, value) {}
    226230
    227231      NodeMap& operator=(const NodeMap& cmap) {
     
    239243      NodeMap& operator=(const CMap& cmap) {
    240244        checkConcept<concept::ReadMap<Node, _Value>, CMap>();
    241         const typename Parent::Graph* graph = Parent::getGraph();
     245        const typename Parent::Notifier* notifier = Parent::getNotifier();
    242246        Node it;
    243         for (graph->first(it); it != INVALID; graph->next(it)) {
     247        for (notifier->first(it); it != INVALID; notifier->next(it)) {
    244248          Parent::set(it, cmap[it]);
    245249        }
     
    251255    template <typename _Value>
    252256    class EdgeMap
    253       : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
     257      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
    254258    public:
    255259      typedef GraphExtender Graph;
    256       typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    257 
    258       EdgeMap(const Graph& _g)
    259         : Parent(_g) {}
    260       EdgeMap(const Graph& _g, const _Value& _v)
    261         : Parent(_g, _v) {}
     260      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
     261
     262      EdgeMap(const Graph& graph)
     263        : Parent(graph) {}
     264      EdgeMap(const Graph& graph, const _Value& value)
     265        : Parent(graph, value) {}
    262266
    263267      EdgeMap& operator=(const EdgeMap& cmap) {
     
    268272      EdgeMap& operator=(const CMap& cmap) {
    269273        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
    270         const typename Parent::Graph* graph = Parent::getGraph();
     274        const typename Parent::Notifier* notifier = Parent::getNotifier();
    271275        Edge it;
    272         for (graph->first(it); it != INVALID; graph->next(it)) {
     276        for (notifier->first(it); it != INVALID; notifier->next(it)) {
    273277          Parent::set(it, cmap[it]);
    274278        }
     
    320324    }
    321325
     326    GraphExtender() {
     327      node_notifier.setContainer(*this);
     328      edge_notifier.setContainer(*this);
     329    }
     330   
    322331
    323332    ~GraphExtender() {
    324       getNotifier(Edge()).clear();
    325       getNotifier(Node()).clear();
     333      edge_notifier.clear();
     334      node_notifier.clear();
    326335    }
    327336  };
    328 
    329   /// \ingroup graphbits
    330   ///
    331   /// \brief BaseExtender for the UGraphs
    332   template <typename Base>
    333   class UGraphBaseExtender : public Base {
    334 
    335   public:
    336 
    337     typedef Base Parent;
    338     typedef typename Parent::Edge UEdge;
    339     typedef typename Parent::Node Node;
    340 
    341     typedef True UndirectedTag;
    342 
    343     class Edge : public UEdge {
    344       friend class UGraphBaseExtender;
    345 
    346     protected:
    347       bool forward;
    348 
    349       Edge(const UEdge &ue, bool _forward) :
    350         UEdge(ue), forward(_forward) {}
    351 
    352     public:
    353       Edge() {}
    354 
    355       /// Invalid edge constructor
    356       Edge(Invalid i) : UEdge(i), forward(true) {}
    357 
    358       bool operator==(const Edge &that) const {
    359         return forward==that.forward && UEdge(*this)==UEdge(that);
    360       }
    361       bool operator!=(const Edge &that) const {
    362         return forward!=that.forward || UEdge(*this)!=UEdge(that);
    363       }
    364       bool operator<(const Edge &that) const {
    365         return forward<that.forward ||
    366           (!(that.forward<forward) && UEdge(*this)<UEdge(that));
    367       }
    368     };
    369 
    370 
    371 
    372     using Parent::source;
    373 
    374     /// Source of the given Edge.
    375     Node source(const Edge &e) const {
    376       return e.forward ? Parent::source(e) : Parent::target(e);
    377     }
    378 
    379     using Parent::target;
    380 
    381     /// Target of the given Edge.
    382     Node target(const Edge &e) const {
    383       return e.forward ? Parent::target(e) : Parent::source(e);
    384     }
    385 
    386     /// \brief Directed edge from an undirected edge.
    387     ///
    388     /// Returns a directed edge corresponding to the specified UEdge.
    389     /// If the given bool is true the given undirected edge and the
    390     /// returned edge have the same source node.
    391     static Edge direct(const UEdge &ue, bool d) {
    392       return Edge(ue, d);
    393     }
    394 
    395     /// Returns whether the given directed edge is same orientation as the
    396     /// corresponding undirected edge.
    397     ///
    398     /// \todo reference to the corresponding point of the undirected graph
    399     /// concept. "What does the direction of an undirected edge mean?"
    400     static bool direction(const Edge &e) { return e.forward; }
    401 
    402 
    403     using Parent::first;
    404     using Parent::next;
    405 
    406     void first(Edge &e) const {
    407       Parent::first(e);
    408       e.forward=true;
    409     }
    410 
    411     void next(Edge &e) const {
    412       if( e.forward ) {
    413         e.forward = false;
    414       }
    415       else {
    416         Parent::next(e);
    417         e.forward = true;
    418       }
    419     }
    420 
    421     void firstOut(Edge &e, const Node &n) const {
    422       Parent::firstIn(e,n);
    423       if( UEdge(e) != INVALID ) {
    424         e.forward = false;
    425       }
    426       else {
    427         Parent::firstOut(e,n);
    428         e.forward = true;
    429       }
    430     }
    431     void nextOut(Edge &e) const {
    432       if( ! e.forward ) {
    433         Node n = Parent::target(e);
    434         Parent::nextIn(e);
    435         if( UEdge(e) == INVALID ) {
    436           Parent::firstOut(e, n);
    437           e.forward = true;
    438         }
    439       }
    440       else {
    441         Parent::nextOut(e);
    442       }
    443     }
    444 
    445     void firstIn(Edge &e, const Node &n) const {
    446       Parent::firstOut(e,n);
    447       if( UEdge(e) != INVALID ) {
    448         e.forward = false;
    449       }
    450       else {
    451         Parent::firstIn(e,n);
    452         e.forward = true;
    453       }
    454     }
    455     void nextIn(Edge &e) const {
    456       if( ! e.forward ) {
    457         Node n = Parent::source(e);
    458         Parent::nextOut(e);
    459         if( UEdge(e) == INVALID ) {
    460           Parent::firstIn(e, n);
    461           e.forward = true;
    462         }
    463       }
    464       else {
    465         Parent::nextIn(e);
    466       }
    467     }
    468 
    469     void firstInc(UEdge &e, bool &d, const Node &n) const {
    470       d = true;
    471       Parent::firstOut(e, n);
    472       if (e != INVALID) return;
    473       d = false;
    474       Parent::firstIn(e, n);
    475     }
    476 
    477     void nextInc(UEdge &e, bool &d) const {
    478       if (d) {
    479         Node s = Parent::source(e);
    480         Parent::nextOut(e);
    481         if (e != INVALID) return;
    482         d = false;
    483         Parent::firstIn(e, s);
    484       } else {
    485         Parent::nextIn(e);
    486       }
    487     }
    488 
    489     Node nodeFromId(int id) const {
    490       return Parent::nodeFromId(id);
    491     }
    492 
    493     Edge edgeFromId(int id) const {
    494       return direct(Parent::edgeFromId(id >> 1), bool(id & 1));
    495     }
    496 
    497     UEdge uEdgeFromId(int id) const {
    498       return Parent::edgeFromId(id >> 1);
    499     }
    500 
    501     int id(const Node &n) const {
    502       return Parent::id(n);
    503     }
    504 
    505     int id(const UEdge &e) const {
    506       return Parent::id(e);
    507     }
    508 
    509     int id(const Edge &e) const {
    510       return 2 * Parent::id(e) + int(e.forward);
    511     }
    512 
    513     int maxNodeId() const {
    514       return Parent::maxNodeId();
    515     }
    516 
    517     int maxEdgeId() const {
    518       return 2 * Parent::maxEdgeId() + 1;
    519     }
    520 
    521     int maxUEdgeId() const {
    522       return Parent::maxEdgeId();
    523     }
    524 
    525 
    526     int edgeNum() const {
    527       return 2 * Parent::edgeNum();
    528     }
    529 
    530     int uEdgeNum() const {
    531       return Parent::edgeNum();
    532     }
    533 
    534     Edge findEdge(Node source, Node target, Edge prev) const {
    535       if (prev == INVALID) {
    536         UEdge edge = Parent::findEdge(source, target);
    537         if (edge != INVALID) return direct(edge, true);
    538         edge = Parent::findEdge(target, source);
    539         if (edge != INVALID) return direct(edge, false);
    540       } else if (direction(prev)) {
    541         UEdge edge = Parent::findEdge(source, target, prev);
    542         if (edge != INVALID) return direct(edge, true);
    543         edge = Parent::findEdge(target, source);
    544         if (edge != INVALID) return direct(edge, false);       
    545       } else {
    546         UEdge edge = Parent::findEdge(target, source, prev);
    547         if (edge != INVALID) return direct(edge, false);             
    548       }
    549       return INVALID;
    550     }
    551 
    552     UEdge findUEdge(Node source, Node target, UEdge prev) const {
    553       if (prev == INVALID) {
    554         UEdge edge = Parent::findEdge(source, target);
    555         if (edge != INVALID) return edge;
    556         edge = Parent::findEdge(target, source);
    557         if (edge != INVALID) return edge;
    558       } else if (Parent::source(prev) == source) {
    559         UEdge edge = Parent::findEdge(source, target, prev);
    560         if (edge != INVALID) return edge;
    561         edge = Parent::findEdge(target, source);
    562         if (edge != INVALID) return edge;       
    563       } else {
    564         UEdge edge = Parent::findEdge(target, source, prev);
    565         if (edge != INVALID) return edge;             
    566       }
    567       return INVALID;
    568     }
    569   };
    570 
    571337
    572338  /// \ingroup graphbits
     
    630396    // Alterable extension
    631397
    632     typedef AlterationNotifier<Node> NodeNotifier;
    633     typedef AlterationNotifier<Edge> EdgeNotifier;
    634     typedef AlterationNotifier<UEdge> UEdgeNotifier;
     398    typedef AlterationNotifier<UGraphExtender, Node> NodeNotifier;
     399    typedef AlterationNotifier<UGraphExtender, Edge> EdgeNotifier;
     400    typedef AlterationNotifier<UGraphExtender, UEdge> UEdgeNotifier;
    635401
    636402
     
    843609    template <typename _Value>
    844610    class NodeMap
    845       : public IterableMapExtender<DefaultMap<Graph, Node, _Value> > {
     611      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
    846612    public:
    847613      typedef UGraphExtender Graph;
    848       typedef IterableMapExtender<DefaultMap<Graph, Node, _Value> > Parent;
    849 
    850       NodeMap(const Graph& _g)
    851         : Parent(_g) {}
    852       NodeMap(const Graph& _g, const _Value& _v)
    853         : Parent(_g, _v) {}
     614      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
     615
     616      NodeMap(const Graph& graph)
     617        : Parent(graph) {}
     618      NodeMap(const Graph& graph, const _Value& value)
     619        : Parent(graph, value) {}
    854620
    855621      NodeMap& operator=(const NodeMap& cmap) {
     
    867633      NodeMap& operator=(const CMap& cmap) {
    868634        checkConcept<concept::ReadMap<Node, _Value>, CMap>();
    869         const typename Parent::Graph* graph = Parent::getGraph();
     635        const typename Parent::Notifier* notifier = Parent::getNotifier();
    870636        Node it;
    871         for (graph->first(it); it != INVALID; graph->next(it)) {
     637        for (notifier->first(it); it != INVALID; notifier->next(it)) {
    872638          Parent::set(it, cmap[it]);
    873639        }
     
    879645    template <typename _Value>
    880646    class EdgeMap
    881       : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
     647      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
    882648    public:
    883649      typedef UGraphExtender Graph;
    884       typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    885 
    886       EdgeMap(const Graph& _g)
    887         : Parent(_g) {}
    888       EdgeMap(const Graph& _g, const _Value& _v)
    889         : Parent(_g, _v) {}
     650      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
     651
     652      EdgeMap(const Graph& graph)
     653        : Parent(graph) {}
     654      EdgeMap(const Graph& graph, const _Value& value)
     655        : Parent(graph, value) {}
    890656
    891657      EdgeMap& operator=(const EdgeMap& cmap) {
     
    896662      EdgeMap& operator=(const CMap& cmap) {
    897663        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
    898         const typename Parent::Graph* graph = Parent::getGraph();
     664        const typename Parent::Notifier* notifier = Parent::getNotifier();
    899665        Edge it;
    900         for (graph->first(it); it != INVALID; graph->next(it)) {
     666        for (notifier->first(it); it != INVALID; notifier->next(it)) {
    901667          Parent::set(it, cmap[it]);
    902668        }
     
    908674    template <typename _Value>
    909675    class UEdgeMap
    910       : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
     676      : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
    911677    public:
    912678      typedef UGraphExtender Graph;
    913       typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
    914 
    915       UEdgeMap(const Graph& _g)
    916         : Parent(_g) {}
    917       UEdgeMap(const Graph& _g, const _Value& _v)
    918         : Parent(_g, _v) {}
     679      typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
     680
     681      UEdgeMap(const Graph& graph)
     682        : Parent(graph) {}
     683      UEdgeMap(const Graph& graph, const _Value& value)
     684        : Parent(graph, value) {}
    919685
    920686      UEdgeMap& operator=(const UEdgeMap& cmap) {
     
    925691      UEdgeMap& operator=(const CMap& cmap) {
    926692        checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
    927         const typename Parent::Graph* graph = Parent::getGraph();
    928         UEdge it;
    929         for (graph->first(it); it != INVALID; graph->next(it)) {
     693        const typename Parent::Notifier* notifier = Parent::getNotifier();
     694        Edge it;
     695        for (notifier->first(it); it != INVALID; notifier->next(it)) {
    930696          Parent::set(it, cmap[it]);
    931697        }
     
    982748    }
    983749
     750    UGraphExtender() {
     751      node_notifier.setContainer(*this);
     752      edge_notifier.setContainer(*this);
     753      uedge_notifier.setContainer(*this);
     754    }
     755
    984756    ~UGraphExtender() {
    985       getNotifier(Edge()).clear();
    986       getNotifier(UEdge()).clear();
    987       getNotifier(Node()).clear();
    988     }
    989 
    990   };
    991 
    992 
    993   /// \ingroup graphbits
    994   ///
    995   /// \brief BaseExtender for the BpUGraphs
    996   template <typename Base>
    997   class BpUGraphBaseExtender : public Base {
    998   public:
    999     typedef Base Parent;
    1000     typedef BpUGraphBaseExtender Graph;
    1001 
    1002     typedef typename Parent::Node Node;
    1003     typedef typename Parent::Edge UEdge;
    1004 
    1005 
    1006     using Parent::first;
    1007     using Parent::next;
    1008 
    1009     using Parent::id;
    1010 
    1011     class ANode : public Node {
    1012       friend class BpUGraphBaseExtender;
    1013     public:
    1014       ANode() {}
    1015       ANode(const Node& node) : Node(node) {
    1016         LEMON_ASSERT(Parent::aNode(node) || node == INVALID,
    1017                      typename Parent::NodeSetError());
    1018       }
    1019       ANode(Invalid) : Node(INVALID) {}
    1020     };
    1021 
    1022     void first(ANode& node) const {
    1023       Parent::firstANode(static_cast<Node&>(node));
    1024     }
    1025     void next(ANode& node) const {
    1026       Parent::nextANode(static_cast<Node&>(node));
    1027     }
    1028 
    1029     int id(const ANode& node) const {
    1030       return Parent::aNodeId(node);
    1031     }
    1032 
    1033     class BNode : public Node {
    1034       friend class BpUGraphBaseExtender;
    1035     public:
    1036       BNode() {}
    1037       BNode(const Node& node) : Node(node) {
    1038         LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
    1039                      typename Parent::NodeSetError());
    1040       }
    1041       BNode(Invalid) : Node(INVALID) {}
    1042     };
    1043 
    1044     void first(BNode& node) const {
    1045       Parent::firstBNode(static_cast<Node&>(node));
    1046     }
    1047     void next(BNode& node) const {
    1048       Parent::nextBNode(static_cast<Node&>(node));
    1049     }
    1050  
    1051     int id(const BNode& node) const {
    1052       return Parent::aNodeId(node);
    1053     }
    1054 
    1055     Node source(const UEdge& edge) const {
    1056       return aNode(edge);
    1057     }
    1058     Node target(const UEdge& edge) const {
    1059       return bNode(edge);
    1060     }
    1061 
    1062     void firstInc(UEdge& edge, bool& direction, const Node& node) const {
    1063       if (Parent::aNode(node)) {
    1064         Parent::firstOut(edge, node);
    1065         direction = true;
    1066       } else {
    1067         Parent::firstIn(edge, node);
    1068         direction = static_cast<UEdge&>(edge) == INVALID;
    1069       }
    1070     }
    1071     void nextInc(UEdge& edge, bool& direction) const {
    1072       if (direction) {
    1073         Parent::nextOut(edge);
    1074       } else {
    1075         Parent::nextIn(edge);
    1076         if (edge == INVALID) direction = true;
    1077       }
    1078     }
    1079 
    1080     int maxUEdgeId() const {
    1081       return Parent::maxEdgeId();
    1082     }
    1083 
    1084     UEdge uEdgeFromId(int id) const {
    1085       return Parent::edgeFromId(id);
    1086     }
    1087 
    1088     class Edge : public UEdge {
    1089       friend class BpUGraphBaseExtender;
    1090     protected:
    1091       bool forward;
    1092 
    1093       Edge(const UEdge& edge, bool _forward)
    1094         : UEdge(edge), forward(_forward) {}
    1095 
    1096     public:
    1097       Edge() {}
    1098       Edge (Invalid) : UEdge(INVALID), forward(true) {}
    1099       bool operator==(const Edge& i) const {
    1100         return UEdge::operator==(i) && forward == i.forward;
    1101       }
    1102       bool operator!=(const Edge& i) const {
    1103         return UEdge::operator!=(i) || forward != i.forward;
    1104       }
    1105       bool operator<(const Edge& i) const {
    1106         return UEdge::operator<(i) ||
    1107           (!(i.forward<forward) && UEdge(*this)<UEdge(i));
    1108       }
    1109     };
    1110 
    1111     void first(Edge& edge) const {
    1112       Parent::first(static_cast<UEdge&>(edge));
    1113       edge.forward = true;
    1114     }
    1115 
    1116     void next(Edge& edge) const {
    1117       if (!edge.forward) {
    1118         Parent::next(static_cast<UEdge&>(edge));
    1119       }
    1120       edge.forward = !edge.forward;
    1121     }
    1122 
    1123     void firstOut(Edge& edge, const Node& node) const {
    1124       if (Parent::aNode(node)) {
    1125         Parent::firstOut(edge, node);
    1126         edge.forward = true;
    1127       } else {
    1128         Parent::firstIn(edge, node);
    1129         edge.forward = static_cast<UEdge&>(edge) == INVALID;
    1130       }
    1131     }
    1132     void nextOut(Edge& edge) const {
    1133       if (edge.forward) {
    1134         Parent::nextOut(edge);
    1135       } else {
    1136         Parent::nextIn(edge);
    1137         edge.forward = static_cast<UEdge&>(edge) == INVALID;
    1138       }
    1139     }
    1140 
    1141     void firstIn(Edge& edge, const Node& node) const {
    1142       if (Parent::bNode(node)) {
    1143         Parent::firstIn(edge, node);
    1144         edge.forward = true;   
    1145       } else {
    1146         Parent::firstOut(edge, node);
    1147         edge.forward = static_cast<UEdge&>(edge) == INVALID;
    1148       }
    1149     }
    1150     void nextIn(Edge& edge) const {
    1151       if (edge.forward) {
    1152         Parent::nextIn(edge);
    1153       } else {
    1154         Parent::nextOut(edge);
    1155         edge.forward = static_cast<UEdge&>(edge) == INVALID;
    1156       }
    1157     }
    1158 
    1159     Node source(const Edge& edge) const {
    1160       return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);
    1161     }
    1162     Node target(const Edge& edge) const {
    1163       return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
    1164     }
    1165 
    1166     int id(const Edge& edge) const {
    1167       return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1);
    1168     }
    1169     Edge edgeFromId(int id) const {
    1170       return Edge(Parent::fromId(id >> 1, UEdge()), (id & 1) == 0);
    1171     }
    1172     int maxEdgeId() const {
    1173       return (Parent::maxId(UEdge()) << 1) + 1;
    1174     }
    1175 
    1176     bool direction(const Edge& edge) const {
    1177       return edge.forward;
    1178     }
    1179 
    1180     Edge direct(const UEdge& edge, bool direction) const {
    1181       return Edge(edge, direction);
    1182     }
     757      uedge_notifier.clear();
     758      edge_notifier.clear();
     759      node_notifier.clear();
     760    }
     761
    1183762  };
    1184763
     
    1246825    } 
    1247826 
    1248     typedef AlterationNotifier<Node> NodeNotifier;
    1249     typedef AlterationNotifier<BNode> BNodeNotifier;
    1250     typedef AlterationNotifier<ANode> ANodeNotifier;
    1251     typedef AlterationNotifier<Edge> EdgeNotifier;
    1252     typedef AlterationNotifier<UEdge> UEdgeNotifier;
     827    typedef AlterationNotifier<BpUGraphExtender, ANode> ANodeNotifier;
     828    typedef AlterationNotifier<BpUGraphExtender, BNode> BNodeNotifier;
     829    typedef AlterationNotifier<BpUGraphExtender, Node> NodeNotifier;
     830    typedef AlterationNotifier<BpUGraphExtender, Edge> EdgeNotifier;
     831    typedef AlterationNotifier<BpUGraphExtender, UEdge> UEdgeNotifier;
    1253832
    1254833  protected:
    1255834
    1256     mutable NodeNotifier nodeNotifier;
    1257     mutable BNodeNotifier bNodeNotifier;
    1258     mutable ANodeNotifier aNodeNotifier;
    1259     mutable EdgeNotifier edgeNotifier;
    1260     mutable UEdgeNotifier uEdgeNotifier;
     835    mutable ANodeNotifier anode_notifier;
     836    mutable BNodeNotifier bnode_notifier;
     837    mutable NodeNotifier node_notifier;
     838    mutable EdgeNotifier edge_notifier;
     839    mutable UEdgeNotifier uedge_notifier;
    1261840
    1262841  public:
    1263842
    1264843    NodeNotifier& getNotifier(Node) const {
    1265       return nodeNotifier;
     844      return node_notifier;
     845    }
     846
     847    ANodeNotifier& getNotifier(ANode) const {
     848      return anode_notifier;
    1266849    }
    1267850
    1268851    BNodeNotifier& getNotifier(BNode) const {
    1269       return bNodeNotifier;
    1270     }
    1271 
    1272     ANodeNotifier& getNotifier(ANode) const {
    1273       return aNodeNotifier;
     852      return bnode_notifier;
    1274853    }
    1275854
    1276855    EdgeNotifier& getNotifier(Edge) const {
    1277       return edgeNotifier;
     856      return edge_notifier;
    1278857    }
    1279858
    1280859    UEdgeNotifier& getNotifier(UEdge) const {
    1281       return uEdgeNotifier;
     860      return uedge_notifier;
    1282861    }
    1283862
     
    15121091    template <typename _Value>
    15131092    class ANodeMap
    1514       : public IterableMapExtender<DefaultMap<Graph, ANode, _Value> > {
     1093      : public MapExtender<DefaultMap<Graph, ANode, _Value> > {
    15151094    public:
    15161095      typedef BpUGraphExtender Graph;
    1517       typedef IterableMapExtender<DefaultMap<Graph, ANode, _Value> >
    1518       Parent;
    1519    
    1520       ANodeMap(const Graph& _g)
    1521         : Parent(_g) {}
    1522       ANodeMap(const Graph& _g, const _Value& _v)
    1523         : Parent(_g, _v) {}
     1096      typedef MapExtender<DefaultMap<Graph, ANode, _Value> > Parent;
     1097   
     1098      ANodeMap(const Graph& graph)
     1099        : Parent(graph) {}
     1100      ANodeMap(const Graph& graph, const _Value& value)
     1101        : Parent(graph, value) {}
    15241102   
    15251103      ANodeMap& operator=(const ANodeMap& cmap) {
     
    15491127    template <typename _Value>
    15501128    class BNodeMap
    1551       : public IterableMapExtender<DefaultMap<Graph, BNode, _Value> > {
     1129      : public MapExtender<DefaultMap<Graph, BNode, _Value> > {
    15521130    public:
    15531131      typedef BpUGraphExtender Graph;
    1554       typedef IterableMapExtender<DefaultMap<Graph, BNode, _Value> >
    1555       Parent;
    1556    
    1557       BNodeMap(const Graph& _g)
    1558         : Parent(_g) {}
    1559       BNodeMap(const Graph& _g, const _Value& _v)
    1560         : Parent(_g, _v) {}
     1132      typedef MapExtender<DefaultMap<Graph, BNode, _Value> > Parent;
     1133   
     1134      BNodeMap(const Graph& graph)
     1135        : Parent(graph) {}
     1136      BNodeMap(const Graph& graph, const _Value& value)
     1137        : Parent(graph, value) {}
    15611138   
    15621139      BNodeMap& operator=(const BNodeMap& cmap) {
     
    15951172
    15961173      /// The reference type of the map;
    1597       typedef typename BNodeMap<_Value>::Reference Reference;
    1598       /// The pointer type of the map;
    1599       typedef typename BNodeMap<_Value>::Pointer Pointer;
    1600      
    1601       /// The const value type of the map.
    1602       typedef const Value ConstValue;
     1174      typedef typename ANodeMap<_Value>::Reference Reference;
    16031175      /// The const reference type of the map;
    1604       typedef typename BNodeMap<_Value>::ConstReference ConstReference;
    1605       /// The pointer type of the map;
    1606       typedef typename BNodeMap<_Value>::ConstPointer ConstPointer;
     1176      typedef typename ANodeMap<_Value>::ConstReference ConstReference;
    16071177
    16081178      typedef True ReferenceMapTag;
    16091179
    1610       NodeMapBase(const Graph& _g)
    1611         : aNodeMap(_g), bNodeMap(_g) {}
    1612       NodeMapBase(const Graph& _g, const _Value& _v)
    1613         : aNodeMap(_g, _v), bNodeMap(_g, _v) {}
     1180      NodeMapBase(const Graph& graph)
     1181        : aNodeMap(graph), bNodeMap(graph) {}
     1182      NodeMapBase(const Graph& graph, const _Value& value)
     1183        : aNodeMap(graph, value), bNodeMap(graph, value) {}
    16141184
    16151185      ConstReference operator[](const Key& node) const {
     
    16501220    template <typename _Value>
    16511221    class NodeMap
    1652       : public IterableMapExtender<NodeMapBase<_Value> > {
     1222      : public MapExtender<NodeMapBase<_Value> > {
    16531223    public:
    16541224      typedef BpUGraphExtender Graph;
    1655       typedef IterableMapExtender< NodeMapBase<_Value> > Parent;
    1656    
    1657       NodeMap(const Graph& _g)
    1658         : Parent(_g) {}
    1659       NodeMap(const Graph& _g, const _Value& _v)
    1660         : Parent(_g, _v) {}
     1225      typedef MapExtender< NodeMapBase<_Value> > Parent;
     1226   
     1227      NodeMap(const Graph& graph)
     1228        : Parent(graph) {}
     1229      NodeMap(const Graph& graph, const _Value& value)
     1230        : Parent(graph, value) {}
    16611231   
    16621232      NodeMap& operator=(const NodeMap& cmap) {
     
    16741244      NodeMap& operator=(const CMap& cmap) {
    16751245        checkConcept<concept::ReadMap<Node, _Value>, CMap>();
    1676         const typename Parent::Graph* graph = Parent::getGraph();
    1677         Node it;
    1678         for (graph->first(it); it != INVALID; graph->next(it)) {
     1246        const typename Parent::Notifier* notifier = Parent::getNotifier();
     1247        Edge it;
     1248        for (notifier->first(it); it != INVALID; notifier->next(it)) {
    16791249          Parent::set(it, cmap[it]);
    16801250        }
     
    16881258    template <typename _Value>
    16891259    class EdgeMap
    1690       : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
     1260      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
    16911261    public:
    16921262      typedef BpUGraphExtender Graph;
    1693       typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    1694    
    1695       EdgeMap(const Graph& _g)
    1696         : Parent(_g) {}
    1697       EdgeMap(const Graph& _g, const _Value& _v)
    1698         : Parent(_g, _v) {}
     1263      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
     1264   
     1265      EdgeMap(const Graph& graph)
     1266        : Parent(graph) {}
     1267      EdgeMap(const Graph& graph, const _Value& value)
     1268        : Parent(graph, value) {}
    16991269   
    17001270      EdgeMap& operator=(const EdgeMap& cmap) {
     
    17051275      EdgeMap& operator=(const CMap& cmap) {
    17061276        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
    1707         const typename Parent::Graph* graph = Parent::getGraph();
     1277        const typename Parent::Notifier* notifier = Parent::getNotifier();
    17081278        Edge it;
    1709         for (graph->first(it); it != INVALID; graph->next(it)) {
     1279        for (notifier->first(it); it != INVALID; notifier->next(it)) {
    17101280          Parent::set(it, cmap[it]);
    17111281        }
     
    17161286    template <typename _Value>
    17171287    class UEdgeMap
    1718       : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
     1288      : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
    17191289    public:
    17201290      typedef BpUGraphExtender Graph;
    1721       typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> >
    1722       Parent;
    1723    
    1724       UEdgeMap(const Graph& _g)
    1725         : Parent(_g) {}
    1726       UEdgeMap(const Graph& _g, const _Value& _v)
    1727         : Parent(_g, _v) {}
     1291      typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
     1292   
     1293      UEdgeMap(const Graph& graph)
     1294        : Parent(graph) {}
     1295      UEdgeMap(const Graph& graph, const _Value& value)
     1296        : Parent(graph, value) {}
    17281297   
    17291298      UEdgeMap& operator=(const UEdgeMap& cmap) {
     
    17341303      UEdgeMap& operator=(const CMap& cmap) {
    17351304        checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
    1736         const typename Parent::Graph* graph = Parent::getGraph();
    1737         UEdge it;
    1738         for (graph->first(it); it != INVALID; graph->next(it)) {
     1305        const typename Parent::Notifier* notifier = Parent::getNotifier();
     1306        Edge it;
     1307        for (notifier->first(it); it != INVALID; notifier->next(it)) {
    17391308          Parent::set(it, cmap[it]);
    17401309        }
     
    18021371
    18031372
     1373    BpUGraphExtender() {
     1374      anode_notifier.setContainer(*this);
     1375      bnode_notifier.setContainer(*this);
     1376      node_notifier.setContainer(*this);
     1377      edge_notifier.setContainer(*this);
     1378      uedge_notifier.setContainer(*this);
     1379    }
     1380
    18041381    ~BpUGraphExtender() {
    1805       getNotifier(Edge()).clear();
    1806       getNotifier(UEdge()).clear();
    1807       getNotifier(Node()).clear();
    1808       getNotifier(BNode()).clear();
    1809       getNotifier(ANode()).clear();
     1382      uedge_notifier.clear();
     1383      edge_notifier.clear();
     1384      node_notifier.clear();
     1385      anode_notifier.clear();
     1386      bnode_notifier.clear();
    18101387    }
    18111388
  • lemon/bits/map_extender.h

    r1996 r1999  
    3030
    3131  /// \ingroup graphbits
     32  ///
     33  /// \brief Extender for maps
    3234  template <typename _Map>
    33   class IterableMapExtender : public _Map {
     35  class MapExtender : public _Map {
    3436  public:
    3537
    3638    typedef _Map Parent;
    37     typedef IterableMapExtender Map;
     39    typedef MapExtender Map;
    3840
    3941
     
    5052    friend class ConstMapIt;
    5153
    52   protected:
    53 
    54     using Parent::getGraph;
    55 
    5654  public:
    5755
    58     IterableMapExtender(const Graph& graph) : Parent(graph) {}
     56    MapExtender(const Graph& graph)
     57      : Parent(graph) {}
    5958
    60     IterableMapExtender(const Graph& graph, const Value& value)
     59    MapExtender(const Graph& graph, const Value& value)
    6160      : Parent(graph, value) {}
    6261
    6362
    64     class MapIt : public ItemSetTraits<Graph, Item>::ItemIt {
     63    class MapIt : public Item {
    6564    public:
    6665     
    67       typedef typename ItemSetTraits<Graph, Item>::ItemIt Parent;
    68 
     66      typedef Item Parent;
    6967      typedef typename Map::Value Value;
    7068     
    71       MapIt(Map& _map) : Parent(*_map.getGraph()), map(_map) {}
     69      MapIt() {}
     70
     71      MapIt(Invalid i) : Parent(i) { }
     72
     73      explicit MapIt(Map& _map) : map(_map) {
     74        map.getNotifier()->first(*this);
     75      }
     76
     77      MapIt(const Map& _map, const Item& item)
     78        : Parent(item), map(_map) {}
     79
     80      MapIt& operator++() {
     81        map.getNotifier()->next(*this);
     82        return *this;
     83      }
    7284     
    7385      typename MapTraits<Map>::ConstReturnValue operator*() const {
     
    88100    };
    89101
    90     class ConstMapIt : public ItemSetTraits<Graph, Key>::ItemIt {
     102    class ConstMapIt : public Item {
    91103    public:
    92104
    93       typedef typename ItemSetTraits<Graph, Key>::ItemIt Parent;
     105      typedef Item Parent;
    94106
    95107      typedef typename Map::Value Value;
     108     
     109      ConstMapIt() {}
    96110
    97       ConstMapIt(const Map& _map) : Parent(*_map.getGraph()), map(_map) {}
     111      ConstMapIt(Invalid i) : Parent(i) { }
     112
     113      explicit ConstMapIt(Map& _map) : map(_map) {
     114        map.getNotifier()->first(*this);
     115      }
     116
     117      ConstMapIt(const Map& _map, const Item& item)
     118        : Parent(item), map(_map) {}
     119
     120      ConstMapIt& operator++() {
     121        map.getNotifier()->next(*this);
     122        return *this;
     123      }
    98124
    99125      typename MapTraits<Map>::ConstReturnValue operator*() const {
    100126        return map[*this];
    101127      }
     128
    102129    protected:
    103130      const Map& map;
    104131    };
    105132
    106     class ItemIt : public ItemSetTraits<Graph, Key>::ItemIt {
     133    class ItemIt : Item {
    107134    public:
    108135     
    109       typedef typename ItemSetTraits<Graph, Key>::ItemIt Parent;
     136      typedef Item Parent;
     137     
     138      ItemIt() {}
    110139
    111       ItemIt(Map& _map) : Parent(*_map.getGraph()) {}
     140      ItemIt(Invalid i) : Parent(i) { }
     141
     142      explicit ItemIt(Map& _map) : map(_map) {
     143        map->getNotifier()->first(*this);
     144      }
     145
     146      ItemIt(const Map& _map, const Item& item)
     147        : Parent(item), map(_map) {}
     148
     149      ItemIt& operator++() {
     150        map.getNotifier()->next(*this);
     151        return *this;
     152      }
     153
     154    protected:
     155      const Map& map;
    112156     
    113157    };
  • 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.