Heap concept moved to namespace concept.
3 #include <lemon/smart_graph.h>
8 ///\todo This is only a static map!
9 ///\param BaseMap is an interger map.
10 template<class BaseMap>
15 typedef typename BaseMap::Key Key;
24 std::vector<Key> vals;
25 int sep; //map[e] is true <=> cref[e]>=sep
27 bool isTrue(Key k) {return cref[k]>=sep;}
28 void swap(Key k, int s)
33 cref[tk]=ti; vals[ti]=tk;
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++; } }
41 void set(Key k,Value v) { if(v) setTrue(k); else setFalse(k);}
49 explicit FalseIt(const BoolIterMap &_M) : M(_M), i(0) { }
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; }
63 explicit TrueIt(BoolIterMap &_M) : M(_M), i(M.vals.size()-1) { }
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; }
78 RefType(BoolIterMap &_M,Key _k) : M(_M), k(_k) { }
80 operator Value() const
84 Value operator = (Value v) const { M.set(k,v); return v; }
88 explicit BoolIterMap(BaseMap &_m) : cref(_m)
91 for(typename BaseMap::MapSet::iterator i=cref.mapSet().begin();
92 i!=cref.mapSet().end();
95 vals.push_back(i->first);
99 RefType operator[] (Key k) { return RefType(*this,k);}
100 Value operator[] (Key k) const { return isTrue(k);}
105 typedef SmartGraph Graph;
106 typedef Graph::NodeIt NodeIt;
107 typedef Graph::OutEdgeIt OutEdgeIt;
108 typedef Graph::EdgeIt EdgeIt;
112 for(int i=0;i<3;i++) G.addNode();
114 for(NodeIt n(G);n!=INVALID;++n)
115 for(NodeIt m(G);m!=INVALID;++m) if(n!=m)
118 //for(OutEdgeIt e(G,NodeIt(G));G.valid(e);G.next(e))
120 Graph::EdgeMap<int> tem(G);
121 typedef BoolIterMap<Graph::EdgeMap<int> > BoolIterEdgeMap;
122 BoolIterEdgeMap map(tem);
126 for(EdgeIt e(G);e!=INVALID;++e) {map[e]=b;b=!b;}
128 std::cout << true << '\n';
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';