/* -*- C++ -*-

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

  *

  * Copyright (C) 2005 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 <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!

   ///\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);}

     ///\e

     class FalseIt

     {

       const IterableBoolMap &M;

       int i;

     public:

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

       FalseIt(Invalid)

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

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

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

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

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

     };

     ///\e

     class TrueIt

     {

       const IterableBoolMap &M;

       int i;

     public:

       explicit TrueIt(const IterableBoolMap &_M)

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

       TrueIt(Invalid)

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

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

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

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

       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::MapSet::iterator i=cref.mapSet().begin();

 	  i!=cref.mapSet().end();

 	  ++i) {

 	i->second=sep;

 	vals.push_back(i->first);

 	sep++;

       }

       if(init) sep=0;

     }

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

     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);}

 #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:

       explicit FalseIt(const IterableBoolNodeMap &m)

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

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

     };

     ///Iterator for the "true" nodes

     class TrueIt : public BimType::TrueIt

     {

     public:

       explicit TrueIt(const IterableBoolNodeMap &m)

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

       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);}

 #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:

       explicit FalseIt(const IterableBoolEdgeMap &m)

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

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

     };

     ///Iterator for the "true" edges

     class TrueIt : public BimType::TrueIt

     {

     public:

       explicit TrueIt(const IterableBoolEdgeMap &m)

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

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

     };  

   };

   /// @}

 }