Changeset 1280:f2255b96c19c in lemon0.x
 Timestamp:
 03/31/05 11:33:52 (18 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1712
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

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