// -*- c++ -*-

 #ifndef MAP_ITERATOR_H

 #define MAP_ITERATOR_H

 #include <iterator>

 #include <hugo/extended_pair.h>

 ///\ingroup graphmaps

 ///\file

 ///\brief Iterators on the maps.

 namespace hugo {

   /// \addtogroup graphmaps

   /// @{

   /** The base class all of the map iterators.

    *  The class defines the typedefs of the iterators,

    *  simple step functions and equality operators.

    */ 

   template <typename Map>

   class MapIteratorBase {

   public:

     /// The key type of the iterator.

     typedef typename Map::KeyType KeyType;

     /// The iterator to iterate on the keys.

     typedef typename Map::KeyIt KeyIt;

     /// The value type of the iterator.

     typedef typename Map::ValueType ValueType;

     /// The reference type of the iterator.

     typedef typename Map::ReferenceType ReferenceType;

     /// The pointer type of the iterator.

     typedef typename Map::PointerType PointerType;

     /// The const value type of the iterator.

     typedef typename Map::ConstValueType ConstValueType;

     /// The const reference type of the iterator.

     typedef typename Map::ConstReferenceType ConstReferenceType;

     /// The pointer type of the iterator.

     typedef typename Map::ConstPointerType ConstPointerType;

   protected:

     KeyIt it;

     /// Default constructor.

     MapIteratorBase() {}

     /// KeyIt initialized MapIteratorBase constructor.

     MapIteratorBase(const KeyIt pit) : it(pit) {}

   public:

     /// Stepping forward in the map.   

     void increment() { 

       ++it; 

     }

     /// The equality operator of the map.

     bool operator==(const MapIteratorBase& pit) const {

       return pit.it == it;

     }

     /// The not-equality operator of the map.

     bool operator!=(const MapIteratorBase& pit) const {

       return !(*this == pit);

     }

   };

   template <typename Map> class MapConstIterator;

   /** Compatible iterator with the stl maps' iterators.

    * It iterates on pairs of a key and a value.

    */

   template <typename Map>  

   class MapIterator : public MapIteratorBase<Map> {

     friend class MapConstIterator<Map>;

   public:

     /// The iterator base class.

     typedef MapIteratorBase<Map> Base;

     /// The key type of the iterator.

     typedef typename Map::KeyType KeyType;

     /// The iterator to iterate on the keys.

     typedef typename Map::KeyIt KeyIt;

     /// The value type of the iterator.

     typedef typename Map::ValueType ValueType;

     /// The reference type of the iterator.

     typedef typename Map::ReferenceType ReferenceType;

     /// The pointer type of the iterator.

     typedef typename Map::PointerType PointerType;

     /// The const value type of the iterator.

     typedef typename Map::ConstValueType ConstValueType;

     /// The const reference type of the iterator.

     typedef typename Map::ConstReferenceType ConstReferenceType;

     /// The pointer type of the iterator.

     typedef typename Map::ConstPointerType ConstPointerType;

   public:

     /// The value type of the iterator.

     typedef extended_pair<KeyType, const KeyType&,

       ValueType, const ValueType&> PairValueType;

     /// The reference type of the iterator. 

     typedef extended_pair<const KeyType&, const KeyType&, 

       ReferenceType, ReferenceType> PairReferenceType;

     /// Default constructor. 

     MapIterator() {}

     /// Constructor to initalize the iterators returned 

     /// by the begin() and end().

     MapIterator(Map& pmap, const KeyIt& pit) : Base(pit), map(&pmap) {}

     /// Dereference operator for the iterator.

     PairReferenceType operator*() {

       return PairReferenceType(Base::it, (*map)[Base::it]);

     }

     /// The pointer type of the iterator.

     class PairPointerType {

       friend class MapIterator;

     private:

       PairReferenceType data;

       PairPointerType(const KeyType& key, ReferenceType val) 

 	: data(key, val) {}

     public:

       PairReferenceType* operator->() {return &data;}

     };

     /// Arrow operator for the iterator.

     PairPointerType operator->() {

       return PairPointerType(Base::it, ((*map)[Base::it])); 

     }

     /// The pre increment operator of the iterator.

     MapIterator& operator++() { 

       Base::increment(); 

       return *this; 

     }

     /// The post increment operator of the iterator.

     MapIterator operator++(int) { 

       MapIterator tmp(*this); 

       Base::increment(); 

       return tmp; 

     }

   private:

     Map* map;

   public:

     // STL  compatibility typedefs.

     typedef std::forward_iterator_tag iterator_category;

     typedef int difference_type;

     typedef PairValueType value_type;

     typedef PairReferenceType reference;

     typedef PairPointerType pointer;

   };

   /** Compatible iterator with the stl maps' iterators.

    *  It iterates on pairs of a key and a value.

    */

   template <typename Map>

   class MapConstIterator : public MapIteratorBase<Map> {

   public:

     /// The iterator base class.

     typedef MapIteratorBase<Map> Base;

     /// The key type of the iterator.

     typedef typename Map::KeyType KeyType;

     /// The iterator to iterate on the keys.

     typedef typename Map::KeyIt KeyIt;

     /// The value type of the iterator.

     typedef typename Map::ValueType ValueType;

     /// The reference type of the iterator.

     typedef typename Map::ReferenceType ReferenceType;

     /// The pointer type of the iterator.

     typedef typename Map::PointerType PointerType;

     /// The const value type of the iterator.

     typedef typename Map::ConstValueType ConstValueType;

     /// The const reference type of the iterator.

     typedef typename Map::ConstReferenceType ConstReferenceType;

     /// The pointer type of the iterator.

     typedef typename Map::ConstPointerType ConstPointerType;

   public:    

     /// Default constructor. 

     MapConstIterator() {}

     /// Constructor to initalize the the iterators returned

     ///  by the begin() and end().

     MapConstIterator(const Map& pmap, const KeyIt& pit) 

       : Base(pit), map(&pmap) {}

     /// Constructor to create const iterator from a non const.

     MapConstIterator(const MapIterator<Map>& pit) {

       Base::it = pit.Base::it;

       map = pit.map;

     }

     /// The value type of the iterator.

     typedef extended_pair<KeyType, const KeyType&,

       ValueType, const ValueType&> PairValueType;

     /// The reference type of map.

     typedef extended_pair<const KeyType&, const KeyType&, 

       ConstReferenceType, ConstReferenceType> PairReferenceType;

     /// Dereference operator for the iterator.

     PairReferenceType operator*() {

       return PairReferenceType(Base::it, (*map)[Base::it]);

     }

     /// The pointer type of the iterator.

     class PairPointerType {

       friend class MapConstIterator;

     private:

       PairReferenceType data;

       PairPointerType(const KeyType& key, ConstReferenceType val) 

 	: data(key, val) {}

     public:

       PairReferenceType* operator->() {return &data;}

     };

     /// Arrow operator for the iterator.

     PairPointerType operator->() {

       return PairPointerType(Base::it, (*map)[Base::it]); 

     }

     /// The pre increment operator of the iterator.

     MapConstIterator& operator++() { 

       Base::increment(); 

       return *this; 

     }

     /// The post increment operator of the iterator.

     MapConstIterator operator++(int) { 

       MapConstIterator tmp(*this); 

       Base::increment(); 

       return tmp; 

     }

   private:

     const Map* map;

   public:

     // STL  compatibility typedefs.

     typedef std::input_iterator_tag iterator_category;

     typedef int difference_type;

     typedef PairValueType value_type;

     typedef PairReferenceType reference;

     typedef PairPointerType pointer;

   };

   /** The class makes the KeyIt to an stl compatible iterator

    *  with dereferencing operator.

    */

   template <typename Map>

   class MapKeyIterator : public MapIteratorBase<Map> {

   public:

     /// The iterator base class.

     typedef MapIteratorBase<Map> Base;

     /// The key type of the iterator.

     typedef typename Map::KeyType KeyType;

     /// The iterator to iterate on the keys.

     typedef typename Map::KeyIt KeyIt;

   public:

     /// Default constructor.

     MapKeyIterator() {}

     /// KeyIt initialized iterator.

     MapKeyIterator(const KeyIt& pit) : Base(pit) {}

     /// The pre increment operator of the iterator.

     MapKeyIterator& operator++() {

       Base::increment(); 

       return *this; 

     }

     /// The post increment operator of the iterator.

     MapKeyIterator operator++(int) {

       MapKeyIterator tmp(*this);

       Base::increment();

       return tmp;

     }

     /// The dereferencing operator of the iterator.

     KeyType operator*() const {

       return static_cast<KeyType>(Base::it);

     }

   public:

     // STL  compatibility typedefs.

     typedef std::input_iterator_tag iterator_category;

     typedef int difference_type;

     typedef KeyType value_type;

     typedef const KeyType& reference;

     typedef const KeyType* pointer;

   };

   template <typename Map> class MapConstValueIterator;

   /** MapValueIterator creates an stl compatible iterator

    *  for the values.

    */

   template <typename Map>

   class MapValueIterator : public MapIteratorBase<Map> {

     friend class MapConstValueIterator<Map>;

   public:

     /// The iterator base class.

     typedef MapIteratorBase<Map> Base;

     /// The key type of the iterator.

     typedef typename Map::KeyType KeyType;

     /// The iterator to iterate on the keys.

     typedef typename Map::KeyIt KeyIt;

     /// The value type of the iterator.

     typedef typename Map::ValueType ValueType;

     /// The reference type of the iterator.

     typedef typename Map::ReferenceType ReferenceType;

     /// The pointer type of the iterator.

     typedef typename Map::PointerType PointerType;

     /// The const value type of the iterator.

     typedef typename Map::ConstValueType ConstValueType;

     /// The const reference type of the iterator.

     typedef typename Map::ConstReferenceType ConstReferenceType;

     /// The pointer type of the iterator.

     typedef typename Map::ConstPointerType ConstPointerType;

   private:

     Map* map;

   public:

     /// Default constructor.

     MapValueIterator() {}

     /// Map and KeyIt initialized iterator.

     MapValueIterator(Map& pmap, const KeyIt& pit) 

       : Base(pit), map(&pmap) {}

     /// The pre increment operator of the iterator.

     MapValueIterator& operator++() {

       Base::increment(); 

       return *this; 

     }

     /// The post increment operator of the iterator.

     MapValueIterator operator++(int) {

       MapValueIterator tmp(*this);

       Base::increment();

       return tmp;

     }

     /// The dereferencing operator of the iterator.

     ReferenceType operator*() const {

       return (*map)[Base::it];

     }

     /// The arrow operator of the iterator.

     PointerType operator->() const {

       return &(operator*());

     }

   public:

     // STL  compatibility typedefs.

     typedef std::forward_iterator_tag iterator_category;

     typedef int difference_type;

     typedef ValueType value_type;

     typedef ReferenceType reference;

     typedef PointerType pointer;

   };

   /** MapValueIterator creates an stl compatible iterator

    *  for the const values.

    */

   template <typename Map>

   class MapConstValueIterator : public MapIteratorBase<Map> {

   public:

     /// The iterator base class.

     typedef MapIteratorBase<Map> Base;

     /// The key type of the iterator.

     typedef typename Map::KeyType KeyType;

     /// The iterator to iterate on the keys.

     typedef typename Map::KeyIt KeyIt;

     /// The value type of the iterator.

     typedef typename Map::ValueType ValueType;

     /// The reference type of the iterator.

     typedef typename Map::ReferenceType ReferenceType;

     /// The pointer type of the iterator.

     typedef typename Map::PointerType PointerType;

     /// The const value type of the iterator.

     typedef typename Map::ConstValueType ConstValueType;

     /// The const reference type of the iterator.

     typedef typename Map::ConstReferenceType ConstReferenceType;

     /// The pointer type of the iterator.

     typedef typename Map::ConstPointerType ConstPointerType;

   private:

     const Map* map;

   public:

     /// Default constructor.

     MapConstValueIterator() {}

     /// Constructor to create const iterator from a non const.

     MapConstValueIterator(const MapValueIterator<Map>& pit) {

       Base::it = pit.Base::it;

       map = pit.map;

     }

     /// Map and KeyIt initialized iterator.

     MapConstValueIterator(const Map& pmap, const KeyIt& pit) 

       : Base(pit), map(&pmap) {}

     /// The pre increment operator of the iterator.

     MapConstValueIterator& operator++() {

       Base::increment(); 

       return *this; 

     }

     /// The post increment operator of the iterator.

     MapConstValueIterator operator++(int) {

       MapConstValueIterator tmp(*this);

       Base::increment();

       return tmp;

     }

     /// The dereferencing operator of the iterator.

     ConstReferenceType operator*() const {

       return (*map)[Base::it];

     }

     /// The arrow operator of the iterator.

     ConstPointerType operator->() const {

       return &(operator*());

     }

   public:

     // STL  compatibility typedefs.

     typedef std::input_iterator_tag iterator_category;

     typedef int difference_type;

     typedef ValueType value_type;

     typedef ConstReferenceType reference;

     typedef ConstPointerType pointer;

   };

   /** This class makes from a map an iteratable set

    *  which contains all the keys of the map.

    */

   template <typename Map>

   class MapConstKeySet {

     const Map* map;

   public:

     /// The key type of the iterator.

     typedef typename Map::KeyType KeyType;

     /// The iterator to iterate on the keys.

     typedef typename Map::KeyIt KeyIt;

     /// The value type of the iterator.

     typedef typename Map::ValueType ValueType;

     /// The reference type of the iterator.

     typedef typename Map::ReferenceType ReferenceType;

     /// The pointer type of the iterator.

     typedef typename Map::PointerType PointerType;

     /// The const value type of the iterator.

     typedef typename Map::ConstValueType ConstValueType;

     /// The const reference type of the iterator.

     typedef typename Map::ConstReferenceType ConstReferenceType;

     /// The pointer type of the iterator.

     typedef typename Map::ConstPointerType ConstPointerType;

     /// The map initialized const key set.

     MapConstKeySet(const Map& pmap) : map(&pmap) {}

     /// The const iterator of the set.

     typedef MapKeyIterator<Map> ConstIterator;

     /// It gives back the const iterator pointed to the first element.

     ConstIterator begin() const {

       return ConstIterator(KeyIt(*map->getGraph()));

     }

     /// It gives back the const iterator pointed to the first ivalid element.

     ConstIterator end() const {

       return ConstIterator(KeyIt(INVALID));

     }

   public:

     // STL  compatibility typedefs.

     typedef ValueType value_type;

     typedef ConstIterator const_iterator;

     typedef ConstReferenceType const_reference;

     typedef ConstPointerType const_pointer;

     typedef int difference_type;

   };

   /** This class makes from a map an iteratable set

    *  which contains all the values of the map.

    *  The values cannot be modified.

    */

   template <typename Map>

   class MapConstValueSet {

     const Map* map;

   public:

     /// The key type of the iterator.

     typedef typename Map::KeyType KeyType;

     /// The iterator to iterate on the keys.

     typedef typename Map::KeyIt KeyIt;

     /// The value type of the iterator.

     typedef typename Map::ValueType ValueType;

     /// The reference type of the iterator.

     typedef typename Map::ReferenceType ReferenceType;

     /// The pointer type of the iterator.

     typedef typename Map::PointerType PointerType;

     /// The const value type of the iterator.

     typedef typename Map::ConstValueType ConstValueType;

     /// The const reference type of the iterator.

     typedef typename Map::ConstReferenceType ConstReferenceType;

     /// The pointer type of the iterator.

     typedef typename Map::ConstPointerType ConstPointerType;

     /// The map initialized const value set.

     MapConstValueSet(const Map& pmap) : map(&pmap) {}

     /// The const iterator of the set.

     typedef MapConstValueIterator<Map> ConstIterator;

     /// It gives back the const iterator pointed to the first element.

     ConstIterator begin() const {

       return ConstIterator(*map, KeyIt(*map->getGraph()));

     }

     /// It gives back the const iterator pointed to the first invalid element.

     ConstIterator end() const {

       return ConstIterator(*map, KeyIt(INVALID));

     }

   public:

     // STL  compatibility typedefs.

     typedef ValueType value_type;

     typedef ConstIterator const_iterator;

     typedef ConstReferenceType const_reference;

     typedef ConstPointerType const_pointer;

     typedef int difference_type;

   };

   /** This class makes from a map an iteratable set

    *  which contains all the values of the map.

    *  The values can be modified.

    */

   template <typename Map>

   class MapValueSet {

     Map* map;

   public:

     /// The key type of the iterator.

     typedef typename Map::KeyType KeyType;

     /// The iterator to iterate on the keys.

     typedef typename Map::KeyIt KeyIt;

     /// The value type of the iterator.

     typedef typename Map::ValueType ValueType;

     /// The reference type of the iterator.

     typedef typename Map::ReferenceType ReferenceType;

     /// The pointer type of the iterator.

     typedef typename Map::PointerType PointerType;

     /// The const value type of the iterator.

     typedef typename Map::ConstValueType ConstValueType;

     /// The const reference type of the iterator.

     typedef typename Map::ConstReferenceType ConstReferenceType;

     /// The pointer type of the iterator.

     typedef typename Map::ConstPointerType ConstPointerType;

     /// The map initialized value set.

     MapValueSet(Map& pmap) : map(&pmap) {}

     /// The const iterator of the set.

     typedef MapConstValueIterator<Map> ConstIterator;

     /// It gives back the const iterator pointed to the first element.

     ConstIterator begin() const {

       return ConstIterator(*map, KeyIt(*map->getGraph()));

     }

     /// It gives back the const iterator pointed to the first invalid element.

     ConstIterator end() const {

       return ConstIterator(*map, KeyIt(INVALID));

     }

     /// The iterator of the set.

     typedef MapValueIterator<Map> Iterator;

     /// It gives back the iterator pointed to the first element.

     Iterator begin() {

       return Iterator(*map, KeyIt(*map->getGraph()));

     }

     /// It gives back the iterator pointed to the first invalid element.

     Iterator end() {

       return Iterator(*map, KeyIt(INVALID));

     }

   public:

     // STL  compatibility typedefs.

     typedef ValueType value_type;

     typedef Iterator iterator;

     typedef ConstIterator const_iterator;

     typedef ReferenceType reference;

     typedef ConstReferenceType const_reference;

     typedef PointerType pointer;

     typedef ConstPointerType const_pointer;

     typedef int difference_type;

   };

   /// @}

 }

 #endif