Empty graph is (strongly) connected.
2 * lemon/map_iterator.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 #ifndef LEMON_MAP_ITERATOR_H
18 #define LEMON_MAP_ITERATOR_H
22 #include <lemon/bits/extended_pair.h>
23 #include <lemon/graph_utils.h>
25 ///\ingroup graphmapfactory
27 ///\brief Iterators on the maps.
31 /// \addtogroup graphmapfactory
34 /** The base class all of the map iterators.
35 * The class defines the typedefs of the iterators,
36 * simple step functions and equality operators.
42 class MapIteratorBase {
46 /// The key type of the iterator.
47 typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
51 /// Default constructor.
54 /// ItemIt initialized MapIteratorBase constructor.
55 MapIteratorBase(const ItemIt _it) : it(_it) {}
59 /// Stepping forward in the map.
64 /// The equality operator of the map.
65 bool operator==(const MapIteratorBase& _it) const {
69 /// The not-equality operator of the map.
70 bool operator!=(const MapIteratorBase& _it) const {
71 return !(*this == _it);
80 class MapConstIterator;
82 /** Compatible iterator with the stl maps' iterators.
83 * It iterates on pairs of a key and a value.
89 class MapIterator : public MapIteratorBase<_Graph, _Item> {
91 friend class MapConstIterator<_Graph, _Item, _Map>;
96 /// The iterator base class.
97 typedef MapIteratorBase<_Graph, _Item> Parent;
101 typedef _Graph Graph;
105 typedef typename Parent::ItemIt ItemIt;
107 typedef typename _Map::Value MapValue;
108 typedef typename _Map::Reference MapReference;
112 /// The value type of the iterator.
113 typedef extended_pair<Item, const Item&,
114 MapValue, const MapValue&> Value;
116 /// The reference type of the iterator.
117 typedef extended_pair<const Item&, const Item&,
118 MapReference, MapReference> Reference;
120 /// Default constructor.
123 /// Constructor to initalize the iterators returned
124 /// by the begin() and end().
125 MapIterator(Map& _map, const ItemIt& _it)
126 : Parent(_it), map(&_map) {}
128 /// Dereference operator for the iterator.
129 Reference operator*() {
130 return Reference(Parent::it, (*map)[Parent::it]);
133 /// The pointer type of the iterator.
135 friend class MapIterator;
138 Pointer(const Item& item, MapReference val)
141 Reference* operator->() {return &data;}
144 /// Arrow operator for the iterator.
145 Pointer operator->() {
146 return Pointer(Parent::it, (*map)[Parent::it]);
149 /// The pre increment operator of the iterator.
150 MapIterator& operator++() {
155 /// The post increment operator of the iterator.
156 MapIterator operator++(int) {
157 MapIterator tmp(*this);
167 // STL compatibility typedefs.
168 typedef std::forward_iterator_tag iterator_category;
169 typedef int difference_type;
170 typedef Value value_type;
171 typedef Reference reference;
172 typedef Pointer pointer;
175 /** Compatible iterator with the stl maps' iterators.
176 * It iterates on pairs of a key and a value.
182 class MapConstIterator : public MapIteratorBase<_Graph, _Item> {
186 /// The iterator base class.
187 typedef MapIteratorBase<_Graph, _Item> Parent;
189 typedef _Graph Graph;
195 typedef typename Parent::ItemIt ItemIt;
197 typedef typename _Map::Value MapValue;
198 typedef typename _Map::ConstReference MapReference;
202 /// The value type of the iterator.
203 typedef extended_pair<Item, const Item&,
204 MapValue, const MapValue&> Value;
206 /// The reference type of the iterator.
207 typedef extended_pair<const Item&, const Item&,
208 MapReference, MapReference> Reference;
210 /// Default constructor.
211 MapConstIterator() {}
213 /// Constructor to initalize the iterators returned
214 /// by the begin() and end().
215 MapConstIterator(const Map& _map, const ItemIt& _it)
216 : Parent(_it), map(&_map) {}
218 /// Dereference operator for the iterator.
219 Reference operator*() {
220 return Reference(Parent::it, (*map)[Parent::it]);
223 /// The pointer type of the iterator.
225 friend class MapConstIterator;
228 Pointer(const Item& item, MapReference val)
231 Reference* operator->() {return &data;}
234 /// Arrow operator for the iterator.
235 Pointer operator->() {
236 return Pointer(Parent::it, ((*map)[Parent::it]));
239 /// The pre increment operator of the iterator.
240 MapConstIterator& operator++() {
245 /// The post increment operator of the iterator.
246 MapConstIterator operator++(int) {
247 MapConstIterator tmp(*this);
256 // STL compatibility typedefs.
257 typedef std::forward_iterator_tag iterator_category;
258 typedef int difference_type;
259 typedef Value value_type;
260 typedef Reference reference;
261 typedef Pointer pointer;
264 /** The class makes the ItemIt to an stl compatible iterator
265 * with dereferencing operator.
270 class MapConstKeyIterator : public MapIteratorBase<_Graph, _Item> {
274 /// The iterator base class.
275 typedef MapIteratorBase<_Graph, _Item> Parent;
277 typedef _Graph Graph;
281 /// The iterator to iterate on the keys.
282 typedef typename Parent::ItemIt ItemIt;
287 typedef const Item& Reference;
288 typedef const Item* Pointer;
290 /// Default constructor.
291 MapConstKeyIterator() {}
293 /// ItemIt initialized iterator.
294 MapConstKeyIterator(const ItemIt& pit) : Parent(pit) {}
296 /// The pre increment operator of the iterator.
297 MapConstKeyIterator& operator++() {
302 /// The post increment operator of the iterator.
303 MapConstKeyIterator operator++(int) {
304 MapConstKeyIterator tmp(*this);
309 /// The dereferencing operator of the iterator.
310 Item operator*() const {
311 return static_cast<Item>(Parent::it);
315 // STL compatibility typedefs.
316 typedef std::input_iterator_tag iterator_category;
317 typedef int difference_type;
318 typedef Value value_type;
319 typedef Reference reference;
320 typedef Pointer pointer;
327 class MapConstValueIterator;
329 /** MapValueIterator creates an stl compatible iterator
336 class MapValueIterator : public MapIteratorBase<_Graph, _Item> {
338 friend class MapConstValueIterator<_Graph, _Item, _Map>;
342 /// The iterator base class.
343 typedef MapIteratorBase<_Graph, _Item> Parent;
345 typedef _Graph Graph;
351 /// The iterator to iterate on the keys.
352 typedef typename Parent::ItemIt ItemIt;
354 /// The value type of the iterator.
355 typedef typename Map::Value MapValue;
356 /// The reference type of the iterator.
357 typedef typename Map::Reference MapReference;
358 /// The pointer type of the iterator.
359 typedef typename Map::Pointer MapPointer;
363 typedef MapValue Value;
364 typedef MapReference Reference;
365 typedef MapPointer Pointer;
367 /// Default constructor.
368 MapValueIterator() {}
370 /// Map and ItemIt initialized iterator.
371 MapValueIterator(Map& _map, const ItemIt& _it)
372 : Parent(_it), map(&_map) {}
375 /// The pre increment operator of the iterator.
376 MapValueIterator& operator++() {
381 /// The post increment operator of the iterator.
382 MapValueIterator operator++(int) {
383 MapValueIterator tmp(*this);
388 /// The dereferencing operator of the iterator.
389 Reference operator*() const {
390 return (*map)[Parent::it];
393 /// The arrow operator of the iterator.
394 Pointer operator->() const {
395 return &(operator*());
403 // STL compatibility typedefs.
404 typedef std::forward_iterator_tag iterator_category;
405 typedef int difference_type;
406 typedef Value value_type;
407 typedef Reference reference;
408 typedef Pointer pointer;
411 /** MapValueIterator creates an stl compatible iterator
418 class MapConstValueIterator : public MapIteratorBase<_Graph, _Item> {
422 /// The iterator base class.
423 typedef MapIteratorBase<_Graph, _Item> Parent;
425 typedef _Graph Graph;
431 /// The iterator to iterate on the keys.
432 typedef typename Parent::ItemIt ItemIt;
434 /// The value type of the iterator.
435 typedef typename Map::Value MapValue;
436 /// The reference type of the iterator.
437 typedef typename Map::ConstReference MapReference;
438 /// The pointer type of the iterator.
439 typedef typename Map::ConstPointer MapPointer;
443 typedef MapValue Value;
444 typedef MapReference Reference;
445 typedef MapPointer Pointer;
447 /// Default constructor.
448 MapConstValueIterator() {}
450 /// Map and ItemIt initialized iterator.
451 MapConstValueIterator(const Map& _map, const ItemIt& _it)
452 : Parent(_it), map(&_map) {}
455 /// The pre increment operator of the iterator.
456 MapConstValueIterator& operator++() {
461 /// The post increment operator of the iterator.
462 MapConstValueIterator operator++(int) {
463 MapConstValueIterator tmp(*this);
468 /// The dereferencing operator of the iterator.
469 Reference operator*() const {
470 return (*map)[Parent::it];
473 /// The arrow operator of the iterator.
474 Pointer operator->() const {
475 return &(operator*());
483 // STL compatibility typedefs.
484 typedef std::forward_iterator_tag iterator_category;
485 typedef int difference_type;
486 typedef Value value_type;
487 typedef Reference reference;
488 typedef Pointer pointer;
492 /** This class makes from a map an iteratable set
493 * which contains all the keys of the map.
495 template <typename _Graph, typename _Item>
496 class MapConstKeySet {
500 typedef _Graph Graph;
501 /// The key type of the iterator.
503 /// The iterator to iterate on the keys.
507 typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
511 /// The map initialized const key set.
512 MapConstKeySet(const Graph& _graph) : graph(&_graph) {}
514 /// The const iterator of the set.
515 typedef MapConstKeyIterator<_Graph, _Item> ConstIterator;
517 typedef typename ConstIterator::Value Value;
518 /// The reference type of the iterator.
519 typedef typename ConstIterator::Reference ConstReference;
520 /// The pointer type of the iterator.
521 typedef typename ConstIterator::Pointer ConstPointer;
523 /// It gives back the const iterator pointed to the first element.
524 ConstIterator begin() const {
525 return ConstIterator(ItemIt(*graph));
528 /// It gives back the const iterator pointed to the first ivalid element.
529 ConstIterator end() const {
530 return ConstIterator(ItemIt(INVALID));
538 // STL compatibility typedefs.
539 typedef Value value_type;
540 typedef ConstIterator const_iterator;
541 typedef ConstReference const_reference;
542 typedef ConstPointer const_pointer;
543 typedef int difference_type;
546 /** This class makes from a map an iteratable set
547 * which contains all the values of the map.
548 * The values cannot be modified.
550 template <typename _Graph, typename _Item, typename _Map>
551 class MapConstValueSet {
555 typedef _Graph Graph;
561 /// The iterator to iterate on the keys.
562 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
566 /// The map initialized const value set.
567 MapConstValueSet(const Graph& _graph, const Map& _map)
568 : graph(&_graph), map(&_map) {}
570 /// The const iterator of the set.
571 typedef MapConstValueIterator<_Graph, _Item, _Map> ConstIterator;
573 typedef typename ConstIterator::Value Value;
574 typedef typename ConstIterator::Reference ConstReference;
575 typedef typename ConstIterator::Pointer ConstPointer;
577 /// It gives back the const iterator pointed to the first element.
578 ConstIterator begin() const {
579 return ConstIterator(*map, ItemIt(*graph));
582 /// It gives back the const iterator pointed to the first invalid element.
583 ConstIterator end() const {
584 return ConstIterator(*map, ItemIt(INVALID));
593 // STL compatibility typedefs.
594 typedef Value value_type;
595 typedef ConstIterator const_iterator;
596 typedef ConstReference const_reference;
597 typedef ConstPointer const_pointer;
598 typedef int difference_type;
602 /** This class makes from a map an iteratable set
603 * which contains all the values of the map.
604 * The values can be modified.
606 template <typename _Graph, typename _Item, typename _Map>
611 typedef _Graph Graph;
617 /// The iterator to iterate on the keys.
618 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
622 /// The map initialized const value set.
623 MapValueSet(const Graph& _graph, Map& _map)
624 : map(&_map), graph(&_graph) {}
626 /// The const iterator of the set.
627 typedef MapValueIterator<_Graph, _Item, _Map> Iterator;
628 /// The const iterator of the set.
629 typedef MapConstValueIterator<_Graph, _Item, _Map> ConstIterator;
631 typedef typename ConstIterator::Value Value;
632 typedef typename Iterator::Reference Reference;
633 typedef typename Iterator::Pointer Pointer;
634 typedef typename ConstIterator::Reference ConstReference;
635 typedef typename ConstIterator::Pointer ConstPointer;
637 /// It gives back the const iterator pointed to the first element.
638 ConstIterator begin() const {
639 return ConstIterator(*map, ItemIt(*graph));
642 /// It gives back the const iterator pointed to the first invalid element.
643 ConstIterator end() const {
644 return ConstIterator(*map, ItemIt(INVALID));
647 /// It gives back the iterator pointed to the first element.
649 return Iterator(*map, ItemIt(*graph));
652 /// It gives back the iterator pointed to the first invalid element.
654 return Iterator(*map, ItemIt(INVALID));
663 // STL compatibility typedefs.
664 typedef Value value_type;
665 typedef Iterator iterator;
666 typedef ConstIterator const_iterator;
667 typedef Reference reference;
668 typedef ConstReference const_reference;
669 typedef Pointer pointer;
670 typedef ConstPointer const_pointer;
671 typedef int difference_type;
675 /** This class makes from a map an iteratable set
676 * which contains all the values of the map.
677 * The values can be modified.
687 typedef _Graph Graph;
693 typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
697 /// The map initialized value set.
698 MapSet(const Graph& _graph, Map& _map) : graph(&_graph), map(&_map) {}
700 /// The const iterator of the set.
701 typedef MapIterator<_Graph, _Item, _Map> Iterator;
702 typedef MapConstIterator<_Graph, _Item, _Map> ConstIterator;
704 typedef typename ConstIterator::Value Value;
705 typedef typename Iterator::Reference Reference;
706 typedef typename Iterator::Pointer Pointer;
707 typedef typename ConstIterator::Reference ConstReference;
708 typedef typename ConstIterator::Pointer ConstPointer;
711 /// It gives back the const iterator pointed to the first element.
712 ConstIterator begin() const {
713 return ConstIterator(*map, ItemIt(*graph));
716 /// It gives back the const iterator pointed to the first invalid element.
717 ConstIterator end() const {
718 return ConstIterator(*map, ItemIt(INVALID));
721 /// The iterator of the set.
723 /// It gives back the iterator pointed to the first element.
725 return Iterator(*map, ItemIt(*graph));
728 /// It gives back the iterator pointed to the first invalid element.
730 return Iterator(*map, ItemIt(INVALID));
739 // STL compatibility typedefs.
740 typedef Value value_type;
741 typedef Iterator iterator;
742 typedef ConstIterator const_iterator;
743 typedef Reference reference;
744 typedef ConstReference const_reference;
745 typedef Pointer pointer;
746 typedef ConstPointer const_pointer;
747 typedef int difference_type;
758 typedef _Graph Graph;
766 typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
769 /// The map initialized value set.
770 ConstMapSet(const Graph& _graph, const Map& _map)
771 : graph(&_graph), map(&_map) {}
773 /// The const iterator of the set.
774 typedef MapConstIterator<_Graph, _Item, _Map> ConstIterator;
776 typedef typename ConstIterator::Value Value;
777 typedef typename ConstIterator::Reference ConstReference;
778 typedef typename ConstIterator::Pointer ConstPointer;
781 /// It gives back the const iterator pointed to the first element.
782 ConstIterator begin() const {
783 return ConstIterator(*map, ItemIt(*graph));
786 /// It gives back the const iterator pointed to the first invalid element.
787 ConstIterator end() const {
788 return ConstIterator(*map, ItemIt(INVALID));
792 // STL compatibility typedefs.
793 typedef Value value_type;
794 typedef ConstIterator const_iterator;
795 typedef ConstReference const_reference;
796 typedef ConstPointer const_pointer;
797 typedef int difference_type;
801 template <typename _Map>
802 class IterableMapExtender : public _Map {
807 typedef typename Map::Graph Graph;
808 typedef typename Map::Key Item;
809 typedef typename Map::Value Value;
811 typedef MapSet<Graph, Item, Map> MapSet;
813 IterableMapExtender() : Parent() {}
815 IterableMapExtender(const Graph& graph) : Parent(graph) {}
817 IterableMapExtender(const Graph& graph, const Value& value)
818 : Parent(graph, value) {}
821 return MapSet(*Parent::getGraph(), *this);
824 typedef ConstMapSet<Graph, Item, Map> ConstMapSet;
826 ConstMapSet mapSet() const {
827 return ConstMapSet(*Parent::getGraph(), *this);
830 typedef MapConstKeySet<Graph, Item> ConstKeySet;
832 ConstKeySet keySet() const {
833 return ConstKeySet(*Parent::getGraph());
836 typedef MapValueSet<Graph, Item, Map> ValueSet;
838 ValueSet valueSet() {
839 return ValueSet(*Parent::getGraph(), *this);
842 typedef MapConstValueSet<Graph, Item, Map> ConstValueSet;
844 ConstValueSet valueSet() const {
845 return ConstValueSet(*Parent::getGraph(), *this);