lemon/bits/alteration_notifier.h
author Alpar Juttner <alpar@cs.elte.hu>
Sun, 12 Oct 2008 19:57:53 +0100
changeset 320 34e185734b42
parent 209 765619b7cbb2
child 230 af4e8ba94294
permissions -rw-r--r--
AUTHORS file added
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2008
     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/core.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   template <typename _Container, typename _Item>
    99   class AlterationNotifier {
   100   public:
   101 
   102     typedef True Notifier;
   103 
   104     typedef _Container Container;
   105     typedef _Item Item;
   106 
   107     /// \brief Exception which can be called from \e clear() and
   108     /// \e erase().
   109     ///
   110     /// From the \e clear() and \e erase() function only this
   111     /// exception is allowed to throw. The exception immediatly
   112     /// detaches the current observer from the notifier. Because the
   113     /// \e clear() and \e erase() should not throw other exceptions
   114     /// it can be used to invalidate the observer.
   115     struct ImmediateDetach {};
   116 
   117     /// \brief ObserverBase is the base class for the observers.
   118     ///
   119     /// ObserverBase is the abstract base class for the observers.
   120     /// It will be notified about an item was inserted into or
   121     /// erased from the graph.
   122     ///
   123     /// The observer interface contains some pure virtual functions
   124     /// to override. The add() and erase() functions are
   125     /// to notify the oberver when one item is added or
   126     /// erased.
   127     ///
   128     /// The build() and clear() members are to notify the observer
   129     /// about the container is built from an empty container or
   130     /// is cleared to an empty container.
   131 
   132     class ObserverBase {
   133     protected:
   134       typedef AlterationNotifier Notifier;
   135 
   136       friend class AlterationNotifier;
   137 
   138       /// \brief Default constructor.
   139       ///
   140       /// Default constructor for ObserverBase.
   141       ///
   142       ObserverBase() : _notifier(0) {}
   143 
   144       /// \brief Constructor which attach the observer into notifier.
   145       ///
   146       /// Constructor which attach the observer into notifier.
   147       ObserverBase(AlterationNotifier& nf) {
   148         attach(nf);
   149       }
   150 
   151       /// \brief Constructor which attach the obserever to the same notifier.
   152       ///
   153       /// Constructor which attach the obserever to the same notifier as
   154       /// the other observer is attached to.
   155       ObserverBase(const ObserverBase& copy) {
   156         if (copy.attached()) {
   157           attach(*copy.notifier());
   158         }
   159       }
   160 
   161       /// \brief Destructor
   162       virtual ~ObserverBase() {
   163         if (attached()) {
   164           detach();
   165         }
   166       }
   167 
   168       /// \brief Attaches the observer into an AlterationNotifier.
   169       ///
   170       /// This member attaches the observer into an AlterationNotifier.
   171       ///
   172       void attach(AlterationNotifier& nf) {
   173         nf.attach(*this);
   174       }
   175 
   176       /// \brief Detaches the observer into an AlterationNotifier.
   177       ///
   178       /// This member detaches the observer from an AlterationNotifier.
   179       ///
   180       void detach() {
   181         _notifier->detach(*this);
   182       }
   183 
   184       /// \brief Gives back a pointer to the notifier which the map
   185       /// attached into.
   186       ///
   187       /// This function gives back a pointer to the notifier which the map
   188       /// attached into.
   189       ///
   190       Notifier* notifier() const { return const_cast<Notifier*>(_notifier); }
   191 
   192       /// Gives back true when the observer is attached into a notifier.
   193       bool attached() const { return _notifier != 0; }
   194 
   195     private:
   196 
   197       ObserverBase& operator=(const ObserverBase& copy);
   198 
   199     protected:
   200 
   201       Notifier* _notifier;
   202       typename std::list<ObserverBase*>::iterator _index;
   203 
   204       /// \brief The member function to notificate the observer about an
   205       /// item is added to the container.
   206       ///
   207       /// The add() member function notificates the observer about an item
   208       /// is added to the container. It have to be overrided in the
   209       /// subclasses.
   210       virtual void add(const Item&) = 0;
   211 
   212       /// \brief The member function to notificate the observer about
   213       /// more item is added to the container.
   214       ///
   215       /// The add() member function notificates the observer about more item
   216       /// is added to the container. It have to be overrided in the
   217       /// subclasses.
   218       virtual void add(const std::vector<Item>& items) = 0;
   219 
   220       /// \brief The member function to notificate the observer about an
   221       /// item is erased from the container.
   222       ///
   223       /// The erase() member function notificates the observer about an
   224       /// item is erased from the container. It have to be overrided in
   225       /// the subclasses.
   226       virtual void erase(const Item&) = 0;
   227 
   228       /// \brief The member function to notificate the observer about
   229       /// more item is erased from the container.
   230       ///
   231       /// The erase() member function notificates the observer about more item
   232       /// is erased from the container. It have to be overrided in the
   233       /// subclasses.
   234       virtual void erase(const std::vector<Item>& items) = 0;
   235 
   236       /// \brief The member function to notificate the observer about the
   237       /// container is built.
   238       ///
   239       /// The build() member function notificates the observer about the
   240       /// container is built from an empty container. It have to be
   241       /// overrided in the subclasses.
   242 
   243       virtual void build() = 0;
   244 
   245       /// \brief The member function to notificate the observer about all
   246       /// items are erased from the container.
   247       ///
   248       /// The clear() member function notificates the observer about all
   249       /// items are erased from the container. It have to be overrided in
   250       /// the subclasses.
   251       virtual void clear() = 0;
   252 
   253     };
   254 
   255   protected:
   256 
   257     const Container* container;
   258 
   259     typedef std::list<ObserverBase*> Observers;
   260     Observers _observers;
   261 
   262 
   263   public:
   264 
   265     /// \brief Default constructor.
   266     ///
   267     /// The default constructor of the AlterationNotifier.
   268     /// It creates an empty notifier.
   269     AlterationNotifier()
   270       : container(0) {}
   271 
   272     /// \brief Constructor.
   273     ///
   274     /// Constructor with the observed container parameter.
   275     AlterationNotifier(const Container& _container)
   276       : container(&_container) {}
   277 
   278     /// \brief Copy Constructor of the AlterationNotifier.
   279     ///
   280     /// Copy constructor of the AlterationNotifier.
   281     /// It creates only an empty notifier because the copiable
   282     /// notifier's observers have to be registered still into that notifier.
   283     AlterationNotifier(const AlterationNotifier& _notifier)
   284       : container(_notifier.container) {}
   285 
   286     /// \brief Destructor.
   287     ///
   288     /// Destructor of the AlterationNotifier.
   289     ///
   290     ~AlterationNotifier() {
   291       typename Observers::iterator it;
   292       for (it = _observers.begin(); it != _observers.end(); ++it) {
   293         (*it)->_notifier = 0;
   294       }
   295     }
   296 
   297     /// \brief Sets the container.
   298     ///
   299     /// Sets the container.
   300     void setContainer(const Container& _container) {
   301       container = &_container;
   302     }
   303 
   304   protected:
   305 
   306     AlterationNotifier& operator=(const AlterationNotifier&);
   307 
   308   public:
   309 
   310 
   311 
   312     /// \brief First item in the container.
   313     ///
   314     /// Returns the first item in the container. It is
   315     /// for start the iteration on the container.
   316     void first(Item& item) const {
   317       container->first(item);
   318     }
   319 
   320     /// \brief Next item in the container.
   321     ///
   322     /// Returns the next item in the container. It is
   323     /// for iterate on the container.
   324     void next(Item& item) const {
   325       container->next(item);
   326     }
   327 
   328     /// \brief Returns the id of the item.
   329     ///
   330     /// Returns the id of the item provided by the container.
   331     int id(const Item& item) const {
   332       return container->id(item);
   333     }
   334 
   335     /// \brief Returns the maximum id of the container.
   336     ///
   337     /// Returns the maximum id of the container.
   338     int maxId() const {
   339       return container->maxId(Item());
   340     }
   341 
   342   protected:
   343 
   344     void attach(ObserverBase& observer) {
   345       observer._index = _observers.insert(_observers.begin(), &observer);
   346       observer._notifier = this;
   347     }
   348 
   349     void detach(ObserverBase& observer) {
   350       _observers.erase(observer._index);
   351       observer._index = _observers.end();
   352       observer._notifier = 0;
   353     }
   354 
   355   public:
   356 
   357     /// \brief Notifies all the registed observers about an item added to
   358     /// the container.
   359     ///
   360     /// It notifies all the registed observers about an item added to
   361     /// the container.
   362     ///
   363     void add(const Item& item) {
   364       typename Observers::reverse_iterator it;
   365       try {
   366         for (it = _observers.rbegin(); it != _observers.rend(); ++it) {
   367           (*it)->add(item);
   368         }
   369       } catch (...) {
   370         typename Observers::iterator jt;
   371         for (jt = it.base(); jt != _observers.end(); ++jt) {
   372           (*jt)->erase(item);
   373         }
   374         throw;
   375       }
   376     }
   377 
   378     /// \brief Notifies all the registed observers about more item added to
   379     /// the container.
   380     ///
   381     /// It notifies all the registed observers about more item added to
   382     /// the container.
   383     ///
   384     void add(const std::vector<Item>& items) {
   385       typename Observers::reverse_iterator it;
   386       try {
   387         for (it = _observers.rbegin(); it != _observers.rend(); ++it) {
   388           (*it)->add(items);
   389         }
   390       } catch (...) {
   391         typename Observers::iterator jt;
   392         for (jt = it.base(); jt != _observers.end(); ++jt) {
   393           (*jt)->erase(items);
   394         }
   395         throw;
   396       }
   397     }
   398 
   399     /// \brief Notifies all the registed observers about an item erased from
   400     /// the container.
   401     ///
   402     /// It notifies all the registed observers about an item erased from
   403     /// the container.
   404     ///
   405     void erase(const Item& item) throw() {
   406       typename Observers::iterator it = _observers.begin();
   407       while (it != _observers.end()) {
   408         try {
   409           (*it)->erase(item);
   410           ++it;
   411         } catch (const ImmediateDetach&) {
   412           it = _observers.erase(it);
   413           (*it)->_index = _observers.end();
   414           (*it)->_notifier = 0;
   415         }
   416       }
   417     }
   418 
   419     /// \brief Notifies all the registed observers about more item erased
   420     /// from the container.
   421     ///
   422     /// It notifies all the registed observers about more item erased from
   423     /// the container.
   424     ///
   425     void erase(const std::vector<Item>& items) {
   426       typename Observers::iterator it = _observers.begin();
   427       while (it != _observers.end()) {
   428         try {
   429           (*it)->erase(items);
   430           ++it;
   431         } catch (const ImmediateDetach&) {
   432           it = _observers.erase(it);
   433           (*it)->_index = _observers.end();
   434           (*it)->_notifier = 0;
   435         }
   436       }
   437     }
   438 
   439     /// \brief Notifies all the registed observers about the container is
   440     /// built.
   441     ///
   442     /// Notifies all the registed observers about the container is built
   443     /// from an empty container.
   444     void build() {
   445       typename Observers::reverse_iterator it;
   446       try {
   447         for (it = _observers.rbegin(); it != _observers.rend(); ++it) {
   448           (*it)->build();
   449         }
   450       } catch (...) {
   451         typename Observers::iterator jt;
   452         for (jt = it.base(); jt != _observers.end(); ++jt) {
   453           (*jt)->clear();
   454         }
   455         throw;
   456       }
   457     }
   458 
   459     /// \brief Notifies all the registed observers about all items are
   460     /// erased.
   461     ///
   462     /// Notifies all the registed observers about all items are erased
   463     /// from the container.
   464     void clear() {
   465       typename Observers::iterator it = _observers.begin();
   466       while (it != _observers.end()) {
   467         try {
   468           (*it)->clear();
   469           ++it;
   470         } catch (const ImmediateDetach&) {
   471           it = _observers.erase(it);
   472           (*it)->_index = _observers.end();
   473           (*it)->_notifier = 0;
   474         }
   475       }
   476     }
   477   };
   478 
   479 }
   480 
   481 #endif