klao@946: /* -*- C++ -*-
klao@946: *
alpar@1956: * This file is a part of LEMON, a generic C++ optimization library
alpar@1956: *
alpar@1956: * Copyright (C) 2003-2006
alpar@1956: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1956: * (Egervary Research Group on Combinatorial Optimization, EGRES).
klao@946: *
klao@946: * Permission to use, modify and distribute this software is granted
klao@946: * provided that this copyright notice appears in all copies. For
klao@946: * precise terms see the accompanying LICENSE file.
klao@946: *
klao@946: * This software is provided "AS IS" with no warranty of any kind,
klao@946: * express or implied, and with no claim as to its suitability for any
klao@946: * purpose.
klao@946: *
klao@946: */
klao@946:
deba@1999: #ifndef LEMON_BITS_ALTERATION_NOTIFIER_H
deba@1999: #define LEMON_BITS_ALTERATION_NOTIFIER_H
klao@946:
klao@946: #include <vector>
deba@1999:
deba@1999: #include <lemon/bits/utility.h>
klao@946:
deba@1996: ///\ingroup graphbits
klao@946: ///\file
deba@1999: ///\brief Observer notifier for graph alteration observers.
klao@946:
klao@946: namespace lemon {
klao@946:
deba@1999: /// \ingroup graphbits
deba@1414: ///
deba@1999: /// \brief Notifier class to notify observes about alterations in
deba@1999: /// a container.
klao@946: ///
deba@1999: /// The simple graph's can be refered as two containers, one node container
deba@1999: /// and one edge container. But they are not standard containers they
deba@1999: /// does not store values directly they are just key continars for more
deba@1999: /// value containers which are the node and edge maps.
klao@946: ///
deba@1999: /// The graph's node and edge sets can be changed as we add or erase
deba@1999: /// nodes and edges in the graph. Lemon would like to handle easily
deba@1999: /// that the node and edge maps should contain values for all nodes or
deba@1999: /// edges. If we want to check on every indicing if the map contains
deba@1999: /// the current indicing key that cause a drawback in the performance
alpar@2006: /// in the library. We use another solution we notify all maps about
deba@1999: /// an alteration in the graph, which cause only drawback on the
deba@1999: /// alteration of the graph.
deba@1999: ///
deba@1999: /// This class provides an interface to the container. The \e first() and \e
deba@1999: /// next() member functions make possible to iterate on the keys of the
deba@1999: /// container. The \e id() function returns an integer id for each key.
deba@1999: /// The \e maxId() function gives back an upper bound of the ids.
deba@1999: ///
deba@1999: /// For the proper functonality of this class, we should notify it
deba@1999: /// about each alteration in the container. The alterations have four type
deba@1999: /// as \e add(), \e erase(), \e build() and \e clear(). The \e add() and
deba@1999: /// \e erase() signals that only one or few items added or erased to or
deba@1999: /// from the graph. If all items are erased from the graph or from an empty
deba@1999: /// graph a new graph is builded then it can be signaled with the
deba@1999: /// clear() and build() members. Important rule that if we erase items
deba@1999: /// from graph we should first signal the alteration and after that erase
deba@1999: /// them from the container, on the other way on item addition we should
deba@1999: /// first extend the container and just after that signal the alteration.
deba@1999: ///
deba@1999: /// The alteration can be observed with a class inherited from the
deba@1999: /// \e ObserverBase nested class. The signals can be handled with
deba@2188: /// overriding the virtual functions defined in the base class. The
deba@2188: /// observer base can be attached to the notifier with the
deba@2188: /// \e attach() member and can be detached with detach() function. The
deba@2188: /// alteration handlers should not call any function which signals
deba@2188: /// an other alteration in the same notifier and should not
deba@2188: /// detach any observer from the notifier.
deba@1999: ///
deba@2188: /// Alteration observers try to be exception safe. If an \e add() or
deba@2188: /// a \e clear() function throws an exception then the remaining
deba@2188: /// observeres will not be notified and the fulfilled additions will
deba@2188: /// be rolled back by calling the \e erase() or \e clear()
deba@2188: /// functions. Thence the \e erase() and \e clear() should not throw
deba@2188: /// exception. Actullay, it can be throw only
deba@2188: /// \ref AlterationObserver::ImmediateDetach ImmediateDetach
deba@2188: /// exception which detach the observer from the notifier.
deba@1999: ///
deba@1999: /// There are some place when the alteration observing is not completly
deba@1999: /// reliable. If we want to carry out the node degree in the graph
deba@1999: /// as in the \ref InDegMap and we use the reverseEdge that cause
deba@1999: /// unreliable functionality. Because the alteration observing signals
deba@1999: /// only erasing and adding but not the reversing it will stores bad
deba@1999: /// degrees. The sub graph adaptors cannot signal the alterations because
deba@1999: /// just a setting in the filter map can modify the graph and this cannot
deba@1999: /// be watched in any way.
deba@1999: ///
deba@1999: /// \param _Container The container which is observed.
deba@1999: /// \param _Item The item type which is obserbved.
klao@946: ///
klao@946: /// \author Balazs Dezso
klao@946:
deba@1999: template <typename _Container, typename _Item>
deba@1038: class AlterationNotifier {
klao@946: public:
deba@1989:
deba@1989: typedef True Notifier;
deba@1989:
deba@1999: typedef _Container Container;
klao@946: typedef _Item Item;
klao@946:
deba@2188: /// \brief Exception which can be called from \e clear() and
deba@2188: /// \e erase().
deba@2188: ///
deba@2188: /// From the \e clear() and \e erase() function only this
deba@2188: /// exception is allowed to throw. The exception immediatly
deba@2188: /// detaches the current observer from the notifier. Because the
deba@2188: /// \e clear() and \e erase() should not throw other exceptions
deba@2188: /// it can be used to invalidate the observer.
deba@2188: struct ImmediateDetach {};
deba@2188:
deba@1999: /// \brief ObserverBase is the base class for the observers.
deba@1999: ///
klao@946: /// ObserverBase is the abstract base class for the observers.
klao@946: /// It will be notified about an item was inserted into or
klao@946: /// erased from the graph.
klao@946: ///
klao@946: /// The observer interface contains some pure virtual functions
klao@946: /// to override. The add() and erase() functions are
klao@946: /// to notify the oberver when one item is added or
klao@946: /// erased.
klao@946: ///
klao@946: /// The build() and clear() members are to notify the observer
alpar@1204: /// about the container is built from an empty container or
klao@946: /// is cleared to an empty container.
klao@946: ///
klao@946: /// \author Balazs Dezso
klao@946:
klao@946: class ObserverBase {
klao@946: protected:
deba@1999: typedef AlterationNotifier Notifier;
klao@946:
deba@1038: friend class AlterationNotifier;
klao@946:
deba@1414: /// \brief Default constructor.
deba@1414: ///
klao@946: /// Default constructor for ObserverBase.
klao@946: ///
deba@1999: ObserverBase() : notifier(0) {}
klao@946:
deba@1999: /// \brief Constructor which attach the observer into notifier.
deba@1999: ///
deba@1999: /// Constructor which attach the observer into notifier.
deba@1999: ObserverBase(AlterationNotifier& _notifier) {
deba@1999: attach(_notifier);
deba@1999: }
deba@1999:
deba@1999: /// \brief Constructor which attach the obserever to the same notifier.
deba@1999: ///
deba@1999: /// Constructor which attach the obserever to the same notifier as
deba@1999: /// the other observer is attached to.
deba@1685: ObserverBase(const ObserverBase& copy) {
deba@1685: if (copy.attached()) {
deba@1999: attach(*copy.getNotifier());
deba@1685: }
deba@1685: }
deba@1685:
deba@1999: /// \brief Destructor
deba@1999: virtual ~ObserverBase() {
deba@1999: if (attached()) {
deba@1999: detach();
deba@1999: }
deba@1999: }
klao@946:
deba@1414: /// \brief Attaches the observer into an AlterationNotifier.
deba@1414: ///
deba@1038: /// This member attaches the observer into an AlterationNotifier.
klao@946: ///
deba@1999: void attach(AlterationNotifier& _notifier) {
deba@1999: notifier = &_notifier;
deba@1999: notifier->attach(*this);
klao@946: }
deba@2188:
deba@1414: /// \brief Detaches the observer into an AlterationNotifier.
deba@1414: ///
deba@1038: /// This member detaches the observer from an AlterationNotifier.
klao@946: ///
klao@946: void detach() {
deba@1999: notifier->detach(*this);
klao@946: }
deba@2188:
deba@1999: /// \brief Gives back a pointer to the notifier which the map
klao@946: /// attached into.
klao@946: ///
deba@1999: /// This function gives back a pointer to the notifier which the map
deba@1999: /// attached into.
deba@1999: ///
deba@1999: Notifier* getNotifier() const { return const_cast<Notifier*>(notifier); }
klao@946:
deba@1999: /// Gives back true when the observer is attached into a notifier.
deba@1999: bool attached() const { return notifier != 0; }
deba@1685:
klao@946: private:
klao@946:
klao@946: ObserverBase& operator=(const ObserverBase& copy);
klao@946:
klao@946: protected:
klao@946:
deba@1999: Notifier* notifier;
deba@1999: int notifier_index;
klao@946:
klao@946: /// \brief The member function to notificate the observer about an
klao@946: /// item is added to the container.
klao@946: ///
klao@946: /// The add() member function notificates the observer about an item
klao@946: /// is added to the container. It have to be overrided in the
klao@946: /// subclasses.
klao@946:
deba@1414: virtual void add(const Item&) = 0;
klao@946:
deba@1414: /// \brief The member function to notificate the observer about
deba@1718: /// more item is added to the container.
deba@1414: ///
deba@1718: /// The add() member function notificates the observer about more item
deba@1414: /// is added to the container. It have to be overrided in the
deba@1414: /// subclasses.
deba@1414:
deba@1414: virtual void add(const std::vector<Item>& items) {
deba@1999: int i;
deba@1999: try {
deba@1999: for (i = 0; i < (int)items.size(); ++i) {
deba@1999: add(items[i]);
deba@1999: }
deba@1999: } catch (...) {
deba@1999: for (int j = 0; j < i; ++j) {
deba@1999: add(items[j]);
deba@1999: }
deba@1999: throw;
deba@1999: }
deba@1414: }
klao@946:
klao@946: /// \brief The member function to notificate the observer about an
klao@946: /// item is erased from the container.
klao@946: ///
klao@946: /// The erase() member function notificates the observer about an
klao@946: /// item is erased from the container. It have to be overrided in
klao@946: /// the subclasses.
klao@946:
klao@946: virtual void erase(const Item&) = 0;
klao@946:
deba@1718: /// \brief The member function to notificate the observer about
deba@1718: /// more item is erased from the container.
deba@1718: ///
deba@1718: /// The erase() member function notificates the observer about more item
deba@1718: /// is erased from the container. It have to be overrided in the
deba@1718: /// subclasses.
deba@1414: virtual void erase(const std::vector<Item>& items) {
deba@1999: for (int i = 0; i < (int)items.size(); ++i) {
deba@1999: erase(items[i]);
deba@1999: }
deba@1414: }
deba@1414:
klao@946: /// \brief The member function to notificate the observer about the
alpar@1204: /// container is built.
klao@946: ///
klao@946: /// The build() member function notificates the observer about the
alpar@1204: /// container is built from an empty container. It have to be
klao@946: /// overrided in the subclasses.
klao@946:
deba@1999: virtual void build() {
deba@1999: Item it;
deba@1999: try {
deba@1999: for (notifier->first(it); it != INVALID; notifier->next(it)) {
deba@1999: add(it);
deba@1999: }
deba@1999: } catch (...) {
deba@1999: Item jt;
deba@1999: for (notifier->first(jt); jt != it; notifier->next(jt)) {
deba@1999: erase(jt);
deba@1999: }
deba@1999: throw;
deba@1999: }
deba@1999: }
klao@946:
klao@946: /// \brief The member function to notificate the observer about all
klao@946: /// items are erased from the container.
klao@946: ///
klao@946: /// The clear() member function notificates the observer about all
klao@946: /// items are erased from the container. It have to be overrided in
deba@1999: /// the subclasses.
deba@1999: virtual void clear() {
deba@1999: Item it;
deba@1999: for (notifier->first(it); it != INVALID; notifier->next(it)) {
deba@1999: erase(it);
deba@1999: }
deba@1999: }
klao@946:
klao@946: };
klao@946:
klao@946: protected:
klao@946:
deba@1999: const Container* container;
klao@946:
deba@1999: typedef std::vector<ObserverBase*> Observers;
deba@1999: Observers observers;
klao@946:
klao@946:
klao@946: public:
klao@946:
deba@1999: /// \brief Default constructor.
klao@946: ///
deba@1038: /// The default constructor of the AlterationNotifier.
deba@1999: /// It creates an empty notifier.
deba@1999: AlterationNotifier()
deba@1999: : container(0) {}
klao@946:
deba@1999: /// \brief Constructor.
deba@1999: ///
deba@1999: /// Constructor with the observed container parameter.
deba@1999: AlterationNotifier(const Container& _container)
deba@1999: : container(&_container) {}
deba@1999:
deba@1999: /// \brief Copy Constructor of the AlterationNotifier.
deba@1999: ///
deba@1038: /// Copy constructor of the AlterationNotifier.
deba@1999: /// It creates only an empty notifier because the copiable
deba@1999: /// notifier's observers have to be registered still into that notifier.
deba@1999: AlterationNotifier(const AlterationNotifier& _notifier)
deba@1999: : container(_notifier.container) {}
klao@946:
deba@1999: /// \brief Destructor.
deba@1999: ///
deba@1999: /// Destructor of the AlterationNotifier.
deba@1999: ///
deba@1999: ~AlterationNotifier() {
deba@1999: typename Observers::iterator it;
deba@1999: for (it = observers.begin(); it != observers.end(); ++it) {
deba@1999: (*it)->notifier = 0;
klao@946: }
klao@946: }
klao@946:
deba@1999: /// \brief Sets the container.
klao@946: ///
deba@1999: /// Sets the container.
deba@1999: void setContainer(const Container& _container) {
deba@1999: container = &_container;
klao@946: }
deba@1999:
deba@1999: protected:
deba@1999:
deba@1999: AlterationNotifier& operator=(const AlterationNotifier&);
deba@1999:
deba@1999: public:
deba@1999:
deba@1999:
deba@1999:
deba@1999: /// \brief First item in the container.
deba@1999: ///
deba@1999: /// Returns the first item in the container. It is
deba@1999: /// for start the iteration on the container.
deba@1999: void first(Item& item) const {
deba@1999: container->first(item);
deba@1999: }
deba@1999:
deba@1999: /// \brief Next item in the container.
deba@1999: ///
deba@1999: /// Returns the next item in the container. It is
deba@1999: /// for iterate on the container.
deba@1999: void next(Item& item) const {
deba@1999: container->next(item);
deba@1999: }
deba@1999:
deba@1999: /// \brief Returns the id of the item.
deba@1999: ///
deba@1999: /// Returns the id of the item provided by the container.
deba@1999: int id(const Item& item) const {
deba@1999: return container->id(item);
deba@1999: }
deba@1999:
deba@1999: /// \brief Returns the maximum id of the container.
deba@1999: ///
deba@1999: /// Returns the maximum id of the container.
deba@1999: int maxId() const {
deba@1999: return container->maxId(Item());
deba@1999: }
deba@1999:
klao@946: protected:
klao@946:
klao@946: void attach(ObserverBase& observer) {
deba@1999: observers.push_back(&observer);
deba@1999: observer.notifier = this;
deba@1999: observer.notifier_index = observers.size() - 1;
klao@946: }
klao@946:
deba@1999: void detach(ObserverBase& observer) {
deba@1999: observers.back()->notifier_index = observer.notifier_index;
deba@1999: observers[observer.notifier_index] = observers.back();
deba@1999: observers.pop_back();
deba@1999: observer.notifier = 0;
klao@946: }
klao@946:
klao@946: public:
klao@946:
deba@1999: /// \brief Notifies all the registed observers about an item added to
deba@1414: /// the container.
deba@1414: ///
deba@1999: /// It notifies all the registed observers about an item added to
deba@1414: /// the container.
klao@946: ///
deba@1414: void add(const Item& item) {
deba@1999: typename Observers::iterator it;
deba@1979: try {
deba@1999: for (it = observers.begin(); it != observers.end(); ++it) {
deba@1979: (*it)->add(item);
deba@1979: }
deba@1979: } catch (...) {
deba@1999: typename Observers::iterator jt;
deba@1999: for (jt = observers.begin(); jt != it; ++jt) {
deba@1979: (*it)->erase(item);
deba@1979: }
deba@1979: throw;
klao@946: }
klao@946: }
klao@946:
deba@1999: /// \brief Notifies all the registed observers about more item added to
deba@1414: /// the container.
deba@1414: ///
deba@1999: /// It notifies all the registed observers about more item added to
deba@1414: /// the container.
deba@1414: ///
deba@1414: void add(const std::vector<Item>& items) {
deba@1999: typename Observers::iterator it;
deba@1979: try {
deba@1999: for (it = observers.begin(); it != observers.end(); ++it) {
deba@1979: (*it)->add(items);
deba@1979: }
deba@1979: } catch (...) {
deba@1999: typename Observers::iterator jt;
deba@1999: for (jt = observers.begin(); jt != it; ++jt) {
deba@1979: (*it)->erase(items);
deba@1979: }
deba@1979: throw;
deba@1414: }
deba@1414: }
deba@1414:
deba@1999: /// \brief Notifies all the registed observers about an item erased from
deba@1414: /// the container.
deba@1414: ///
deba@1999: /// It notifies all the registed observers about an item erased from
deba@1414: /// the container.
klao@946: ///
deba@2188: void erase(const Item& key) throw() {
deba@2188: int i = 0;
deba@2188: while (i != (int)observers.size()) {
deba@2188: try {
deba@2188: observers[i]->erase(key);
deba@2188: ++i;
deba@2188: } catch (const ImmediateDetach&) {
deba@2188: observers[i]->detach();
deba@2188: }
klao@946: }
klao@946: }
deba@1414:
deba@1999: /// \brief Notifies all the registed observers about more item erased
deba@1414: /// from the container.
deba@1414: ///
deba@1999: /// It notifies all the registed observers about more item erased from
deba@1414: /// the container.
deba@1414: ///
deba@1414: void erase(const std::vector<Item>& items) {
deba@2188: int i = 0;
deba@2188: while (i != (int)observers.size()) {
deba@2188: try {
deba@2188: observers[i]->erase(items);
deba@2188: ++i;
deba@2188: } catch (const ImmediateDetach&) {
deba@2188: observers[i]->detach();
deba@2188: }
deba@1414: }
deba@1414: }
klao@946:
deba@1999: /// \brief Notifies all the registed observers about the container is
deba@1414: /// built.
deba@1414: ///
deba@1999: /// Notifies all the registed observers about the container is built
klao@946: /// from an empty container.
klao@946: void build() {
deba@1999: typename Observers::iterator it;
deba@1979: try {
deba@1999: for (it = observers.begin(); it != observers.end(); ++it) {
deba@1979: (*it)->build();
deba@1979: }
deba@1979: } catch (...) {
deba@1999: typename Observers::iterator jt;
deba@1999: for (jt = observers.begin(); jt != it; ++jt) {
deba@1979: (*it)->clear();
deba@1979: }
deba@1979: throw;
klao@946: }
klao@946: }
klao@946:
deba@1999: /// \brief Notifies all the registed observers about all items are
deba@1414: /// erased.
deba@1414: ///
deba@1999: /// Notifies all the registed observers about all items are erased
klao@946: /// from the container.
klao@946: void clear() {
deba@2188: int i = 0;
deba@2188: while (i != (int)observers.size()) {
deba@2188: try {
deba@2188: observers[i]->clear();
deba@2188: ++i;
deba@2188: } catch (const ImmediateDetach&) {
deba@2188: observers[i]->detach();
deba@2188: }
klao@946: }
klao@946: }
klao@946: };
klao@946:
klao@946: }
klao@946:
klao@946: #endif