/* -*- C++ -*-

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

 *

 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, 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.

 *

 */

#include <lemon/traits.h>

#include <lemon/invalid.h>

#include <vector>

#include <limits>

///\ingroup maps

///\file

///\brief Maps that makes it possible to iterate through the keys having

///a certain value

///

///

namespace lemon {

  ///\todo This is only a static map!

  ///\todo Undocumented.

  ///\param BaseMap is an interger map.

  template<class BaseMap>

  class IterableBoolMap

  {

  public:

    typedef typename BaseMap::Key Key;

    typedef bool Value;

    friend class RefType;

    friend class FalseIt;

    friend class TrueIt;

  private:

    BaseMap &cref;

    std::vector<Key> vals;

    int sep;           //map[e] is true <=> cref[e]>=sep

    bool isTrue(Key k) {return cref[k]>=sep;}

    void swap(Key k, int s) 

    {

      int ti=cref[k];

      Key tk=vals[s];

      cref[k]=s; vals[s]=k;

      cref[tk]=ti; vals[ti]=tk;

    }  

    void setTrue(Key k) { if(cref[k]<sep) { sep--; swap(k,sep); } }

    void setFalse(Key k) { if(cref[k]>=sep) { swap(k,sep); sep++; } }

  public:

    ///\e

    void set(Key k,Value v) { if(v) setTrue(k); else setFalse(k);}

    ///Number of \c true items in the map

    ///Returns the number of \c true values in the map.

    ///This is a constant time operation.

    int countTrue() { return vals.size()-sep; }

    ///Number of \c false items in the map

    ///Returns the number of \c false values in the map.

    ///This is a constant time operation.

    int countFalse() { return sep; }

    ///\e

    class FalseIt

    {

      const IterableBoolMap &M;

      int i;

    public:

      ///\e

      explicit FalseIt(const IterableBoolMap &_M) : M(_M), i(0) { }

      ///\e

      FalseIt(Invalid)

	: M(*((IterableBoolMap*)(0))), i(std::numeric_limits<int>::max()) { }

      ///\e

      FalseIt &operator++() { ++i; return *this;}

      ///\e

      operator Key() const { return i<M.sep ? M.vals[i] : INVALID; }

      ///\e

      bool operator !=(Invalid) const { return i<M.sep; }

      ///\e

      bool operator ==(Invalid) const { return i>=M.sep; }

    };

    ///\e

    class TrueIt

    {

      const IterableBoolMap &M;

      int i;

    public:

      ///\e

      explicit TrueIt(const IterableBoolMap &_M)

	: M(_M), i(M.vals.size()-1) { }

      ///\e

      TrueIt(Invalid)

	: M(*((IterableBoolMap*)(0))), i(-1) { }

      ///\e

      TrueIt &operator++() { --i; return *this;}

      ///\e

      operator Key() const { return i>=M.sep ? M.vals[i] : INVALID; }

      ///\e

      bool operator !=(Invalid) const { return i>=M.sep; }

      ///\e

      bool operator ==(Invalid) const { return i<M.sep; }

    };

    ///\e

    class RefType

    {

      IterableBoolMap &M;

      Key k;

    public:

      RefType(IterableBoolMap &_M,Key _k) : M(_M), k(_k) { }

      operator Value() const 

      {

	return M.isTrue(k);

      }

      Value operator = (Value v) const { M.set(k,v); return v; }

    };

  public:

    explicit IterableBoolMap(BaseMap &_m,bool init=false) : cref(_m)

    {

      sep=0;

      for(typename BaseMap::MapIt i(cref);i!=INVALID; ++i) {

	i.set(sep);

	vals.push_back(i);

	sep++;

      }

      if(init) sep=0;

    }

    ///\e

    RefType operator[] (Key k) { return RefType(*this,k);}  

    ///\e

    Value operator[] (Key k) const { return isTrue(k);}  

  };

  /// \addtogroup graph_maps

  /// @{

  /// Iterable bool NodeMap

  /// This map can be used in the same way

  /// as the standard NodeMap<bool> of the

  /// given graph \c Graph. 

  /// In addition, this class provides two iterators called \ref TrueIt

  /// and \ref FalseIt to iterate through the "true" and "false" nodes.

  template <class Graph>

  class IterableBoolNodeMap

  {

    typename Graph::template NodeMap<int> cmap;

  public:

    typedef IterableBoolMap<typename Graph::template NodeMap<int> > BimType;

    BimType imap;

    typedef typename BimType::RefType RefType;

    typedef typename Graph::Node Key;

    typedef bool Value;

    friend class FalseIt;

    friend class TrueIt;

    ///\e

    IterableBoolNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}

  public:

    ///\e

    void set(Key k, bool v) { imap.set(k,v);}

    ///Number of \c true items in the map

    ///Returns the number of \c true values in the map.

    ///This is a constant time operation.

    int countTrue() { return imap.countTrue(); }

    ///Number of \c false items in the map

    ///Returns the number of \c false values in the map.

    ///This is a constant time operation.

    int countFalse() { return imap.countFalse(); }

#ifdef DOXYGEN

    ///\e

    bool &operator[](Key k) { return imap[k];}  

    ///\e

    const bool &operator[](Key k) const { return imap[k];}  

#else

    Value operator[](Key k) const { return imap[k];}  

    RefType operator[](Key k) { return imap[k];}  

#endif

    ///Iterator for the "false" nodes

    class FalseIt : public BimType::FalseIt

    {

    public:

      ///\e

      explicit FalseIt(const IterableBoolNodeMap &m)

	: BimType::FalseIt(m.imap) { }

      ///\e

      FalseIt(Invalid i) : BimType::FalseIt(i) { }

    };

    ///Iterator for the "true" nodes

    class TrueIt : public BimType::TrueIt

    {

    public:

      ///\e

      explicit TrueIt(const IterableBoolNodeMap &m)

	: BimType::TrueIt(m.imap) { }

      ///\e

      TrueIt(Invalid i) : BimType::TrueIt(i) { }

    };  

  };

  /// Iterable bool UpperNodeMap

  /// This map can be used in the same way

  /// as the standard UpperNodeMap<bool> of the

  /// given graph \c Graph. 

  /// In addition, this class provides two iterators called \ref TrueIt

  /// and \ref FalseIt to iterate through the "true" and "false" nodes.

  template <class Graph>

  class IterableBoolUpperNodeMap

  {

    typename Graph::template UpperNodeMap<int> cmap;

  public:

    typedef IterableBoolMap<typename Graph::template UpperNodeMap<int> > BimType;

    BimType imap;

    typedef typename BimType::RefType RefType;

    typedef typename Graph::Node Key;

    typedef bool Value;

    friend class FalseIt;

    friend class TrueIt;

    ///\e

    IterableBoolUpperNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}

  public:

    ///\e

    void set(Key k, bool v) { imap.set(k,v);}

    ///Number of \c true items in the map

    ///Returns the number of \c true values in the map.

    ///This is a constant time operation.

    int countTrue() { return imap.countTrue(); }

    ///Number of \c false items in the map

    ///Returns the number of \c false values in the map.

    ///This is a constant time operation.

    int countFalse() { return imap.countFalse(); }

#ifdef DOXYGEN

    ///\e

    bool &operator[](Key k) { return imap[k];}  

    ///\e

    const bool &operator[](Key k) const { return imap[k];}  

#else

    Value operator[](Key k) const { return imap[k];}  

    RefType operator[](Key k) { return imap[k];}  

#endif

    ///Iterator for the "false" nodes

    class FalseIt : public BimType::FalseIt

    {

    public:

      ///\e

      explicit FalseIt(const IterableBoolUpperNodeMap &m)

	: BimType::FalseIt(m.imap) { }

      ///\e

      FalseIt(Invalid i) : BimType::FalseIt(i) { }

    };

    ///Iterator for the "true" nodes

    class TrueIt : public BimType::TrueIt

    {

    public:

      ///\e

      explicit TrueIt(const IterableBoolUpperNodeMap &m)

	: BimType::TrueIt(m.imap) { }

      ///\e

      TrueIt(Invalid i) : BimType::TrueIt(i) { }

    };  

  };

  /// Iterable bool LowerNodeMap

  /// This map can be used in the same way

  /// as the standard LowerNodeMap<bool> of the

  /// given graph \c Graph. 

  /// In addition, this class provides two iterators called \ref TrueIt

  /// and \ref FalseIt to iterate through the "true" and "false" nodes.

  template <class Graph>

  class IterableBoolLowerNodeMap

  {

    typename Graph::template LowerNodeMap<int> cmap;

  public:

    typedef IterableBoolMap<typename Graph::template LowerNodeMap<int> > BimType;

    BimType imap;

    typedef typename BimType::RefType RefType;

    typedef typename Graph::Node Key;

    typedef bool Value;

    friend class FalseIt;

    friend class TrueIt;

    ///\e

    IterableBoolLowerNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}

  public:

    ///\e

    void set(Key k, bool v) { imap.set(k,v);}

    ///Number of \c true items in the map

    ///Returns the number of \c true values in the map.

    ///This is a constant time operation.

    int countTrue() { return imap.countTrue(); }

    ///Number of \c false items in the map

    ///Returns the number of \c false values in the map.

    ///This is a constant time operation.

    int countFalse() { return imap.countFalse(); }

#ifdef DOXYGEN

    ///\e

    bool &operator[](Key k) { return imap[k];}  

    ///\e

    const bool &operator[](Key k) const { return imap[k];}  

#else

    Value operator[](Key k) const { return imap[k];}  

    RefType operator[](Key k) { return imap[k];}  

#endif

    ///Iterator for the "false" nodes

    class FalseIt : public BimType::FalseIt

    {

    public:

      ///\e

      explicit FalseIt(const IterableBoolLowerNodeMap &m)

	: BimType::FalseIt(m.imap) { }

      ///\e

      FalseIt(Invalid i) : BimType::FalseIt(i) { }

    };

    ///Iterator for the "true" nodes

    class TrueIt : public BimType::TrueIt

    {

    public:

      ///\e

      explicit TrueIt(const IterableBoolLowerNodeMap &m)

	: BimType::TrueIt(m.imap) { }

      ///\e

      TrueIt(Invalid i) : BimType::TrueIt(i) { }

    };  

  };

  /// Iterable bool EdgeMap

  /// This map can be used in the same way

  /// as the standard EdgeMap<bool> of the

  /// given graph \c Graph. 

  /// In addition, this class provides two iterators called \ref TrueIt

  /// and \ref FalseIt to iterate through the "true" and "false" edges.

  template <class Graph>

  class IterableBoolEdgeMap

  {

    typename Graph::template EdgeMap<int> cmap;

  public:

    typedef IterableBoolMap<typename Graph::template EdgeMap<int> > BimType;

    BimType imap;

    typedef typename BimType::RefType RefType;

    typedef typename Graph::Edge Key;

    typedef bool Value;

    friend class FalseIt;

    friend class TrueIt;

    ///\e

    IterableBoolEdgeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}

  public:

    ///\e

    void set(Key k, bool v) { imap.set(k,v);}

    ///Returns the number of \c true values in the map.

    ///This is a constant time operation.

    int countTrue() { return imap.countTrue(); }

    ///Number of \c false items in the map

    ///Returns the number of \c false values in the map.

    ///This is a constant time operation.

    int countFalse() { return imap.countFalse(); }

#ifdef DOXYGEN

    ///\e

    bool &operator[](Key k) { return imap[k];}  

    ///\e

    const bool &operator[](Key k) const { return imap[k];}  

#else

    Value operator[](Key k) const { return imap[k];}  

    RefType operator[](Key k) { return imap[k];}  

#endif

    ///Iterator for the "false" edges

    class FalseIt : public BimType::FalseIt

    {

    public:

      ///\e

      explicit FalseIt(const IterableBoolEdgeMap &m)

	: BimType::FalseIt(m.imap) { }

      ///\e

      FalseIt(Invalid i) : BimType::FalseIt(i) { }

    };

    ///Iterator for the "true" edges

    class TrueIt : public BimType::TrueIt

    {

    public:

      ///\e

      explicit TrueIt(const IterableBoolEdgeMap &m)

	: BimType::TrueIt(m.imap) { }

      ///\e

      TrueIt(Invalid i) : BimType::TrueIt(i) { }

    };  

  };

  namespace _iterable_maps_bits {

    template <typename Item>

    struct IterableIntMapNode {

      IterableIntMapNode() {}

      IterableIntMapNode(int _value) : value(_value) {}

      Item prev, next;

      int value;

    };

  }

  ///\ingroup maps

  ///

  /// \brief Dynamic iterable integer map.

  ///

  /// This class provides a special graph map type which can store

  /// for each graph item(node, edge, etc.) an integer value. For each

  /// non negative value it is possible to iterate on the keys which

  /// mapped to the given value.

  /// 

  /// \param _Graph The graph type.

  /// \param _Item One of the graph's item type, the key of the map.

  template <typename _Graph, typename _Item>

  class IterableIntMap : protected ItemSetTraits<_Graph, _Item> 

  ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >::Parent {

  public:

    typedef typename ItemSetTraits<_Graph, _Item> 

    ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >

    ::Parent Parent;

    /// The key type

    typedef _Item Key;

    /// The value type

    typedef int Value;

    /// The graph type

    typedef _Graph Graph;

    /// \brief Constructor of the Map.

    ///

    /// Constructor of the Map. It set all values -1.

    explicit IterableIntMap(const Graph& graph) 

      : Parent(graph, _iterable_maps_bits::IterableIntMapNode<_Item>(-1)) {}

    /// \brief Constructor of the Map with a given value.

    ///

    /// Constructor of the Map with a given value.

    explicit IterableIntMap(const Graph& graph, int value) 

      : Parent(graph, _iterable_maps_bits::IterableIntMapNode<_Item>(value)) {

      if (value >= 0) {

	for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {

	  lace(it);

	}

      }

    }

  private:

    void unlace(const Key& key) {

      typename Parent::Value& node = Parent::operator[](key);

      if (node.value < 0) return;

      if (node.prev != INVALID) {

	Parent::operator[](node.prev).next = node.next;	

      } else {

	first[node.value] = node.next;

      }

      if (node.next != INVALID) {

	Parent::operator[](node.next).prev = node.prev;

      }

      while (!first.empty() && first.back() == INVALID) {

	first.pop_back();

      }

    }

    void lace(const Key& key) {

      typename Parent::Value& node = Parent::operator[](key);

      if (node.value < 0) return;

      if (node.value >= (int)first.size()) {

	first.resize(node.value + 1, INVALID);

      } 

      node.prev = INVALID;

      node.next = first[node.value];

      if (node.next != INVALID) {

	Parent::operator[](node.next).prev = key;	

      }

      first[node.value] = key;

    }

  public:

    /// Indicates that the map if reference map.

    typedef True ReferenceMapTag;

    /// \brief Refernce to the value of the map.

    ///

    /// This class is near to similar to the int type. It can

    /// be converted to int and it has the same operators.

    class Reference {

      friend class IterableIntMap;

    private:

      Reference(IterableIntMap& map, const Key& key) 

	: _key(key), _map(map) {} 

    public:

      Reference& operator=(const Reference& value) {

	_map.set(_key, (const int&)value);

 	return *this;

      }

      operator const int&() const { 

	return static_cast<const IterableIntMap&>(_map)[_key]; 

      }

      Reference& operator=(int value) { 

	_map.set(_key, value); 

	return *this; 

      }

      Reference& operator++() {

	_map.set(_key, _map[_key] + 1); 

	return *this; 	

      }

      int operator++(int) {

	int value = _map[_key];

	_map.set(_key, value + 1); 

	return value; 	

      }

      Reference& operator--() {

	_map.set(_key, _map[_key] - 1); 

	return *this; 	

      }

      int operator--(int) {

	int value = _map[_key];

	_map.set(_key, value - 1); 

	return value; 	

      }

      Reference& operator+=(int value) { 

	_map.set(_key, _map[_key] + value); 

	return *this;

      }

      Reference& operator-=(int value) { 

	_map.set(_key, _map[_key] - value); 

	return *this;

      }

      Reference& operator*=(int value) { 

	_map.set(_key, _map[_key] * value); 

	return *this;

      }

      Reference& operator/=(int value) { 

	_map.set(_key, _map[_key] / value); 

	return *this;

      }

      Reference& operator%=(int value) { 

	_map.set(_key, _map[_key] % value); 

	return *this;

      }

      Reference& operator&=(int value) { 

	_map.set(_key, _map[_key] & value); 

	return *this;

      }

      Reference& operator|=(int value) { 

	_map.set(_key, _map[_key] | value); 

	return *this;

      }

      Reference& operator^=(int value) { 

	_map.set(_key, _map[_key] ^ value); 

	return *this;

      }

      Reference& operator<<=(int value) { 

	_map.set(_key, _map[_key] << value); 

	return *this;

      }

      Reference& operator>>=(int value) { 

	_map.set(_key, _map[_key] >> value); 

	return *this;

      }

    private:

      Key _key;

      IterableIntMap& _map; 

    };

    /// The const reference type.    

    typedef const Value& ConstReference;

    /// \brief Gives back the maximal value plus one.

    ///

    /// Gives back the maximal value plus one.

    int size() const {

      return (int)first.size();

    }

    /// \brief Set operation of the map.

    ///

    /// Set operation of the map.

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

      unlace(key);

      Parent::operator[](key).value = value;

      lace(key);

    }

    /// \brief Const subscript operator of the map.

    ///

    /// Const subscript operator of the map.

    const Value& operator[](const Key& key) const {

      return Parent::operator[](key).value;

    }

    /// \brief Subscript operator of the map.

    ///

    /// Subscript operator of the map.

    Reference operator[](const Key& key) {

      return Reference(*this, key);

    }

    /// \brief Iterator for the keys with the same value.

    ///

    /// Iterator for the keys with the same value. It works

    /// like a graph item iterator in the map, it can be converted

    /// the item type of the map, incremented with \c ++ operator, and

    /// if the iterator leave the last valid item it will be equal to 

    /// \c INVALID.

    class ItemIt : public _Item {

    public:

      typedef _Item Parent;

      /// \brief Invalid constructor \& conversion.

      ///

      /// This constructor initializes the item to be invalid.

      /// \sa Invalid for more details.

      ItemIt(Invalid) : Parent(INVALID), _map(0) {}

      /// \brief Creates an iterator with a value.

      ///

      /// Creates an iterator with a value. It iterates on the 

      /// keys which have the given value.

      /// \param map The IterableIntMap

      /// \param value The value

      ItemIt(const IterableIntMap& map, int value) : _map(&map) {

	if (value < 0 || value >= (int)_map->first.size()) {	  

	  Parent::operator=(INVALID);

	} else {

	  Parent::operator=(_map->first[value]);

	}

      } 

      /// \brief Increment operator.

      ///

      /// Increment Operator.

      ItemIt& operator++() {

	Parent::operator=(_map->IterableIntMap::Parent::

			  operator[](static_cast<Parent&>(*this)).next);

	return *this;

      }

    private:

      const IterableIntMap* _map;

    };

  protected:

    virtual void erase(const Key& key) {

      unlace(key);

      Parent::erase(key);

    }

    virtual void clear() {

      first.clear();

      Parent::clear();

    }

  private:

    std::vector<_Item> first;

  };

  /// @}

}