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@1032: ///\ingroup gutils
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@1032:   /// \addtogroup gutils
deba@1032:   /// @{
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@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@1037:     typedef typename _Map::Key Key;
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@1032:     /// Constructor.
deba@1032: 
deba@1032:     /// Construct a new InversableMap for the graph.
deba@1032:     ///
deba@1032:     InversableMap(const Graph& graph) : Map(graph) {} 
deba@1032:     
deba@1032:     /// The setter function of the map.
deba@1032: 
deba@1032:     /// It sets the map and the inverse map 
deba@1032:     void set(const Key& key, const Value& val) {
deba@1032:       Value oldval = Map::operator[](key);
deba@1037:       typename InverseMap::iterator it = inv_map.find(oldval);
deba@1037:       if (it != inv_map.end() && it->second == key) {
deba@1037: 	inv_map.erase(it);
deba@1032:       }      
deba@1037:       inv_map.insert(make_pair(val, key));
deba@1032:       Map::set(key, val);
deba@1032:     }
deba@1032: 
deba@1032:     ConstReference operator[](const Key&) const {
deba@1032:       return Map::operator[](key);
deba@1032:     }
deba@1032: 
deba@1032:     virtual void add(const Key&) {
deba@1032:       Map::add(key);
deba@1032:     }
deba@1032: 
deba@1032:     virtual void erase(const Key&) {
deba@1032:       Value val = Map::operator[](key);
deba@1037:       typename InverseMap::iterator it = inv_map.find(val);
deba@1037:       if (it != inv_map.end() && it->second == key) {
deba@1032: 	invMap.erase(it);
deba@1032:       }
deba@1032:       Map::erase(key);
deba@1032:     }
deba@1032: 
deba@1032:     const InverseMap& inverse() const {
deba@1037:       return inv_map;
deba@1032:     } 
deba@1032: 
deba@1032: 
deba@1032:   private:
deba@1037:     InverseMap inv_map;    
deba@1032:   };
deba@1032: 
deba@1037: 
deba@1037:   // unique, continous, mutable
deba@1037: 
deba@1037:   template <
deba@1037:     typename _Graph,   
deba@1037:     typename _Item,
deba@1037:     typename _ItemIt,
deba@1037:     typename _Map
deba@1037:   >
deba@1037:   class DescriptorMap : protected _Map {
deba@1037:   public:
deba@1037:     typedef _Graph Graph;
deba@1037:     typedef _Item Item;
deba@1037:     typedef _ItemIt ItemIt;
deba@1037:     typedef _Map Map;
deba@1037: 
deba@1037: 
deba@1037:     typedef typename _Map::Key Key;
deba@1037:     typedef typename _Map::Value Value;
deba@1037: 
deba@1037:     typedef vector<Item> InverseMap;
deba@1037: 
deba@1037:     DescriptorMap(const Graph& _graph) : Map(_graph) {
deba@1037:       build();
deba@1037:     }
deba@1037: 
deba@1037:     virtual void add(const Item& item) {
deba@1037:       Map::add(item);
deba@1037:       Map::set(item, inv_map.size());
deba@1037:       inv_map.push_back(item);
deba@1037:     }
deba@1037: 
deba@1037:     virtual void erase(const Item& item) {
deba@1037:       Map::set(inv_map.back(), Map::operator[](item));
deba@1037:       inv_map[Map::operator[](item)] = inv_map.back();
deba@1037:       Map::erase(item);
deba@1037:     }
deba@1037: 
deba@1037:     virtual void build() {
deba@1037:       Map::build();
deba@1037:       for (ItemIt it(*Map::getGraph()); it != INVALID; ++it) {
deba@1037: 	Map::set(it, inv_map.size());
deba@1037: 	inv_map.push_back(it);	
deba@1037:       }      
deba@1037:     }
deba@1037:     
deba@1037:     virtual void clear() {
deba@1037:       inv_map.clear();
deba@1037:       Map::clear();
deba@1037:     }
deba@1037: 
deba@1037:     int operator[](const Item& item) const {
deba@1037:       return Map::operator[](item);
deba@1037:     }
deba@1037: 
deba@1037:     
deba@1037:     const InverseMap inverse() const {
deba@1037:       return inv_map;
deba@1037:     }
deba@1037: 
deba@1037:   private:
deba@1037:     vector<Item> inv_map;
deba@1037:   };
deba@1037: 
deba@1037:   // unique, immutable => IDMap
deba@1037:   
deba@1037:   
deba@1037: 
deba@1032: }
deba@1032: