alpar@906: /* -*- C++ -*-
alpar@921:  * src/lemon/map_registry.h - Part of LEMON, a generic C++ optimization library
alpar@906:  *
alpar@906:  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@906:  * (Egervary Combinatorial Optimization Research Group, EGRES).
alpar@906:  *
alpar@906:  * Permission to use, modify and distribute this software is granted
alpar@906:  * provided that this copyright notice appears in all copies. For
alpar@906:  * precise terms see the accompanying LICENSE file.
alpar@906:  *
alpar@906:  * This software is provided "AS IS" with no warranty of any kind,
alpar@906:  * express or implied, and with no claim as to its suitability for any
alpar@906:  * purpose.
alpar@906:  *
alpar@906:  */
alpar@906: 
alpar@921: #ifndef LEMON_MAP_REGISTRY_H
alpar@921: #define LEMON_MAP_REGISTRY_H
deba@782: 
deba@782: #include <vector>
deba@782: 
alpar@785: ///\ingroup graphmapfactory
alpar@785: ///\file
alpar@785: ///\brief Map registry for graph maps.
alpar@785: 
deba@782: using namespace std;
deba@782: 
alpar@921: namespace lemon {
deba@782: 
deba@937:   /// \addtogroup graphmapfactory
deba@937:   /// @{
alpar@785: 
deba@937:   /// Map registry for graph maps.
deba@937: 
deba@937:   /** 
deba@937:    * Registry class to register edge or node maps into the graph. The
deba@937:    * registry helps you to implement an observer pattern. If you add
deba@937:    * or erase an edge or node you must notify all the maps about the
deba@937:    * event.
deba@937:    *
deba@937:    * \param G The graph type to register maps.
deba@937:    * \param K The key type of the maps registered into the registry.
deba@937:    * \param KIt The key iterator type iterates on the keys.
deba@937:    *
deba@937:    * \author Balazs Dezso
deba@937:    */
deba@937: 
deba@782:   template <typename G, typename K, typename KIt>
deba@782:   class MapRegistry {
deba@782:   public:
deba@782:     typedef G Graph;
alpar@786:     typedef K KeyType;
deba@782:     typedef KIt KeyIt;
deba@937: 
deba@937:     /// MapBase is the base class of the dynamic maps.
deba@782: 	
deba@782:     /**
deba@937:      * MapBase is the base class of the dynamic maps.
deba@782:      * It defines the core modification operations on the maps and
deba@782:      * implements some helper functions. 
deba@782:      */
deba@782:     class MapBase {
deba@782:     public:
deba@782:       typedef G Graph;
alpar@786:       typedef K KeyType;
deba@782:       typedef KIt KeyIt;
deba@782: 
deba@782:       typedef MapRegistry<G, K, KIt> Registry;
deba@782: 	
deba@782:       friend class MapRegistry<G, K, KIt>;
deba@782: 
deba@937:       /// Default constructor.
deba@937: 
deba@782:       /**
deba@782:        * Default constructor for MapBase.
deba@782:        */
deba@782: 
deba@782:       MapBase() : graph(0), registry(0) {}
deba@937: 
deba@937:       /// Constructor to register map into a graph registry.
deba@782: 		
deba@782:       /** 
deba@937:        * Simple constructor to register dynamic map into a graph registry.
deba@782:       */
deba@782: 	
deba@782:       MapBase(const Graph& g, Registry& r) : graph(&g), registry(0) {
deba@782: 	r.attach(*this);
deba@782:       }
deba@782: 
deba@937:       /// Copy constructor.
deba@937: 
deba@782:       /** 
deba@782:        * Copy constructor to register into the registry.
deba@937:        * If the copiable map is registered into a registry
deba@937:        * the construated map will be registered to the same registry.
deba@782:       */	
deba@782: 	
deba@783:       MapBase(const MapBase& copy) : graph(copy.graph), registry(0) {
deba@782: 	if (copy.registry) {
deba@782: 	  copy.registry->attach(*this);
deba@782: 	}
deba@782:       } 
deba@937: 
deba@937:       /// Assign operator.
deba@782: 	
deba@782:       /** 
deba@937:        * Assign operator. This member detach first the map
deba@937:        * from the current registry and then it attach to the
deba@937:        * copiable map's registry if it exists.
deba@782:       */	
deba@782:       const MapBase& operator=(const MapBase& copy) {
deba@782: 	if (registry) {
deba@782: 	  registry->detach(*this);
deba@782: 	}
deba@782: 	graph = copy.graph;
deba@782: 	if (copy.registry) {
deba@782: 	  copy.registry->attach(*this);
deba@782: 	}
deba@783: 	return *this;
deba@782:       }
deba@782: 	
deba@937:       /// Destructor
deba@782: 
deba@782:       /** 
deba@937:        * This member detach the map from the its registry if the
deba@937:        * registry exists.
deba@782:       */		
deba@782: 
deba@782:       virtual ~MapBase() {
deba@782: 	if (registry) {
deba@782: 	  registry->detach(*this);
deba@782: 	}
deba@782:       }
deba@782: 
deba@937:       /// The graph of the map.
deba@937: 
deba@782:       /*
deba@782:        * Returns the graph that the map belongs to.
deba@782:       */
deba@782: 
deba@782:       const Graph* getGraph() const { return graph; }
deba@782: 	
deba@782:     protected:
deba@782: 		
deba@782:       const Graph* graph;     
deba@782:       Registry* registry;
deba@782: 
deba@782:       int registry_index;
deba@782: 
deba@782:     protected:
deba@937: 
deba@937:       /// Helper function to implement constructors in the subclasses.
deba@782: 	
deba@782:       /**
deba@937:        * Helper function to implement constructors in the subclasses.
deba@937:        * It adds all of the nodes or edges to the map via the 
deba@937:        * \ref MapRegistry::MapBase::add add
deba@937:        * member function.
deba@782:       */
deba@782: 	
deba@782:       virtual void init() {
deba@782: 	for (KeyIt it(*graph); it != INVALID; ++it) {
deba@782: 	  add(it);
deba@782: 	}
deba@782:       }
deba@782: 	
deba@937: 
deba@937:       /// Helper function to implement destructors in the subclasses.
deba@937: 	
deba@782:       /**
deba@937:        * Helper function to implement destructors in the subclasses.
deba@937:        * It erases all of the nodes or edges of the map via the 
deba@937:        * \ref MapRegistry::MapBase::erase erase
deba@937:        * member function. It can be used by the clear function also.
deba@782:       */
deba@782: 	
deba@782:       virtual void destroy() {
deba@782: 	for (KeyIt it(*getGraph()); it != INVALID; ++it) {
deba@782: 	  erase(it);
deba@782: 	}
deba@782:       }
deba@937: 
deba@937:       /// The member function to add new node or edge to the map.
deba@782: 	
deba@782:       /** 
deba@782: 	  The add member function should be overloaded in the subclasses.
deba@937: 	  \e Add extends the map with the new node or edge.
deba@782:       */
deba@782: 	
alpar@786:       virtual void add(const KeyType&) = 0;	
deba@937: 
deba@937: 
deba@937:       /// The member function to erase a node or edge from the map.
deba@937: 
deba@782:       /** 
deba@782: 	  The erase member function should be overloaded in the subclasses.
deba@937: 	  \e Erase removes the node or edge from the map.
deba@782:       */
deba@782: 	
alpar@786:       virtual void erase(const KeyType&) = 0;
deba@782: 
deba@782:       /**
deba@782:        *  The clear member function should be overloaded in the subclasses.
deba@782:        *  \e Clear makes empty the data structure.
deba@782:        */
deba@782: 
deba@782:       virtual void clear() = 0;
deba@937: 
deba@937:       /// Exception class to throw at unsupported operation.
deba@782: 	
deba@782:       /**
deba@937:        * Exception class to throw at unsupported operation.
deba@937:        * If the map does not support erasing or adding new
deba@937:        * node or key it must be throwed.
deba@782:       */
deba@782: 	
deba@782:       class NotSupportedOperationException {};
deba@782: 
deba@782:     };
deba@782: 	
deba@782:   protected:
deba@782: 	
deba@937: 
deba@782:     typedef std::vector<MapBase*> Container; 
deba@782: 
deba@782:     Container container;
deba@782: 
deba@782: 		
deba@782:   public:
deba@937: 
deba@937:     /// Default constructor.
deba@782: 	
deba@782:     /**
deba@937:      * Default constructor of the \e MapRegistry. 
deba@937:      * It creates an empty registry.
deba@782:      */
deba@782:     MapRegistry() {}
deba@937: 
deba@937:     /// Copy Constructor of the MapRegistry. 
deba@782: 	
deba@782:     /**
deba@937:      * Copy constructor of the \e MapRegistry. 
deba@937:      * The new registry does not steal
deba@937:      * the maps from the copiable registry. 
deba@937:      * The new registry will be empty.
deba@782:      */
deba@782:     MapRegistry(const MapRegistry&) {}
deba@937: 
deba@937:     /// Assign operator.
deba@782: 		
deba@782:     /**
deba@937:      * Assign operator. This registry does not steal the maps 
deba@937:      * from the copiable registry. This registry will be an empty registry.
deba@937:      * This operator will be called when a graph is assigned.
deba@782:      */
deba@782:     MapRegistry& operator=(const MapRegistry&) {
deba@782:       typename Container::iterator it;
deba@782:       for (it = container.begin(); it != container.end(); ++it) {
deba@937: 	(*it)->clear();
deba@782: 	(*it)->graph = 0;
deba@782: 	(*it)->registry = 0;
deba@782:       }
deba@782:     }
deba@937: 
deba@937:     /// Destructor.
deba@782: 				
deba@782:     /**
deba@937:      * Destructor of the MapRegistry. It makes empty the attached map
deba@937:      * first then detachs them.
deba@782:      */
deba@782:     ~MapRegistry() {
deba@782:       typename Container::iterator it;
deba@782:       for (it = container.begin(); it != container.end(); ++it) {
deba@937: 	(*it)->clear();
deba@782: 	(*it)->registry = 0;
deba@782: 	(*it)->graph = 0;
deba@782:       }
deba@782:     }
deba@782: 	
deba@782: 	
deba@782:     public:
deba@937: 
deba@937:     /// Attachs a map to the \e MapRegistry.
deba@782: 	
deba@782:     /**
deba@937:      * Attachs a map into thr registry. If the map has been attached
deba@782:      * into an other registry it is detached from that automaticly.
deba@782:      */
deba@782:     void attach(MapBase& map) {
deba@782:       if (map.registry) {
deba@782: 	map.registry->detach(map);
deba@782:       }
deba@782:       container.push_back(&map);
deba@782:       map.registry = this;
deba@782:       map.registry_index = container.size()-1;
deba@782:     } 
deba@937: 
deba@937:     /// Detachs a map from the \e MapRegistry.
deba@782: 	
deba@782:     /**
deba@937:      * Detachs a map from the \e MapRegistry.
deba@782:      */
deba@782:     void detach(MapBase& map) {
deba@782:       container.back()->registry_index = map.registry_index; 
deba@782:       container[map.registry_index] = container.back();
deba@782:       container.pop_back();
deba@782:       map.registry = 0;
deba@782:       map.graph = 0;
deba@782:     }
deba@782: 	
deba@937:     /// Notify all the registered maps about a Key added.
deba@782: 		
deba@782:     /**
deba@782:      * Notify all the registered maps about a Key added.
deba@937:      * This member should be called whenever a node or edge
deba@937:      * is added to the graph.
deba@782:      */
deba@937:     void add(const KeyType& key) {
deba@782:       typename Container::iterator it;
deba@782:       for (it = container.begin(); it != container.end(); ++it) {
deba@782: 	(*it)->add(key);
deba@782:       }
deba@782:     }	
deba@937: 
deba@937:     /// Notify all the registered maps about a Key erased.
deba@782: 		
deba@782:     /**
deba@782:      * Notify all the registered maps about a Key erased.
deba@937:      * This member should be called whenever a node or edge
deba@937:      * is erased from the graph.
deba@782:      */ 
deba@937:     void erase(const KeyType& key) {
deba@782:       typename Container::iterator it;
deba@782:       for (it = container.begin(); it != container.end(); ++it) {
deba@782: 	(*it)->erase(key);
deba@782:       }
deba@782:     }
deba@782: 
deba@937: 
deba@937:     /// Notify all the registered maps about all the Keys are erased.
deba@937: 
deba@782:     /**
deba@782:      * Notify all the registered maps about the map should be cleared.
deba@937:      * This member should be called whenever all of the nodes or edges
deba@937:      * are erased from the graph.
deba@782:      */ 
deba@783:     void clear() {
deba@782:       typename Container::iterator it;
deba@782:       for (it = container.begin(); it != container.end(); ++it) {
deba@782: 	(*it)->clear();
deba@782:       }
deba@782:     }
deba@782:   };
deba@782: 
alpar@785:   
alpar@785: /// @}
alpar@785:   
alpar@785: 
deba@782: }
deba@782: 
deba@782: #endif