lemon/bits/alteration_notifier.h
changeset 89 e6452a49192c
child 107 31a2e6d28f61
equal deleted inserted replaced
-1:000000000000 0:60aa8a3b3904
       
     1 /* -*- C++ -*-
       
     2  *
       
     3  * This file is a part of LEMON, a generic C++ optimization library
       
     4  *
       
     5  * Copyright (C) 2003-2007
       
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
       
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
       
     8  *
       
     9  * Permission to use, modify and distribute this software is granted
       
    10  * provided that this copyright notice appears in all copies. For
       
    11  * precise terms see the accompanying LICENSE file.
       
    12  *
       
    13  * This software is provided "AS IS" with no warranty of any kind,
       
    14  * express or implied, and with no claim as to its suitability for any
       
    15  * purpose.
       
    16  *
       
    17  */
       
    18 
       
    19 #ifndef LEMON_BITS_ALTERATION_NOTIFIER_H
       
    20 #define LEMON_BITS_ALTERATION_NOTIFIER_H
       
    21 
       
    22 #include <vector>
       
    23 #include <list>
       
    24 
       
    25 #include <lemon/bits/utility.h>
       
    26 
       
    27 ///\ingroup graphbits
       
    28 ///\file
       
    29 ///\brief Observer notifier for graph alteration observers.
       
    30 
       
    31 namespace lemon {
       
    32 
       
    33   /// \ingroup graphbits
       
    34   ///
       
    35   /// \brief Notifier class to notify observes about alterations in 
       
    36   /// a container.
       
    37   ///
       
    38   /// The simple graph's can be refered as two containers, one node container
       
    39   /// and one edge container. But they are not standard containers they
       
    40   /// does not store values directly they are just key continars for more
       
    41   /// value containers which are the node and edge maps.
       
    42   ///
       
    43   /// The graph's node and edge sets can be changed as we add or erase
       
    44   /// nodes and edges in the graph. Lemon would like to handle easily
       
    45   /// that the node and edge maps should contain values for all nodes or
       
    46   /// edges. If we want to check on every indicing if the map contains
       
    47   /// the current indicing key that cause a drawback in the performance
       
    48   /// in the library. We use another solution we notify all maps about
       
    49   /// an alteration in the graph, which cause only drawback on the
       
    50   /// alteration of the graph.
       
    51   ///
       
    52   /// This class provides an interface to the container. The \e first() and \e 
       
    53   /// next() member functions make possible to iterate on the keys of the
       
    54   /// container. The \e id() function returns an integer id for each key.
       
    55   /// The \e maxId() function gives back an upper bound of the ids.
       
    56   ///
       
    57   /// For the proper functonality of this class, we should notify it
       
    58   /// about each alteration in the container. The alterations have four type
       
    59   /// as \e add(), \e erase(), \e build() and \e clear(). The \e add() and
       
    60   /// \e erase() signals that only one or few items added or erased to or
       
    61   /// from the graph. If all items are erased from the graph or from an empty
       
    62   /// graph a new graph is builded then it can be signaled with the
       
    63   /// clear() and build() members. Important rule that if we erase items 
       
    64   /// from graph we should first signal the alteration and after that erase
       
    65   /// them from the container, on the other way on item addition we should
       
    66   /// first extend the container and just after that signal the alteration.
       
    67   ///
       
    68   /// The alteration can be observed with a class inherited from the
       
    69   /// \e ObserverBase nested class. The signals can be handled with
       
    70   /// overriding the virtual functions defined in the base class.  The
       
    71   /// observer base can be attached to the notifier with the 
       
    72   /// \e attach() member and can be detached with detach() function. The
       
    73   /// alteration handlers should not call any function which signals
       
    74   /// an other alteration in the same notifier and should not
       
    75   /// detach any observer from the notifier.
       
    76   ///
       
    77   /// Alteration observers try to be exception safe. If an \e add() or
       
    78   /// a \e clear() function throws an exception then the remaining
       
    79   /// observeres will not be notified and the fulfilled additions will
       
    80   /// be rolled back by calling the \e erase() or \e clear()
       
    81   /// functions. Thence the \e erase() and \e clear() should not throw
       
    82   /// exception. Actullay, it can be throw only 
       
    83   /// \ref AlterationObserver::ImmediateDetach ImmediateDetach
       
    84   /// exception which detach the observer from the notifier.
       
    85   ///
       
    86   /// There are some place when the alteration observing is not completly
       
    87   /// reliable. If we want to carry out the node degree in the graph
       
    88   /// as in the \ref InDegMap and we use the reverseEdge that cause 
       
    89   /// unreliable functionality. Because the alteration observing signals
       
    90   /// only erasing and adding but not the reversing it will stores bad
       
    91   /// degrees. The sub graph adaptors cannot signal the alterations because
       
    92   /// just a setting in the filter map can modify the graph and this cannot
       
    93   /// be watched in any way.
       
    94   ///
       
    95   /// \param _Container The container which is observed.
       
    96   /// \param _Item The item type which is obserbved.
       
    97   ///
       
    98   /// \author Balazs Dezso
       
    99 
       
   100   template <typename _Container, typename _Item>
       
   101   class AlterationNotifier {
       
   102   public:
       
   103 
       
   104     typedef True Notifier;
       
   105 
       
   106     typedef _Container Container;
       
   107     typedef _Item Item;
       
   108 
       
   109     /// \brief Exception which can be called from \e clear() and 
       
   110     /// \e erase().
       
   111     ///
       
   112     /// From the \e clear() and \e erase() function only this
       
   113     /// exception is allowed to throw. The exception immediatly
       
   114     /// detaches the current observer from the notifier. Because the
       
   115     /// \e clear() and \e erase() should not throw other exceptions
       
   116     /// it can be used to invalidate the observer.
       
   117     struct ImmediateDetach {};
       
   118 
       
   119     /// \brief ObserverBase is the base class for the observers.
       
   120     ///
       
   121     /// ObserverBase is the abstract base class for the observers.
       
   122     /// It will be notified about an item was inserted into or
       
   123     /// erased from the graph.
       
   124     ///
       
   125     /// The observer interface contains some pure virtual functions
       
   126     /// to override. The add() and erase() functions are
       
   127     /// to notify the oberver when one item is added or
       
   128     /// erased.
       
   129     ///
       
   130     /// The build() and clear() members are to notify the observer
       
   131     /// about the container is built from an empty container or
       
   132     /// is cleared to an empty container. 
       
   133     /// 
       
   134     /// \author Balazs Dezso
       
   135 
       
   136     class ObserverBase {
       
   137     protected:
       
   138       typedef AlterationNotifier Notifier;
       
   139 
       
   140       friend class AlterationNotifier;
       
   141 
       
   142       /// \brief Default constructor.
       
   143       ///
       
   144       /// Default constructor for ObserverBase.
       
   145       /// 
       
   146       ObserverBase() : _notifier(0) {}
       
   147 
       
   148       /// \brief Constructor which attach the observer into notifier.
       
   149       ///
       
   150       /// Constructor which attach the observer into notifier.
       
   151       ObserverBase(AlterationNotifier& nf) {
       
   152         attach(nf);
       
   153       }
       
   154 
       
   155       /// \brief Constructor which attach the obserever to the same notifier.
       
   156       ///
       
   157       /// Constructor which attach the obserever to the same notifier as
       
   158       /// the other observer is attached to. 
       
   159       ObserverBase(const ObserverBase& copy) {
       
   160 	if (copy.attached()) {
       
   161           attach(*copy.notifier());
       
   162 	}
       
   163       }
       
   164 	
       
   165       /// \brief Destructor
       
   166       virtual ~ObserverBase() {
       
   167         if (attached()) {
       
   168           detach();
       
   169         }
       
   170       }
       
   171 
       
   172       /// \brief Attaches the observer into an AlterationNotifier.
       
   173       ///
       
   174       /// This member attaches the observer into an AlterationNotifier.
       
   175       ///
       
   176       void attach(AlterationNotifier& nf) {
       
   177 	nf.attach(*this);
       
   178       }
       
   179       
       
   180       /// \brief Detaches the observer into an AlterationNotifier.
       
   181       ///
       
   182       /// This member detaches the observer from an AlterationNotifier.
       
   183       ///
       
   184       void detach() {
       
   185         _notifier->detach(*this);
       
   186       }
       
   187       
       
   188       /// \brief Gives back a pointer to the notifier which the map 
       
   189       /// attached into.
       
   190       ///
       
   191       /// This function gives back a pointer to the notifier which the map
       
   192       /// attached into.
       
   193       ///
       
   194       Notifier* notifier() const { return const_cast<Notifier*>(_notifier); }
       
   195       
       
   196       /// Gives back true when the observer is attached into a notifier.
       
   197       bool attached() const { return _notifier != 0; }
       
   198 
       
   199     private:
       
   200 
       
   201       ObserverBase& operator=(const ObserverBase& copy);
       
   202 
       
   203     protected:
       
   204       
       
   205       Notifier* _notifier;
       
   206       typename std::list<ObserverBase*>::iterator _index;
       
   207 
       
   208       /// \brief The member function to notificate the observer about an
       
   209       /// item is added to the container.
       
   210       ///
       
   211       /// The add() member function notificates the observer about an item
       
   212       /// is added to the container. It have to be overrided in the
       
   213       /// subclasses.
       
   214       virtual void add(const Item&) = 0;
       
   215 
       
   216       /// \brief The member function to notificate the observer about 
       
   217       /// more item is added to the container.
       
   218       ///
       
   219       /// The add() member function notificates the observer about more item
       
   220       /// is added to the container. It have to be overrided in the
       
   221       /// subclasses.
       
   222       virtual void add(const std::vector<Item>& items) = 0;
       
   223 
       
   224       /// \brief The member function to notificate the observer about an
       
   225       /// item is erased from the container.
       
   226       ///
       
   227       /// The erase() member function notificates the observer about an
       
   228       /// item is erased from the container. It have to be overrided in
       
   229       /// the subclasses.	
       
   230       virtual void erase(const Item&) = 0;
       
   231 
       
   232       /// \brief The member function to notificate the observer about 
       
   233       /// more item is erased from the container.
       
   234       ///
       
   235       /// The erase() member function notificates the observer about more item
       
   236       /// is erased from the container. It have to be overrided in the
       
   237       /// subclasses.
       
   238       virtual void erase(const std::vector<Item>& items) = 0;
       
   239 
       
   240       /// \brief The member function to notificate the observer about the
       
   241       /// container is built.
       
   242       ///
       
   243       /// The build() member function notificates the observer about the
       
   244       /// container is built from an empty container. It have to be
       
   245       /// overrided in the subclasses.
       
   246 
       
   247       virtual void build() = 0;
       
   248 
       
   249       /// \brief The member function to notificate the observer about all
       
   250       /// items are erased from the container.
       
   251       ///
       
   252       /// The clear() member function notificates the observer about all
       
   253       /// items are erased from the container. It have to be overrided in
       
   254       /// the subclasses.      
       
   255       virtual void clear() = 0;
       
   256 
       
   257     };
       
   258 	
       
   259   protected:
       
   260 
       
   261     const Container* container;
       
   262 
       
   263     typedef std::list<ObserverBase*> Observers; 
       
   264     Observers _observers;
       
   265 
       
   266 		
       
   267   public:
       
   268 
       
   269     /// \brief Default constructor.
       
   270     ///
       
   271     /// The default constructor of the AlterationNotifier. 
       
   272     /// It creates an empty notifier.
       
   273     AlterationNotifier() 
       
   274       : container(0) {}
       
   275 
       
   276     /// \brief Constructor.
       
   277     ///
       
   278     /// Constructor with the observed container parameter.
       
   279     AlterationNotifier(const Container& _container) 
       
   280       : container(&_container) {}
       
   281 
       
   282     /// \brief Copy Constructor of the AlterationNotifier. 
       
   283     ///
       
   284     /// Copy constructor of the AlterationNotifier. 
       
   285     /// It creates only an empty notifier because the copiable
       
   286     /// notifier's observers have to be registered still into that notifier.
       
   287     AlterationNotifier(const AlterationNotifier& _notifier) 
       
   288       : container(_notifier.container) {}
       
   289 
       
   290     /// \brief Destructor.
       
   291     ///		
       
   292     /// Destructor of the AlterationNotifier.
       
   293     ///
       
   294     ~AlterationNotifier() {
       
   295       typename Observers::iterator it;
       
   296       for (it = _observers.begin(); it != _observers.end(); ++it) {
       
   297 	(*it)->_notifier = 0;
       
   298       }
       
   299     }
       
   300 
       
   301     /// \brief Sets the container.
       
   302     ///
       
   303     /// Sets the container.
       
   304     void setContainer(const Container& _container) {
       
   305       container = &_container;
       
   306     }
       
   307 
       
   308   protected:
       
   309 
       
   310     AlterationNotifier& operator=(const AlterationNotifier&);
       
   311 
       
   312   public:
       
   313 
       
   314 
       
   315 
       
   316     /// \brief First item in the container.
       
   317     ///
       
   318     /// Returns the first item in the container. It is
       
   319     /// for start the iteration on the container.
       
   320     void first(Item& item) const {
       
   321       container->first(item);
       
   322     }
       
   323 
       
   324     /// \brief Next item in the container.
       
   325     ///
       
   326     /// Returns the next item in the container. It is
       
   327     /// for iterate on the container.
       
   328     void next(Item& item) const {
       
   329       container->next(item);
       
   330     }
       
   331 
       
   332     /// \brief Returns the id of the item.
       
   333     ///
       
   334     /// Returns the id of the item provided by the container.
       
   335     int id(const Item& item) const {
       
   336       return container->id(item);
       
   337     }
       
   338 
       
   339     /// \brief Returns the maximum id of the container.
       
   340     ///
       
   341     /// Returns the maximum id of the container.
       
   342     int maxId() const {
       
   343       return container->maxId(Item());
       
   344     }
       
   345 		
       
   346   protected:
       
   347 
       
   348     void attach(ObserverBase& observer) {
       
   349       observer._index = _observers.insert(_observers.begin(), &observer);
       
   350       observer._notifier = this;
       
   351     } 
       
   352 
       
   353     void detach(ObserverBase& observer) {
       
   354       _observers.erase(observer._index);
       
   355       observer._index = _observers.end();
       
   356       observer._notifier = 0;
       
   357     }
       
   358 
       
   359   public:
       
   360 	
       
   361     /// \brief Notifies all the registed observers about an item added to 
       
   362     /// the container.
       
   363     ///
       
   364     /// It notifies all the registed observers about an item added to 
       
   365     /// the container.
       
   366     /// 
       
   367     void add(const Item& item) {
       
   368       typename Observers::reverse_iterator it;
       
   369       try {
       
   370         for (it = _observers.rbegin(); it != _observers.rend(); ++it) {
       
   371           (*it)->add(item);
       
   372         }
       
   373       } catch (...) {
       
   374         typename Observers::iterator jt;
       
   375         for (jt = it.base(); jt != _observers.end(); ++jt) {
       
   376           (*jt)->erase(item);
       
   377         }
       
   378         throw;
       
   379       }
       
   380     }	
       
   381 
       
   382     /// \brief Notifies all the registed observers about more item added to 
       
   383     /// the container.
       
   384     ///
       
   385     /// It notifies all the registed observers about more item added to 
       
   386     /// the container.
       
   387     /// 
       
   388     void add(const std::vector<Item>& items) {
       
   389       typename Observers::reverse_iterator it;
       
   390       try {
       
   391         for (it = _observers.rbegin(); it != _observers.rend(); ++it) {
       
   392           (*it)->add(items);
       
   393         }
       
   394       } catch (...) {
       
   395         typename Observers::iterator jt;
       
   396         for (jt = it.base(); jt != _observers.end(); ++jt) {
       
   397           (*jt)->erase(items);
       
   398         }
       
   399         throw;
       
   400       }
       
   401     }	
       
   402 
       
   403     /// \brief Notifies all the registed observers about an item erased from 
       
   404     /// the container.
       
   405     ///	
       
   406     /// It notifies all the registed observers about an item erased from 
       
   407     /// the container.
       
   408     /// 
       
   409     void erase(const Item& item) throw() {
       
   410       typename Observers::iterator it = _observers.begin();
       
   411       while (it != _observers.end()) {
       
   412         try {
       
   413           (*it)->erase(item);
       
   414           ++it;
       
   415         } catch (const ImmediateDetach&) {
       
   416           it = _observers.erase(it);
       
   417           (*it)->_index = _observers.end();
       
   418           (*it)->_notifier = 0;
       
   419         }
       
   420       }
       
   421     }
       
   422 
       
   423     /// \brief Notifies all the registed observers about more item erased  
       
   424     /// from the container.
       
   425     ///	
       
   426     /// It notifies all the registed observers about more item erased from 
       
   427     /// the container.
       
   428     /// 
       
   429     void erase(const std::vector<Item>& items) {
       
   430       typename Observers::iterator it = _observers.begin();
       
   431       while (it != _observers.end()) {
       
   432         try {
       
   433           (*it)->erase(items);
       
   434           ++it;
       
   435         } catch (const ImmediateDetach&) {
       
   436           it = _observers.erase(it);
       
   437           (*it)->_index = _observers.end();
       
   438           (*it)->_notifier = 0;
       
   439         }
       
   440       }
       
   441     }
       
   442 
       
   443     /// \brief Notifies all the registed observers about the container is 
       
   444     /// built.
       
   445     ///		
       
   446     /// Notifies all the registed observers about the container is built
       
   447     /// from an empty container.
       
   448     void build() {
       
   449       typename Observers::reverse_iterator it;
       
   450       try {
       
   451         for (it = _observers.rbegin(); it != _observers.rend(); ++it) {
       
   452           (*it)->build();
       
   453         }
       
   454       } catch (...) {
       
   455         typename Observers::iterator jt;
       
   456         for (jt = it.base(); jt != _observers.end(); ++jt) {
       
   457           (*jt)->clear();
       
   458         }
       
   459         throw;
       
   460       }
       
   461     }
       
   462 
       
   463     /// \brief Notifies all the registed observers about all items are 
       
   464     /// erased.
       
   465     ///
       
   466     /// Notifies all the registed observers about all items are erased
       
   467     /// from the container.
       
   468     void clear() {
       
   469       typename Observers::iterator it = _observers.begin();
       
   470       while (it != _observers.end()) {
       
   471         try {
       
   472           (*it)->clear();
       
   473           ++it;
       
   474         } catch (const ImmediateDetach&) {
       
   475           it = _observers.erase(it);
       
   476           (*it)->_index = _observers.end();
       
   477           (*it)->_notifier = 0;
       
   478         }
       
   479       }
       
   480     }
       
   481   };
       
   482 
       
   483 }
       
   484 
       
   485 #endif