The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor, where
we have to proxy the signals from the graph.
The SubBidirGraphAdaptor is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor<UndirGraphAdaptor<Graph>>.
The ResGraphAdaptor is based on this composition.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
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 #include <lemon/traits.h>
20 #include <lemon/invalid.h>
22 #include <lemon/bits/default_map.h>
32 ///\brief Maps that makes it possible to iterate through the keys having
40 ///\ingroup graph_maps
42 /// \brief Dynamic iterable bool map.
44 /// This class provides a special graph map type which can store
45 /// for each graph item(node, edge, etc.) a bool value. For both
46 /// the true and the false it is possible to iterate on the keys which
47 /// mapped to the given value.
49 /// \param _Graph The graph type.
50 /// \param _Item One of the graph's item type, the key of the map.
51 template <typename _Graph, typename _Item>
52 class IterableBoolMap : protected DefaultMap<_Graph, _Item, int> {
56 typedef typename ItemSetTraits<Graph, _Item>::ItemIt KeyIt;
57 typedef DefaultMap<_Graph, _Item, int> Parent;
59 std::vector<_Item> array;
66 /// Indicates that the map if reference map.
67 typedef True ReferenceMapTag;
73 /// The const reference type.
74 typedef const Value& ConstReference;
78 int position(const Key& key) const {
79 return Parent::operator[](key);
84 /// \brief Refernce to the value of the map.
86 /// This class is near to similar to the bool type. It can
87 /// be converted to bool and it has the same operators.
89 friend class IterableBoolMap;
91 Reference(IterableBoolMap& map, const Key& key)
92 : _key(key), _map(map) {}
95 Reference& operator=(const Reference& value) {
96 _map.set(_key, (bool)value);
100 operator bool() const {
101 return static_cast<const IterableBoolMap&>(_map)[_key];
104 Reference& operator=(bool value) {
105 _map.set(_key, value);
108 Reference& operator&=(bool value) {
109 _map.set(_key, _map[_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);
122 IterableBoolMap& _map;
125 /// \brief Constructor of the Map with a default value.
127 /// Constructor of the Map with a default value.
128 IterableBoolMap(const Graph& _graph, bool def = false)
129 : Parent(_graph), graph(_graph) {
130 for (KeyIt it(graph); it != INVALID; ++it) {
131 Parent::set(it, array.size());
134 sep = (def ? array.size() : 0);
137 /// \brief Const subscript operator of the map.
139 /// Const subscript operator of the map.
140 bool operator[](const Key& key) const {
141 return position(key) < sep;
144 /// \brief Subscript operator of the map.
146 /// Subscript operator of the map.
147 Reference operator[](const Key& key) {
148 return Reference(*this, key);
151 /// \brief Set operation of the map.
153 /// Set operation of the map.
154 void set(const Key& key, bool value) {
155 int pos = position(key);
157 if (pos < sep) return;
158 Key tmp = array[sep];
160 Parent::set(key, sep);
162 Parent::set(tmp, pos);
165 if (pos >= sep) return;
167 Key tmp = array[sep];
169 Parent::set(key, sep);
171 Parent::set(tmp, pos);
175 /// \brief Returns the number of the keys mapped to true.
177 /// Returns the number of the keys mapped to true.
178 int trueNum() const {
182 /// \brief Returns the number of the keys mapped to false.
184 /// Returns the number of the keys mapped to false.
185 int falseNum() const {
186 return array.size() - sep;
189 /// \brief Iterator for the keys mapped to true.
191 /// Iterator for the keys mapped to true. It works
192 /// like a graph item iterator in the map, it can be converted
193 /// the key type of the map, incremented with \c ++ operator, and
194 /// if the iterator leave the last valid key it will be equal to
196 class TrueIt : public Key {
200 /// \brief Creates an iterator.
202 /// Creates an iterator. It iterates on the
203 /// keys which mapped to true.
204 /// \param _map The IterableIntMap
205 TrueIt(const IterableBoolMap& _map)
206 : Parent(_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID),
209 /// \brief Invalid constructor \& conversion.
211 /// This constructor initializes the key to be invalid.
212 /// \sa Invalid for more details.
213 TrueIt(Invalid) : Parent(INVALID), map(0) {}
215 /// \brief Increment operator.
217 /// Increment Operator.
218 TrueIt& operator++() {
219 int pos = map->position(*this);
220 Parent::operator=(pos > 0 ? map->array[pos - 1] : INVALID);
226 const IterableBoolMap* map;
229 /// \brief Iterator for the keys mapped to false.
231 /// Iterator for the keys mapped to false. It works
232 /// like a graph item iterator in the map, it can be converted
233 /// the key type of the map, incremented with \c ++ operator, and
234 /// if the iterator leave the last valid key it will be equal to
236 class FalseIt : public Key {
240 /// \brief Creates an iterator.
242 /// Creates an iterator. It iterates on the
243 /// keys which mapped to false.
244 /// \param _map The IterableIntMap
245 FalseIt(const IterableBoolMap& _map)
246 : Parent(_map.sep < (int)_map.array.size() ?
247 _map.array.back() : INVALID), map(&_map) {}
249 /// \brief Invalid constructor \& conversion.
251 /// This constructor initializes the key to be invalid.
252 /// \sa Invalid for more details.
253 FalseIt(Invalid) : Parent(INVALID), map(0) {}
255 /// \brief Increment operator.
257 /// Increment Operator.
258 FalseIt& operator++() {
259 int pos = map->position(*this);
260 Parent::operator=(pos > map->sep ? map->array[pos - 1] : INVALID);
265 const IterableBoolMap* map;
268 /// \brief Iterator for the keys mapped to a given value.
270 /// Iterator for the keys mapped to a given value. It works
271 /// like a graph item iterator in the map, it can be converted
272 /// the key type of the map, incremented with \c ++ operator, and
273 /// if the iterator leave the last valid key it will be equal to
275 class ItemIt : public Key {
279 /// \brief Creates an iterator.
281 /// Creates an iterator. It iterates on the
282 /// keys which mapped to false.
283 /// \param _map The IterableIntMap
284 /// \param value Which elements should be iterated.
285 ItemIt(const IterableBoolMap& _map, bool value)
286 : Parent(value ? (_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID) :
287 (_map.sep < (int)_map.array.size() ?
288 _map.array.back() : INVALID)), map(&_map) {}
290 /// \brief Invalid constructor \& conversion.
292 /// This constructor initializes the key to be invalid.
293 /// \sa Invalid for more details.
294 ItemIt(Invalid) : Parent(INVALID), map(0) {}
296 /// \brief Increment operator.
298 /// Increment Operator.
299 ItemIt& operator++() {
300 int pos = map->position(*this);
301 int sep = pos >= map->sep ? map->sep : 0;
302 Parent::operator=(pos > sep ? map->array[pos - 1] : INVALID);
307 const IterableBoolMap* map;
312 virtual void add(const Key& key) {
314 Parent::set(key, array.size());
315 array.push_back(key);
318 virtual void add(const std::vector<Key>& keys) {
320 for (int i = 0; i < (int)keys.size(); ++i) {
321 Parent::set(keys[i], array.size());
322 array.push_back(keys[i]);
326 virtual void erase(const Key& key) {
327 int pos = position(key);
330 Parent::set(array[sep], pos);
331 array[pos] = array[sep];
332 Parent::set(array.back(), sep);
333 array[sep] = array.back();
336 Parent::set(array.back(), pos);
337 array[pos] = array.back();
343 virtual void erase(const std::vector<Key>& keys) {
344 for (int i = 0; i < (int)keys.size(); ++i) {
345 int pos = position(keys[i]);
348 Parent::set(array[sep], pos);
349 array[pos] = array[sep];
350 Parent::set(array.back(), sep);
351 array[sep] = array.back();
354 Parent::set(array.back(), pos);
355 array[pos] = array.back();
362 virtual void build() {
364 for (KeyIt it(graph); it != INVALID; ++it) {
365 Parent::set(it, array.size());
371 virtual void clear() {
380 namespace _iterable_maps_bits {
381 template <typename Item>
382 struct IterableIntMapNode {
383 IterableIntMapNode() : value(-1) {}
384 IterableIntMapNode(int _value) : value(_value) {}
390 ///\ingroup graph_maps
392 /// \brief Dynamic iterable integer map.
394 /// This class provides a special graph map type which can store
395 /// for each graph item(node, edge, etc.) an integer value. For each
396 /// non negative value it is possible to iterate on the keys which
397 /// mapped to the given value.
399 /// \param _Graph The graph type.
400 /// \param _Item One of the graph's item type, the key of the map.
401 template <typename _Graph, typename _Item>
403 : protected DefaultMap<_Graph, _Item, _iterable_maps_bits::
404 IterableIntMapNode<_Item> > {
406 typedef DefaultMap<_Graph, _Item, _iterable_maps_bits::
407 IterableIntMapNode<_Item> >
415 typedef _Graph Graph;
417 /// \brief Constructor of the Map.
419 /// Constructor of the Map. It set all values -1.
420 explicit IterableIntMap(const Graph& graph)
423 /// \brief Constructor of the Map with a given value.
425 /// Constructor of the Map with a given value.
426 explicit IterableIntMap(const Graph& graph, int value)
427 : Parent(graph, _iterable_maps_bits::IterableIntMapNode<_Item>(value)) {
429 for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
437 void unlace(const Key& key) {
438 typename Parent::Value& node = Parent::operator[](key);
439 if (node.value < 0) return;
440 if (node.prev != INVALID) {
441 Parent::operator[](node.prev).next = node.next;
443 first[node.value] = node.next;
445 if (node.next != INVALID) {
446 Parent::operator[](node.next).prev = node.prev;
448 while (!first.empty() && first.back() == INVALID) {
453 void lace(const Key& key) {
454 typename Parent::Value& node = Parent::operator[](key);
455 if (node.value < 0) return;
456 if (node.value >= (int)first.size()) {
457 first.resize(node.value + 1, INVALID);
460 node.next = first[node.value];
461 if (node.next != INVALID) {
462 Parent::operator[](node.next).prev = key;
464 first[node.value] = key;
469 /// Indicates that the map if reference map.
470 typedef True ReferenceMapTag;
472 /// \brief Refernce to the value of the map.
474 /// This class is near to similar to the int type. It can
475 /// be converted to int and it has the same operators.
477 friend class IterableIntMap;
479 Reference(IterableIntMap& map, const Key& key)
480 : _key(key), _map(map) {}
483 Reference& operator=(const Reference& value) {
484 _map.set(_key, (const int&)value);
488 operator const int&() const {
489 return static_cast<const IterableIntMap&>(_map)[_key];
492 Reference& operator=(int value) {
493 _map.set(_key, value);
496 Reference& operator++() {
497 _map.set(_key, _map[_key] + 1);
500 int operator++(int) {
501 int value = _map[_key];
502 _map.set(_key, value + 1);
505 Reference& operator--() {
506 _map.set(_key, _map[_key] - 1);
509 int operator--(int) {
510 int value = _map[_key];
511 _map.set(_key, value - 1);
514 Reference& operator+=(int value) {
515 _map.set(_key, _map[_key] + value);
518 Reference& operator-=(int value) {
519 _map.set(_key, _map[_key] - value);
522 Reference& operator*=(int value) {
523 _map.set(_key, _map[_key] * value);
526 Reference& operator/=(int value) {
527 _map.set(_key, _map[_key] / value);
530 Reference& operator%=(int value) {
531 _map.set(_key, _map[_key] % value);
534 Reference& operator&=(int value) {
535 _map.set(_key, _map[_key] & value);
538 Reference& operator|=(int value) {
539 _map.set(_key, _map[_key] | value);
542 Reference& operator^=(int value) {
543 _map.set(_key, _map[_key] ^ value);
546 Reference& operator<<=(int value) {
547 _map.set(_key, _map[_key] << value);
550 Reference& operator>>=(int value) {
551 _map.set(_key, _map[_key] >> value);
557 IterableIntMap& _map;
560 /// The const reference type.
561 typedef const Value& ConstReference;
563 /// \brief Gives back the maximal value plus one.
565 /// Gives back the maximal value plus one.
566 unsigned int size() const {
570 /// \brief Set operation of the map.
572 /// Set operation of the map.
573 void set(const Key& key, const Value& value) {
575 Parent::operator[](key).value = value;
579 /// \brief Const subscript operator of the map.
581 /// Const subscript operator of the map.
582 const Value& operator[](const Key& key) const {
583 return Parent::operator[](key).value;
586 /// \brief Subscript operator of the map.
588 /// Subscript operator of the map.
589 Reference operator[](const Key& key) {
590 return Reference(*this, key);
593 /// \brief Iterator for the keys with the same value.
595 /// Iterator for the keys with the same value. It works
596 /// like a graph item iterator in the map, it can be converted
597 /// the item type of the map, incremented with \c ++ operator, and
598 /// if the iterator leave the last valid item it will be equal to
600 class ItemIt : public _Item {
602 typedef _Item Parent;
604 /// \brief Invalid constructor \& conversion.
606 /// This constructor initializes the item to be invalid.
607 /// \sa Invalid for more details.
608 ItemIt(Invalid) : Parent(INVALID), _map(0) {}
610 /// \brief Creates an iterator with a value.
612 /// Creates an iterator with a value. It iterates on the
613 /// keys which have the given value.
614 /// \param map The IterableIntMap
615 /// \param value The value
616 ItemIt(const IterableIntMap& map, int value) : _map(&map) {
617 if (value < 0 || value >= (int)_map->first.size()) {
618 Parent::operator=(INVALID);
620 Parent::operator=(_map->first[value]);
624 /// \brief Increment operator.
626 /// Increment Operator.
627 ItemIt& operator++() {
628 Parent::operator=(_map->IterableIntMap::Parent::
629 operator[](static_cast<Parent&>(*this)).next);
635 const IterableIntMap* _map;
640 virtual void erase(const Key& key) {
645 virtual void erase(const std::vector<Key>& keys) {
646 for (int i = 0; i < (int)keys.size(); ++i) {
652 virtual void clear() {
658 std::vector<_Item> first;
661 namespace _iterable_maps_bits {
662 template <typename Item, typename Value>
663 struct IterableValueMapNode {
664 IterableValueMapNode(Value _value = Value()) : value(_value) {}
670 ///\ingroup graph_maps
672 /// \brief Dynamic iterable map for comparable values.
674 /// This class provides a special graph map type which can store
675 /// for each graph item(node, edge, etc.) a value. For each
676 /// value it is possible to iterate on the keys which mapped to the
677 /// given value. The type stores for each value a linked list with
678 /// the items which mapped to the value, and the values are stored
679 /// in balanced binary tree. The values of the map can be accessed
680 /// with stl compatible forward iterator.
682 /// This type is not reference map so it cannot be modified with
683 /// the subscription operator.
685 /// \see InvertableMap
687 /// \param _Graph The graph type.
688 /// \param _Item One of the graph's item type, the key of the map.
689 /// \param _Value Any comparable value type.
690 template <typename _Graph, typename _Item, typename _Value>
691 class IterableValueMap
692 : protected DefaultMap<_Graph, _Item, _iterable_maps_bits::
693 IterableValueMapNode<_Item, _Value> > {
695 typedef DefaultMap<_Graph, _Item, _iterable_maps_bits::
696 IterableValueMapNode<_Item, _Value> > Parent;
701 typedef _Value Value;
703 typedef _Graph Graph;
707 typedef typename ItemSetTraits<_Graph, Key>::ItemIt KeyIt;
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 (KeyIt it(*Parent::getGraph()); 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 (KeyIt it(*Parent::getGraph()); it != INVALID; ++it) {
911 virtual void clear() {
917 std::map<Value, Key> first;