COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/bits/map_iterator.h @ 1359:1581f961cfaa

Last change on this file since 1359:1581f961cfaa was 1359:1581f961cfaa, checked in by Alpar Juttner, 15 years ago

Correct the english name of EGRES.

File size: 21.1 KB
Line 
1/* -*- C++ -*-
2 * src/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/map_utils.h>
24
25///\ingroup graphmaps
26///\file
27///\brief Iterators on the maps.
28
29namespace lemon {
30
31  /// \addtogroup graphmaps
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 ReferenceMapTraits<_Map>::Value MapValue;
108    typedef typename ReferenceMapTraits<_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 ReferenceMapTraits<_Map>::Value MapValue;
198    typedef typename ReferenceMapTraits<_Map>::ConstReference
199    MapReference;
200   
201  public:
202
203    /// The value type of the iterator.
204    typedef extended_pair<Item, const Item&,
205      MapValue, const MapValue&> Value;
206
207    /// The reference type of the iterator.
208    typedef extended_pair<const Item&, const Item&,
209      MapReference, MapReference> Reference;
210
211    /// Default constructor.
212    MapConstIterator() {}
213
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) {}
218
219    /// Dereference operator for the iterator.
220    Reference operator*() {
221      return Reference(Parent::it, (*map)[Parent::it]);
222    }
223
224    /// The pointer type of the iterator.
225    class Pointer {
226      friend class MapConstIterator;
227    protected:
228      Reference data;
229      Pointer(const Item& item, MapReference val)
230        : data(item, val) {}
231    public:
232      Reference* operator->() {return &data;}
233    };
234
235    /// Arrow operator for the iterator.
236    Pointer operator->() {
237      return Pointer(Parent::it, ((*map)[Parent::it]));
238    }
239       
240    /// The pre increment operator of the iterator.
241    MapConstIterator& operator++() {
242      Parent::increment();
243      return *this;
244    }
245
246    /// The post increment operator of the iterator.
247    MapConstIterator operator++(int) {
248      MapConstIterator tmp(*this);
249      Parent::increment();
250      return tmp;
251    }
252
253  protected:
254    const Map* map;
255
256  public:
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;
263  };
264 
265  /** The class makes the ItemIt to an stl compatible iterator
266   *  with dereferencing operator.
267   */
268  template <
269    typename _Graph,
270    typename _Item>
271  class MapConstKeyIterator : public MapIteratorBase<_Graph, _Item> {
272
273  public:
274
275    /// The iterator base class.
276    typedef MapIteratorBase<_Graph, _Item> Parent;
277 
278    typedef _Graph Graph;
279    typedef _Item Item;
280
281  protected:
282    /// The iterator to iterate on the keys.
283    typedef typename Parent::ItemIt ItemIt;
284
285  public:
286
287    typedef Item Value;
288    typedef const Item& Reference;
289    typedef const Item* Pointer;
290
291    /// Default constructor.
292    MapConstKeyIterator() {}
293
294    /// ItemIt initialized iterator.
295    MapConstKeyIterator(const ItemIt& pit) : Parent(pit) {}
296
297    /// The pre increment operator of the iterator.
298    MapConstKeyIterator& operator++() {
299      Parent::increment();
300      return *this;
301    }
302
303    /// The post increment operator of the iterator.
304    MapConstKeyIterator operator++(int) {
305      MapConstKeyIterator tmp(*this);
306      Parent::increment();
307      return tmp;
308    }
309
310    /// The dereferencing operator of the iterator.
311    Item operator*() const {
312      return static_cast<Item>(Parent::it);
313    }
314
315  public:
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;
322  };
323
324  template <
325    typename _Graph,
326    typename _Item,
327    typename _Map>
328  class MapConstValueIterator;
329
330  /** MapValueIterator creates an stl compatible iterator
331   *  for the values.
332   */
333  template <
334    typename _Graph,
335    typename _Item,
336    typename _Map>
337  class MapValueIterator : public MapIteratorBase<_Graph, _Item> {
338
339    friend class MapConstValueIterator<_Graph, _Item, _Map>;
340
341  public:
342
343    /// The iterator base class.
344    typedef MapIteratorBase<_Graph, _Item> Parent;
345
346    typedef _Graph Graph;
347    typedef _Item Item;
348    typedef _Map Map;
349
350  protected:
351
352    /// The iterator to iterate on the keys.
353    typedef typename Parent::ItemIt ItemIt;
354
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;
361
362  public:
363
364    typedef MapValue Value;
365    typedef MapReference Reference;
366    typedef MapPointer Pointer;
367
368    /// Default constructor.
369    MapValueIterator() {}
370
371    /// Map and ItemIt initialized iterator.
372    MapValueIterator(Map& _map, const ItemIt& _it)
373      : Parent(_it), map(&_map) {}
374   
375
376    /// The pre increment operator of the iterator.
377    MapValueIterator& operator++() {
378      Parent::increment();
379      return *this;
380    }
381
382    /// The post increment operator of the iterator.
383    MapValueIterator operator++(int) {
384      MapValueIterator tmp(*this);
385      Parent::increment();
386      return tmp;
387    }
388
389    /// The dereferencing operator of the iterator.
390    Reference operator*() const {
391      return (*map)[Parent::it];
392    }
393
394    /// The arrow operator of the iterator.
395    Pointer operator->() const {
396      return &(operator*());
397    }
398
399  protected:
400
401    Map* map;
402
403  public:
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;
410  };
411
412  /** MapValueIterator creates an stl compatible iterator
413   *  for the values.
414   */
415  template <
416    typename _Graph,
417    typename _Item,
418    typename _Map>
419  class MapConstValueIterator : public MapIteratorBase<_Graph, _Item> {
420
421  public:
422
423    /// The iterator base class.
424    typedef MapIteratorBase<_Graph, _Item> Parent;
425
426    typedef _Graph Graph;
427    typedef _Item Item;
428    typedef _Map Map;
429
430  protected:
431
432    /// The iterator to iterate on the keys.
433    typedef typename Parent::ItemIt ItemIt;
434
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;
441
442  public:
443
444    typedef MapValue Value;
445    typedef MapReference Reference;
446    typedef MapPointer Pointer;
447
448    /// Default constructor.
449    MapConstValueIterator() {}
450
451    /// Map and ItemIt initialized iterator.
452    MapConstValueIterator(const Map& _map, const ItemIt& _it)
453      : Parent(_it), map(&_map) {}
454   
455
456    /// The pre increment operator of the iterator.
457    MapConstValueIterator& operator++() {
458      Parent::increment();
459      return *this;
460    }
461
462    /// The post increment operator of the iterator.
463    MapConstValueIterator operator++(int) {
464      MapConstValueIterator tmp(*this);
465      Parent::increment();
466      return tmp;
467    }
468
469    /// The dereferencing operator of the iterator.
470    Reference operator*() const {
471      return (*map)[Parent::it];
472    }
473
474    /// The arrow operator of the iterator.
475    Pointer operator->() const {
476      return &(operator*());
477    }
478
479  protected:
480
481    const Map* map;
482
483  public:
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;
490  };
491
492
493  /** This class makes from a map an iteratable set
494   *  which contains all the keys of the map.
495   */
496  template <typename _Graph, typename _Item>
497  class MapConstKeySet {
498
499  public:
500
501    typedef _Graph Graph;
502    /// The key type of the iterator.
503    typedef _Item Item;
504    /// The iterator to iterate on the keys.
505
506  protected:
507
508    typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
509
510  public:
511
512    /// The map initialized const key set.
513    MapConstKeySet(const Graph& _graph) : graph(&_graph) {}
514
515    /// The const iterator of the set.
516    typedef MapConstKeyIterator<_Graph, _Item> ConstIterator;
517
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;
523
524    /// It gives back the const iterator pointed to the first element.
525    ConstIterator begin() const {
526      return ConstIterator(ItemIt(*graph));
527    }
528           
529    /// It gives back the const iterator pointed to the first ivalid element.
530    ConstIterator end() const {
531      return ConstIterator(ItemIt(INVALID));
532    }
533
534  protected:
535
536    const Graph* graph;
537 
538  public:
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;
545  };
546
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.
550   */
551  template <typename _Graph, typename _Item, typename _Map>
552  class MapConstValueSet {
553
554  public:
555   
556    typedef _Graph Graph;
557    typedef _Item Item;
558    typedef _Map Map;
559
560  protected:
561
562    /// The iterator to iterate on the keys.
563    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
564
565  public:
566
567    /// The map initialized const value set.
568    MapConstValueSet(const Graph& _graph, const Map& _map)
569      : graph(&_graph), map(&_map) {}
570
571    /// The const iterator of the set.
572    typedef MapConstValueIterator<_Graph, _Item, _Map> ConstIterator;
573
574    typedef typename ConstIterator::Value Value;
575    typedef typename ConstIterator::Reference ConstReference;
576    typedef typename ConstIterator::Pointer ConstPointer;
577
578    /// It gives back the const iterator pointed to the first element.
579    ConstIterator begin() const {
580      return ConstIterator(*map, ItemIt(*graph));
581    }
582
583    /// It gives back the const iterator pointed to the first invalid element.
584    ConstIterator end() const {
585      return ConstIterator(*map, ItemIt(INVALID));
586    }
587
588  protected:
589   
590    const Map* map;
591    const Graph * graph;
592
593  public:
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;
600  };
601
602
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.
606   */
607  template <typename _Graph, typename _Item, typename _Map>
608  class MapValueSet {
609
610  public:
611   
612    typedef _Graph Graph;
613    typedef _Item Item;
614    typedef _Map Map;
615
616  protected:
617
618    /// The iterator to iterate on the keys.
619    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
620
621  public:
622
623    /// The map initialized const value set.
624    MapValueSet(const Graph& _graph, Map& _map)
625      : map(&_map), graph(&_graph) {}
626
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;
631
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;
637
638    /// It gives back the const iterator pointed to the first element.
639    ConstIterator begin() const {
640      return ConstIterator(*map, ItemIt(*graph));
641    }
642
643    /// It gives back the const iterator pointed to the first invalid element.
644    ConstIterator end() const {
645      return ConstIterator(*map, ItemIt(INVALID));
646    }
647
648    /// It gives back the iterator pointed to the first element.
649    Iterator begin() {
650      return Iterator(*map, ItemIt(*graph));
651    }
652
653    /// It gives back the iterator pointed to the first invalid element.
654    Iterator end() {
655      return Iterator(*map, ItemIt(INVALID));
656    }
657
658  protected:
659   
660    Map* map;
661    const Graph * graph;
662
663  public:
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;
673
674  };
675
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.
679   */
680  template <
681    typename _Graph,
682    typename _Item,
683    typename _Map
684    >
685  class MapSet {
686  public:   
687
688    typedef _Graph Graph;
689    typedef _Item Item;
690    typedef _Map Map;
691
692  protected:
693
694    typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
695
696  public:
697
698    /// The map initialized value set.
699    MapSet(const Graph& _graph, Map& _map) : graph(&_graph), map(&_map) {}
700
701    /// The const iterator of the set.
702    typedef MapIterator<_Graph, _Item, _Map> Iterator;
703    typedef MapConstIterator<_Graph, _Item, _Map> ConstIterator;
704
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;
710
711
712    /// It gives back the const iterator pointed to the first element.
713    ConstIterator begin() const {
714      return ConstIterator(*map, ItemIt(*graph));
715    }
716
717    /// It gives back the const iterator pointed to the first invalid element.
718    ConstIterator end() const {
719      return ConstIterator(*map, ItemIt(INVALID));
720    }
721
722    /// The iterator of the set.
723
724    /// It gives back the iterator pointed to the first element.
725    Iterator begin() {
726      return Iterator(*map, ItemIt(*graph));
727    }
728
729    /// It gives back the iterator pointed to the first invalid element.
730    Iterator end() {
731      return Iterator(*map, ItemIt(INVALID));
732    }
733
734  protected:
735   
736    const Graph* graph;
737    Map* map;
738           
739  public:
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;
749
750  };
751
752  template <
753    typename _Graph,
754    typename _Item,
755    typename _Map
756    >
757  class ConstMapSet {
758   
759    typedef _Graph Graph;
760    typedef _Map Map;
761
762    const Graph* graph;
763    const Map* map;
764
765  public:
766
767    typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
768
769
770    /// The map initialized value set.
771    ConstMapSet(const Graph& _graph, const Map& _map)
772      : graph(&_graph), map(&_map) {}
773
774    /// The const iterator of the set.
775    typedef MapConstIterator<_Graph, _Item, _Map> ConstIterator;
776
777    typedef typename ConstIterator::Value Value;
778    typedef typename ConstIterator::Reference ConstReference;
779    typedef typename ConstIterator::Pointer ConstPointer;
780
781
782    /// It gives back the const iterator pointed to the first element.
783    ConstIterator begin() const {
784      return ConstIterator(*map, ItemIt(*graph));
785    }
786
787    /// It gives back the const iterator pointed to the first invalid element.
788    ConstIterator end() const {
789      return ConstIterator(*map, ItemIt(INVALID));
790    }
791           
792  public:
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;
799
800  };
801
802  template <typename _Map>
803  class IterableMapExtender : public _Map {
804  public:
805
806    typedef _Map Parent;
807    typedef Parent Map;
808    typedef typename Map::Graph Graph;
809    typedef typename Map::Key Item;
810    typedef typename Map::Value Value;
811
812    typedef MapSet<Graph, Item, Map> MapSet;
813
814    IterableMapExtender() : Parent() {}
815
816    IterableMapExtender(const Graph& graph) : Parent(graph) {}
817
818    IterableMapExtender(const Graph& graph, const Value& value)
819      : Parent(graph, value) {}
820
821    MapSet mapSet() {
822      return MapSet(*Parent::getGraph(), *this);
823    }
824
825    typedef ConstMapSet<Graph, Item, Map> ConstMapSet;
826
827    ConstMapSet mapSet() const {
828      return ConstMapSet(*Parent::getGraph(), *this);
829    }
830
831    typedef MapConstKeySet<Graph, Item> ConstKeySet;
832 
833    ConstKeySet keySet() const {
834      return ConstKeySet(*Parent::getGraph());
835    }
836
837    typedef MapValueSet<Graph, Item, Map> ValueSet;
838 
839    ValueSet valueSet() {
840      return ValueSet(*Parent::getGraph(), *this);
841    }
842
843    typedef MapConstValueSet<Graph, Item, Map> ConstValueSet;
844 
845    ConstValueSet valueSet() const {
846      return ConstValueSet(*Parent::getGraph(), *this);
847    }
848
849  };
850
851  /// @}
852
853}
854
855#endif
Note: See TracBrowser for help on using the repository browser.