deba@822: // -*- c++ -*-
deba@822: #ifndef MAP_ITERATOR_H
deba@822: #define MAP_ITERATOR_H
deba@822: 
deba@822: #include <hugo/extended_pair.h>
deba@822: 
deba@830: ///\ingroup graphmaps
deba@830: ///\file
deba@830: ///\brief Iterators on the maps.
deba@830: 
deba@822: namespace hugo {
deba@822: 
deba@830:   /// \addtogroup graphmaps
deba@830:   /// @{
deba@830: 
deba@830:   /** The base class all of the map iterators.
deba@830:    *  The class defines the typedefs of the iterators,
deba@830:    *  simple step functions and equality operators.
deba@830:    */ 
deba@822: 
deba@822:   template <typename Map>
deba@830:   class MapIteratorBase {
deba@822: 
deba@830:   public:
deba@830:     /// The key type of the iterator.
deba@830:     typedef typename Map::KeyType KeyType;
deba@830:     /// The iterator to iterate on the keys.
deba@830:     typedef typename Map::KeyIt KeyIt;
deba@830: 
deba@830:     /// The value type of the iterator.
deba@830:     typedef typename Map::ValueType ValueType;
deba@830:     /// The reference type of the iterator.
deba@830:     typedef typename Map::ReferenceType ReferenceType;
deba@830:     /// The pointer type of the iterator.
deba@830:     typedef typename Map::PointerType PointerType;
deba@830: 
deba@830:     /// The const value type of the iterator.
deba@830:     typedef typename Map::ConstValueType ConstValueType;
deba@830:     /// The const reference type of the iterator.
deba@830:     typedef typename Map::ConstReferenceType ConstReferenceType;
deba@830:     /// The pointer type of the iterator.
deba@830:     typedef typename Map::ConstPointerType ConstPointerType;
deba@830: 
deba@830:   protected:
deba@830: 
deba@830:     KeyIt it;
deba@830: 
deba@830:     /// Default constructor.
deba@830:     MapIteratorBase() {}
deba@830: 
deba@830:     /// KeyIt initialized MapIteratorBase constructor.
deba@830:     MapIteratorBase(const KeyIt pit) : it(pit) {}
deba@830: 
deba@830:   public:
deba@830: 
deba@830:     /// Stepping forward in the map.   
deba@830:     void increment() { 
deba@830:       ++it; 
deba@830:     }
deba@830: 
deba@830:     /// The equality operator of the map.
deba@830:     bool operator==(const MapIteratorBase& pit) const {
deba@830:       return pit.it == it;
deba@830:     }
deba@830: 	
deba@830:     /// The not-equality operator of the map.
deba@830:     bool operator!=(const MapIteratorBase& pit) const {
deba@830:       return !(*this == pit);
deba@830:     }
deba@830:   };
deba@830: 
deba@830:   template <typename Map> class MapConstIterator;
deba@822: 
deba@822:   /** Compatible iterator with the stl maps' iterators.
deba@830:    * It iterates on pairs of a key and a value.
deba@822:    */
deba@822:   template <typename Map>  
deba@830:   class MapIterator : public MapIteratorBase<Map> {
deba@830: 
deba@822:     friend class MapConstIterator<Map>;
deba@822: 
deba@822:   public:
deba@822: 
deba@822:     /// The key type of the iterator.
deba@822:     typedef typename Map::KeyType KeyType;
deba@822:     /// The iterator to iterate on the keys.
deba@822:     typedef typename Map::KeyIt KeyIt;
deba@822: 
deba@822:     /// The value type of the iterator.
deba@822:     typedef typename Map::ValueType ValueType;
deba@822:     /// The reference type of the iterator.
deba@822:     typedef typename Map::ReferenceType ReferenceType;
deba@822:     /// The pointer type of the iterator.
deba@822:     typedef typename Map::PointerType PointerType;
deba@822: 
deba@822:     /// The const value type of the iterator.
deba@822:     typedef typename Map::ConstValueType ConstValueType;
deba@822:     /// The const reference type of the iterator.
deba@822:     typedef typename Map::ConstReferenceType ConstReferenceType;
deba@822:     /// The pointer type of the iterator.
deba@822:     typedef typename Map::ConstPointerType ConstPointerType;
deba@822:     
deba@822:   public:
deba@822: 
deba@830:     /// The reference type of the iterator. 
deba@822:     typedef extended_pair<const KeyType&, const KeyType&, 
deba@822:       ReferenceType, ReferenceType> PairReferenceType;
deba@822: 
deba@830:     /// Default constructor. 
deba@830:     MapIterator() {}
deba@830: 
deba@830:     /// Constructor to initalize the iterators returned 
deba@830:     /// by the begin() and end().
deba@830:     MapIterator(Map& pmap, const KeyIt& pit) 
deba@830:       : MapIteratorBase<Map>(pit), map(&pmap) {}
deba@830: 
deba@830:     /// Dereference operator for the iterator.
deba@822:     PairReferenceType operator*() {
deba@822:       return PairReferenceType(it, (*map)[it]);
deba@822:     }
deba@822: 
deba@830:     /// The pointer type of the iterator.
deba@822:     class PairPointerType {
deba@822:       friend class MapIterator;
deba@822:     private:
deba@822:       PairReferenceType data;
deba@822:       PairPointerType(const KeyType& key, ReferenceType val) 
deba@822: 	: data(key, val) {}
deba@822:     public:
deba@822:       PairReferenceType* operator->() {return &data;}
deba@822:     };
deba@822: 
deba@830:     /// Arrow operator for the iterator.
deba@822:     PairPointerType operator->() {
deba@822:       return PairPointerType(it, ((*map)[it])); 
deba@822:     }
deba@830: 	
deba@830:     /// The pre increment operator of the iterator.
deba@822:     MapIterator& operator++() { 
deba@830:       increment(); 
deba@822:       return *this; 
deba@822:     }
deba@822: 
deba@830:     /// The post increment operator of the iterator.
deba@822:     MapIterator operator++(int) { 
deba@822:       MapIterator tmp(it); 
deba@830:       increment(); 
deba@822:       return tmp; 
deba@822:     }
deba@822: 
deba@822:   private:
deba@822:     Map* map;
deba@822:   };
deba@822: 
deba@822:   /** Compatible iterator with the stl maps' iterators.
deba@822:    *  It iterates on pairs of a key and a value.
deba@822:    */
deba@822:   template <typename Map>
deba@830:   class MapConstIterator : public MapIteratorBase<Map> {
deba@830:     
deba@822:   public:
deba@822: 
deba@822:     /// The key type of the iterator.
deba@822:     typedef typename Map::KeyType KeyType;
deba@822:     /// The iterator to iterate on the keys.
deba@822:     typedef typename Map::KeyIt KeyIt;
deba@822: 
deba@822:     /// The value type of the iterator.
deba@822:     typedef typename Map::ValueType ValueType;
deba@822:     /// The reference type of the iterator.
deba@822:     typedef typename Map::ReferenceType ReferenceType;
deba@822:     /// The pointer type of the iterator.
deba@822:     typedef typename Map::PointerType PointerType;
deba@822: 
deba@822:     /// The const value type of the iterator.
deba@822:     typedef typename Map::ConstValueType ConstValueType;
deba@822:     /// The const reference type of the iterator.
deba@822:     typedef typename Map::ConstReferenceType ConstReferenceType;
deba@822:     /// The pointer type of the iterator.
deba@822:     typedef typename Map::ConstPointerType ConstPointerType;
deba@822: 
deba@822:   public:    
deba@822: 
deba@830:     /// Default constructor. 
deba@822:     MapConstIterator() {}
deba@822: 
deba@830:     /// Constructor to initalize the the iterators returned
deba@830:     ///  by the begin() and end().
deba@830:     MapConstIterator(const Map& pmap, const KeyIt& pit) 
deba@830:       : MapIteratorBase<Map>(pit), map(&pmap) {}
deba@830: 
deba@830:     /// Constructor to create const iterator from a non const.
deba@830:     MapConstIterator(const MapIterator<Map>& pit) {
deba@830:       it = pit.it;
deba@830:       map = pit.map;
deba@830:     }
deba@830: 
deba@830:     /// The reference type of map.
deba@822:     typedef extended_pair<const KeyType&, const KeyType&, 
deba@822:       ConstReferenceType, ConstReferenceType> PairReferenceType;
deba@822: 
deba@830:     /// Dereference operator for the iterator.
deba@822:     PairReferenceType operator*() {
deba@822:       return PairReferenceType(it, (*map)[it]);
deba@822:     }
deba@822: 
deba@830:     /// The pointer type of the iterator.
deba@822:     class PairPointerType {
deba@822:       friend class MapConstIterator;
deba@822:     private:
deba@822:       PairReferenceType data;
deba@822:       PairPointerType(const KeyType& key, ConstReferenceType val) 
deba@822: 	: data(key, val) {}
deba@822:     public:
deba@822:       PairReferenceType* operator->() {return &data;}
deba@822:     };
deba@822: 
deba@830:     /// Arrow operator for the iterator.
deba@822:     PairPointerType operator->() {
deba@822:       return PairPointerType(it, ((*map)[it])); 
deba@822:     }
deba@822: 
deba@830:     /// The pre increment operator of the iterator.
deba@822:     MapConstIterator& operator++() { 
deba@830:       increment(); 
deba@822:       return *this; 
deba@822:     }
deba@822: 
deba@830:     /// The post increment operator of the iterator.
deba@822:     MapConstIterator operator++(int) { 
deba@822:       MapConstIterator<Map> tmp(it); 
deba@830:       increment(); 
deba@822:       return tmp; 
deba@822:     }
deba@822: 
deba@830:   private:
deba@830:     const Map* map;
deba@830:   };
deba@830: 
deba@830:   /** The class makes the KeyIt to an stl compatible iterator
deba@830:    *  with dereferencing operator.
deba@830:    */
deba@830:   template <typename Map>
deba@830:   class MapKeyIterator : public MapIteratorBase<Map> {
deba@830: 
deba@830:   public:
deba@830: 
deba@830:     /// The key type of the iterator.
deba@830:     typedef typename Map::KeyType KeyType;
deba@830:     /// The iterator to iterate on the keys.
deba@830:     typedef typename Map::KeyIt KeyIt;
deba@830: 
deba@830:   public:
deba@830: 
deba@830:     /// Default constructor.
deba@830:     MapKeyIterator() {}
deba@830: 
deba@830:     /// KeyIt initialized iterator.
deba@830:     MapKeyIterator(const KeyIt& pit) : MapIteratorBase<Map>(pit) {}
deba@830: 
deba@830:     /// The pre increment operator of the iterator.
deba@830:     MapKeyIterator& operator++() {
deba@830:       increment(); 
deba@830:       return *this; 
deba@822:     }
deba@822: 
deba@830:     /// The post increment operator of the iterator.
deba@830:     MapKeyIterator operator++(int) {
deba@830:       MapKeyIterator tmp(*this);
deba@830:       increment();
deba@830:       return tmp;
deba@822:     }
deba@830: 
deba@830:     /// The dereferencing operator of the iterator.
deba@830:     KeyType operator*() const {
deba@830:       return static_cast<KeyType>(it);
deba@822:     }
deba@830:   };
deba@830: 
deba@830:   template <typename Map> class MapConstValueIterator;
deba@830: 
deba@830:   template <typename Map>
deba@830:   class MapValueIterator : public MapIteratorBase<Map> {
deba@830: 
deba@830:     friend class MapConstValueIterator<Map>;
deba@830: 
deba@830:   public:
deba@830: 
deba@830:     /// The key type of the iterator.
deba@830:     typedef typename Map::KeyType KeyType;
deba@830:     /// The iterator to iterate on the keys.
deba@830:     typedef typename Map::KeyIt KeyIt;
deba@830: 
deba@830: 
deba@830:     /// The value type of the iterator.
deba@830:     typedef typename Map::ValueType ValueType;
deba@830:     /// The reference type of the iterator.
deba@830:     typedef typename Map::ReferenceType ReferenceType;
deba@830:     /// The pointer type of the iterator.
deba@830:     typedef typename Map::PointerType PointerType;
deba@830: 
deba@830:     /// The const value type of the iterator.
deba@830:     typedef typename Map::ConstValueType ConstValueType;
deba@830:     /// The const reference type of the iterator.
deba@830:     typedef typename Map::ConstReferenceType ConstReferenceType;
deba@830:     /// The pointer type of the iterator.
deba@830:     typedef typename Map::ConstPointerType ConstPointerType;
deba@830: 
deba@822:   private:
deba@830: 
deba@830:     Map* map;
deba@830: 
deba@830:   public:
deba@830: 
deba@830:     /// Default constructor.
deba@830:     MapValueIterator() {}
deba@830: 
deba@830:     /// Map and KeyIt initialized iterator.
deba@830:     MapValueIterator(Map& pmap, const KeyIt& pit) 
deba@830:       : MapIteratorBase<Map>(pit), map(&pmap) {}
deba@830:     
deba@830: 
deba@830:     /// The pre increment operator of the iterator.
deba@830:     MapValueIterator& operator++() {
deba@830:       increment(); 
deba@830:       return *this; 
deba@830:     }
deba@830: 
deba@830:     /// The post increment operator of the iterator.
deba@830:     MapValueIterator operator++(int) {
deba@830:       MapValueIterator tmp(*this);
deba@830:       increment();
deba@830:       return tmp;
deba@830:     }
deba@830: 
deba@830:     /// The dereferencing operator of the iterator.
deba@830:     ReferenceType operator*() const {
deba@830:       return (*map)[it];
deba@830:     }
deba@830: 
deba@830:     /// The arrow operator of the iterator.
deba@830:     PointerType operator->() const {
deba@830:       return &(operator*());
deba@830:     }
deba@830: 
deba@830:   };
deba@830: 
deba@830: 
deba@830:   template <typename Map>
deba@830:   class MapConstValueIterator : public MapIteratorBase<Map> {
deba@830: 
deba@830:   public:
deba@830: 
deba@830:     /// The key type of the iterator.
deba@830:     typedef typename Map::KeyType KeyType;
deba@830:     /// The iterator to iterate on the keys.
deba@830:     typedef typename Map::KeyIt KeyIt;
deba@830: 
deba@830: 
deba@830:     /// The value type of the iterator.
deba@830:     typedef typename Map::ValueType ValueType;
deba@830:     /// The reference type of the iterator.
deba@830:     typedef typename Map::ReferenceType ReferenceType;
deba@830:     /// The pointer type of the iterator.
deba@830:     typedef typename Map::PointerType PointerType;
deba@830: 
deba@830:     /// The const value type of the iterator.
deba@830:     typedef typename Map::ConstValueType ConstValueType;
deba@830:     /// The const reference type of the iterator.
deba@830:     typedef typename Map::ConstReferenceType ConstReferenceType;
deba@830:     /// The pointer type of the iterator.
deba@830:     typedef typename Map::ConstPointerType ConstPointerType;
deba@830: 
deba@830:   private:
deba@830: 
deba@822:     const Map* map;
deba@830: 
deba@830:   public:
deba@830: 
deba@830:     /// Default constructor.
deba@830:     MapConstValueIterator() {}
deba@830: 
deba@830:     /// Constructor to create const iterator from a non const.
deba@830:     MapConstValueIterator(const MapValueIterator<Map>& pit) {
deba@830:       it = pit.it;
deba@830:       map = pit.map;
deba@830:     }
deba@830: 
deba@830:     /// Map and KeyIt initialized iterator.
deba@830:     MapConstValueIterator(const Map& pmap, const KeyIt& pit) 
deba@830:       : MapIteratorBase<Map>(pit), map(&pmap) {}
deba@830: 
deba@830:     /// The pre increment operator of the iterator.
deba@830:     MapConstValueIterator& operator++() {
deba@830:       increment(); 
deba@830:       return *this; 
deba@830:     }
deba@830: 
deba@830:     /// The post increment operator of the iterator.
deba@830:     MapConstValueIterator operator++(int) {
deba@830:       MapConstValueIterator tmp(*this);
deba@830:       increment();
deba@830:       return tmp;
deba@830:     }
deba@830: 
deba@830:     /// The dereferencing operator of the iterator.
deba@830:     ConstReferenceType operator*() const {
deba@830:       return (*map)[it];
deba@830:     }
deba@830: 
deba@830:     /// The arrow operator of the iterator.
deba@830:     ConstPointerType operator->() const {
deba@830:       return &(operator*());
deba@830:     }
deba@830: 
deba@822:   };
deba@822: 
deba@830: 
deba@830:   /** This class makes from a map an iteratable set
deba@830:    *  which contains all the keys of the map.
deba@830:    */
deba@830:   template <typename Map>
deba@830:   class MapConstKeySet {
deba@830: 
deba@830:     const Map* map;
deba@830: 
deba@830:   public:
deba@830: 
deba@830:     /// The key type of the iterator.
deba@830:     typedef typename Map::KeyType KeyType;
deba@830:     /// The iterator to iterate on the keys.
deba@830:     typedef typename Map::KeyIt KeyIt;
deba@830: 
deba@830:     /// The map initialized const key set.
deba@830:     MapConstKeySet(const Map& pmap) : map(&pmap) {}
deba@830: 
deba@830:     /// The const iterator of the set.
deba@830:     typedef MapKeyIterator<Map> ConstIterator;
deba@830: 
deba@830:     /// It gives back the const iterator pointed to the first element.
deba@830:     ConstIterator begin() const {
deba@830:       return ConstIterator(KeyIt(*map->getGraph()));
deba@830:     }
deba@830:             
deba@830:     /// It gives back the const iterator pointed to the first ivalid element.
deba@830:     ConstIterator end() const {
deba@830:       return ConstIterator(KeyIt(INVALID));
deba@830:     }
deba@830:   };
deba@830: 
deba@830:   /** This class makes from a map an iteratable set
deba@830:    *  which contains all the values of the map.
deba@830:    *  The values cannot be modified.
deba@830:    */
deba@830:   template <typename Map>
deba@830:   class MapConstValueSet {
deba@830: 
deba@830:     const Map* map;
deba@830: 
deba@830:   public:
deba@830: 
deba@830:     /// The key type of the iterator.
deba@830:     typedef typename Map::KeyType KeyType;
deba@830:     /// The iterator to iterate on the keys.
deba@830:     typedef typename Map::KeyIt KeyIt;
deba@830: 
deba@830:     /// The map initialized const value set.
deba@830:     MapConstValueSet(const Map& pmap) : map(&pmap) {}
deba@830: 
deba@830:     /// The const iterator of the set.
deba@830:     typedef MapConstValueIterator<Map> ConstIterator;
deba@830: 
deba@830:     /// It gives back the const iterator pointed to the first element.
deba@830:     ConstIterator begin() const {
deba@830:       return ConstIterator(*map, KeyIt(*map->getGraph()));
deba@830:     }
deba@830: 
deba@830:     /// It gives back the const iterator pointed to the first invalid element.
deba@830:     ConstIterator end() const {
deba@830:       return ConstIterator(*map, KeyIt(INVALID));
deba@830:     }
deba@830:   };
deba@830: 
deba@830: 
deba@830:   /** This class makes from a map an iteratable set
deba@830:    *  which contains all the values of the map.
deba@830:    *  The values can be modified.
deba@830:    */
deba@830:   template <typename Map>
deba@830:   class MapValueSet {
deba@830: 
deba@830:     Map* map;
deba@830: 
deba@830:   public:
deba@830: 
deba@830:     /// The key type of the iterator.
deba@830:     typedef typename Map::KeyType KeyType;
deba@830:     /// The iterator to iterate on the keys.
deba@830:     typedef typename Map::KeyIt KeyIt;
deba@830: 
deba@830:     /// The map initialized value set.
deba@830:     MapValueSet(Map& pmap) : map(&pmap) {}
deba@830: 
deba@830:     /// The const iterator of the set.
deba@830:     typedef MapConstValueIterator<Map> ConstIterator;
deba@830: 
deba@830:     /// It gives back the const iterator pointed to the first element.
deba@830:     ConstIterator begin() const {
deba@830:       return ConstIterator(*map, KeyIt(*map->getGraph()));
deba@830:     }
deba@830: 
deba@830:     /// It gives back the const iterator pointed to the first invalid element.
deba@830:     ConstIterator end() const {
deba@830:       return ConstIterator(*map, KeyIt(INVALID));
deba@830:     }
deba@830: 
deba@830:     /// The iterator of the set.
deba@830:     typedef MapValueIterator<Map> Iterator;
deba@830: 
deba@830:     /// It gives back the iterator pointed to the first element.
deba@830:     Iterator begin() {
deba@830:       return Iterator(*map, KeyIt(*map->getGraph()));
deba@830:     }
deba@830: 
deba@830:     /// It gives back the iterator pointed to the first invalid element.
deba@830:     Iterator end() {
deba@830:       return Iterator(*map, KeyIt(INVALID));
deba@830:     }
deba@830:             
deba@830:   };
deba@830: 
deba@830:   /// @}
deba@830: 
deba@822: }
deba@822: 
deba@822: #endif