alpar@348: #include <iostream>
alpar@348: #include <vector>
alpar@1280: #include <lemon/smart_graph.h>
alpar@1280: #include <limits>
alpar@348: 
alpar@921: using namespace lemon;
alpar@348: 
alpar@348: ///\todo This is only a static map!
alpar@1280: ///\param BaseMap is an interger map.
alpar@1280: template<class BaseMap>
alpar@1280: class BoolIterMap
alpar@348: {
alpar@348: public:
alpar@348:   
alpar@1280:   typedef typename BaseMap::Key Key;
alpar@987:   typedef bool Value;
alpar@348:   
alpar@348:   friend class RefType;
alpar@1280:   friend class FalseIt;
alpar@1280:   friend class TrueIt;
alpar@348: 
alpar@348: private:
alpar@1280:   BaseMap &cref;
alpar@1280:   std::vector<Key> vals;
alpar@348:   int sep;           //map[e] is true <=> cref[e]>=sep
alpar@348:   
alpar@1280:   bool isTrue(Key k) {return cref[k]>=sep;}
alpar@1280:   void swap(Key k, int s) 
alpar@348:   {
alpar@1280:     int ti=cref[k];
alpar@1280:     Key tk=vals[s];
alpar@1280:     cref[k]=s; vals[s]=k;
alpar@1280:     cref[tk]=ti; vals[ti]=tk;
alpar@348:   }  
alpar@348: 
alpar@1280:   void setTrue(Key k) { if(cref[k]<sep) { sep--; swap(k,sep); } }
alpar@1280:   void setFalse(Key k) { if(cref[k]>=sep) { swap(k,sep); sep++; } }
alpar@348:   
alpar@348: public:
alpar@1280:   ///\e
alpar@1280:   void set(Key k,Value v) { if(v) setTrue(k); else setFalse(k);}
alpar@1280: 
alpar@1280:   ///\e
alpar@1280:   class FalseIt
alpar@348:   {
alpar@1280:     const BoolIterMap &M;
alpar@348:     int i;
alpar@348:   public:
alpar@1280:     explicit FalseIt(const BoolIterMap &_M) : M(_M), i(0) { }
alpar@1280:     FalseIt(Invalid)
alpar@1280:       : M(*((BoolIterMap*)(0))), i(std::numeric_limits<int>::max()) { }
alpar@1280:     FalseIt &operator++() { ++i; return *this;}
alpar@1280:     operator Key() { return i<M.sep ? M.vals[i] : INVALID; }
alpar@1280:     bool operator !=(Invalid) { return i<M.sep; }
alpar@1280:     bool operator ==(Invalid) { return i>=M.sep; }
alpar@348:   };
alpar@1280:   ///\e
alpar@1280:   class TrueIt
alpar@348:   {
alpar@1280:     BoolIterMap &M;
alpar@348:     int i;
alpar@348:   public:
alpar@1280:     explicit TrueIt(BoolIterMap &_M) : M(_M), i(M.vals.size()-1) { }
alpar@1280:     TrueIt(Invalid)
alpar@1280:       : M(*((BoolIterMap*)(0))), i(-1) { }
alpar@1280:     TrueIt &operator++() { --i; return *this;}
alpar@1280:     operator Key() { return i>=M.sep ? M.vals[i] : INVALID; }
alpar@1280:     bool operator !=(Invalid) { return i>=M.sep; }
alpar@1280:     bool operator ==(Invalid) { return i<M.sep; }
alpar@348:   };
alpar@348:   
alpar@1280:   ///\e
alpar@1280:   class RefType
alpar@348:   {
alpar@1280:     BoolIterMap &M;
alpar@1280:     Key k;
alpar@348:   public:
alpar@1280:     RefType(BoolIterMap &_M,Key _k) : M(_M), k(_k) { }
alpar@348:     
alpar@987:     operator Value() const 
alpar@348:     {
alpar@1280:       return M.isTrue(k);
alpar@348:     }
alpar@1280:     Value operator = (Value v) const { M.set(k,v); return v; }
alpar@348:   };
alpar@348:   
alpar@348: public:
alpar@1280:   explicit BoolIterMap(BaseMap &_m) : cref(_m)
alpar@348:   {
alpar@348:     sep=0;
alpar@1280:     for(typename BaseMap::MapSet::iterator i=cref.mapSet().begin();
alpar@1280: 	i!=cref.mapSet().end();
alpar@1280: 	++i) {
alpar@1280:       i->second=sep;
alpar@1280:       vals.push_back(i->first);
alpar@348:       sep++;
alpar@348:     }
alpar@348:   }
alpar@1280:   RefType operator[] (Key k) { return RefType(*this,k);}  
alpar@1280:   Value operator[] (Key k) const { return isTrue(k);}  
alpar@348: };
alpar@348: 
alpar@348: int main()
alpar@348: {
alpar@348:   typedef SmartGraph Graph;
alpar@348:   typedef Graph::NodeIt NodeIt;
alpar@348:   typedef Graph::OutEdgeIt OutEdgeIt;
alpar@348:   typedef Graph::EdgeIt EdgeIt;
alpar@348:   
alpar@348:   Graph G;
alpar@348: 
alpar@348:   for(int i=0;i<3;i++) G.addNode();
alpar@348: 
alpar@1280:   for(NodeIt n(G);n!=INVALID;++n)
alpar@1280:     for(NodeIt m(G);m!=INVALID;++m) if(n!=m)
alpar@348:       G.addEdge(n,m);
alpar@348: 
alpar@348:   //for(OutEdgeIt e(G,NodeIt(G));G.valid(e);G.next(e))
alpar@348:     
alpar@1280:   Graph::EdgeMap<int> tem(G);
alpar@1280:   typedef BoolIterMap<Graph::EdgeMap<int> > BoolIterEdgeMap;
alpar@1280:   BoolIterEdgeMap map(tem);
alpar@348: 
alpar@348:   bool b=true;
alpar@348:   
alpar@1280:   for(EdgeIt e(G);e!=INVALID;++e) {map[e]=b;b=!b;}
alpar@348:   
alpar@348:   std::cout << true << '\n';
alpar@348: 
alpar@1280:   for(EdgeIt e(G);e!=INVALID;++e) 
alpar@986:     std::cout << G.id(G.source(e)) << "->" << G.id(G.target(e))
alpar@348:       << ": " << map[e] << '\n';
alpar@348:   std::cout << "True Edges:\n";
alpar@1280:   for(BoolIterEdgeMap::TrueIt i(map);i!=INVALID;++i)
alpar@986:     std::cout << G.id(G.source(i)) << "->" << G.id(G.target(i)) << '\n';
alpar@348:   std::cout << "False Edges:\n";
alpar@1280:   for(BoolIterEdgeMap::FalseIt i(map);i!=INVALID;++i)
alpar@986:     std::cout << G.id(G.source(i)) << "->" << G.id(G.target(i)) << '\n';
alpar@348: }
alpar@348: