source: lemon-0.x/src/work/alpar/boolmap_iter.cc @ 378:c3f93631cd24

#include <iostream>
#include <vector>
#include <smart_graph.h>

using namespace hugo;

///\todo This is only a static map!
///
template<class GG>
class BoolIterEdgeMap
{
public:
  typedef GG Graph;
  typedef typename GG::Edge Edge;
  
  typedef Edge KeyType;
  typedef bool ValueType;
  
  friend class RefType;
  friend class FalseIterator;
  friend class TrueIterator;

private:
  Graph &G;
  typename Graph::EdgeMap<int> cref;
  std::vector<Edge> vals;
  int sep;           //map[e] is true <=> cref[e]>=sep
  
  bool isTrue(Edge e) {return cref[e]>=sep;}
  void swap(Edge e, int s) 
  {
    int ti=cref[e];
    Edge te=vals[s];
    cref[e]=s; vals[s]=e;
    cref[te]=ti; vals[ti]=te;
  }  

  void setTrue(Edge e) { if(cref[e]<sep) { sep--; swap(e,sep); } }
  void setFalse(Edge e) { if(cref[e]>=sep) { swap(e,sep); sep++; } }
  
public:
  class FalseIterator 
  {
    BoolIterEdgeMap &M;
    int i;
  public:
    FalseIterator(BoolIterEdgeMap &_M) : M(_M), i(0) { }
    FalseIterator &operator++() { ++i; return *this;}
    operator Edge() { return i<M.sep ? M.vals[i] : INVALID; }
    operator bool() { return i<M.sep; }
  };
  class TrueIterator 
  {
    BoolIterEdgeMap &M;
    int i;
  public:
    TrueIterator(BoolIterEdgeMap &_M) : M(_M), i(M.vals.size()-1) { }
    TrueIterator &operator++() { --i; return *this;}
    operator Edge() { return i>=M.sep ? M.vals[i] : INVALID; }
    operator bool() { return i>=M.sep; }
  };
  
  class RefType 
  {
    BoolIterEdgeMap &M;
    Edge e;
  public:
    RefType(BoolIterEdgeMap &_M,Edge _e) : M(_M), e(_e) { }
    
    operator ValueType() const 
    {
      return M.isTrue(e);
      
    }
    ValueType operator = (ValueType v) const
    {
      if(v) M.setTrue(e); 
      else M.setFalse(e);
      return v;
    }
  };
  
public:
  BoolIterEdgeMap(Graph &_G) : G(_G), cref(G)
  {
    sep=0;
    for(typename Graph::EdgeIt e(G);G.valid(e);G.next(e)) {
      cref[e]=sep;
      vals.push_back(e);
      sep++;
    }
  }
  RefType operator[] (Edge e) { return RefType(*this,e);}  
};

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);G.valid(n);G.next(n))
    for(NodeIt m(G);G.valid(m);G.next(m)) if(n!=m)
      G.addEdge(n,m);

  //for(OutEdgeIt e(G,NodeIt(G));G.valid(e);G.next(e))
    
  BoolIterEdgeMap<Graph> map(G);

  bool b=true;
  
  for(EdgeIt e(G);G.valid(e);G.next(e)) {map[e]=b;b=!b;}
  
  std::cout << true << '\n';

  for(EdgeIt e(G);G.valid(e);G.next(e))
    std::cout << G.id(G.tail(e)) << "->" << G.id(G.head(e))
      << ": " << map[e] << '\n';
  std::cout << "True Edges:\n";
  for(BoolIterEdgeMap<Graph>::TrueIterator i(map);i;++i)
    std::cout << G.id(G.tail(i)) << "->" << G.id(G.head(i)) << '\n';
  std::cout << "False Edges:\n";
  for(BoolIterEdgeMap<Graph>::FalseIterator i(map);i;++i)
    std::cout << G.id(G.tail(i)) << "->" << G.id(G.head(i)) << '\n';
}