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

   };

   /// @}

 }