deba@1032: /* -*- C++ -*-
deba@1032:  * src/lemon/map_utils.h - Part of LEMON, a generic C++ optimization library
deba@1032:  *
deba@1032:  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@1032:  * (Egervary Combinatorial Optimization Research Group, EGRES).
deba@1032:  *
deba@1032:  * Permission to use, modify and distribute this software is granted
deba@1032:  * provided that this copyright notice appears in all copies. For
deba@1032:  * precise terms see the accompanying LICENSE file.
deba@1032:  *
deba@1032:  * This software is provided "AS IS" with no warranty of any kind,
deba@1032:  * express or implied, and with no claim as to its suitability for any
deba@1032:  * purpose.
deba@1032:  *
deba@1032:  */
deba@1032: 
deba@1115: ///\ingroup mutils
deba@1032: ///\file
deba@1032: ///\brief Map utilities.
deba@1032: 
deba@1032: #include <map>
deba@1032: 
deba@1032: 
deba@1032: namespace lemon {
deba@1032: 
deba@1133:   /// \addtogroup mutils
deba@1032:   /// @{
deba@1032: 
deba@1032:   /// \brief General inversable map type.
deba@1032: 
deba@1032:   /// This type provides simple inversable map functions. 
deba@1032:   /// The InversableMap wraps an arbitrary ReadWriteMap 
deba@1032:   /// and if a key is setted to a new value then store it
deba@1032:   /// in the inverse map.
deba@1133:   /// \param _Graph The graph type.
deba@1133:   /// \param _Map The map to extend with inversable functionality. 
deba@1032:   template <
deba@1032:     typename _Graph, 
deba@1037:     typename _Map
deba@1032:   >
deba@1032:   class InversableMap : protected _Map {
deba@1032: 
deba@1032:   public:
deba@1037:     typedef _Graph Graph;
deba@1032: 
deba@1037:     typedef _Map Map;
deba@1133:     /// The key type of InversableMap (Node, Edge, UndirEdge).
deba@1037:     typedef typename _Map::Key Key;
deba@1133:     /// The value type of the InversableMap.
deba@1037:     typedef typename _Map::Value Value;
deba@1037:     typedef std::map<Value, Key> InverseMap;
deba@1032:     
deba@1037:     typedef typename _Map::ConstReference ConstReference;
deba@1032: 
deba@1115:     /// \brief Constructor.
deba@1115:     ///
deba@1032:     /// Construct a new InversableMap for the graph.
deba@1032:     ///
deba@1032:     InversableMap(const Graph& graph) : Map(graph) {} 
deba@1032:     
deba@1115:     /// \brief The setter function of the map.
deba@1115:     ///
deba@1115:     /// It sets the map and the inverse map to given key-value pair.
deba@1032:     void set(const Key& key, const Value& val) {
deba@1032:       Value oldval = Map::operator[](key);
deba@1133:       typename InverseMap::iterator it = invMap.find(oldval);
deba@1133:       if (it != invMap.end() && it->second == key) {
deba@1133: 	invMap.erase(it);
deba@1032:       }      
deba@1133:       invMap.insert(make_pair(val, key));
deba@1032:       Map::set(key, val);
deba@1032:     }
deba@1032: 
deba@1133:     /// \brief The getter function of the map.
deba@1133:     ///
deba@1133:     /// It gives back the value associated with the key.
deba@1133:     ConstReference operator[](const Key& key) const {
deba@1032:       return Map::operator[](key);
deba@1032:     }
deba@1032: 
deba@1133:     /// \brief Add a new key to the map.
deba@1133:     ///
deba@1133:     /// Add a new key to the map. It is called by the
deba@1133:     /// \c AlterationNotifier.
deba@1133:     virtual void add(const Key& key) {
deba@1032:       Map::add(key);
deba@1032:     }
deba@1032: 
deba@1133:     /// \brief Erase the key from the map.
deba@1133:     ///
deba@1133:     /// Erase the key to the map. It is called by the
deba@1133:     /// \c AlterationNotifier.
deba@1133:     virtual void erase(const Key& key) {
deba@1032:       Value val = Map::operator[](key);
deba@1133:       typename InverseMap::iterator it = invMap.find(val);
deba@1133:       if (it != invMap.end() && it->second == key) {
deba@1032: 	invMap.erase(it);
deba@1032:       }
deba@1032:       Map::erase(key);
deba@1032:     }
deba@1032: 
deba@1133:     /// \brief Clear the keys from the map and inverse map.
deba@1133:     ///
deba@1133:     /// Clear the keys from the map and inverse map. It is called by the
deba@1133:     /// \c AlterationNotifier.
deba@1133:     virtual void clear() {
deba@1133:       invMap.clear();
deba@1133:       Map::clear();
deba@1133:     }
deba@1133: 
deba@1133:     /// \brief It gives back the just readeable inverse map.
deba@1133:     ///
deba@1133:     /// It gives back the just readeable inverse map.
deba@1032:     const InverseMap& inverse() const {
deba@1133:       return invMap;
deba@1032:     } 
deba@1032: 
deba@1032: 
deba@1032:   private:
deba@1133:     InverseMap invMap;    
deba@1032:   };
deba@1032: 
deba@1037: 
deba@1115:   
deba@1115:   /// \brief Provides a mutable, continous and unique descriptor for each 
deba@1115:   /// item in the graph.
deba@1115:   ///
deba@1115:   /// The DescriptorMap class provides a mutable, continous and immutable
deba@1115:   /// mapping for each item in the graph.
deba@1115:   ///
deba@1115:   /// \param _Graph The graph class the \c DescriptorMap belongs to.
deba@1115:   /// \param _Item The Item is the Key of the Map. It may be Node, Edge or 
deba@1115:   /// UndirEdge.
deba@1115:   /// \param _Map A ReadWriteMap mapping from the item type to integer.
deba@1037: 
deba@1037:   template <
deba@1037:     typename _Graph,   
deba@1037:     typename _Item,
deba@1037:     typename _Map
deba@1037:   >
deba@1037:   class DescriptorMap : protected _Map {
deba@1115: 
deba@1037:     typedef _Item Item;
deba@1037:     typedef _Map Map;
deba@1037: 
deba@1115:   public:
deba@1115:     /// The graph class of DescriptorMap.
deba@1115:     typedef _Graph Graph;
deba@1037: 
deba@1115:     /// The key type of DescriptorMap (Node, Edge, UndirEdge).
deba@1037:     typedef typename _Map::Key Key;
deba@1115:     /// The value type of DescriptorMap.
deba@1037:     typedef typename _Map::Value Value;
deba@1037: 
deba@1115:     typedef std::vector<Item> InverseMap;
deba@1037: 
deba@1115:     /// \brief Constructor.
deba@1115:     ///
deba@1115:     /// Constructor for creating descriptor map.
deba@1037:     DescriptorMap(const Graph& _graph) : Map(_graph) {
deba@1037:       build();
deba@1037:     }
deba@1037: 
deba@1133:     /// \brief Add a new key to the map.
deba@1133:     ///
deba@1133:     /// Add a new key to the map. It is called by the
deba@1133:     /// \c AlterationNotifier.
deba@1037:     virtual void add(const Item& item) {
deba@1037:       Map::add(item);
deba@1133:       Map::set(item, invMap.size());
deba@1133:       invMap.push_back(item);
deba@1037:     }
deba@1037: 
deba@1133:     /// \brief Erase the key from the map.
deba@1133:     ///
deba@1133:     /// Erase the key to the map. It is called by the
deba@1133:     /// \c AlterationNotifier.
deba@1037:     virtual void erase(const Item& item) {
deba@1133:       Map::set(invMap.back(), Map::operator[](item));
deba@1133:       invMap[Map::operator[](item)] = invMap.back();
deba@1037:       Map::erase(item);
deba@1037:     }
deba@1037: 
deba@1133:     /// \brief Build the unique map.
deba@1133:     ///
deba@1133:     /// Build the unique map. It is called by the
deba@1133:     /// \c AlterationNotifier.
deba@1037:     virtual void build() {
deba@1037:       Map::build();
deba@1115:       Item it;
deba@1115:       for (getGraph()->first(it); it != INVALID; getGraph()->next(it)) {
deba@1133: 	Map::set(it, invMap.size());
deba@1133: 	invMap.push_back(it);	
deba@1037:       }      
deba@1037:     }
deba@1037:     
deba@1133:     /// \brief Clear the keys from the map.
deba@1133:     ///
deba@1133:     /// Clear the keys from the map. It is called by the
deba@1133:     /// \c AlterationNotifier.
deba@1037:     virtual void clear() {
deba@1133:       invMap.clear();
deba@1037:       Map::clear();
deba@1037:     }
deba@1037: 
deba@1115:     /// \brief Gives back the \e descriptor of the item.
deba@1115:     ///
deba@1115:     /// Gives back the mutable and unique \e descriptor of the map.
deba@1037:     int operator[](const Item& item) const {
deba@1037:       return Map::operator[](item);
deba@1037:     }
deba@1037:     
deba@1115:     /// \brief Gives back the inverse of the map.
deba@1115:     ///
deba@1115:     /// Gives back the inverse of the map.
deba@1037:     const InverseMap inverse() const {
deba@1133:       return invMap;
deba@1037:     }
deba@1037: 
deba@1037:   private:
deba@1133:     vector<Item> invMap;
deba@1037:   };
deba@1115:   
deba@1115:   /// Provides an immutable and unique id for each item in the graph.
deba@1037: 
deba@1115:   /// The IdMap class provides an unique and immutable mapping for each item
deba@1115:   /// in the graph.
deba@1115:   ///
deba@1115:   template <typename _Graph, typename _Item>
deba@1115:   class IdMap {
deba@1115:   public:
deba@1115:     typedef _Graph Graph;
deba@1115:     typedef int Value;
deba@1115:     typedef _Item Item;
deba@1115: 
deba@1115:     /// \brief The class represents the inverse of the map.
deba@1115:     ///
deba@1115:     /// The class represents the inverse of the map.
deba@1115:     /// \see inverse()
deba@1115:     class InverseMap {
deba@1115:     protected:
deba@1115:       InverseMap(const Graph& _graph) : graph(_graph) {}
deba@1115:     public:
deba@1115:       /// \brief Gives back the given item by its id.
deba@1115:       ///
deba@1115:       /// Gives back the given item by its id.
deba@1115:       /// 
deba@1115:       Item operator[](int id) const { return graph->fromId(id, Item());}
deba@1115:     private:
deba@1115:       Graph* graph;
deba@1115:     };
deba@1115: 
deba@1115:     /// \brief Constructor.
deba@1115:     ///
deba@1115:     /// Constructor for creating id map.
deba@1115:     IdMap(const Graph& _graph) : graph(&_graph) {}
deba@1115: 
deba@1115:     /// \brief Gives back the \e id of the item.
deba@1115:     ///
deba@1115:     /// Gives back the immutable and unique \e id of the map.
deba@1115:     int operator[](const Item& item) const { return graph->id(item);}
deba@1115: 
deba@1115:     /// \brief Gives back the inverse of the map.
deba@1115:     ///
deba@1115:     /// Gives back the inverse of the map.
deba@1115:     InverseMap inverse() const { return InverseMap(*graph);} 
deba@1115: 
deba@1115:   private:
deba@1115:     const Graph* graph;
deba@1115: 
deba@1115:   };
deba@1115: 
deba@1115: 
deba@1037: 
deba@1032: }
deba@1032: