source: lemon-0.x/src/work/alpar/boolmap_iter.cc @ 1360:4338e4280f67

#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';
}