src/work/alpar/boolmap_iter.cc
changeset 706 0fe42b8ec5a6
child 921 818510fa3d99
equal deleted inserted replaced
-1:000000000000 0:ecfb2ffe4ebe
       
     1 #include <iostream>
       
     2 #include <vector>
       
     3 #include <smart_graph.h>
       
     4 
       
     5 using namespace hugo;
       
     6 
       
     7 ///\todo This is only a static map!
       
     8 ///
       
     9 template<class GG>
       
    10 class BoolIterEdgeMap
       
    11 {
       
    12 public:
       
    13   typedef GG Graph;
       
    14   typedef typename GG::Edge Edge;
       
    15   
       
    16   typedef Edge KeyType;
       
    17   typedef bool ValueType;
       
    18   
       
    19   friend class RefType;
       
    20   friend class FalseIterator;
       
    21   friend class TrueIterator;
       
    22 
       
    23 private:
       
    24   Graph &G;
       
    25   typename Graph::EdgeMap<int> cref;
       
    26   std::vector<Edge> vals;
       
    27   int sep;           //map[e] is true <=> cref[e]>=sep
       
    28   
       
    29   bool isTrue(Edge e) {return cref[e]>=sep;}
       
    30   void swap(Edge e, int s) 
       
    31   {
       
    32     int ti=cref[e];
       
    33     Edge te=vals[s];
       
    34     cref[e]=s; vals[s]=e;
       
    35     cref[te]=ti; vals[ti]=te;
       
    36   }  
       
    37 
       
    38   void setTrue(Edge e) { if(cref[e]<sep) { sep--; swap(e,sep); } }
       
    39   void setFalse(Edge e) { if(cref[e]>=sep) { swap(e,sep); sep++; } }
       
    40   
       
    41 public:
       
    42   class FalseIterator 
       
    43   {
       
    44     BoolIterEdgeMap &M;
       
    45     int i;
       
    46   public:
       
    47     FalseIterator(BoolIterEdgeMap &_M) : M(_M), i(0) { }
       
    48     FalseIterator &operator++() { ++i; return *this;}
       
    49     operator Edge() { return i<M.sep ? M.vals[i] : INVALID; }
       
    50     operator bool() { return i<M.sep; }
       
    51   };
       
    52   class TrueIterator 
       
    53   {
       
    54     BoolIterEdgeMap &M;
       
    55     int i;
       
    56   public:
       
    57     TrueIterator(BoolIterEdgeMap &_M) : M(_M), i(M.vals.size()-1) { }
       
    58     TrueIterator &operator++() { --i; return *this;}
       
    59     operator Edge() { return i>=M.sep ? M.vals[i] : INVALID; }
       
    60     operator bool() { return i>=M.sep; }
       
    61   };
       
    62   
       
    63   class RefType 
       
    64   {
       
    65     BoolIterEdgeMap &M;
       
    66     Edge e;
       
    67   public:
       
    68     RefType(BoolIterEdgeMap &_M,Edge _e) : M(_M), e(_e) { }
       
    69     
       
    70     operator ValueType() const 
       
    71     {
       
    72       return M.isTrue(e);
       
    73       
       
    74     }
       
    75     ValueType operator = (ValueType v) const
       
    76     {
       
    77       if(v) M.setTrue(e); 
       
    78       else M.setFalse(e);
       
    79       return v;
       
    80     }
       
    81   };
       
    82   
       
    83 public:
       
    84   BoolIterEdgeMap(Graph &_G) : G(_G), cref(G)
       
    85   {
       
    86     sep=0;
       
    87     for(typename Graph::EdgeIt e(G);G.valid(e);G.next(e)) {
       
    88       cref[e]=sep;
       
    89       vals.push_back(e);
       
    90       sep++;
       
    91     }
       
    92   }
       
    93   RefType operator[] (Edge e) { return RefType(*this,e);}  
       
    94 };
       
    95 
       
    96 int main()
       
    97 {
       
    98   typedef SmartGraph Graph;
       
    99   typedef Graph::NodeIt NodeIt;
       
   100   typedef Graph::OutEdgeIt OutEdgeIt;
       
   101   typedef Graph::EdgeIt EdgeIt;
       
   102   
       
   103   Graph G;
       
   104 
       
   105   for(int i=0;i<3;i++) G.addNode();
       
   106 
       
   107   for(NodeIt n(G);G.valid(n);G.next(n))
       
   108     for(NodeIt m(G);G.valid(m);G.next(m)) if(n!=m)
       
   109       G.addEdge(n,m);
       
   110 
       
   111   //for(OutEdgeIt e(G,NodeIt(G));G.valid(e);G.next(e))
       
   112     
       
   113   BoolIterEdgeMap<Graph> map(G);
       
   114 
       
   115   bool b=true;
       
   116   
       
   117   for(EdgeIt e(G);G.valid(e);G.next(e)) {map[e]=b;b=!b;}
       
   118   
       
   119   std::cout << true << '\n';
       
   120 
       
   121   for(EdgeIt e(G);G.valid(e);G.next(e))
       
   122     std::cout << G.id(G.tail(e)) << "->" << G.id(G.head(e))
       
   123       << ": " << map[e] << '\n';
       
   124   std::cout << "True Edges:\n";
       
   125   for(BoolIterEdgeMap<Graph>::TrueIterator i(map);i;++i)
       
   126     std::cout << G.id(G.tail(i)) << "->" << G.id(G.head(i)) << '\n';
       
   127   std::cout << "False Edges:\n";
       
   128   for(BoolIterEdgeMap<Graph>::FalseIterator i(map);i;++i)
       
   129     std::cout << G.id(G.tail(i)) << "->" << G.id(G.head(i)) << '\n';
       
   130 }
       
   131