1 #include <iostream> |
|
2 #include <vector> |
|
3 #include <lemon/smart_graph.h> |
|
4 #include <limits> |
|
5 |
|
6 using namespace lemon; |
|
7 |
|
8 ///\todo This is only a static map! |
|
9 ///\param BaseMap is an interger map. |
|
10 template<class BaseMap> |
|
11 class BoolIterMap |
|
12 { |
|
13 public: |
|
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 |
|
22 private: |
|
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 |
|
39 public: |
|
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 |
|
87 public: |
|
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 |
|
103 int 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 |
|