#include <iostream>

#include <vector>

#include <lemon/smart_graph.h>

#include <limits>

using namespace lemon;

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

///\param BaseMap is an interger map.

template<class BaseMap>

class BoolIterMap

{

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 BoolIterMap &M;

    int i;

  public:

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

    FalseIt(Invalid)

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

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

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

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

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

  };

  ///\e

  class TrueIt

  {

    BoolIterMap &M;

    int i;

  public:

    explicit TrueIt(BoolIterMap &_M) : M(_M), i(M.vals.size()-1) { }

    TrueIt(Invalid)

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

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

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

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

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

  };

  ///\e

  class RefType

  {

    BoolIterMap &M;

    Key k;

  public:

    RefType(BoolIterMap &_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 BoolIterMap(BaseMap &_m) : 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++;

    }

  }

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

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

};

int main()

{

  typedef SmartGraph Graph;

  typedef Graph::NodeIt NodeIt;

  typedef Graph::OutEdgeIt OutEdgeIt;

  typedef Graph::EdgeIt EdgeIt;

  Graph G;

  for(int i=0;i<3;i++) G.addNode();

  for(NodeIt n(G);n!=INVALID;++n)

    for(NodeIt m(G);m!=INVALID;++m) if(n!=m)

      G.addEdge(n,m);

  //for(OutEdgeIt e(G,NodeIt(G));G.valid(e);G.next(e))

  Graph::EdgeMap<int> tem(G);

  typedef BoolIterMap<Graph::EdgeMap<int> > BoolIterEdgeMap;

  BoolIterEdgeMap map(tem);

  bool b=true;

  for(EdgeIt e(G);e!=INVALID;++e) {map[e]=b;b=!b;}

  std::cout << true << '\n';

  for(EdgeIt e(G);e!=INVALID;++e) 

    std::cout << G.id(G.source(e)) << "->" << G.id(G.target(e))

      << ": " << map[e] << '\n';

  std::cout << "True Edges:\n";

  for(BoolIterEdgeMap::TrueIt i(map);i!=INVALID;++i)

    std::cout << G.id(G.source(i)) << "->" << G.id(G.target(i)) << '\n';

  std::cout << "False Edges:\n";

  for(BoolIterEdgeMap::FalseIt i(map);i!=INVALID;++i)

    std::cout << G.id(G.source(i)) << "->" << G.id(G.target(i)) << '\n';

}