COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/map_iterator.h @ 932:ade3cdb9b45d

Last change on this file since 932:ade3cdb9b45d was 921:818510fa3d99, checked in by Alpar Juttner, 16 years ago

hugo -> lemon

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