Iterable Bool maps can count the number of true and false values.
2 * lemon/iterable_maps.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #include <lemon/traits.h>
18 #include <lemon/invalid.h>
24 ///\brief Maps that makes it possible to iterate through the keys having
32 ///\todo This is only a static map!
33 ///\todo Undocumented.
34 ///\param BaseMap is an interger map.
35 template<class BaseMap>
40 typedef typename BaseMap::Key Key;
49 std::vector<Key> vals;
50 int sep; //map[e] is true <=> cref[e]>=sep
52 bool isTrue(Key k) {return cref[k]>=sep;}
53 void swap(Key k, int s)
58 cref[tk]=ti; vals[ti]=tk;
61 void setTrue(Key k) { if(cref[k]<sep) { sep--; swap(k,sep); } }
62 void setFalse(Key k) { if(cref[k]>=sep) { swap(k,sep); sep++; } }
66 void set(Key k,Value v) { if(v) setTrue(k); else setFalse(k);}
67 ///Number of \c true items in the map
69 ///Returns the number of \c true values in the map.
70 ///This is a constant time operation.
71 int countTrue() { return vals.size()-sep; }
72 ///Number of \c false items in the map
74 ///Returns the number of \c false values in the map.
75 ///This is a constant time operation.
76 int countFalse() { return sep; }
81 const IterableBoolMap &M;
85 explicit FalseIt(const IterableBoolMap &_M) : M(_M), i(0) { }
88 : M(*((IterableBoolMap*)(0))), i(std::numeric_limits<int>::max()) { }
90 FalseIt &operator++() { ++i; return *this;}
92 operator Key() const { return i<M.sep ? M.vals[i] : INVALID; }
94 bool operator !=(Invalid) const { return i<M.sep; }
96 bool operator ==(Invalid) const { return i>=M.sep; }
101 const IterableBoolMap &M;
105 explicit TrueIt(const IterableBoolMap &_M)
106 : M(_M), i(M.vals.size()-1) { }
109 : M(*((IterableBoolMap*)(0))), i(-1) { }
111 TrueIt &operator++() { --i; return *this;}
113 operator Key() const { return i>=M.sep ? M.vals[i] : INVALID; }
115 bool operator !=(Invalid) const { return i>=M.sep; }
117 bool operator ==(Invalid) const { return i<M.sep; }
126 RefType(IterableBoolMap &_M,Key _k) : M(_M), k(_k) { }
128 operator Value() const
132 Value operator = (Value v) const { M.set(k,v); return v; }
136 explicit IterableBoolMap(BaseMap &_m,bool init=false) : cref(_m)
139 for(typename BaseMap::MapSet::iterator i=cref.mapSet().begin();
140 i!=cref.mapSet().end();
143 vals.push_back(i->first);
149 RefType operator[] (Key k) { return RefType(*this,k);}
151 Value operator[] (Key k) const { return isTrue(k);}
157 /// \addtogroup graph_maps
160 /// Iterable bool NodeMap
162 /// This map can be used in the same way
163 /// as the standard NodeMap<bool> of the
164 /// given graph \c Graph.
165 /// In addition, this class provides two iterators called \ref TrueIt
166 /// and \ref FalseIt to iterate through the "true" and "false" nodes.
167 template <class Graph>
168 class IterableBoolNodeMap
170 typename Graph::template NodeMap<int> cmap;
174 typedef IterableBoolMap<typename Graph::template NodeMap<int> > BimType;
178 typedef typename BimType::RefType RefType;
179 typedef typename Graph::Node Key;
182 friend class FalseIt;
186 IterableBoolNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
190 void set(Key k, bool v) { imap.set(k,v);}
191 ///Number of \c true items in the map
193 ///Returns the number of \c true values in the map.
194 ///This is a constant time operation.
195 int countTrue() { return imap.countTrue(); }
196 ///Number of \c false items in the map
198 ///Returns the number of \c false values in the map.
199 ///This is a constant time operation.
200 int countFalse() { return imap.countFalse(); }
203 bool &operator[](Key k) { return imap[k];}
205 const bool &operator[](Key k) const { return imap[k];}
207 Value operator[](Key k) const { return imap[k];}
208 RefType operator[](Key k) { return imap[k];}
210 ///Iterator for the "false" nodes
211 class FalseIt : public BimType::FalseIt
215 explicit FalseIt(const IterableBoolNodeMap &m)
216 : BimType::FalseIt(m.imap) { }
218 FalseIt(Invalid i) : BimType::FalseIt(i) { }
220 ///Iterator for the "true" nodes
221 class TrueIt : public BimType::TrueIt
225 explicit TrueIt(const IterableBoolNodeMap &m)
226 : BimType::TrueIt(m.imap) { }
228 TrueIt(Invalid i) : BimType::TrueIt(i) { }
232 /// Iterable bool EdgeMap
234 /// This map can be used in the same way
235 /// as the standard EdgeMap<bool> of the
236 /// given graph \c Graph.
237 /// In addition, this class provides two iterators called \ref TrueIt
238 /// and \ref FalseIt to iterate through the "true" and "false" edges.
239 template <class Graph>
240 class IterableBoolEdgeMap
242 typename Graph::template EdgeMap<int> cmap;
246 typedef IterableBoolMap<typename Graph::template EdgeMap<int> > BimType;
250 typedef typename BimType::RefType RefType;
251 typedef typename Graph::Edge Key;
254 friend class FalseIt;
258 IterableBoolEdgeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
262 void set(Key k, bool v) { imap.set(k,v);}
263 ///Returns the number of \c true values in the map.
264 ///This is a constant time operation.
265 int countTrue() { return imap.countTrue(); }
266 ///Number of \c false items in the map
268 ///Returns the number of \c false values in the map.
269 ///This is a constant time operation.
270 int countFalse() { return imap.countFalse(); }
273 bool &operator[](Key k) { return imap[k];}
275 const bool &operator[](Key k) const { return imap[k];}
277 Value operator[](Key k) const { return imap[k];}
278 RefType operator[](Key k) { return imap[k];}
280 ///Iterator for the "false" edges
281 class FalseIt : public BimType::FalseIt
285 explicit FalseIt(const IterableBoolEdgeMap &m)
286 : BimType::FalseIt(m.imap) { }
288 FalseIt(Invalid i) : BimType::FalseIt(i) { }
290 ///Iterator for the "true" edges
291 class TrueIt : public BimType::TrueIt
295 explicit TrueIt(const IterableBoolEdgeMap &m)
296 : BimType::TrueIt(m.imap) { }
298 TrueIt(Invalid i) : BimType::TrueIt(i) { }
303 namespace _iterable_maps_bits {
304 template <typename Item>
305 struct IterableIntMapNode {
306 IterableIntMapNode() : value(-1) {}
314 /// \brief Dynamic iterable integer map.
316 /// \todo Document please
317 template <typename _Graph, typename _Item>
318 class IterableIntMap : protected ItemSetTraits<_Graph, _Item>
319 ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >::Parent {
321 typedef typename ItemSetTraits<_Graph, _Item>
322 ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >
327 typedef _Graph Graph;
329 explicit IterableIntMap(const Graph& graph) : Parent(graph) {}
333 void unlace(const Key& key) {
334 typename Parent::Value& node = Parent::operator[](key);
335 if (node.value < 0) return;
336 if (node.prev != INVALID) {
337 Parent::operator[](node.prev).next = node.next;
339 first[node.value] = node.next;
341 if (node.next != INVALID) {
342 Parent::operator[](node.next).prev = node.prev;
344 while (!first.empty() && first.back() == INVALID) {
349 void lace(const Key& key) {
350 typename Parent::Value& node = Parent::operator[](key);
351 if (node.value < 0) return;
352 if (node.value >= (int)first.size()) {
353 first.resize(node.value + 1, INVALID);
356 node.next = first[node.value];
357 if (node.next != INVALID) {
358 Parent::operator[](node.next).prev = key;
360 first[node.value] = key;
365 typedef True ReferenceMapTag;
368 friend class IterableIntMap;
370 Reference(IterableIntMap& map, const Key& key)
371 : _key(key), _map(map) {}
374 Reference& operator=(const Reference& value) {
375 _map.set(_key, (const int&)value);
379 operator const int&() const {
380 return static_cast<const IterableIntMap&>(_map)[_key];
383 Reference& operator=(int value) {
384 _map.set(_key, value);
387 Reference& operator++() {
388 _map.set(_key, _map[_key] + 1);
391 int operator++(int) {
392 int value = _map[_key];
393 _map.set(_key, value + 1);
396 Reference& operator--() {
397 _map.set(_key, _map[_key] - 1);
400 int operator--(int) {
401 int value = _map[_key];
402 _map.set(_key, value - 1);
405 Reference& operator+=(int value) {
406 _map.set(_key, _map[_key] + value);
409 Reference& operator-=(int value) {
410 _map.set(_key, _map[_key] - value);
413 Reference& operator*=(int value) {
414 _map.set(_key, _map[_key] * value);
417 Reference& operator/=(int value) {
418 _map.set(_key, _map[_key] / value);
421 Reference& operator%=(int value) {
422 _map.set(_key, _map[_key] % value);
425 Reference& operator&=(int value) {
426 _map.set(_key, _map[_key] & value);
429 Reference& operator|=(int value) {
430 _map.set(_key, _map[_key] | value);
433 Reference& operator^=(int value) {
434 _map.set(_key, _map[_key] ^ value);
437 Reference& operator<<=(int value) {
438 _map.set(_key, _map[_key] << value);
441 Reference& operator>>=(int value) {
442 _map.set(_key, _map[_key] >> value);
448 IterableIntMap& _map;
451 typedef const Value& ConstReference;
454 return (int)first.size();
457 void set(const Key& key, const Value& value) {
459 Parent::operator[](key).value = value;
463 const Value& operator[](const Key& key) const {
464 return Parent::operator[](key).value;
467 Reference operator[](const Key& key) {
468 return Reference(*this, key);
471 class ItemIt : public _Item {
473 typedef _Item Parent;
475 ItemIt(Invalid) : Parent(INVALID), _map(0) {}
477 ItemIt(const IterableIntMap& map, int value) : _map(&map) {
478 if (value < 0 || value >= (int)_map->first.size()) {
479 Parent::operator=(INVALID);
481 Parent::operator=(_map->first[value]);
485 ItemIt& operator++() {
486 Parent::operator=(_map->IterableIntMap::Parent::
487 operator[](static_cast<Parent&>(*this)).next);
493 const IterableIntMap* _map;
498 virtual void erase(const Key& key) {
503 virtual void clear() {
509 std::vector<_Item> first;