1.1 --- a/src/work/alpar/boolmap_iter.cc Thu Mar 31 08:34:55 2005 +0000
1.2 +++ b/src/work/alpar/boolmap_iter.cc Thu Mar 31 09:33:52 2005 +0000
1.3 @@ -1,96 +1,103 @@
1.4 #include <iostream>
1.5 #include <vector>
1.6 -#include <smart_graph.h>
1.7 +#include <lemon/smart_graph.h>
1.8 +#include <limits>
1.9
1.10 using namespace lemon;
1.11
1.12 ///\todo This is only a static map!
1.13 -///
1.14 -template<class GG>
1.15 -class BoolIterEdgeMap
1.16 +///\param BaseMap is an interger map.
1.17 +template<class BaseMap>
1.18 +class BoolIterMap
1.19 {
1.20 public:
1.21 - typedef GG Graph;
1.22 - typedef typename GG::Edge Edge;
1.23
1.24 - typedef Edge Key;
1.25 + typedef typename BaseMap::Key Key;
1.26 typedef bool Value;
1.27
1.28 friend class RefType;
1.29 - friend class FalseIterator;
1.30 - friend class TrueIterator;
1.31 + friend class FalseIt;
1.32 + friend class TrueIt;
1.33
1.34 private:
1.35 - Graph &G;
1.36 - typename Graph::EdgeMap<int> cref;
1.37 - std::vector<Edge> vals;
1.38 + BaseMap &cref;
1.39 + std::vector<Key> vals;
1.40 int sep; //map[e] is true <=> cref[e]>=sep
1.41
1.42 - bool isTrue(Edge e) {return cref[e]>=sep;}
1.43 - void swap(Edge e, int s)
1.44 + bool isTrue(Key k) {return cref[k]>=sep;}
1.45 + void swap(Key k, int s)
1.46 {
1.47 - int ti=cref[e];
1.48 - Edge te=vals[s];
1.49 - cref[e]=s; vals[s]=e;
1.50 - cref[te]=ti; vals[ti]=te;
1.51 + int ti=cref[k];
1.52 + Key tk=vals[s];
1.53 + cref[k]=s; vals[s]=k;
1.54 + cref[tk]=ti; vals[ti]=tk;
1.55 }
1.56
1.57 - void setTrue(Edge e) { if(cref[e]<sep) { sep--; swap(e,sep); } }
1.58 - void setFalse(Edge e) { if(cref[e]>=sep) { swap(e,sep); sep++; } }
1.59 + void setTrue(Key k) { if(cref[k]<sep) { sep--; swap(k,sep); } }
1.60 + void setFalse(Key k) { if(cref[k]>=sep) { swap(k,sep); sep++; } }
1.61
1.62 public:
1.63 - class FalseIterator
1.64 + ///\e
1.65 + void set(Key k,Value v) { if(v) setTrue(k); else setFalse(k);}
1.66 +
1.67 + ///\e
1.68 + class FalseIt
1.69 {
1.70 - BoolIterEdgeMap &M;
1.71 + const BoolIterMap &M;
1.72 int i;
1.73 public:
1.74 - FalseIterator(BoolIterEdgeMap &_M) : M(_M), i(0) { }
1.75 - FalseIterator &operator++() { ++i; return *this;}
1.76 - operator Edge() { return i<M.sep ? M.vals[i] : INVALID; }
1.77 - operator bool() { return i<M.sep; }
1.78 + explicit FalseIt(const BoolIterMap &_M) : M(_M), i(0) { }
1.79 + FalseIt(Invalid)
1.80 + : M(*((BoolIterMap*)(0))), i(std::numeric_limits<int>::max()) { }
1.81 + FalseIt &operator++() { ++i; return *this;}
1.82 + operator Key() { return i<M.sep ? M.vals[i] : INVALID; }
1.83 + bool operator !=(Invalid) { return i<M.sep; }
1.84 + bool operator ==(Invalid) { return i>=M.sep; }
1.85 };
1.86 - class TrueIterator
1.87 + ///\e
1.88 + class TrueIt
1.89 {
1.90 - BoolIterEdgeMap &M;
1.91 + BoolIterMap &M;
1.92 int i;
1.93 public:
1.94 - TrueIterator(BoolIterEdgeMap &_M) : M(_M), i(M.vals.size()-1) { }
1.95 - TrueIterator &operator++() { --i; return *this;}
1.96 - operator Edge() { return i>=M.sep ? M.vals[i] : INVALID; }
1.97 - operator bool() { return i>=M.sep; }
1.98 + explicit TrueIt(BoolIterMap &_M) : M(_M), i(M.vals.size()-1) { }
1.99 + TrueIt(Invalid)
1.100 + : M(*((BoolIterMap*)(0))), i(-1) { }
1.101 + TrueIt &operator++() { --i; return *this;}
1.102 + operator Key() { return i>=M.sep ? M.vals[i] : INVALID; }
1.103 + bool operator !=(Invalid) { return i>=M.sep; }
1.104 + bool operator ==(Invalid) { return i<M.sep; }
1.105 };
1.106
1.107 - class RefType
1.108 + ///\e
1.109 + class RefType
1.110 {
1.111 - BoolIterEdgeMap &M;
1.112 - Edge e;
1.113 + BoolIterMap &M;
1.114 + Key k;
1.115 public:
1.116 - RefType(BoolIterEdgeMap &_M,Edge _e) : M(_M), e(_e) { }
1.117 + RefType(BoolIterMap &_M,Key _k) : M(_M), k(_k) { }
1.118
1.119 operator Value() const
1.120 {
1.121 - return M.isTrue(e);
1.122 -
1.123 + return M.isTrue(k);
1.124 }
1.125 - Value operator = (Value v) const
1.126 - {
1.127 - if(v) M.setTrue(e);
1.128 - else M.setFalse(e);
1.129 - return v;
1.130 - }
1.131 + Value operator = (Value v) const { M.set(k,v); return v; }
1.132 };
1.133
1.134 public:
1.135 - BoolIterEdgeMap(Graph &_G) : G(_G), cref(G)
1.136 + explicit BoolIterMap(BaseMap &_m) : cref(_m)
1.137 {
1.138 sep=0;
1.139 - for(typename Graph::EdgeIt e(G);G.valid(e);G.next(e)) {
1.140 - cref[e]=sep;
1.141 - vals.push_back(e);
1.142 + for(typename BaseMap::MapSet::iterator i=cref.mapSet().begin();
1.143 + i!=cref.mapSet().end();
1.144 + ++i) {
1.145 + i->second=sep;
1.146 + vals.push_back(i->first);
1.147 sep++;
1.148 }
1.149 }
1.150 - RefType operator[] (Edge e) { return RefType(*this,e);}
1.151 + RefType operator[] (Key k) { return RefType(*this,k);}
1.152 + Value operator[] (Key k) const { return isTrue(k);}
1.153 };
1.154
1.155 int main()
1.156 @@ -104,28 +111,30 @@
1.157
1.158 for(int i=0;i<3;i++) G.addNode();
1.159
1.160 - for(NodeIt n(G);G.valid(n);G.next(n))
1.161 - for(NodeIt m(G);G.valid(m);G.next(m)) if(n!=m)
1.162 + for(NodeIt n(G);n!=INVALID;++n)
1.163 + for(NodeIt m(G);m!=INVALID;++m) if(n!=m)
1.164 G.addEdge(n,m);
1.165
1.166 //for(OutEdgeIt e(G,NodeIt(G));G.valid(e);G.next(e))
1.167
1.168 - BoolIterEdgeMap<Graph> map(G);
1.169 + Graph::EdgeMap<int> tem(G);
1.170 + typedef BoolIterMap<Graph::EdgeMap<int> > BoolIterEdgeMap;
1.171 + BoolIterEdgeMap map(tem);
1.172
1.173 bool b=true;
1.174
1.175 - for(EdgeIt e(G);G.valid(e);G.next(e)) {map[e]=b;b=!b;}
1.176 + for(EdgeIt e(G);e!=INVALID;++e) {map[e]=b;b=!b;}
1.177
1.178 std::cout << true << '\n';
1.179
1.180 - for(EdgeIt e(G);G.valid(e);G.next(e))
1.181 + for(EdgeIt e(G);e!=INVALID;++e)
1.182 std::cout << G.id(G.source(e)) << "->" << G.id(G.target(e))
1.183 << ": " << map[e] << '\n';
1.184 std::cout << "True Edges:\n";
1.185 - for(BoolIterEdgeMap<Graph>::TrueIterator i(map);i;++i)
1.186 + for(BoolIterEdgeMap::TrueIt i(map);i!=INVALID;++i)
1.187 std::cout << G.id(G.source(i)) << "->" << G.id(G.target(i)) << '\n';
1.188 std::cout << "False Edges:\n";
1.189 - for(BoolIterEdgeMap<Graph>::FalseIterator i(map);i;++i)
1.190 + for(BoolIterEdgeMap::FalseIt i(map);i!=INVALID;++i)
1.191 std::cout << G.id(G.source(i)) << "->" << G.id(G.target(i)) << '\n';
1.192 }
1.193