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