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

}