COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/map_iterator.h @ 1719:674182524bd9

Last change on this file since 1719:674182524bd9 was 1719:674182524bd9, checked in by Balazs Dezso, 14 years ago

Traits moved to own file
Tag for reference maps
Possibility to handle proper the return type
of the operator[]() const -- value or reference

File size: 20.9 KB
Line 
1/* -*- C++ -*-
2 * lemon/map_iterator.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, 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/bits/extended_pair.h>
23#include <lemon/graph_utils.h>
24
25///\ingroup graphmapfactory
26///\file
27///\brief Iterators on the maps.
28
29namespace lemon {
30
31  /// \addtogroup graphmapfactory
32  /// @{
33
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.
37   */
38
39  template <
40    typename _Graph,
41    typename _Item>
42  class MapIteratorBase {
43
44  protected:
45
46    /// The key type of the iterator.
47    typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
48
49    ItemIt it;
50
51    /// Default constructor.
52    MapIteratorBase() {}
53
54    /// ItemIt initialized MapIteratorBase constructor.
55    MapIteratorBase(const ItemIt _it) : it(_it) {}
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& _it) const {
66      return _it.it == it;
67    }
68       
69    /// The not-equality operator of the map.
70    bool operator!=(const MapIteratorBase& _it) const {
71      return !(*this == _it);
72    }
73  };
74
75
76  template <
77    typename _Graph,
78    typename _Item,
79    typename _Map>
80  class MapConstIterator;
81
82  /** Compatible iterator with the stl maps' iterators.
83   * It iterates on pairs of a key and a value.
84   */
85  template <
86    typename _Graph,
87    typename _Item,
88    typename _Map>
89  class MapIterator : public MapIteratorBase<_Graph, _Item> {
90
91    friend class MapConstIterator<_Graph, _Item, _Map>;
92
93
94  public:
95
96    /// The iterator base class.
97    typedef MapIteratorBase<_Graph, _Item> Parent;
98
99    typedef _Item Item;
100    typedef _Map Map;
101    typedef _Graph Graph;
102
103  protected:
104
105    typedef typename Parent::ItemIt ItemIt;
106
107    typedef typename _Map::Value MapValue;
108    typedef typename _Map::Reference MapReference;
109   
110  public:
111
112    /// The value type of the iterator.
113    typedef extended_pair<Item, const Item&,
114      MapValue, const MapValue&> Value;
115
116    /// The reference type of the iterator.
117    typedef extended_pair<const Item&, const Item&,
118      MapReference, MapReference> Reference;
119
120    /// Default constructor.
121    MapIterator() {}
122
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) {}
127
128    /// Dereference operator for the iterator.
129    Reference operator*() {
130      return Reference(Parent::it, (*map)[Parent::it]);
131    }
132
133    /// The pointer type of the iterator.
134    class Pointer {
135      friend class MapIterator;
136    protected:
137      Reference data;
138      Pointer(const Item& item, MapReference val)
139        : data(item, val) {}
140    public:
141      Reference* operator->() {return &data;}
142    };
143
144    /// Arrow operator for the iterator.
145    Pointer operator->() {
146      return Pointer(Parent::it, (*map)[Parent::it]);
147    }
148       
149    /// The pre increment operator of the iterator.
150    MapIterator& operator++() {
151      Parent::increment();
152      return *this;
153    }
154
155    /// The post increment operator of the iterator.
156    MapIterator operator++(int) {
157      MapIterator tmp(*this);
158      Parent::increment();
159      return tmp;
160    }
161
162  protected:
163
164    Map* map;
165
166  public:
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;
173  };
174
175  /** Compatible iterator with the stl maps' iterators.
176   *  It iterates on pairs of a key and a value.
177   */
178  template <
179    typename _Graph,
180    typename _Item,
181    typename _Map>
182  class MapConstIterator : public MapIteratorBase<_Graph, _Item> {
183
184  public:
185
186    /// The iterator base class.
187    typedef MapIteratorBase<_Graph, _Item> Parent;
188
189    typedef _Graph Graph;
190    typedef _Item Item;
191    typedef _Map Map;
192
193  protected:
194
195    typedef typename Parent::ItemIt ItemIt;
196
197    typedef typename _Map::Value MapValue;
198    typedef typename _Map::ConstReference MapReference;
199   
200  public:
201
202    /// The value type of the iterator.
203    typedef extended_pair<Item, const Item&,
204      MapValue, const MapValue&> Value;
205
206    /// The reference type of the iterator.
207    typedef extended_pair<const Item&, const Item&,
208      MapReference, MapReference> Reference;
209
210    /// Default constructor.
211    MapConstIterator() {}
212
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) {}
217
218    /// Dereference operator for the iterator.
219    Reference operator*() {
220      return Reference(Parent::it, (*map)[Parent::it]);
221    }
222
223    /// The pointer type of the iterator.
224    class Pointer {
225      friend class MapConstIterator;
226    protected:
227      Reference data;
228      Pointer(const Item& item, MapReference val)
229        : data(item, val) {}
230    public:
231      Reference* operator->() {return &data;}
232    };
233
234    /// Arrow operator for the iterator.
235    Pointer operator->() {
236      return Pointer(Parent::it, ((*map)[Parent::it]));
237    }
238       
239    /// The pre increment operator of the iterator.
240    MapConstIterator& operator++() {
241      Parent::increment();
242      return *this;
243    }
244
245    /// The post increment operator of the iterator.
246    MapConstIterator operator++(int) {
247      MapConstIterator tmp(*this);
248      Parent::increment();
249      return tmp;
250    }
251
252  protected:
253    const Map* map;
254
255  public:
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;
262  };
263 
264  /** The class makes the ItemIt to an stl compatible iterator
265   *  with dereferencing operator.
266   */
267  template <
268    typename _Graph,
269    typename _Item>
270  class MapConstKeyIterator : public MapIteratorBase<_Graph, _Item> {
271
272  public:
273
274    /// The iterator base class.
275    typedef MapIteratorBase<_Graph, _Item> Parent;
276 
277    typedef _Graph Graph;
278    typedef _Item Item;
279
280  protected:
281    /// The iterator to iterate on the keys.
282    typedef typename Parent::ItemIt ItemIt;
283
284  public:
285
286    typedef Item Value;
287    typedef const Item& Reference;
288    typedef const Item* Pointer;
289
290    /// Default constructor.
291    MapConstKeyIterator() {}
292
293    /// ItemIt initialized iterator.
294    MapConstKeyIterator(const ItemIt& pit) : Parent(pit) {}
295
296    /// The pre increment operator of the iterator.
297    MapConstKeyIterator& operator++() {
298      Parent::increment();
299      return *this;
300    }
301
302    /// The post increment operator of the iterator.
303    MapConstKeyIterator operator++(int) {
304      MapConstKeyIterator tmp(*this);
305      Parent::increment();
306      return tmp;
307    }
308
309    /// The dereferencing operator of the iterator.
310    Item operator*() const {
311      return static_cast<Item>(Parent::it);
312    }
313
314  public:
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;
321  };
322
323  template <
324    typename _Graph,
325    typename _Item,
326    typename _Map>
327  class MapConstValueIterator;
328
329  /** MapValueIterator creates an stl compatible iterator
330   *  for the values.
331   */
332  template <
333    typename _Graph,
334    typename _Item,
335    typename _Map>
336  class MapValueIterator : public MapIteratorBase<_Graph, _Item> {
337
338    friend class MapConstValueIterator<_Graph, _Item, _Map>;
339
340  public:
341
342    /// The iterator base class.
343    typedef MapIteratorBase<_Graph, _Item> Parent;
344
345    typedef _Graph Graph;
346    typedef _Item Item;
347    typedef _Map Map;
348
349  protected:
350
351    /// The iterator to iterate on the keys.
352    typedef typename Parent::ItemIt ItemIt;
353
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;
360
361  public:
362
363    typedef MapValue Value;
364    typedef MapReference Reference;
365    typedef MapPointer Pointer;
366
367    /// Default constructor.
368    MapValueIterator() {}
369
370    /// Map and ItemIt initialized iterator.
371    MapValueIterator(Map& _map, const ItemIt& _it)
372      : Parent(_it), map(&_map) {}
373   
374
375    /// The pre increment operator of the iterator.
376    MapValueIterator& operator++() {
377      Parent::increment();
378      return *this;
379    }
380
381    /// The post increment operator of the iterator.
382    MapValueIterator operator++(int) {
383      MapValueIterator tmp(*this);
384      Parent::increment();
385      return tmp;
386    }
387
388    /// The dereferencing operator of the iterator.
389    Reference operator*() const {
390      return (*map)[Parent::it];
391    }
392
393    /// The arrow operator of the iterator.
394    Pointer operator->() const {
395      return &(operator*());
396    }
397
398  protected:
399
400    Map* map;
401
402  public:
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;
409  };
410
411  /** MapValueIterator creates an stl compatible iterator
412   *  for the values.
413   */
414  template <
415    typename _Graph,
416    typename _Item,
417    typename _Map>
418  class MapConstValueIterator : public MapIteratorBase<_Graph, _Item> {
419
420  public:
421
422    /// The iterator base class.
423    typedef MapIteratorBase<_Graph, _Item> Parent;
424
425    typedef _Graph Graph;
426    typedef _Item Item;
427    typedef _Map Map;
428
429  protected:
430
431    /// The iterator to iterate on the keys.
432    typedef typename Parent::ItemIt ItemIt;
433
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;
440
441  public:
442
443    typedef MapValue Value;
444    typedef MapReference Reference;
445    typedef MapPointer Pointer;
446
447    /// Default constructor.
448    MapConstValueIterator() {}
449
450    /// Map and ItemIt initialized iterator.
451    MapConstValueIterator(const Map& _map, const ItemIt& _it)
452      : Parent(_it), map(&_map) {}
453   
454
455    /// The pre increment operator of the iterator.
456    MapConstValueIterator& operator++() {
457      Parent::increment();
458      return *this;
459    }
460
461    /// The post increment operator of the iterator.
462    MapConstValueIterator operator++(int) {
463      MapConstValueIterator tmp(*this);
464      Parent::increment();
465      return tmp;
466    }
467
468    /// The dereferencing operator of the iterator.
469    Reference operator*() const {
470      return (*map)[Parent::it];
471    }
472
473    /// The arrow operator of the iterator.
474    Pointer operator->() const {
475      return &(operator*());
476    }
477
478  protected:
479
480    const Map* map;
481
482  public:
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;
489  };
490
491
492  /** This class makes from a map an iteratable set
493   *  which contains all the keys of the map.
494   */
495  template <typename _Graph, typename _Item>
496  class MapConstKeySet {
497
498  public:
499
500    typedef _Graph Graph;
501    /// The key type of the iterator.
502    typedef _Item Item;
503    /// The iterator to iterate on the keys.
504
505  protected:
506
507    typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
508
509  public:
510
511    /// The map initialized const key set.
512    MapConstKeySet(const Graph& _graph) : graph(&_graph) {}
513
514    /// The const iterator of the set.
515    typedef MapConstKeyIterator<_Graph, _Item> ConstIterator;
516
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;
522
523    /// It gives back the const iterator pointed to the first element.
524    ConstIterator begin() const {
525      return ConstIterator(ItemIt(*graph));
526    }
527           
528    /// It gives back the const iterator pointed to the first ivalid element.
529    ConstIterator end() const {
530      return ConstIterator(ItemIt(INVALID));
531    }
532
533  protected:
534
535    const Graph* graph;
536 
537  public:
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;
544  };
545
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.
549   */
550  template <typename _Graph, typename _Item, typename _Map>
551  class MapConstValueSet {
552
553  public:
554   
555    typedef _Graph Graph;
556    typedef _Item Item;
557    typedef _Map Map;
558
559  protected:
560
561    /// The iterator to iterate on the keys.
562    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
563
564  public:
565
566    /// The map initialized const value set.
567    MapConstValueSet(const Graph& _graph, const Map& _map)
568      : graph(&_graph), map(&_map) {}
569
570    /// The const iterator of the set.
571    typedef MapConstValueIterator<_Graph, _Item, _Map> ConstIterator;
572
573    typedef typename ConstIterator::Value Value;
574    typedef typename ConstIterator::Reference ConstReference;
575    typedef typename ConstIterator::Pointer ConstPointer;
576
577    /// It gives back the const iterator pointed to the first element.
578    ConstIterator begin() const {
579      return ConstIterator(*map, ItemIt(*graph));
580    }
581
582    /// It gives back the const iterator pointed to the first invalid element.
583    ConstIterator end() const {
584      return ConstIterator(*map, ItemIt(INVALID));
585    }
586
587  protected:
588   
589    const Map* map;
590    const Graph * graph;
591
592  public:
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;
599  };
600
601
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.
605   */
606  template <typename _Graph, typename _Item, typename _Map>
607  class MapValueSet {
608
609  public:
610   
611    typedef _Graph Graph;
612    typedef _Item Item;
613    typedef _Map Map;
614
615  protected:
616
617    /// The iterator to iterate on the keys.
618    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
619
620  public:
621
622    /// The map initialized const value set.
623    MapValueSet(const Graph& _graph, Map& _map)
624      : map(&_map), graph(&_graph) {}
625
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;
630
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;
636
637    /// It gives back the const iterator pointed to the first element.
638    ConstIterator begin() const {
639      return ConstIterator(*map, ItemIt(*graph));
640    }
641
642    /// It gives back the const iterator pointed to the first invalid element.
643    ConstIterator end() const {
644      return ConstIterator(*map, ItemIt(INVALID));
645    }
646
647    /// It gives back the iterator pointed to the first element.
648    Iterator begin() {
649      return Iterator(*map, ItemIt(*graph));
650    }
651
652    /// It gives back the iterator pointed to the first invalid element.
653    Iterator end() {
654      return Iterator(*map, ItemIt(INVALID));
655    }
656
657  protected:
658   
659    Map* map;
660    const Graph * graph;
661
662  public:
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;
672
673  };
674
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.
678   */
679  template <
680    typename _Graph,
681    typename _Item,
682    typename _Map
683    >
684  class MapSet {
685  public:   
686
687    typedef _Graph Graph;
688    typedef _Item Item;
689    typedef _Map Map;
690
691  protected:
692
693    typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
694
695  public:
696
697    /// The map initialized value set.
698    MapSet(const Graph& _graph, Map& _map) : graph(&_graph), map(&_map) {}
699
700    /// The const iterator of the set.
701    typedef MapIterator<_Graph, _Item, _Map> Iterator;
702    typedef MapConstIterator<_Graph, _Item, _Map> ConstIterator;
703
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;
709
710
711    /// It gives back the const iterator pointed to the first element.
712    ConstIterator begin() const {
713      return ConstIterator(*map, ItemIt(*graph));
714    }
715
716    /// It gives back the const iterator pointed to the first invalid element.
717    ConstIterator end() const {
718      return ConstIterator(*map, ItemIt(INVALID));
719    }
720
721    /// The iterator of the set.
722
723    /// It gives back the iterator pointed to the first element.
724    Iterator begin() {
725      return Iterator(*map, ItemIt(*graph));
726    }
727
728    /// It gives back the iterator pointed to the first invalid element.
729    Iterator end() {
730      return Iterator(*map, ItemIt(INVALID));
731    }
732
733  protected:
734   
735    const Graph* graph;
736    Map* map;
737           
738  public:
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;
748
749  };
750
751  template <
752    typename _Graph,
753    typename _Item,
754    typename _Map
755    >
756  class ConstMapSet {
757   
758    typedef _Graph Graph;
759    typedef _Map Map;
760
761    const Graph* graph;
762    const Map* map;
763
764  public:
765
766    typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
767
768
769    /// The map initialized value set.
770    ConstMapSet(const Graph& _graph, const Map& _map)
771      : graph(&_graph), map(&_map) {}
772
773    /// The const iterator of the set.
774    typedef MapConstIterator<_Graph, _Item, _Map> ConstIterator;
775
776    typedef typename ConstIterator::Value Value;
777    typedef typename ConstIterator::Reference ConstReference;
778    typedef typename ConstIterator::Pointer ConstPointer;
779
780
781    /// It gives back the const iterator pointed to the first element.
782    ConstIterator begin() const {
783      return ConstIterator(*map, ItemIt(*graph));
784    }
785
786    /// It gives back the const iterator pointed to the first invalid element.
787    ConstIterator end() const {
788      return ConstIterator(*map, ItemIt(INVALID));
789    }
790           
791  public:
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;
798
799  };
800
801  template <typename _Map>
802  class IterableMapExtender : public _Map {
803  public:
804
805    typedef _Map Parent;
806    typedef Parent Map;
807    typedef typename Map::Graph Graph;
808    typedef typename Map::Key Item;
809    typedef typename Map::Value Value;
810
811    typedef MapSet<Graph, Item, Map> MapSet;
812
813    IterableMapExtender() : Parent() {}
814
815    IterableMapExtender(const Graph& graph) : Parent(graph) {}
816
817    IterableMapExtender(const Graph& graph, const Value& value)
818      : Parent(graph, value) {}
819
820    MapSet mapSet() {
821      return MapSet(*Parent::getGraph(), *this);
822    }
823
824    typedef ConstMapSet<Graph, Item, Map> ConstMapSet;
825
826    ConstMapSet mapSet() const {
827      return ConstMapSet(*Parent::getGraph(), *this);
828    }
829
830    typedef MapConstKeySet<Graph, Item> ConstKeySet;
831 
832    ConstKeySet keySet() const {
833      return ConstKeySet(*Parent::getGraph());
834    }
835
836    typedef MapValueSet<Graph, Item, Map> ValueSet;
837 
838    ValueSet valueSet() {
839      return ValueSet(*Parent::getGraph(), *this);
840    }
841
842    typedef MapConstValueSet<Graph, Item, Map> ConstValueSet;
843 
844    ConstValueSet valueSet() const {
845      return ConstValueSet(*Parent::getGraph(), *this);
846    }
847
848  };
849
850  /// @}
851
852}
853
854#endif
Note: See TracBrowser for help on using the repository browser.