- Doc images partly turned on again.
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 ReferenceMapTraits<_Map>::Value MapValue;
108 typedef typename ReferenceMapTraits<_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 ReferenceMapTraits<_Map>::Value MapValue;
198 typedef typename ReferenceMapTraits<_Map>::ConstReference
203 /// The value type of the iterator.
204 typedef extended_pair<Item, const Item&,
205 MapValue, const MapValue&> Value;
207 /// The reference type of the iterator.
208 typedef extended_pair<const Item&, const Item&,
209 MapReference, MapReference> Reference;
211 /// Default constructor.
212 MapConstIterator() {}
214 /// Constructor to initalize the iterators returned
215 /// by the begin() and end().
216 MapConstIterator(const Map& _map, const ItemIt& _it)
217 : Parent(_it), map(&_map) {}
219 /// Dereference operator for the iterator.
220 Reference operator*() {
221 return Reference(Parent::it, (*map)[Parent::it]);
224 /// The pointer type of the iterator.
226 friend class MapConstIterator;
229 Pointer(const Item& item, MapReference val)
232 Reference* operator->() {return &data;}
235 /// Arrow operator for the iterator.
236 Pointer operator->() {
237 return Pointer(Parent::it, ((*map)[Parent::it]));
240 /// The pre increment operator of the iterator.
241 MapConstIterator& operator++() {
246 /// The post increment operator of the iterator.
247 MapConstIterator operator++(int) {
248 MapConstIterator tmp(*this);
257 // STL compatibility typedefs.
258 typedef std::forward_iterator_tag iterator_category;
259 typedef int difference_type;
260 typedef Value value_type;
261 typedef Reference reference;
262 typedef Pointer pointer;
265 /** The class makes the ItemIt to an stl compatible iterator
266 * with dereferencing operator.
271 class MapConstKeyIterator : public MapIteratorBase<_Graph, _Item> {
275 /// The iterator base class.
276 typedef MapIteratorBase<_Graph, _Item> Parent;
278 typedef _Graph Graph;
282 /// The iterator to iterate on the keys.
283 typedef typename Parent::ItemIt ItemIt;
288 typedef const Item& Reference;
289 typedef const Item* Pointer;
291 /// Default constructor.
292 MapConstKeyIterator() {}
294 /// ItemIt initialized iterator.
295 MapConstKeyIterator(const ItemIt& pit) : Parent(pit) {}
297 /// The pre increment operator of the iterator.
298 MapConstKeyIterator& operator++() {
303 /// The post increment operator of the iterator.
304 MapConstKeyIterator operator++(int) {
305 MapConstKeyIterator tmp(*this);
310 /// The dereferencing operator of the iterator.
311 Item operator*() const {
312 return static_cast<Item>(Parent::it);
316 // STL compatibility typedefs.
317 typedef std::input_iterator_tag iterator_category;
318 typedef int difference_type;
319 typedef Value value_type;
320 typedef Reference reference;
321 typedef Pointer pointer;
328 class MapConstValueIterator;
330 /** MapValueIterator creates an stl compatible iterator
337 class MapValueIterator : public MapIteratorBase<_Graph, _Item> {
339 friend class MapConstValueIterator<_Graph, _Item, _Map>;
343 /// The iterator base class.
344 typedef MapIteratorBase<_Graph, _Item> Parent;
346 typedef _Graph Graph;
352 /// The iterator to iterate on the keys.
353 typedef typename Parent::ItemIt ItemIt;
355 /// The value type of the iterator.
356 typedef typename ReferenceMapTraits<Map>::Value MapValue;
357 /// The reference type of the iterator.
358 typedef typename ReferenceMapTraits<Map>::Reference MapReference;
359 /// The pointer type of the iterator.
360 typedef typename ReferenceMapTraits<Map>::Pointer MapPointer;
364 typedef MapValue Value;
365 typedef MapReference Reference;
366 typedef MapPointer Pointer;
368 /// Default constructor.
369 MapValueIterator() {}
371 /// Map and ItemIt initialized iterator.
372 MapValueIterator(Map& _map, const ItemIt& _it)
373 : Parent(_it), map(&_map) {}
376 /// The pre increment operator of the iterator.
377 MapValueIterator& operator++() {
382 /// The post increment operator of the iterator.
383 MapValueIterator operator++(int) {
384 MapValueIterator tmp(*this);
389 /// The dereferencing operator of the iterator.
390 Reference operator*() const {
391 return (*map)[Parent::it];
394 /// The arrow operator of the iterator.
395 Pointer operator->() const {
396 return &(operator*());
404 // STL compatibility typedefs.
405 typedef std::forward_iterator_tag iterator_category;
406 typedef int difference_type;
407 typedef Value value_type;
408 typedef Reference reference;
409 typedef Pointer pointer;
412 /** MapValueIterator creates an stl compatible iterator
419 class MapConstValueIterator : public MapIteratorBase<_Graph, _Item> {
423 /// The iterator base class.
424 typedef MapIteratorBase<_Graph, _Item> Parent;
426 typedef _Graph Graph;
432 /// The iterator to iterate on the keys.
433 typedef typename Parent::ItemIt ItemIt;
435 /// The value type of the iterator.
436 typedef typename ReferenceMapTraits<Map>::Value MapValue;
437 /// The reference type of the iterator.
438 typedef typename ReferenceMapTraits<Map>::ConstReference MapReference;
439 /// The pointer type of the iterator.
440 typedef typename ReferenceMapTraits<Map>::ConstPointer MapPointer;
444 typedef MapValue Value;
445 typedef MapReference Reference;
446 typedef MapPointer Pointer;
448 /// Default constructor.
449 MapConstValueIterator() {}
451 /// Map and ItemIt initialized iterator.
452 MapConstValueIterator(const Map& _map, const ItemIt& _it)
453 : Parent(_it), map(&_map) {}
456 /// The pre increment operator of the iterator.
457 MapConstValueIterator& operator++() {
462 /// The post increment operator of the iterator.
463 MapConstValueIterator operator++(int) {
464 MapConstValueIterator tmp(*this);
469 /// The dereferencing operator of the iterator.
470 Reference operator*() const {
471 return (*map)[Parent::it];
474 /// The arrow operator of the iterator.
475 Pointer operator->() const {
476 return &(operator*());
484 // STL compatibility typedefs.
485 typedef std::forward_iterator_tag iterator_category;
486 typedef int difference_type;
487 typedef Value value_type;
488 typedef Reference reference;
489 typedef Pointer pointer;
493 /** This class makes from a map an iteratable set
494 * which contains all the keys of the map.
496 template <typename _Graph, typename _Item>
497 class MapConstKeySet {
501 typedef _Graph Graph;
502 /// The key type of the iterator.
504 /// The iterator to iterate on the keys.
508 typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
512 /// The map initialized const key set.
513 MapConstKeySet(const Graph& _graph) : graph(&_graph) {}
515 /// The const iterator of the set.
516 typedef MapConstKeyIterator<_Graph, _Item> ConstIterator;
518 typedef typename ConstIterator::Value Value;
519 /// The reference type of the iterator.
520 typedef typename ConstIterator::Reference ConstReference;
521 /// The pointer type of the iterator.
522 typedef typename ConstIterator::Pointer ConstPointer;
524 /// It gives back the const iterator pointed to the first element.
525 ConstIterator begin() const {
526 return ConstIterator(ItemIt(*graph));
529 /// It gives back the const iterator pointed to the first ivalid element.
530 ConstIterator end() const {
531 return ConstIterator(ItemIt(INVALID));
539 // STL compatibility typedefs.
540 typedef Value value_type;
541 typedef ConstIterator const_iterator;
542 typedef ConstReference const_reference;
543 typedef ConstPointer const_pointer;
544 typedef int difference_type;
547 /** This class makes from a map an iteratable set
548 * which contains all the values of the map.
549 * The values cannot be modified.
551 template <typename _Graph, typename _Item, typename _Map>
552 class MapConstValueSet {
556 typedef _Graph Graph;
562 /// The iterator to iterate on the keys.
563 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
567 /// The map initialized const value set.
568 MapConstValueSet(const Graph& _graph, const Map& _map)
569 : graph(&_graph), map(&_map) {}
571 /// The const iterator of the set.
572 typedef MapConstValueIterator<_Graph, _Item, _Map> ConstIterator;
574 typedef typename ConstIterator::Value Value;
575 typedef typename ConstIterator::Reference ConstReference;
576 typedef typename ConstIterator::Pointer ConstPointer;
578 /// It gives back the const iterator pointed to the first element.
579 ConstIterator begin() const {
580 return ConstIterator(*map, ItemIt(*graph));
583 /// It gives back the const iterator pointed to the first invalid element.
584 ConstIterator end() const {
585 return ConstIterator(*map, ItemIt(INVALID));
594 // STL compatibility typedefs.
595 typedef Value value_type;
596 typedef ConstIterator const_iterator;
597 typedef ConstReference const_reference;
598 typedef ConstPointer const_pointer;
599 typedef int difference_type;
603 /** This class makes from a map an iteratable set
604 * which contains all the values of the map.
605 * The values can be modified.
607 template <typename _Graph, typename _Item, typename _Map>
612 typedef _Graph Graph;
618 /// The iterator to iterate on the keys.
619 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
623 /// The map initialized const value set.
624 MapValueSet(const Graph& _graph, Map& _map)
625 : map(&_map), graph(&_graph) {}
627 /// The const iterator of the set.
628 typedef MapValueIterator<_Graph, _Item, _Map> Iterator;
629 /// The const iterator of the set.
630 typedef MapConstValueIterator<_Graph, _Item, _Map> ConstIterator;
632 typedef typename ConstIterator::Value Value;
633 typedef typename Iterator::Reference Reference;
634 typedef typename Iterator::Pointer Pointer;
635 typedef typename ConstIterator::Reference ConstReference;
636 typedef typename ConstIterator::Pointer ConstPointer;
638 /// It gives back the const iterator pointed to the first element.
639 ConstIterator begin() const {
640 return ConstIterator(*map, ItemIt(*graph));
643 /// It gives back the const iterator pointed to the first invalid element.
644 ConstIterator end() const {
645 return ConstIterator(*map, ItemIt(INVALID));
648 /// It gives back the iterator pointed to the first element.
650 return Iterator(*map, ItemIt(*graph));
653 /// It gives back the iterator pointed to the first invalid element.
655 return Iterator(*map, ItemIt(INVALID));
664 // STL compatibility typedefs.
665 typedef Value value_type;
666 typedef Iterator iterator;
667 typedef ConstIterator const_iterator;
668 typedef Reference reference;
669 typedef ConstReference const_reference;
670 typedef Pointer pointer;
671 typedef ConstPointer const_pointer;
672 typedef int difference_type;
676 /** This class makes from a map an iteratable set
677 * which contains all the values of the map.
678 * The values can be modified.
688 typedef _Graph Graph;
694 typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
698 /// The map initialized value set.
699 MapSet(const Graph& _graph, Map& _map) : graph(&_graph), map(&_map) {}
701 /// The const iterator of the set.
702 typedef MapIterator<_Graph, _Item, _Map> Iterator;
703 typedef MapConstIterator<_Graph, _Item, _Map> ConstIterator;
705 typedef typename ConstIterator::Value Value;
706 typedef typename Iterator::Reference Reference;
707 typedef typename Iterator::Pointer Pointer;
708 typedef typename ConstIterator::Reference ConstReference;
709 typedef typename ConstIterator::Pointer ConstPointer;
712 /// It gives back the const iterator pointed to the first element.
713 ConstIterator begin() const {
714 return ConstIterator(*map, ItemIt(*graph));
717 /// It gives back the const iterator pointed to the first invalid element.
718 ConstIterator end() const {
719 return ConstIterator(*map, ItemIt(INVALID));
722 /// The iterator of the set.
724 /// It gives back the iterator pointed to the first element.
726 return Iterator(*map, ItemIt(*graph));
729 /// It gives back the iterator pointed to the first invalid element.
731 return Iterator(*map, ItemIt(INVALID));
740 // STL compatibility typedefs.
741 typedef Value value_type;
742 typedef Iterator iterator;
743 typedef ConstIterator const_iterator;
744 typedef Reference reference;
745 typedef ConstReference const_reference;
746 typedef Pointer pointer;
747 typedef ConstPointer const_pointer;
748 typedef int difference_type;
759 typedef _Graph Graph;
767 typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
770 /// The map initialized value set.
771 ConstMapSet(const Graph& _graph, const Map& _map)
772 : graph(&_graph), map(&_map) {}
774 /// The const iterator of the set.
775 typedef MapConstIterator<_Graph, _Item, _Map> ConstIterator;
777 typedef typename ConstIterator::Value Value;
778 typedef typename ConstIterator::Reference ConstReference;
779 typedef typename ConstIterator::Pointer ConstPointer;
782 /// It gives back the const iterator pointed to the first element.
783 ConstIterator begin() const {
784 return ConstIterator(*map, ItemIt(*graph));
787 /// It gives back the const iterator pointed to the first invalid element.
788 ConstIterator end() const {
789 return ConstIterator(*map, ItemIt(INVALID));
793 // STL compatibility typedefs.
794 typedef Value value_type;
795 typedef ConstIterator const_iterator;
796 typedef ConstReference const_reference;
797 typedef ConstPointer const_pointer;
798 typedef int difference_type;
802 template <typename _Map>
803 class IterableMapExtender : public _Map {
808 typedef typename Map::Graph Graph;
809 typedef typename Map::Key Item;
810 typedef typename Map::Value Value;
812 typedef MapSet<Graph, Item, Map> MapSet;
814 IterableMapExtender() : Parent() {}
816 IterableMapExtender(const Graph& graph) : Parent(graph) {}
818 IterableMapExtender(const Graph& graph, const Value& value)
819 : Parent(graph, value) {}
822 return MapSet(*Parent::getGraph(), *this);
825 typedef ConstMapSet<Graph, Item, Map> ConstMapSet;
827 ConstMapSet mapSet() const {
828 return ConstMapSet(*Parent::getGraph(), *this);
831 typedef MapConstKeySet<Graph, Item> ConstKeySet;
833 ConstKeySet keySet() const {
834 return ConstKeySet(*Parent::getGraph());
837 typedef MapValueSet<Graph, Item, Map> ValueSet;
839 ValueSet valueSet() {
840 return ValueSet(*Parent::getGraph(), *this);
843 typedef MapConstValueSet<Graph, Item, Map> ConstValueSet;
845 ConstValueSet valueSet() const {
846 return ConstValueSet(*Parent::getGraph(), *this);