klao@946: /* -*- C++ -*-
deba@1038:  * src/lemon/notifier.h - Part of LEMON, a generic C++ optimization library
klao@946:  *
alpar@1164:  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
klao@946:  * (Egervary Combinatorial Optimization Research Group, 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: 
klao@946: #ifndef LEMON_ALTERATION_OBSERVER_REGISTRY_H
klao@946: #define LEMON_ALTERATION_OBSERVER_REGISTRY_H
klao@946: 
klao@946: #include <vector>
klao@946: #include <algorithm>
klao@946: 
klao@946: ///\ingroup graphmaps
klao@946: ///\file
klao@946: ///\brief Observer registry for graph alteration observers.
klao@946: 
klao@946: using namespace std;
klao@946: 
klao@946: namespace lemon {
klao@946: 
klao@946:   /// \addtogroup graphmaps
klao@946:   /// @{
klao@946: 
klao@946:   /// Registry class to register objects observes alterations in the graph.
klao@946: 
klao@946:   /// This class is a registry for the objects which observe the
klao@946:   /// alterations in a container. The alteration observers can be attached
klao@946:   /// to and detached from the registry. The observers have to inherit
deba@1038:   /// from the \ref AlterationNotifier::ObserverBase and override
klao@946:   /// the virtual functions in that.
klao@946:   ///
klao@946:   /// The most important application of the alteration observing is the
klao@946:   /// dynamic map implementation when the observers are observing the
klao@946:   /// alterations in the graph.
klao@946:   ///
klao@946:   /// \param _Item The item type what the observers are observing, usually
klao@946:   /// edge or node.
klao@946:   ///
klao@946:   /// \author Balazs Dezso
klao@946: 
klao@946:   template <typename _Item>
deba@1038:   class AlterationNotifier {
klao@946:   public:
klao@946:     typedef _Item Item;
klao@946: 
klao@946:     /// ObserverBase is the base class for the observers.
klao@946: 	
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@1038:       typedef AlterationNotifier Registry;
klao@946: 
deba@1038:       friend class AlterationNotifier;
klao@946: 
klao@946:       /// Default constructor.
klao@946: 
klao@946:       /// Default constructor for ObserverBase.
klao@946:       /// 
klao@946:       ObserverBase() : registry(0) {}
klao@946: 
klao@946:       virtual ~ObserverBase() {}
klao@946: 
deba@1038:       /// Attaches the observer into an AlterationNotifier.
klao@946: 
deba@1038:       /// This member attaches the observer into an AlterationNotifier.
klao@946:       ///
deba@1038:       void attach(AlterationNotifier& r) {
klao@946: 	registry = &r;
klao@946: 	registry->attach(*this);
klao@946:       }
klao@946: 
deba@1038:       /// Detaches the observer into an AlterationNotifier.
klao@946: 
deba@1038:       /// This member detaches the observer from an AlterationNotifier.
klao@946:       ///
klao@946:       void detach() {
klao@946: 	if (registry) {
klao@946: 	  registry->detach(*this);
klao@946: 	}
klao@946:       }
klao@946: 	
klao@946: 
klao@946:       /// Gives back a pointer to the registry what the map attached into.
klao@946: 
klao@946:       /// This function gives back a pointer to the registry what the map
klao@946:       /// attached into.
klao@946:       ///
klao@946:       Registry* getRegistry() const { return const_cast<Registry*>(registry); }
klao@946:       
klao@946:       /// Gives back true when the observer is attached into a registry.
klao@946:       bool attached() const { return registry != 0; }
klao@946: 	
klao@946:     private:
klao@946: 
klao@946:       ObserverBase(const ObserverBase& copy);
klao@946:       ObserverBase& operator=(const ObserverBase& copy);
klao@946: 
klao@946:     protected:
klao@946:       
klao@946:       Registry* registry;
klao@946:       int registry_index;
klao@946: 
klao@946:     public:
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: 	
klao@946:       virtual void add(const Item&) = 0;	
klao@946: 
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: 
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: 
klao@946:       virtual void build() = 0;
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
klao@946:       /// the subclasses.
klao@946:       
klao@946:       virtual void clear() = 0;
klao@946: 
klao@946:     };
klao@946: 	
klao@946:   protected:
klao@946: 	
klao@946: 
klao@946:     typedef std::vector<ObserverBase*> Container; 
klao@946: 
klao@946:     Container container;
klao@946: 
klao@946: 		
klao@946:   public:
klao@946: 
klao@946:     /// Default constructor.
klao@946: 	
klao@946:     ///
deba@1038:     /// The default constructor of the AlterationNotifier. 
klao@946:     /// It creates an empty registry.
deba@1038:     AlterationNotifier() {}
klao@946: 
deba@1038:     /// Copy Constructor of the AlterationNotifier. 
klao@946: 	
deba@1038:     /// Copy constructor of the AlterationNotifier. 
klao@946:     /// It creates only an empty registry because the copiable
klao@946:     /// registry's observers have to be registered still into that registry.
deba@1039:     AlterationNotifier(const AlterationNotifier&) {}
klao@946: 
klao@946:     /// Assign operator.
klao@946: 		
deba@1038:     /// Assign operator for the AlterationNotifier. 
deba@1040:     /// It makes the notifier only empty because the copiable
deba@1040:     /// notifier's observers have to be registered still into that registry.
deba@1039:     AlterationNotifier& operator=(const AlterationNotifier&) {
klao@946:       typename Container::iterator it;
klao@946:       for (it = container.begin(); it != container.end(); ++it) {
klao@946: 	(*it)->registry = 0;
klao@946:       }
klao@946:     }
klao@946: 
klao@946:     /// Destructor.
klao@946: 				
deba@1038:     /// Destructor of the AlterationNotifier.
klao@946:     ///
deba@1038:     ~AlterationNotifier() {
klao@946:       typename Container::iterator it;
klao@946:       for (it = container.begin(); it != container.end(); ++it) {
klao@946: 	(*it)->registry = 0;
klao@946:       }
klao@946:     }
klao@946: 	
klao@946: 	
klao@946:   protected:
klao@946: 
klao@946:     void attach(ObserverBase& observer) {
klao@946:       container.push_back(&observer);
klao@946:       observer.registry = this;
klao@946:       observer.registry_index = container.size()-1;
klao@946:     } 
klao@946: 
klao@946:     void detach(ObserverBase& base) {
klao@946:       container.back()->registry_index = base.registry_index; 
klao@946:       container[base.registry_index] = container.back();
klao@946:       container.pop_back();
klao@946:       base.registry = 0;
klao@946:     }
klao@946: 
klao@946:   public:
klao@946: 	
klao@946:     /// Notifies all the registered observers about an Item added to the container.
klao@946: 		
klao@946:     /// It notifies all the registered observers about an Item added to the container.
klao@946:     /// 
klao@946:     void add(const Item& key) {
klao@946:       typename Container::iterator it;
klao@946:       for (it = container.begin(); it != container.end(); ++it) {
klao@946: 	(*it)->add(key);
klao@946:       }
klao@946:     }	
klao@946: 
klao@946:     /// Notifies all the registered observers about an Item erased from the container.
klao@946: 		
klao@946:     /// It notifies all the registered observers about an Item erased from the container.
klao@946:     /// 
klao@946:     void erase(const Item& key) {
klao@946:       typename Container::iterator it;
klao@946:       for (it = container.begin(); it != container.end(); ++it) {
klao@946: 	(*it)->erase(key);
klao@946:       }
klao@946:     }
klao@946:     
klao@946: 
alpar@1204:     /// Notifies all the registered observers about the container is built.
klao@946: 		
alpar@1204:     /// Notifies all the registered observers about the container is built
klao@946:     /// from an empty container.
klao@946:     void build() {
klao@946:       typename Container::iterator it;
klao@946:       for (it = container.begin(); it != container.end(); ++it) {
klao@946: 	(*it)->build();
klao@946:       }
klao@946:     }
klao@946: 
klao@946: 
klao@946:     /// Notifies all the registered observers about all Items are erased.
klao@946: 
klao@946:     /// Notifies all the registered observers about all Items are erased
klao@946:     /// from the container.
klao@946:     void clear() {
klao@946:       typename Container::iterator it;
klao@946:       for (it = container.begin(); it != container.end(); ++it) {
klao@946: 	(*it)->clear();
klao@946:       }
klao@946:     }
klao@946:   };
klao@946: 
klao@946: 
klao@962:   /// \brief Class to extend a graph with the functionality of alteration
klao@962:   /// observing.
klao@962:   ///
klao@962:   /// AlterableGraphExtender extends the _Base graphs functionality with
klao@962:   /// the possibility of alteration observing. It defines two observer
klao@962:   /// registrys for the nodes and mapes.
klao@962:   /// 
klao@962:   /// \todo Document what "alteration observing" is. And probably find a
klao@962:   /// better (shorter) name.
klao@946:   ///
klao@946:   /// \param _Base is the base class to extend.
klao@946:   ///
klao@946:   /// \pre _Base is conform to the BaseGraphComponent concept.
klao@946:   ///
klao@962:   /// \post AlterableGraphExtender<_Base> is conform to the
klao@962:   /// AlterableGraphComponent concept.
klao@946:   ///
klao@946:   /// \author Balazs Dezso
klao@946: 
klao@946:   template <typename _Base> 
klao@946:   class AlterableGraphExtender : public _Base {
klao@946:   public:
klao@946: 
klao@946:     typedef AlterableGraphExtender Graph;
klao@946:     typedef _Base Parent;
klao@946: 
klao@946:     typedef typename Parent::Node Node;
klao@946:     typedef typename Parent::Edge Edge;
klao@946: 
klao@962:     /// The edge observer registry.
deba@1039:     typedef AlterationNotifier<Edge> EdgeNotifier;
klao@946:     /// The node observer registry.
deba@1039:     typedef AlterationNotifier<Node> NodeNotifier;
klao@946: 
klao@946: 
klao@946:   protected:
klao@946: 
deba@1040:     mutable EdgeNotifier edge_notifier;
klao@946: 
deba@1040:     mutable NodeNotifier node_notifier;
klao@946: 
klao@946:   public:
klao@946: 
deba@1134:     /// \brief Gives back the edge alteration notifier.
deba@1134:     ///
deba@1134:     /// Gives back the edge alteration notifier.
deba@1134:     EdgeNotifier& getNotifier(Edge) const {
deba@1040:       return edge_notifier;
klao@946:     }
klao@946: 
deba@1134:     /// \brief Gives back the node alteration notifier.
deba@1134:     ///
deba@1134:     /// Gives back the node alteration notifier.
deba@1134:     NodeNotifier& getNotifier(Node) const {
deba@1040:       return node_notifier;
klao@946:     }
klao@946: 
klao@946:     ~AlterableGraphExtender() {
deba@1040:       node_notifier.clear();
deba@1040:       edge_notifier.clear();
klao@946:     }
klao@946:     
klao@946:   };
klao@946: 
klao@962:   /// \brief Class to extend an undirected graph with the functionality of
klao@962:   /// alteration observing.
klao@962:   ///
klao@962:   /// \todo Document.
klao@962:   ///
klao@962:   /// \sa AlterableGraphExtender
klao@962:   ///
klao@962:   /// \bug This should be done some other way. Possibilities: template
klao@962:   /// specialization (not very easy, if at all possible); some kind of
klao@962:   /// enable_if boost technique?
klao@962: 
klao@962:   template <typename _Base> 
klao@962:   class AlterableUndirGraphExtender
klao@962:     : public AlterableGraphExtender<_Base> {
klao@962:   public:
klao@962: 
klao@962:     typedef AlterableUndirGraphExtender Graph;
klao@962:     typedef AlterableGraphExtender<_Base> Parent;
klao@962: 
klao@962:     typedef typename Parent::UndirEdge UndirEdge;
klao@962: 
klao@962:     /// The edge observer registry.
deba@1039:     typedef AlterationNotifier<UndirEdge> UndirEdgeNotifier;
klao@962: 
klao@962:   protected:
klao@962: 
deba@1040:     mutable UndirEdgeNotifier undir_edge_notifier;
klao@962: 
klao@1022:   public:
klao@1022: 
deba@1038:     using Parent::getNotifier;
deba@1039:     UndirEdgeNotifier& getNotifier(UndirEdge) const {
deba@1040:       return undir_edge_notifier;
klao@962:     }
klao@962: 
klao@962:     ~AlterableUndirGraphExtender() {
deba@1040:       undir_edge_notifier.clear();
klao@962:     }
klao@962:   };
klao@946:   
klao@946: /// @}
klao@946:   
klao@946: 
klao@946: }
klao@946: 
klao@946: #endif