Documenatation of MapWin.
2 * lemon/iterable_maps.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2006 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::MapIt i(cref);i!=INVALID; ++i) {
147 RefType operator[] (Key k) { return RefType(*this,k);}
149 Value operator[] (Key k) const { return isTrue(k);}
155 /// \addtogroup graph_maps
158 /// Iterable bool NodeMap
160 /// This map can be used in the same way
161 /// as the standard NodeMap<bool> of the
162 /// given graph \c Graph.
163 /// In addition, this class provides two iterators called \ref TrueIt
164 /// and \ref FalseIt to iterate through the "true" and "false" nodes.
165 template <class Graph>
166 class IterableBoolNodeMap
168 typename Graph::template NodeMap<int> cmap;
172 typedef IterableBoolMap<typename Graph::template NodeMap<int> > BimType;
176 typedef typename BimType::RefType RefType;
177 typedef typename Graph::Node Key;
180 friend class FalseIt;
184 IterableBoolNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
188 void set(Key k, bool v) { imap.set(k,v);}
189 ///Number of \c true items in the map
191 ///Returns the number of \c true values in the map.
192 ///This is a constant time operation.
193 int countTrue() { return imap.countTrue(); }
194 ///Number of \c false items in the map
196 ///Returns the number of \c false values in the map.
197 ///This is a constant time operation.
198 int countFalse() { return imap.countFalse(); }
201 bool &operator[](Key k) { return imap[k];}
203 const bool &operator[](Key k) const { return imap[k];}
205 Value operator[](Key k) const { return imap[k];}
206 RefType operator[](Key k) { return imap[k];}
208 ///Iterator for the "false" nodes
209 class FalseIt : public BimType::FalseIt
213 explicit FalseIt(const IterableBoolNodeMap &m)
214 : BimType::FalseIt(m.imap) { }
216 FalseIt(Invalid i) : BimType::FalseIt(i) { }
218 ///Iterator for the "true" nodes
219 class TrueIt : public BimType::TrueIt
223 explicit TrueIt(const IterableBoolNodeMap &m)
224 : BimType::TrueIt(m.imap) { }
226 TrueIt(Invalid i) : BimType::TrueIt(i) { }
230 /// Iterable bool UpperNodeMap
232 /// This map can be used in the same way
233 /// as the standard UpperNodeMap<bool> of the
234 /// given graph \c Graph.
235 /// In addition, this class provides two iterators called \ref TrueIt
236 /// and \ref FalseIt to iterate through the "true" and "false" nodes.
237 template <class Graph>
238 class IterableBoolUpperNodeMap
240 typename Graph::template UpperNodeMap<int> cmap;
244 typedef IterableBoolMap<typename Graph::template UpperNodeMap<int> > BimType;
248 typedef typename BimType::RefType RefType;
249 typedef typename Graph::Node Key;
252 friend class FalseIt;
256 IterableBoolUpperNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
260 void set(Key k, bool v) { imap.set(k,v);}
261 ///Number of \c true items in the map
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" nodes
281 class FalseIt : public BimType::FalseIt
285 explicit FalseIt(const IterableBoolUpperNodeMap &m)
286 : BimType::FalseIt(m.imap) { }
288 FalseIt(Invalid i) : BimType::FalseIt(i) { }
290 ///Iterator for the "true" nodes
291 class TrueIt : public BimType::TrueIt
295 explicit TrueIt(const IterableBoolUpperNodeMap &m)
296 : BimType::TrueIt(m.imap) { }
298 TrueIt(Invalid i) : BimType::TrueIt(i) { }
302 /// Iterable bool LowerNodeMap
304 /// This map can be used in the same way
305 /// as the standard LowerNodeMap<bool> of the
306 /// given graph \c Graph.
307 /// In addition, this class provides two iterators called \ref TrueIt
308 /// and \ref FalseIt to iterate through the "true" and "false" nodes.
309 template <class Graph>
310 class IterableBoolLowerNodeMap
312 typename Graph::template LowerNodeMap<int> cmap;
316 typedef IterableBoolMap<typename Graph::template LowerNodeMap<int> > BimType;
320 typedef typename BimType::RefType RefType;
321 typedef typename Graph::Node Key;
324 friend class FalseIt;
328 IterableBoolLowerNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
332 void set(Key k, bool v) { imap.set(k,v);}
333 ///Number of \c true items in the map
335 ///Returns the number of \c true values in the map.
336 ///This is a constant time operation.
337 int countTrue() { return imap.countTrue(); }
338 ///Number of \c false items in the map
340 ///Returns the number of \c false values in the map.
341 ///This is a constant time operation.
342 int countFalse() { return imap.countFalse(); }
345 bool &operator[](Key k) { return imap[k];}
347 const bool &operator[](Key k) const { return imap[k];}
349 Value operator[](Key k) const { return imap[k];}
350 RefType operator[](Key k) { return imap[k];}
352 ///Iterator for the "false" nodes
353 class FalseIt : public BimType::FalseIt
357 explicit FalseIt(const IterableBoolLowerNodeMap &m)
358 : BimType::FalseIt(m.imap) { }
360 FalseIt(Invalid i) : BimType::FalseIt(i) { }
362 ///Iterator for the "true" nodes
363 class TrueIt : public BimType::TrueIt
367 explicit TrueIt(const IterableBoolLowerNodeMap &m)
368 : BimType::TrueIt(m.imap) { }
370 TrueIt(Invalid i) : BimType::TrueIt(i) { }
374 /// Iterable bool EdgeMap
376 /// This map can be used in the same way
377 /// as the standard EdgeMap<bool> of the
378 /// given graph \c Graph.
379 /// In addition, this class provides two iterators called \ref TrueIt
380 /// and \ref FalseIt to iterate through the "true" and "false" edges.
381 template <class Graph>
382 class IterableBoolEdgeMap
384 typename Graph::template EdgeMap<int> cmap;
388 typedef IterableBoolMap<typename Graph::template EdgeMap<int> > BimType;
392 typedef typename BimType::RefType RefType;
393 typedef typename Graph::Edge Key;
396 friend class FalseIt;
400 IterableBoolEdgeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
404 void set(Key k, bool v) { imap.set(k,v);}
405 ///Returns the number of \c true values in the map.
406 ///This is a constant time operation.
407 int countTrue() { return imap.countTrue(); }
408 ///Number of \c false items in the map
410 ///Returns the number of \c false values in the map.
411 ///This is a constant time operation.
412 int countFalse() { return imap.countFalse(); }
415 bool &operator[](Key k) { return imap[k];}
417 const bool &operator[](Key k) const { return imap[k];}
419 Value operator[](Key k) const { return imap[k];}
420 RefType operator[](Key k) { return imap[k];}
422 ///Iterator for the "false" edges
423 class FalseIt : public BimType::FalseIt
427 explicit FalseIt(const IterableBoolEdgeMap &m)
428 : BimType::FalseIt(m.imap) { }
430 FalseIt(Invalid i) : BimType::FalseIt(i) { }
432 ///Iterator for the "true" edges
433 class TrueIt : public BimType::TrueIt
437 explicit TrueIt(const IterableBoolEdgeMap &m)
438 : BimType::TrueIt(m.imap) { }
440 TrueIt(Invalid i) : BimType::TrueIt(i) { }
445 namespace _iterable_maps_bits {
446 template <typename Item>
447 struct IterableIntMapNode {
448 IterableIntMapNode() {}
449 IterableIntMapNode(int _value) : value(_value) {}
457 /// \brief Dynamic iterable integer map.
459 /// This class provides a special graph map type which can store
460 /// for each graph item(node, edge, etc.) an integer value. For each
461 /// non negative value it is possible to iterate on the keys which
462 /// mapped to the given value.
464 /// \param _Graph The graph type.
465 /// \param _Item One of the graph's item type, the key of the map.
466 template <typename _Graph, typename _Item>
467 class IterableIntMap : protected ItemSetTraits<_Graph, _Item>
468 ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >::Parent {
470 typedef typename ItemSetTraits<_Graph, _Item>
471 ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >
479 typedef _Graph Graph;
481 /// \brief Constructor of the Map.
483 /// Constructor of the Map. It set all values -1.
484 explicit IterableIntMap(const Graph& graph)
485 : Parent(graph, _iterable_maps_bits::IterableIntMapNode<_Item>(-1)) {}
487 /// \brief Constructor of the Map with a given value.
489 /// Constructor of the Map with a given value.
490 explicit IterableIntMap(const Graph& graph, int value)
491 : Parent(graph, _iterable_maps_bits::IterableIntMapNode<_Item>(value)) {
493 for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
501 void unlace(const Key& key) {
502 typename Parent::Value& node = Parent::operator[](key);
503 if (node.value < 0) return;
504 if (node.prev != INVALID) {
505 Parent::operator[](node.prev).next = node.next;
507 first[node.value] = node.next;
509 if (node.next != INVALID) {
510 Parent::operator[](node.next).prev = node.prev;
512 while (!first.empty() && first.back() == INVALID) {
517 void lace(const Key& key) {
518 typename Parent::Value& node = Parent::operator[](key);
519 if (node.value < 0) return;
520 if (node.value >= (int)first.size()) {
521 first.resize(node.value + 1, INVALID);
524 node.next = first[node.value];
525 if (node.next != INVALID) {
526 Parent::operator[](node.next).prev = key;
528 first[node.value] = key;
533 /// Indicates that the map if reference map.
534 typedef True ReferenceMapTag;
536 /// \brief Refernce to the value of the map.
538 /// This class is near to similar to the int type. It can
539 /// be converted to int and it has the same operators.
541 friend class IterableIntMap;
543 Reference(IterableIntMap& map, const Key& key)
544 : _key(key), _map(map) {}
547 Reference& operator=(const Reference& value) {
548 _map.set(_key, (const int&)value);
552 operator const int&() const {
553 return static_cast<const IterableIntMap&>(_map)[_key];
556 Reference& operator=(int value) {
557 _map.set(_key, value);
560 Reference& operator++() {
561 _map.set(_key, _map[_key] + 1);
564 int operator++(int) {
565 int value = _map[_key];
566 _map.set(_key, value + 1);
569 Reference& operator--() {
570 _map.set(_key, _map[_key] - 1);
573 int operator--(int) {
574 int value = _map[_key];
575 _map.set(_key, value - 1);
578 Reference& operator+=(int value) {
579 _map.set(_key, _map[_key] + value);
582 Reference& operator-=(int value) {
583 _map.set(_key, _map[_key] - value);
586 Reference& operator*=(int value) {
587 _map.set(_key, _map[_key] * value);
590 Reference& operator/=(int value) {
591 _map.set(_key, _map[_key] / value);
594 Reference& operator%=(int value) {
595 _map.set(_key, _map[_key] % value);
598 Reference& operator&=(int value) {
599 _map.set(_key, _map[_key] & value);
602 Reference& operator|=(int value) {
603 _map.set(_key, _map[_key] | value);
606 Reference& operator^=(int value) {
607 _map.set(_key, _map[_key] ^ value);
610 Reference& operator<<=(int value) {
611 _map.set(_key, _map[_key] << value);
614 Reference& operator>>=(int value) {
615 _map.set(_key, _map[_key] >> value);
621 IterableIntMap& _map;
624 /// The const reference type.
625 typedef const Value& ConstReference;
627 /// \brief Gives back the maximal value plus one.
629 /// Gives back the maximal value plus one.
631 return (int)first.size();
634 /// \brief Set operation of the map.
636 /// Set operation of the map.
637 void set(const Key& key, const Value& value) {
639 Parent::operator[](key).value = value;
643 /// \brief Const subscript operator of the map.
645 /// Const subscript operator of the map.
646 const Value& operator[](const Key& key) const {
647 return Parent::operator[](key).value;
650 /// \brief Subscript operator of the map.
652 /// Subscript operator of the map.
653 Reference operator[](const Key& key) {
654 return Reference(*this, key);
657 /// \brief Iterator for the keys with the same value.
659 /// Iterator for the keys with the same value. It works
660 /// like a graph item iterator in the map, it can be converted
661 /// the item type of the map, incremented with \c ++ operator, and
662 /// if the iterator leave the last valid item it will be equal to
664 class ItemIt : public _Item {
666 typedef _Item Parent;
668 /// \brief Invalid constructor \& conversion.
670 /// This constructor initializes the item to be invalid.
671 /// \sa Invalid for more details.
672 ItemIt(Invalid) : Parent(INVALID), _map(0) {}
674 /// \brief Creates an iterator with a value.
676 /// Creates an iterator with a value. It iterates on the
677 /// keys which have the given value.
678 /// \param map The IterableIntMap
679 /// \param value The value
680 ItemIt(const IterableIntMap& map, int value) : _map(&map) {
681 if (value < 0 || value >= (int)_map->first.size()) {
682 Parent::operator=(INVALID);
684 Parent::operator=(_map->first[value]);
688 /// \brief Increment operator.
690 /// Increment Operator.
691 ItemIt& operator++() {
692 Parent::operator=(_map->IterableIntMap::Parent::
693 operator[](static_cast<Parent&>(*this)).next);
699 const IterableIntMap* _map;
704 virtual void erase(const Key& key) {
709 virtual void clear() {
715 std::vector<_Item> first;