Completions.
2 * src/lemon/map_iterator.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, 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/extended_pair.h>
26 ///\brief Iterators on the maps.
30 /// \addtogroup graphmaps
33 /** The base class all of the map iterators.
34 * The class defines the typedefs of the iterators,
35 * simple step functions and equality operators.
38 template <typename Map>
39 class MapIteratorBase {
43 /// The key type of the iterator.
44 typedef typename Map::Key Key;
45 /// The iterator to iterate on the keys.
46 typedef typename Map::KeyIt KeyIt;
48 /// The value type of the iterator.
49 typedef typename Map::Value Value;
50 /// The reference type of the iterator.
51 typedef typename Map::Reference Reference;
52 /// The pointer type of the iterator.
53 typedef typename Map::Pointer Pointer;
55 /// The const value type of the iterator.
56 typedef typename Map::ConstValue ConstValue;
57 /// The const reference type of the iterator.
58 typedef typename Map::ConstReference ConstReference;
59 /// The pointer type of the iterator.
60 typedef typename Map::ConstPointer ConstPointer;
66 /// Default constructor.
69 /// KeyIt initialized MapIteratorBase constructor.
70 MapIteratorBase(const KeyIt pit) : it(pit) {}
74 /// Stepping forward in the map.
79 /// The equality operator of the map.
80 bool operator==(const MapIteratorBase& pit) const {
84 /// The not-equality operator of the map.
85 bool operator!=(const MapIteratorBase& pit) const {
86 return !(*this == pit);
90 template <typename Map> class MapConstIterator;
92 /** Compatible iterator with the stl maps' iterators.
93 * It iterates on pairs of a key and a value.
95 template <typename Map>
96 class MapIterator : public MapIteratorBase<Map> {
98 friend class MapConstIterator<Map>;
103 /// The iterator base class.
104 typedef MapIteratorBase<Map> Base;
106 /// The key type of the iterator.
107 typedef typename Map::Key Key;
108 /// The iterator to iterate on the keys.
109 typedef typename Map::KeyIt KeyIt;
111 /// The value type of the iterator.
112 typedef typename Map::Value Value;
113 /// The reference type of the iterator.
114 typedef typename Map::Reference Reference;
115 /// The pointer type of the iterator.
116 typedef typename Map::Pointer Pointer;
118 /// The const value type of the iterator.
119 typedef typename Map::ConstValue ConstValue;
120 /// The const reference type of the iterator.
121 typedef typename Map::ConstReference ConstReference;
122 /// The pointer type of the iterator.
123 typedef typename Map::ConstPointer ConstPointer;
127 /// The value type of the iterator.
128 typedef extended_pair<Key, const Key&,
129 Value, const Value&> PairValue;
131 /// The reference type of the iterator.
132 typedef extended_pair<const Key&, const Key&,
133 Reference, Reference> PairReference;
135 /// Default constructor.
138 /// Constructor to initalize the iterators returned
139 /// by the begin() and end().
140 MapIterator(Map& pmap, const KeyIt& pit) : Base(pit), map(&pmap) {}
142 /// Dereference operator for the iterator.
143 PairReference operator*() {
144 return PairReference(Base::it, (*map)[Base::it]);
147 /// The pointer type of the iterator.
149 friend class MapIterator;
152 PairPointer(const Key& key, Reference val)
155 PairReference* operator->() {return &data;}
158 /// Arrow operator for the iterator.
159 PairPointer operator->() {
160 return PairPointer(Base::it, ((*map)[Base::it]));
163 /// The pre increment operator of the iterator.
164 MapIterator& operator++() {
169 /// The post increment operator of the iterator.
170 MapIterator operator++(int) {
171 MapIterator tmp(*this);
180 // STL compatibility typedefs.
181 typedef std::forward_iterator_tag iterator_category;
182 typedef int difference_type;
183 typedef PairValue value_type;
184 typedef PairReference reference;
185 typedef PairPointer pointer;
188 /** Compatible iterator with the stl maps' iterators.
189 * It iterates on pairs of a key and a value.
191 template <typename Map>
192 class MapConstIterator : public MapIteratorBase<Map> {
196 /// The iterator base class.
197 typedef MapIteratorBase<Map> Base;
199 /// The key type of the iterator.
200 typedef typename Map::Key Key;
201 /// The iterator to iterate on the keys.
202 typedef typename Map::KeyIt KeyIt;
204 /// The value type of the iterator.
205 typedef typename Map::Value Value;
206 /// The reference type of the iterator.
207 typedef typename Map::Reference Reference;
208 /// The pointer type of the iterator.
209 typedef typename Map::Pointer Pointer;
211 /// The const value type of the iterator.
212 typedef typename Map::ConstValue ConstValue;
213 /// The const reference type of the iterator.
214 typedef typename Map::ConstReference ConstReference;
215 /// The pointer type of the iterator.
216 typedef typename Map::ConstPointer ConstPointer;
220 /// Default constructor.
221 MapConstIterator() {}
223 /// Constructor to initalize the the iterators returned
224 /// by the begin() and end().
225 MapConstIterator(const Map& pmap, const KeyIt& pit)
226 : Base(pit), map(&pmap) {}
228 /// Constructor to create const iterator from a non const.
229 MapConstIterator(const MapIterator<Map>& pit) {
230 Base::it = pit.Base::it;
234 /// The value type of the iterator.
235 typedef extended_pair<Key, const Key&,
236 Value, const Value&> PairValue;
238 /// The reference type of map.
239 typedef extended_pair<const Key&, const Key&,
240 ConstReference, ConstReference> PairReference;
242 /// Dereference operator for the iterator.
243 PairReference operator*() {
244 return PairReference(Base::it, (*map)[Base::it]);
247 /// The pointer type of the iterator.
249 friend class MapConstIterator;
252 PairPointer(const Key& key, ConstReference val)
255 PairReference* operator->() {return &data;}
258 /// Arrow operator for the iterator.
259 PairPointer operator->() {
260 return PairPointer(Base::it, (*map)[Base::it]);
263 /// The pre increment operator of the iterator.
264 MapConstIterator& operator++() {
269 /// The post increment operator of the iterator.
270 MapConstIterator operator++(int) {
271 MapConstIterator tmp(*this);
280 // STL compatibility typedefs.
281 typedef std::input_iterator_tag iterator_category;
282 typedef int difference_type;
283 typedef PairValue value_type;
284 typedef PairReference reference;
285 typedef PairPointer pointer;
288 /** The class makes the KeyIt to an stl compatible iterator
289 * with dereferencing operator.
291 template <typename Map>
292 class MapKeyIterator : public MapIteratorBase<Map> {
296 /// The iterator base class.
297 typedef MapIteratorBase<Map> Base;
299 /// The key type of the iterator.
300 typedef typename Map::Key Key;
301 /// The iterator to iterate on the keys.
302 typedef typename Map::KeyIt KeyIt;
306 /// Default constructor.
309 /// KeyIt initialized iterator.
310 MapKeyIterator(const KeyIt& pit) : Base(pit) {}
312 /// The pre increment operator of the iterator.
313 MapKeyIterator& operator++() {
318 /// The post increment operator of the iterator.
319 MapKeyIterator operator++(int) {
320 MapKeyIterator tmp(*this);
325 /// The dereferencing operator of the iterator.
326 Key operator*() const {
327 return static_cast<Key>(Base::it);
331 // STL compatibility typedefs.
332 typedef std::input_iterator_tag iterator_category;
333 typedef int difference_type;
334 typedef Key value_type;
335 typedef const Key& reference;
336 typedef const Key* pointer;
339 template <typename Map> class MapConstValueIterator;
341 /** MapValueIterator creates an stl compatible iterator
344 template <typename Map>
345 class MapValueIterator : public MapIteratorBase<Map> {
347 friend class MapConstValueIterator<Map>;
351 /// The iterator base class.
352 typedef MapIteratorBase<Map> Base;
354 /// The key type of the iterator.
355 typedef typename Map::Key Key;
356 /// The iterator to iterate on the keys.
357 typedef typename Map::KeyIt KeyIt;
360 /// The value type of the iterator.
361 typedef typename Map::Value Value;
362 /// The reference type of the iterator.
363 typedef typename Map::Reference Reference;
364 /// The pointer type of the iterator.
365 typedef typename Map::Pointer Pointer;
367 /// The const value type of the iterator.
368 typedef typename Map::ConstValue ConstValue;
369 /// The const reference type of the iterator.
370 typedef typename Map::ConstReference ConstReference;
371 /// The pointer type of the iterator.
372 typedef typename Map::ConstPointer ConstPointer;
380 /// Default constructor.
381 MapValueIterator() {}
383 /// Map and KeyIt initialized iterator.
384 MapValueIterator(Map& pmap, const KeyIt& pit)
385 : Base(pit), map(&pmap) {}
388 /// The pre increment operator of the iterator.
389 MapValueIterator& operator++() {
394 /// The post increment operator of the iterator.
395 MapValueIterator operator++(int) {
396 MapValueIterator tmp(*this);
401 /// The dereferencing operator of the iterator.
402 Reference operator*() const {
403 return (*map)[Base::it];
406 /// The arrow operator of the iterator.
407 Pointer operator->() const {
408 return &(operator*());
412 // STL compatibility typedefs.
413 typedef std::forward_iterator_tag iterator_category;
414 typedef int difference_type;
415 typedef Value value_type;
416 typedef Reference reference;
417 typedef Pointer pointer;
420 /** MapValueIterator creates an stl compatible iterator
421 * for the const values.
424 template <typename Map>
425 class MapConstValueIterator : public MapIteratorBase<Map> {
429 /// The iterator base class.
430 typedef MapIteratorBase<Map> Base;
432 /// The key type of the iterator.
433 typedef typename Map::Key Key;
434 /// The iterator to iterate on the keys.
435 typedef typename Map::KeyIt KeyIt;
437 /// The value type of the iterator.
438 typedef typename Map::Value Value;
439 /// The reference type of the iterator.
440 typedef typename Map::Reference Reference;
441 /// The pointer type of the iterator.
442 typedef typename Map::Pointer Pointer;
444 /// The const value type of the iterator.
445 typedef typename Map::ConstValue ConstValue;
446 /// The const reference type of the iterator.
447 typedef typename Map::ConstReference ConstReference;
448 /// The pointer type of the iterator.
449 typedef typename Map::ConstPointer ConstPointer;
457 /// Default constructor.
458 MapConstValueIterator() {}
460 /// Constructor to create const iterator from a non const.
461 MapConstValueIterator(const MapValueIterator<Map>& pit) {
462 Base::it = pit.Base::it;
466 /// Map and KeyIt initialized iterator.
467 MapConstValueIterator(const Map& pmap, const KeyIt& pit)
468 : Base(pit), map(&pmap) {}
470 /// The pre increment operator of the iterator.
471 MapConstValueIterator& operator++() {
476 /// The post increment operator of the iterator.
477 MapConstValueIterator operator++(int) {
478 MapConstValueIterator tmp(*this);
483 /// The dereferencing operator of the iterator.
484 ConstReference operator*() const {
485 return (*map)[Base::it];
488 /// The arrow operator of the iterator.
489 ConstPointer operator->() const {
490 return &(operator*());
494 // STL compatibility typedefs.
495 typedef std::input_iterator_tag iterator_category;
496 typedef int difference_type;
497 typedef Value value_type;
498 typedef ConstReference reference;
499 typedef ConstPointer pointer;
503 /** This class makes from a map an iteratable set
504 * which contains all the keys of the map.
506 template <typename Map>
507 class MapConstKeySet {
513 /// The key type of the iterator.
514 typedef typename Map::Key Key;
515 /// The iterator to iterate on the keys.
516 typedef typename Map::KeyIt KeyIt;
519 /// The value type of the iterator.
520 typedef typename Map::Value Value;
521 /// The reference type of the iterator.
522 typedef typename Map::Reference Reference;
523 /// The pointer type of the iterator.
524 typedef typename Map::Pointer Pointer;
526 /// The const value type of the iterator.
527 typedef typename Map::ConstValue ConstValue;
528 /// The const reference type of the iterator.
529 typedef typename Map::ConstReference ConstReference;
530 /// The pointer type of the iterator.
531 typedef typename Map::ConstPointer ConstPointer;
533 /// The map initialized const key set.
534 MapConstKeySet(const Map& pmap) : map(&pmap) {}
536 /// The const iterator of the set.
537 typedef MapKeyIterator<Map> ConstIterator;
539 /// It gives back the const iterator pointed to the first element.
540 ConstIterator begin() const {
541 return ConstIterator(KeyIt(*map->getGraph()));
544 /// It gives back the const iterator pointed to the first ivalid element.
545 ConstIterator end() const {
546 return ConstIterator(KeyIt(INVALID));
550 // STL compatibility typedefs.
551 typedef Value value_type;
552 typedef ConstIterator const_iterator;
553 typedef ConstReference const_reference;
554 typedef ConstPointer const_pointer;
555 typedef int difference_type;
558 /** This class makes from a map an iteratable set
559 * which contains all the values of the map.
560 * The values cannot be modified.
562 template <typename Map>
563 class MapConstValueSet {
569 /// The key type of the iterator.
570 typedef typename Map::Key Key;
571 /// The iterator to iterate on the keys.
572 typedef typename Map::KeyIt KeyIt;
575 /// The value type of the iterator.
576 typedef typename Map::Value Value;
577 /// The reference type of the iterator.
578 typedef typename Map::Reference Reference;
579 /// The pointer type of the iterator.
580 typedef typename Map::Pointer Pointer;
582 /// The const value type of the iterator.
583 typedef typename Map::ConstValue ConstValue;
584 /// The const reference type of the iterator.
585 typedef typename Map::ConstReference ConstReference;
586 /// The pointer type of the iterator.
587 typedef typename Map::ConstPointer ConstPointer;
589 /// The map initialized const value set.
590 MapConstValueSet(const Map& pmap) : map(&pmap) {}
592 /// The const iterator of the set.
593 typedef MapConstValueIterator<Map> ConstIterator;
595 /// It gives back the const iterator pointed to the first element.
596 ConstIterator begin() const {
597 return ConstIterator(*map, KeyIt(*map->getGraph()));
600 /// It gives back the const iterator pointed to the first invalid element.
601 ConstIterator end() const {
602 return ConstIterator(*map, KeyIt(INVALID));
606 // STL compatibility typedefs.
607 typedef Value value_type;
608 typedef ConstIterator const_iterator;
609 typedef ConstReference const_reference;
610 typedef ConstPointer const_pointer;
611 typedef int difference_type;
615 /** This class makes from a map an iteratable set
616 * which contains all the values of the map.
617 * The values can be modified.
619 template <typename Map>
626 /// The key type of the iterator.
627 typedef typename Map::Key Key;
628 /// The iterator to iterate on the keys.
629 typedef typename Map::KeyIt KeyIt;
632 /// The value type of the iterator.
633 typedef typename Map::Value Value;
634 /// The reference type of the iterator.
635 typedef typename Map::Reference Reference;
636 /// The pointer type of the iterator.
637 typedef typename Map::Pointer Pointer;
639 /// The const value type of the iterator.
640 typedef typename Map::ConstValue ConstValue;
641 /// The const reference type of the iterator.
642 typedef typename Map::ConstReference ConstReference;
643 /// The pointer type of the iterator.
644 typedef typename Map::ConstPointer ConstPointer;
646 /// The map initialized value set.
647 MapValueSet(Map& pmap) : map(&pmap) {}
649 /// The const iterator of the set.
650 typedef MapConstValueIterator<Map> ConstIterator;
652 /// It gives back the const iterator pointed to the first element.
653 ConstIterator begin() const {
654 return ConstIterator(*map, KeyIt(*map->getGraph()));
657 /// It gives back the const iterator pointed to the first invalid element.
658 ConstIterator end() const {
659 return ConstIterator(*map, KeyIt(INVALID));
662 /// The iterator of the set.
663 typedef MapValueIterator<Map> Iterator;
665 /// It gives back the iterator pointed to the first element.
667 return Iterator(*map, KeyIt(*map->getGraph()));
670 /// It gives back the iterator pointed to the first invalid element.
672 return Iterator(*map, KeyIt(INVALID));
676 // STL compatibility typedefs.
677 typedef Value value_type;
678 typedef Iterator iterator;
679 typedef ConstIterator const_iterator;
680 typedef Reference reference;
681 typedef ConstReference const_reference;
682 typedef Pointer pointer;
683 typedef ConstPointer const_pointer;
684 typedef int difference_type;