/* -*- 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) { }

    };  

  };

  /// @}

}