COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/boolmap_iter.cc @ 1314:9269c76551cf

Last change on this file since 1314:9269c76551cf was 1280:f2255b96c19c, checked in by Alpar Juttner, 15 years ago

It works again

File size: 3.3 KB
Line 
1#include <iostream>
2#include <vector>
3#include <lemon/smart_graph.h>
4#include <limits>
5
6using namespace lemon;
7
8///\todo This is only a static map!
9///\param BaseMap is an interger map.
10template<class BaseMap>
11class BoolIterMap
12{
13public:
14 
15  typedef typename BaseMap::Key Key;
16  typedef bool Value;
17 
18  friend class RefType;
19  friend class FalseIt;
20  friend class TrueIt;
21
22private:
23  BaseMap &cref;
24  std::vector<Key> vals;
25  int sep;           //map[e] is true <=> cref[e]>=sep
26 
27  bool isTrue(Key k) {return cref[k]>=sep;}
28  void swap(Key k, int s)
29  {
30    int ti=cref[k];
31    Key tk=vals[s];
32    cref[k]=s; vals[s]=k;
33    cref[tk]=ti; vals[ti]=tk;
34  } 
35
36  void setTrue(Key k) { if(cref[k]<sep) { sep--; swap(k,sep); } }
37  void setFalse(Key k) { if(cref[k]>=sep) { swap(k,sep); sep++; } }
38 
39public:
40  ///\e
41  void set(Key k,Value v) { if(v) setTrue(k); else setFalse(k);}
42
43  ///\e
44  class FalseIt
45  {
46    const BoolIterMap &M;
47    int i;
48  public:
49    explicit FalseIt(const BoolIterMap &_M) : M(_M), i(0) { }
50    FalseIt(Invalid)
51      : M(*((BoolIterMap*)(0))), i(std::numeric_limits<int>::max()) { }
52    FalseIt &operator++() { ++i; return *this;}
53    operator Key() { return i<M.sep ? M.vals[i] : INVALID; }
54    bool operator !=(Invalid) { return i<M.sep; }
55    bool operator ==(Invalid) { return i>=M.sep; }
56  };
57  ///\e
58  class TrueIt
59  {
60    BoolIterMap &M;
61    int i;
62  public:
63    explicit TrueIt(BoolIterMap &_M) : M(_M), i(M.vals.size()-1) { }
64    TrueIt(Invalid)
65      : M(*((BoolIterMap*)(0))), i(-1) { }
66    TrueIt &operator++() { --i; return *this;}
67    operator Key() { return i>=M.sep ? M.vals[i] : INVALID; }
68    bool operator !=(Invalid) { return i>=M.sep; }
69    bool operator ==(Invalid) { return i<M.sep; }
70  };
71 
72  ///\e
73  class RefType
74  {
75    BoolIterMap &M;
76    Key k;
77  public:
78    RefType(BoolIterMap &_M,Key _k) : M(_M), k(_k) { }
79   
80    operator Value() const
81    {
82      return M.isTrue(k);
83    }
84    Value operator = (Value v) const { M.set(k,v); return v; }
85  };
86 
87public:
88  explicit BoolIterMap(BaseMap &_m) : cref(_m)
89  {
90    sep=0;
91    for(typename BaseMap::MapSet::iterator i=cref.mapSet().begin();
92        i!=cref.mapSet().end();
93        ++i) {
94      i->second=sep;
95      vals.push_back(i->first);
96      sep++;
97    }
98  }
99  RefType operator[] (Key k) { return RefType(*this,k);} 
100  Value operator[] (Key k) const { return isTrue(k);} 
101};
102
103int main()
104{
105  typedef SmartGraph Graph;
106  typedef Graph::NodeIt NodeIt;
107  typedef Graph::OutEdgeIt OutEdgeIt;
108  typedef Graph::EdgeIt EdgeIt;
109 
110  Graph G;
111
112  for(int i=0;i<3;i++) G.addNode();
113
114  for(NodeIt n(G);n!=INVALID;++n)
115    for(NodeIt m(G);m!=INVALID;++m) if(n!=m)
116      G.addEdge(n,m);
117
118  //for(OutEdgeIt e(G,NodeIt(G));G.valid(e);G.next(e))
119   
120  Graph::EdgeMap<int> tem(G);
121  typedef BoolIterMap<Graph::EdgeMap<int> > BoolIterEdgeMap;
122  BoolIterEdgeMap map(tem);
123
124  bool b=true;
125 
126  for(EdgeIt e(G);e!=INVALID;++e) {map[e]=b;b=!b;}
127 
128  std::cout << true << '\n';
129
130  for(EdgeIt e(G);e!=INVALID;++e)
131    std::cout << G.id(G.source(e)) << "->" << G.id(G.target(e))
132      << ": " << map[e] << '\n';
133  std::cout << "True Edges:\n";
134  for(BoolIterEdgeMap::TrueIt i(map);i!=INVALID;++i)
135    std::cout << G.id(G.source(i)) << "->" << G.id(G.target(i)) << '\n';
136  std::cout << "False Edges:\n";
137  for(BoolIterEdgeMap::FalseIt i(map);i!=INVALID;++i)
138    std::cout << G.id(G.source(i)) << "->" << G.id(G.target(i)) << '\n';
139}
140
Note: See TracBrowser for help on using the repository browser.