Small bug fixes.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_ITERABLE_MAPS_H
20 #define LEMON_ITERABLE_MAPS_H
22 #include <lemon/bits/traits.h>
23 #include <lemon/bits/invalid.h>
25 #include <lemon/bits/default_map.h>
26 #include <lemon/bits/map_extender.h>
36 ///\brief Maps that makes it possible to iterate through the keys having
44 ///\ingroup graph_maps
46 /// \brief Dynamic iterable bool map.
48 /// This class provides a special graph map type which can store
49 /// for each graph item(node, edge, etc.) a bool value. For both
50 /// the true and the false it is possible to iterate on the keys which
51 /// mapped to the given value.
53 /// \param _Graph The graph type.
54 /// \param _Item One of the graph's item type, the key of the map.
55 template <typename _Graph, typename _Item>
56 class IterableBoolMap : protected DefaultMap<_Graph, _Item, int> {
60 typedef typename ItemSetTraits<Graph, _Item>::ItemIt KeyIt;
61 typedef DefaultMap<_Graph, _Item, int> Parent;
63 std::vector<_Item> array;
70 /// Indicates that the map if reference map.
71 typedef True ReferenceMapTag;
77 /// The const reference type.
78 typedef const Value& ConstReference;
82 int position(const Key& key) const {
83 return Parent::operator[](key);
88 /// \brief Refernce to the value of the map.
90 /// This class is near to similar to the bool type. It can
91 /// be converted to bool and it has the same operators.
93 friend class IterableBoolMap;
95 Reference(IterableBoolMap& map, const Key& key)
96 : _key(key), _map(map) {}
99 Reference& operator=(const Reference& value) {
100 _map.set(_key, static_cast<bool>(value));
104 operator bool() const {
105 return static_cast<const IterableBoolMap&>(_map)[_key];
108 Reference& operator=(bool value) {
109 _map.set(_key, value);
112 Reference& operator&=(bool value) {
113 _map.set(_key, _map[_key] & value);
116 Reference& operator|=(bool value) {
117 _map.set(_key, _map[_key] | value);
120 Reference& operator^=(bool value) {
121 _map.set(_key, _map[_key] ^ value);
126 IterableBoolMap& _map;
129 /// \brief Constructor of the Map with a default value.
131 /// Constructor of the Map with a default value.
132 explicit IterableBoolMap(const Graph& _graph, bool def = false)
133 : Parent(_graph), graph(_graph) {
134 for (KeyIt it(graph); it != INVALID; ++it) {
135 Parent::set(it, array.size());
138 sep = (def ? array.size() : 0);
141 /// \brief Const subscript operator of the map.
143 /// Const subscript operator of the map.
144 bool operator[](const Key& key) const {
145 return position(key) < sep;
148 /// \brief Subscript operator of the map.
150 /// Subscript operator of the map.
151 Reference operator[](const Key& key) {
152 return Reference(*this, key);
155 /// \brief Set operation of the map.
157 /// Set operation of the map.
158 void set(const Key& key, bool value) {
159 int pos = position(key);
161 if (pos < sep) return;
162 Key tmp = array[sep];
164 Parent::set(key, sep);
166 Parent::set(tmp, pos);
169 if (pos >= sep) return;
171 Key tmp = array[sep];
173 Parent::set(key, sep);
175 Parent::set(tmp, pos);
179 /// \brief Returns the number of the keys mapped to true.
181 /// Returns the number of the keys mapped to true.
182 int trueNum() const {
186 /// \brief Returns the number of the keys mapped to false.
188 /// Returns the number of the keys mapped to false.
189 int falseNum() const {
190 return array.size() - sep;
193 /// \brief Iterator for the keys mapped to true.
195 /// Iterator for the keys mapped to true. It works
196 /// like a graph item iterator in the map, it can be converted
197 /// the key type of the map, incremented with \c ++ operator, and
198 /// if the iterator leave the last valid key it will be equal to
200 class TrueIt : public Key {
204 /// \brief Creates an iterator.
206 /// Creates an iterator. It iterates on the
207 /// keys which mapped to true.
208 /// \param _map The IterableIntMap
209 explicit TrueIt(const IterableBoolMap& _map)
210 : Parent(_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID),
213 /// \brief Invalid constructor \& conversion.
215 /// This constructor initializes the key to be invalid.
216 /// \sa Invalid for more details.
217 TrueIt(Invalid) : Parent(INVALID), map(0) {}
219 /// \brief Increment operator.
221 /// Increment Operator.
222 TrueIt& operator++() {
223 int pos = map->position(*this);
224 Parent::operator=(pos > 0 ? map->array[pos - 1] : INVALID);
230 const IterableBoolMap* map;
233 /// \brief Iterator for the keys mapped to false.
235 /// Iterator for the keys mapped to false. It works
236 /// like a graph item iterator in the map, it can be converted
237 /// the key type of the map, incremented with \c ++ operator, and
238 /// if the iterator leave the last valid key it will be equal to
240 class FalseIt : public Key {
244 /// \brief Creates an iterator.
246 /// Creates an iterator. It iterates on the
247 /// keys which mapped to false.
248 /// \param _map The IterableIntMap
249 explicit FalseIt(const IterableBoolMap& _map)
250 : Parent(_map.sep < int(_map.array.size()) ?
251 _map.array.back() : INVALID), map(&_map) {}
253 /// \brief Invalid constructor \& conversion.
255 /// This constructor initializes the key to be invalid.
256 /// \sa Invalid for more details.
257 FalseIt(Invalid) : Parent(INVALID), map(0) {}
259 /// \brief Increment operator.
261 /// Increment Operator.
262 FalseIt& operator++() {
263 int pos = map->position(*this);
264 Parent::operator=(pos > map->sep ? map->array[pos - 1] : INVALID);
269 const IterableBoolMap* map;
272 /// \brief Iterator for the keys mapped to a given value.
274 /// Iterator for the keys mapped to a given value. It works
275 /// like a graph item iterator in the map, it can be converted
276 /// the key type of the map, incremented with \c ++ operator, and
277 /// if the iterator leave the last valid key it will be equal to
279 class ItemIt : public Key {
283 /// \brief Creates an iterator.
285 /// Creates an iterator. It iterates on the
286 /// keys which mapped to false.
287 /// \param _map The IterableIntMap
288 /// \param value Which elements should be iterated.
289 ItemIt(const IterableBoolMap& _map, bool value)
290 : Parent(value ? (_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID) :
291 (_map.sep < int(_map.array.size()) ?
292 _map.array.back() : INVALID)), map(&_map) {}
294 /// \brief Invalid constructor \& conversion.
296 /// This constructor initializes the key to be invalid.
297 /// \sa Invalid for more details.
298 ItemIt(Invalid) : Parent(INVALID), map(0) {}
300 /// \brief Increment operator.
302 /// Increment Operator.
303 ItemIt& operator++() {
304 int pos = map->position(*this);
305 int sep = pos >= map->sep ? map->sep : 0;
306 Parent::operator=(pos > sep ? map->array[pos - 1] : INVALID);
311 const IterableBoolMap* map;
316 virtual void add(const Key& key) {
318 Parent::set(key, array.size());
319 array.push_back(key);
322 virtual void add(const std::vector<Key>& keys) {
324 for (int i = 0; i < int(keys.size()); ++i) {
325 Parent::set(keys[i], array.size());
326 array.push_back(keys[i]);
330 virtual void erase(const Key& key) {
331 int pos = position(key);
334 Parent::set(array[sep], pos);
335 array[pos] = array[sep];
336 Parent::set(array.back(), sep);
337 array[sep] = array.back();
340 Parent::set(array.back(), pos);
341 array[pos] = array.back();
347 virtual void erase(const std::vector<Key>& keys) {
348 for (int i = 0; i < int(keys.size()); ++i) {
349 int pos = position(keys[i]);
352 Parent::set(array[sep], pos);
353 array[pos] = array[sep];
354 Parent::set(array.back(), sep);
355 array[sep] = array.back();
358 Parent::set(array.back(), pos);
359 array[pos] = array.back();
366 virtual void build() {
368 for (KeyIt it(graph); it != INVALID; ++it) {
369 Parent::set(it, array.size());
375 virtual void clear() {
384 namespace _iterable_maps_bits {
385 template <typename Item>
386 struct IterableIntMapNode {
387 IterableIntMapNode() : value(-1) {}
388 IterableIntMapNode(int _value) : value(_value) {}
394 ///\ingroup graph_maps
396 /// \brief Dynamic iterable integer map.
398 /// This class provides a special graph map type which can store
399 /// for each graph item(node, edge, etc.) an integer value. For each
400 /// non negative value it is possible to iterate on the keys which
401 /// mapped to the given value.
403 /// \param _Graph The graph type.
404 /// \param _Item One of the graph's item type, the key of the map.
405 template <typename _Graph, typename _Item>
407 : protected MapExtender<DefaultMap<_Graph, _Item, _iterable_maps_bits::
408 IterableIntMapNode<_Item> > >{
410 typedef MapExtender<DefaultMap<_Graph, _Item, _iterable_maps_bits::
411 IterableIntMapNode<_Item> > > Parent;
418 typedef _Graph Graph;
420 /// \brief Constructor of the Map.
422 /// Constructor of the Map. It set all values -1.
423 explicit IterableIntMap(const Graph& graph)
426 /// \brief Constructor of the Map with a given value.
428 /// Constructor of the Map with a given value.
429 explicit IterableIntMap(const Graph& graph, int value)
430 : Parent(graph, _iterable_maps_bits::IterableIntMapNode<_Item>(value)) {
432 for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
440 void unlace(const Key& key) {
441 typename Parent::Value& node = Parent::operator[](key);
442 if (node.value < 0) return;
443 if (node.prev != INVALID) {
444 Parent::operator[](node.prev).next = node.next;
446 first[node.value] = node.next;
448 if (node.next != INVALID) {
449 Parent::operator[](node.next).prev = node.prev;
451 while (!first.empty() && first.back() == INVALID) {
456 void lace(const Key& key) {
457 typename Parent::Value& node = Parent::operator[](key);
458 if (node.value < 0) return;
459 if (node.value >= int(first.size())) {
460 first.resize(node.value + 1, INVALID);
463 node.next = first[node.value];
464 if (node.next != INVALID) {
465 Parent::operator[](node.next).prev = key;
467 first[node.value] = key;
472 /// Indicates that the map if reference map.
473 typedef True ReferenceMapTag;
475 /// \brief Refernce to the value of the map.
477 /// This class is near to similar to the int type. It can
478 /// be converted to int and it has the same operators.
480 friend class IterableIntMap;
482 Reference(IterableIntMap& map, const Key& key)
483 : _key(key), _map(map) {}
486 Reference& operator=(const Reference& value) {
487 _map.set(_key, static_cast<const int&>(value));
491 operator const int&() const {
492 return static_cast<const IterableIntMap&>(_map)[_key];
495 Reference& operator=(int value) {
496 _map.set(_key, value);
499 Reference& operator++() {
500 _map.set(_key, _map[_key] + 1);
503 int operator++(int) {
504 int value = _map[_key];
505 _map.set(_key, value + 1);
508 Reference& operator--() {
509 _map.set(_key, _map[_key] - 1);
512 int operator--(int) {
513 int value = _map[_key];
514 _map.set(_key, value - 1);
517 Reference& operator+=(int value) {
518 _map.set(_key, _map[_key] + value);
521 Reference& operator-=(int value) {
522 _map.set(_key, _map[_key] - value);
525 Reference& operator*=(int value) {
526 _map.set(_key, _map[_key] * value);
529 Reference& operator/=(int value) {
530 _map.set(_key, _map[_key] / value);
533 Reference& operator%=(int value) {
534 _map.set(_key, _map[_key] % value);
537 Reference& operator&=(int value) {
538 _map.set(_key, _map[_key] & value);
541 Reference& operator|=(int value) {
542 _map.set(_key, _map[_key] | value);
545 Reference& operator^=(int value) {
546 _map.set(_key, _map[_key] ^ value);
549 Reference& operator<<=(int value) {
550 _map.set(_key, _map[_key] << value);
553 Reference& operator>>=(int value) {
554 _map.set(_key, _map[_key] >> value);
560 IterableIntMap& _map;
563 /// The const reference type.
564 typedef const Value& ConstReference;
566 /// \brief Gives back the maximal value plus one.
568 /// Gives back the maximal value plus one.
569 unsigned int size() const {
573 /// \brief Set operation of the map.
575 /// Set operation of the map.
576 void set(const Key& key, const Value& value) {
578 Parent::operator[](key).value = value;
582 /// \brief Const subscript operator of the map.
584 /// Const subscript operator of the map.
585 const Value& operator[](const Key& key) const {
586 return Parent::operator[](key).value;
589 /// \brief Subscript operator of the map.
591 /// Subscript operator of the map.
592 Reference operator[](const Key& key) {
593 return Reference(*this, key);
596 /// \brief Iterator for the keys with the same value.
598 /// Iterator for the keys with the same value. It works
599 /// like a graph item iterator in the map, it can be converted
600 /// the item type of the map, incremented with \c ++ operator, and
601 /// if the iterator leave the last valid item it will be equal to
603 class ItemIt : public _Item {
605 typedef _Item Parent;
607 /// \brief Invalid constructor \& conversion.
609 /// This constructor initializes the item to be invalid.
610 /// \sa Invalid for more details.
611 ItemIt(Invalid) : Parent(INVALID), _map(0) {}
613 /// \brief Creates an iterator with a value.
615 /// Creates an iterator with a value. It iterates on the
616 /// keys which have the given value.
617 /// \param map The IterableIntMap
618 /// \param value The value
619 ItemIt(const IterableIntMap& map, int value) : _map(&map) {
620 if (value < 0 || value >= int(_map->first.size())) {
621 Parent::operator=(INVALID);
623 Parent::operator=(_map->first[value]);
627 /// \brief Increment operator.
629 /// Increment Operator.
630 ItemIt& operator++() {
631 Parent::operator=(_map->IterableIntMap::Parent::
632 operator[](static_cast<Parent&>(*this)).next);
638 const IterableIntMap* _map;
643 virtual void erase(const Key& key) {
648 virtual void erase(const std::vector<Key>& keys) {
649 for (int i = 0; i < int(keys.size()); ++i) {
655 virtual void clear() {
661 std::vector<_Item> first;
664 namespace _iterable_maps_bits {
665 template <typename Item, typename Value>
666 struct IterableValueMapNode {
667 IterableValueMapNode(Value _value = Value()) : value(_value) {}
673 ///\ingroup graph_maps
675 /// \brief Dynamic iterable map for comparable values.
677 /// This class provides a special graph map type which can store
678 /// for each graph item(node, edge, etc.) a value. For each
679 /// value it is possible to iterate on the keys which mapped to the
680 /// given value. The type stores for each value a linked list with
681 /// the items which mapped to the value, and the values are stored
682 /// in balanced binary tree. The values of the map can be accessed
683 /// with stl compatible forward iterator.
685 /// This type is not reference map so it cannot be modified with
686 /// the subscription operator.
688 /// \see InvertableMap
690 /// \param _Graph The graph type.
691 /// \param _Item One of the graph's item type, the key of the map.
692 /// \param _Value Any comparable value type.
693 template <typename _Graph, typename _Item, typename _Value>
694 class IterableValueMap
695 : protected MapExtender<DefaultMap<_Graph, _Item, _iterable_maps_bits::
696 IterableValueMapNode<_Item, _Value> > >{
698 typedef MapExtender<DefaultMap<_Graph, _Item, _iterable_maps_bits::
699 IterableValueMapNode<_Item, _Value> > >
705 typedef _Value Value;
707 typedef _Graph Graph;
711 /// \brief Constructor of the Map with a given value.
713 /// Constructor of the Map with a given value.
714 explicit IterableValueMap(const Graph& graph,
715 const Value& value = Value())
716 : Parent(graph, _iterable_maps_bits::
717 IterableValueMapNode<_Item, _Value>(value)) {
718 for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
725 void unlace(const Key& key) {
726 typename Parent::Value& node = Parent::operator[](key);
727 if (node.prev != INVALID) {
728 Parent::operator[](node.prev).next = node.next;
730 if (node.next != INVALID) {
731 first[node.value] = node.next;
733 first.erase(node.value);
736 if (node.next != INVALID) {
737 Parent::operator[](node.next).prev = node.prev;
741 void lace(const Key& key) {
742 typename Parent::Value& node = Parent::operator[](key);
743 typename std::map<Value, Key>::iterator it = first.find(node.value);
744 if (it == first.end()) {
745 node.prev = node.next = INVALID;
746 if (node.next != INVALID) {
747 Parent::operator[](node.next).prev = key;
749 first.insert(make_pair(node.value, key));
752 node.next = it->second;
753 if (node.next != INVALID) {
754 Parent::operator[](node.next).prev = key;
762 /// \brief Forward iterator for values.
764 /// This iterator is an stl compatible forward
765 /// iterator on the values of the map. The values can
766 /// be accessed in the [beginValue, endValue) range.
769 : public std::iterator<std::forward_iterator_tag, Value> {
770 friend class IterableValueMap;
772 ValueIterator(typename std::map<Value, Key>::const_iterator _it)
778 ValueIterator& operator++() { ++it; return *this; }
779 ValueIterator operator++(int) {
780 ValueIterator tmp(*this);
785 const Value& operator*() const { return it->first; }
786 const Value* operator->() const { return &(it->first); }
788 bool operator==(ValueIterator jt) const { return it == jt.it; }
789 bool operator!=(ValueIterator jt) const { return it != jt.it; }
792 typename std::map<Value, Key>::const_iterator it;
795 /// \brief Returns an iterator to the first value.
797 /// Returns an stl compatible iterator to the
798 /// first value of the map. The values of the
799 /// map can be accessed in the [beginValue, endValue)
801 ValueIterator beginValue() const {
802 return ValueIterator(first.begin());
805 /// \brief Returns an iterator after the last value.
807 /// Returns an stl compatible iterator after the
808 /// last value of the map. The values of the
809 /// map can be accessed in the [beginValue, endValue)
811 ValueIterator endValue() const {
812 return ValueIterator(first.end());
815 /// \brief Set operation of the map.
817 /// Set operation of the map.
818 void set(const Key& key, const Value& value) {
820 Parent::operator[](key).value = value;
824 /// \brief Const subscript operator of the map.
826 /// Const subscript operator of the map.
827 const Value& operator[](const Key& key) const {
828 return Parent::operator[](key).value;
831 /// \brief Iterator for the keys with the same value.
833 /// Iterator for the keys with the same value. It works
834 /// like a graph item iterator in the map, it can be converted
835 /// the item type of the map, incremented with \c ++ operator, and
836 /// if the iterator leave the last valid item it will be equal to
838 class ItemIt : public _Item {
840 typedef _Item Parent;
842 /// \brief Invalid constructor \& conversion.
844 /// This constructor initializes the item to be invalid.
845 /// \sa Invalid for more details.
846 ItemIt(Invalid) : Parent(INVALID), _map(0) {}
848 /// \brief Creates an iterator with a value.
850 /// Creates an iterator with a value. It iterates on the
851 /// keys which have the given value.
852 /// \param map The IterableValueMap
853 /// \param value The value
854 ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) {
855 typename std::map<Value, Key>::const_iterator it =
856 map.first.find(value);
857 if (it == map.first.end()) {
858 Parent::operator=(INVALID);
860 Parent::operator=(it->second);
864 /// \brief Increment operator.
866 /// Increment Operator.
867 ItemIt& operator++() {
868 Parent::operator=(_map->IterableValueMap::Parent::
869 operator[](static_cast<Parent&>(*this)).next);
875 const IterableValueMap* _map;
880 virtual void add(const Key& key) {
885 virtual void add(const std::vector<Key>& keys) {
887 for (int i = 0; i < int(keys.size()); ++i) {
892 virtual void erase(const Key& key) {
897 virtual void erase(const std::vector<Key>& keys) {
898 for (int i = 0; i < int(keys.size()); ++i) {
904 virtual void build() {
906 for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
911 virtual void clear() {
917 std::map<Value, Key> first;