COIN-OR::LEMON - Graph Library

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/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
Note: See TracChangeset for help on using the changeset viewer.