/* -*- 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
  
  

}