COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/map_iterator.h @ 899:f485b3008cf5

Last change on this file since 899:f485b3008cf5 was 844:9bf990cb066d, checked in by Balazs Dezso, 20 years ago

Bug fix in the symmetric maps.
Faster map initialization.
Iterators and Containers STL compatible.

File size: 18.7 KB
Line 
1// -*- c++ -*-
2#ifndef MAP_ITERATOR_H
3#define MAP_ITERATOR_H
4
5#include <iterator>
6
7#include <hugo/extended_pair.h>
8
9///\ingroup graphmaps
10///\file
11///\brief Iterators on the maps.
12
13namespace hugo {
14
15  /// \addtogroup graphmaps
16  /// @{
17
18  /** The base class all of the map iterators.
19   *  The class defines the typedefs of the iterators,
20   *  simple step functions and equality operators.
21   */
22
23  template <typename Map>
24  class MapIteratorBase {
25
26  public:
27
28    /// The key type of the iterator.
29    typedef typename Map::KeyType KeyType;
30    /// The iterator to iterate on the keys.
31    typedef typename Map::KeyIt KeyIt;
32
33    /// The value type of the iterator.
34    typedef typename Map::ValueType ValueType;
35    /// The reference type of the iterator.
36    typedef typename Map::ReferenceType ReferenceType;
37    /// The pointer type of the iterator.
38    typedef typename Map::PointerType PointerType;
39
40    /// The const value type of the iterator.
41    typedef typename Map::ConstValueType ConstValueType;
42    /// The const reference type of the iterator.
43    typedef typename Map::ConstReferenceType ConstReferenceType;
44    /// The pointer type of the iterator.
45    typedef typename Map::ConstPointerType ConstPointerType;
46
47  protected:
48
49    KeyIt it;
50
51    /// Default constructor.
52    MapIteratorBase() {}
53
54    /// KeyIt initialized MapIteratorBase constructor.
55    MapIteratorBase(const KeyIt pit) : it(pit) {}
56
57  public:
58
59    /// Stepping forward in the map.   
60    void increment() {
61      ++it;
62    }
63
64    /// The equality operator of the map.
65    bool operator==(const MapIteratorBase& pit) const {
66      return pit.it == it;
67    }
68       
69    /// The not-equality operator of the map.
70    bool operator!=(const MapIteratorBase& pit) const {
71      return !(*this == pit);
72    }
73  };
74
75  template <typename Map> class MapConstIterator;
76
77  /** Compatible iterator with the stl maps' iterators.
78   * It iterates on pairs of a key and a value.
79   */
80  template <typename Map> 
81  class MapIterator : public MapIteratorBase<Map> {
82
83    friend class MapConstIterator<Map>;
84
85
86  public:
87
88    /// The iterator base class.
89    typedef MapIteratorBase<Map> Base;
90
91    /// The key type of the iterator.
92    typedef typename Map::KeyType KeyType;
93    /// The iterator to iterate on the keys.
94    typedef typename Map::KeyIt KeyIt;
95
96    /// The value type of the iterator.
97    typedef typename Map::ValueType ValueType;
98    /// The reference type of the iterator.
99    typedef typename Map::ReferenceType ReferenceType;
100    /// The pointer type of the iterator.
101    typedef typename Map::PointerType PointerType;
102
103    /// The const value type of the iterator.
104    typedef typename Map::ConstValueType ConstValueType;
105    /// The const reference type of the iterator.
106    typedef typename Map::ConstReferenceType ConstReferenceType;
107    /// The pointer type of the iterator.
108    typedef typename Map::ConstPointerType ConstPointerType;
109   
110  public:
111
112    /// The value type of the iterator.
113    typedef extended_pair<KeyType, const KeyType&,
114      ValueType, const ValueType&> PairValueType;
115
116    /// The reference type of the iterator.
117    typedef extended_pair<const KeyType&, const KeyType&,
118      ReferenceType, ReferenceType> PairReferenceType;
119
120    /// Default constructor.
121    MapIterator() {}
122
123    /// Constructor to initalize the iterators returned
124    /// by the begin() and end().
125    MapIterator(Map& pmap, const KeyIt& pit) : Base(pit), map(&pmap) {}
126
127    /// Dereference operator for the iterator.
128    PairReferenceType operator*() {
129      return PairReferenceType(Base::it, (*map)[Base::it]);
130    }
131
132    /// The pointer type of the iterator.
133    class PairPointerType {
134      friend class MapIterator;
135    private:
136      PairReferenceType data;
137      PairPointerType(const KeyType& key, ReferenceType val)
138        : data(key, val) {}
139    public:
140      PairReferenceType* operator->() {return &data;}
141    };
142
143    /// Arrow operator for the iterator.
144    PairPointerType operator->() {
145      return PairPointerType(Base::it, ((*map)[Base::it]));
146    }
147       
148    /// The pre increment operator of the iterator.
149    MapIterator& operator++() {
150      Base::increment();
151      return *this;
152    }
153
154    /// The post increment operator of the iterator.
155    MapIterator operator++(int) {
156      MapIterator tmp(*this);
157      Base::increment();
158      return tmp;
159    }
160
161  private:
162    Map* map;
163
164  public:
165    // STL  compatibility typedefs.
166    typedef std::forward_iterator_tag iterator_category;
167    typedef int difference_type;
168    typedef PairValueType value_type;
169    typedef PairReferenceType reference;
170    typedef PairPointerType pointer;
171  };
172
173  /** Compatible iterator with the stl maps' iterators.
174   *  It iterates on pairs of a key and a value.
175   */
176  template <typename Map>
177  class MapConstIterator : public MapIteratorBase<Map> {
178   
179  public:
180
181    /// The iterator base class.
182    typedef MapIteratorBase<Map> Base;
183
184    /// The key type of the iterator.
185    typedef typename Map::KeyType KeyType;
186    /// The iterator to iterate on the keys.
187    typedef typename Map::KeyIt KeyIt;
188
189    /// The value type of the iterator.
190    typedef typename Map::ValueType ValueType;
191    /// The reference type of the iterator.
192    typedef typename Map::ReferenceType ReferenceType;
193    /// The pointer type of the iterator.
194    typedef typename Map::PointerType PointerType;
195
196    /// The const value type of the iterator.
197    typedef typename Map::ConstValueType ConstValueType;
198    /// The const reference type of the iterator.
199    typedef typename Map::ConstReferenceType ConstReferenceType;
200    /// The pointer type of the iterator.
201    typedef typename Map::ConstPointerType ConstPointerType;
202
203  public:   
204
205    /// Default constructor.
206    MapConstIterator() {}
207
208    /// Constructor to initalize the the iterators returned
209    ///  by the begin() and end().
210    MapConstIterator(const Map& pmap, const KeyIt& pit)
211      : Base(pit), map(&pmap) {}
212
213    /// Constructor to create const iterator from a non const.
214    MapConstIterator(const MapIterator<Map>& pit) {
215      Base::it = pit.Base::it;
216      map = pit.map;
217    }
218
219    /// The value type of the iterator.
220    typedef extended_pair<KeyType, const KeyType&,
221      ValueType, const ValueType&> PairValueType;
222
223    /// The reference type of map.
224    typedef extended_pair<const KeyType&, const KeyType&,
225      ConstReferenceType, ConstReferenceType> PairReferenceType;
226
227    /// Dereference operator for the iterator.
228    PairReferenceType operator*() {
229      return PairReferenceType(Base::it, (*map)[Base::it]);
230    }
231
232    /// The pointer type of the iterator.
233    class PairPointerType {
234      friend class MapConstIterator;
235    private:
236      PairReferenceType data;
237      PairPointerType(const KeyType& key, ConstReferenceType val)
238        : data(key, val) {}
239    public:
240      PairReferenceType* operator->() {return &data;}
241    };
242
243    /// Arrow operator for the iterator.
244    PairPointerType operator->() {
245      return PairPointerType(Base::it, (*map)[Base::it]);
246    }
247
248    /// The pre increment operator of the iterator.
249    MapConstIterator& operator++() {
250      Base::increment();
251      return *this;
252    }
253
254    /// The post increment operator of the iterator.
255    MapConstIterator operator++(int) {
256      MapConstIterator tmp(*this);
257      Base::increment();
258      return tmp;
259    }
260
261  private:
262    const Map* map;
263
264  public:
265    // STL  compatibility typedefs.
266    typedef std::input_iterator_tag iterator_category;
267    typedef int difference_type;
268    typedef PairValueType value_type;
269    typedef PairReferenceType reference;
270    typedef PairPointerType pointer;
271  };
272
273  /** The class makes the KeyIt to an stl compatible iterator
274   *  with dereferencing operator.
275   */
276  template <typename Map>
277  class MapKeyIterator : public MapIteratorBase<Map> {
278
279  public:
280
281    /// The iterator base class.
282    typedef MapIteratorBase<Map> Base;
283 
284    /// The key type of the iterator.
285    typedef typename Map::KeyType KeyType;
286    /// The iterator to iterate on the keys.
287    typedef typename Map::KeyIt KeyIt;
288
289  public:
290
291    /// Default constructor.
292    MapKeyIterator() {}
293
294    /// KeyIt initialized iterator.
295    MapKeyIterator(const KeyIt& pit) : Base(pit) {}
296
297    /// The pre increment operator of the iterator.
298    MapKeyIterator& operator++() {
299      Base::increment();
300      return *this;
301    }
302
303    /// The post increment operator of the iterator.
304    MapKeyIterator operator++(int) {
305      MapKeyIterator tmp(*this);
306      Base::increment();
307      return tmp;
308    }
309
310    /// The dereferencing operator of the iterator.
311    KeyType operator*() const {
312      return static_cast<KeyType>(Base::it);
313    }
314
315  public:
316    // STL  compatibility typedefs.
317    typedef std::input_iterator_tag iterator_category;
318    typedef int difference_type;
319    typedef KeyType value_type;
320    typedef const KeyType& reference;
321    typedef const KeyType* pointer;
322  };
323
324  template <typename Map> class MapConstValueIterator;
325
326  /** MapValueIterator creates an stl compatible iterator
327   *  for the values.
328   */
329  template <typename Map>
330  class MapValueIterator : public MapIteratorBase<Map> {
331
332    friend class MapConstValueIterator<Map>;
333
334  public:
335
336    /// The iterator base class.
337    typedef MapIteratorBase<Map> Base;
338
339    /// The key type of the iterator.
340    typedef typename Map::KeyType KeyType;
341    /// The iterator to iterate on the keys.
342    typedef typename Map::KeyIt KeyIt;
343
344
345    /// The value type of the iterator.
346    typedef typename Map::ValueType ValueType;
347    /// The reference type of the iterator.
348    typedef typename Map::ReferenceType ReferenceType;
349    /// The pointer type of the iterator.
350    typedef typename Map::PointerType PointerType;
351
352    /// The const value type of the iterator.
353    typedef typename Map::ConstValueType ConstValueType;
354    /// The const reference type of the iterator.
355    typedef typename Map::ConstReferenceType ConstReferenceType;
356    /// The pointer type of the iterator.
357    typedef typename Map::ConstPointerType ConstPointerType;
358
359  private:
360
361    Map* map;
362
363  public:
364
365    /// Default constructor.
366    MapValueIterator() {}
367
368    /// Map and KeyIt initialized iterator.
369    MapValueIterator(Map& pmap, const KeyIt& pit)
370      : Base(pit), map(&pmap) {}
371   
372
373    /// The pre increment operator of the iterator.
374    MapValueIterator& operator++() {
375      Base::increment();
376      return *this;
377    }
378
379    /// The post increment operator of the iterator.
380    MapValueIterator operator++(int) {
381      MapValueIterator tmp(*this);
382      Base::increment();
383      return tmp;
384    }
385
386    /// The dereferencing operator of the iterator.
387    ReferenceType operator*() const {
388      return (*map)[Base::it];
389    }
390
391    /// The arrow operator of the iterator.
392    PointerType operator->() const {
393      return &(operator*());
394    }
395
396  public:
397    // STL  compatibility typedefs.
398    typedef std::forward_iterator_tag iterator_category;
399    typedef int difference_type;
400    typedef ValueType value_type;
401    typedef ReferenceType reference;
402    typedef PointerType pointer;
403  };
404
405  /** MapValueIterator creates an stl compatible iterator
406   *  for the const values.
407   */
408
409  template <typename Map>
410  class MapConstValueIterator : public MapIteratorBase<Map> {
411
412  public:
413
414    /// The iterator base class.
415    typedef MapIteratorBase<Map> Base;
416
417    /// The key type of the iterator.
418    typedef typename Map::KeyType KeyType;
419    /// The iterator to iterate on the keys.
420    typedef typename Map::KeyIt KeyIt;
421
422    /// The value type of the iterator.
423    typedef typename Map::ValueType ValueType;
424    /// The reference type of the iterator.
425    typedef typename Map::ReferenceType ReferenceType;
426    /// The pointer type of the iterator.
427    typedef typename Map::PointerType PointerType;
428
429    /// The const value type of the iterator.
430    typedef typename Map::ConstValueType ConstValueType;
431    /// The const reference type of the iterator.
432    typedef typename Map::ConstReferenceType ConstReferenceType;
433    /// The pointer type of the iterator.
434    typedef typename Map::ConstPointerType ConstPointerType;
435
436  private:
437
438    const Map* map;
439
440  public:
441
442    /// Default constructor.
443    MapConstValueIterator() {}
444
445    /// Constructor to create const iterator from a non const.
446    MapConstValueIterator(const MapValueIterator<Map>& pit) {
447      Base::it = pit.Base::it;
448      map = pit.map;
449    }
450
451    /// Map and KeyIt initialized iterator.
452    MapConstValueIterator(const Map& pmap, const KeyIt& pit)
453      : Base(pit), map(&pmap) {}
454
455    /// The pre increment operator of the iterator.
456    MapConstValueIterator& operator++() {
457      Base::increment();
458      return *this;
459    }
460
461    /// The post increment operator of the iterator.
462    MapConstValueIterator operator++(int) {
463      MapConstValueIterator tmp(*this);
464      Base::increment();
465      return tmp;
466    }
467
468    /// The dereferencing operator of the iterator.
469    ConstReferenceType operator*() const {
470      return (*map)[Base::it];
471    }
472
473    /// The arrow operator of the iterator.
474    ConstPointerType operator->() const {
475      return &(operator*());
476    }
477
478  public:
479    // STL  compatibility typedefs.
480    typedef std::input_iterator_tag iterator_category;
481    typedef int difference_type;
482    typedef ValueType value_type;
483    typedef ConstReferenceType reference;
484    typedef ConstPointerType pointer;
485  };
486
487
488  /** This class makes from a map an iteratable set
489   *  which contains all the keys of the map.
490   */
491  template <typename Map>
492  class MapConstKeySet {
493
494    const Map* map;
495
496  public:
497
498    /// The key type of the iterator.
499    typedef typename Map::KeyType KeyType;
500    /// The iterator to iterate on the keys.
501    typedef typename Map::KeyIt KeyIt;
502
503
504    /// The value type of the iterator.
505    typedef typename Map::ValueType ValueType;
506    /// The reference type of the iterator.
507    typedef typename Map::ReferenceType ReferenceType;
508    /// The pointer type of the iterator.
509    typedef typename Map::PointerType PointerType;
510
511    /// The const value type of the iterator.
512    typedef typename Map::ConstValueType ConstValueType;
513    /// The const reference type of the iterator.
514    typedef typename Map::ConstReferenceType ConstReferenceType;
515    /// The pointer type of the iterator.
516    typedef typename Map::ConstPointerType ConstPointerType;
517
518    /// The map initialized const key set.
519    MapConstKeySet(const Map& pmap) : map(&pmap) {}
520
521    /// The const iterator of the set.
522    typedef MapKeyIterator<Map> ConstIterator;
523
524    /// It gives back the const iterator pointed to the first element.
525    ConstIterator begin() const {
526      return ConstIterator(KeyIt(*map->getGraph()));
527    }
528           
529    /// It gives back the const iterator pointed to the first ivalid element.
530    ConstIterator end() const {
531      return ConstIterator(KeyIt(INVALID));
532    }
533 
534  public:
535    // STL  compatibility typedefs.
536    typedef ValueType value_type;
537    typedef ConstIterator const_iterator;
538    typedef ConstReferenceType const_reference;
539    typedef ConstPointerType const_pointer;
540    typedef int difference_type;
541  };
542
543  /** This class makes from a map an iteratable set
544   *  which contains all the values of the map.
545   *  The values cannot be modified.
546   */
547  template <typename Map>
548  class MapConstValueSet {
549
550    const Map* map;
551
552  public:
553
554    /// The key type of the iterator.
555    typedef typename Map::KeyType KeyType;
556    /// The iterator to iterate on the keys.
557    typedef typename Map::KeyIt KeyIt;
558
559
560    /// The value type of the iterator.
561    typedef typename Map::ValueType ValueType;
562    /// The reference type of the iterator.
563    typedef typename Map::ReferenceType ReferenceType;
564    /// The pointer type of the iterator.
565    typedef typename Map::PointerType PointerType;
566
567    /// The const value type of the iterator.
568    typedef typename Map::ConstValueType ConstValueType;
569    /// The const reference type of the iterator.
570    typedef typename Map::ConstReferenceType ConstReferenceType;
571    /// The pointer type of the iterator.
572    typedef typename Map::ConstPointerType ConstPointerType;
573
574    /// The map initialized const value set.
575    MapConstValueSet(const Map& pmap) : map(&pmap) {}
576
577    /// The const iterator of the set.
578    typedef MapConstValueIterator<Map> ConstIterator;
579
580    /// It gives back the const iterator pointed to the first element.
581    ConstIterator begin() const {
582      return ConstIterator(*map, KeyIt(*map->getGraph()));
583    }
584
585    /// It gives back the const iterator pointed to the first invalid element.
586    ConstIterator end() const {
587      return ConstIterator(*map, KeyIt(INVALID));
588    }
589
590  public:
591    // STL  compatibility typedefs.
592    typedef ValueType value_type;
593    typedef ConstIterator const_iterator;
594    typedef ConstReferenceType const_reference;
595    typedef ConstPointerType const_pointer;
596    typedef int difference_type;
597  };
598
599
600  /** This class makes from a map an iteratable set
601   *  which contains all the values of the map.
602   *  The values can be modified.
603   */
604  template <typename Map>
605  class MapValueSet {
606
607    Map* map;
608
609  public:
610
611    /// The key type of the iterator.
612    typedef typename Map::KeyType KeyType;
613    /// The iterator to iterate on the keys.
614    typedef typename Map::KeyIt KeyIt;
615
616
617    /// The value type of the iterator.
618    typedef typename Map::ValueType ValueType;
619    /// The reference type of the iterator.
620    typedef typename Map::ReferenceType ReferenceType;
621    /// The pointer type of the iterator.
622    typedef typename Map::PointerType PointerType;
623
624    /// The const value type of the iterator.
625    typedef typename Map::ConstValueType ConstValueType;
626    /// The const reference type of the iterator.
627    typedef typename Map::ConstReferenceType ConstReferenceType;
628    /// The pointer type of the iterator.
629    typedef typename Map::ConstPointerType ConstPointerType;
630
631    /// The map initialized value set.
632    MapValueSet(Map& pmap) : map(&pmap) {}
633
634    /// The const iterator of the set.
635    typedef MapConstValueIterator<Map> ConstIterator;
636
637    /// It gives back the const iterator pointed to the first element.
638    ConstIterator begin() const {
639      return ConstIterator(*map, KeyIt(*map->getGraph()));
640    }
641
642    /// It gives back the const iterator pointed to the first invalid element.
643    ConstIterator end() const {
644      return ConstIterator(*map, KeyIt(INVALID));
645    }
646
647    /// The iterator of the set.
648    typedef MapValueIterator<Map> Iterator;
649
650    /// It gives back the iterator pointed to the first element.
651    Iterator begin() {
652      return Iterator(*map, KeyIt(*map->getGraph()));
653    }
654
655    /// It gives back the iterator pointed to the first invalid element.
656    Iterator end() {
657      return Iterator(*map, KeyIt(INVALID));
658    }
659           
660  public:
661    // STL  compatibility typedefs.
662    typedef ValueType value_type;
663    typedef Iterator iterator;
664    typedef ConstIterator const_iterator;
665    typedef ReferenceType reference;
666    typedef ConstReferenceType const_reference;
667    typedef PointerType pointer;
668    typedef ConstPointerType const_pointer;
669    typedef int difference_type;
670
671  };
672
673  /// @}
674
675}
676
677#endif
Note: See TracBrowser for help on using the repository browser.