/* -*- C++ -*-

  * src/lemon/map_utils.h - Part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Combinatorial Optimization Research Group, EGRES).

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 ///\ingroup gutils

 ///\file

 ///\brief Map utilities.

 #include <map>

 namespace lemon {

   /// \addtogroup gutils

   /// @{

   /// \brief General inversable map type.

   /// This type provides simple inversable map functions. 

   /// The InversableMap wraps an arbitrary ReadWriteMap 

   /// and if a key is setted to a new value then store it

   /// in the inverse map.

   template <

     typename _Graph, 

     typename _Map

   >

   class InversableMap : protected _Map {

   public:

     typedef _Graph Graph;

     typedef _Map Map;

     typedef typename _Map::Key Key;

     typedef typename _Map::Value Value;

     typedef std::map<Value, Key> InverseMap;

     typedef typename _Map::ConstReference ConstReference;

     /// Constructor.

     /// Construct a new InversableMap for the graph.

     ///

     InversableMap(const Graph& graph) : Map(graph) {} 

     /// The setter function of the map.

     /// It sets the map and the inverse map 

     void set(const Key& key, const Value& val) {

       Value oldval = Map::operator[](key);

       typename InverseMap::iterator it = inv_map.find(oldval);

       if (it != inv_map.end() && it->second == key) {

 	inv_map.erase(it);

       }      

       inv_map.insert(make_pair(val, key));

       Map::set(key, val);

     }

     ConstReference operator[](const Key&) const {

       return Map::operator[](key);

     }

     virtual void add(const Key&) {

       Map::add(key);

     }

     virtual void erase(const Key&) {

       Value val = Map::operator[](key);

       typename InverseMap::iterator it = inv_map.find(val);

       if (it != inv_map.end() && it->second == key) {

 	invMap.erase(it);

       }

       Map::erase(key);

     }

     const InverseMap& inverse() const {

       return inv_map;

     } 

   private:

     InverseMap inv_map;    

   };

   // unique, continous, mutable

   template <

     typename _Graph,   

     typename _Item,

     typename _ItemIt,

     typename _Map

   >

   class DescriptorMap : protected _Map {

   public:

     typedef _Graph Graph;

     typedef _Item Item;

     typedef _ItemIt ItemIt;

     typedef _Map Map;

     typedef typename _Map::Key Key;

     typedef typename _Map::Value Value;

     typedef vector<Item> InverseMap;

     DescriptorMap(const Graph& _graph) : Map(_graph) {

       build();

     }

     virtual void add(const Item& item) {

       Map::add(item);

       Map::set(item, inv_map.size());

       inv_map.push_back(item);

     }

     virtual void erase(const Item& item) {

       Map::set(inv_map.back(), Map::operator[](item));

       inv_map[Map::operator[](item)] = inv_map.back();

       Map::erase(item);

     }

     virtual void build() {

       Map::build();

       for (ItemIt it(*Map::getGraph()); it != INVALID; ++it) {

 	Map::set(it, inv_map.size());

 	inv_map.push_back(it);	

       }      

     }

     virtual void clear() {

       inv_map.clear();

       Map::clear();

     }

     int operator[](const Item& item) const {

       return Map::operator[](item);

     }

     const InverseMap inverse() const {

       return inv_map;

     }

   private:

     vector<Item> inv_map;

   };

   // unique, immutable => IDMap

 }