/* -*- C++ -*-

  * src/lemon/map_iterator.h - Part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Combinatorial Optimization Research Group, EGRES).

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 #ifndef LEMON_MAP_ITERATOR_H

 #define LEMON_MAP_ITERATOR_H

 #include <iterator>

 #include <lemon/extended_pair.h>

 ///\ingroup graphmaps

 ///\file

 ///\brief Iterators on the maps.

 namespace lemon {

   /// \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::Key Key;

     /// The iterator to iterate on the keys.

     typedef typename Map::KeyIt KeyIt;

     /// The value type of the iterator.

     typedef typename Map::Value Value;

     /// The reference type of the iterator.

     typedef typename Map::Reference Reference;

     /// The pointer type of the iterator.

     typedef typename Map::Pointer Pointer;

     /// The const value type of the iterator.

     typedef typename Map::ConstValue ConstValue;

     /// The const reference type of the iterator.

     typedef typename Map::ConstReference ConstReference;

     /// The pointer type of the iterator.

     typedef typename Map::ConstPointer ConstPointer;

   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::Key Key;

     /// The iterator to iterate on the keys.

     typedef typename Map::KeyIt KeyIt;

     /// The value type of the iterator.

     typedef typename Map::Value Value;

     /// The reference type of the iterator.

     typedef typename Map::Reference Reference;

     /// The pointer type of the iterator.

     typedef typename Map::Pointer Pointer;

     /// The const value type of the iterator.

     typedef typename Map::ConstValue ConstValue;

     /// The const reference type of the iterator.

     typedef typename Map::ConstReference ConstReference;

     /// The pointer type of the iterator.

     typedef typename Map::ConstPointer ConstPointer;

   public:

     /// The value type of the iterator.

     typedef extended_pair<Key, const Key&,

       Value, const Value&> PairValue;

     /// The reference type of the iterator. 

     typedef extended_pair<const Key&, const Key&, 

       Reference, Reference> PairReference;

     /// 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.

     PairReference operator*() {

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

     }

     /// The pointer type of the iterator.

     class PairPointer {

       friend class MapIterator;

     private:

       PairReference data;

       PairPointer(const Key& key, Reference val) 

 	: data(key, val) {}

     public:

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

     };

     /// Arrow operator for the iterator.

     PairPointer operator->() {

       return PairPointer(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 PairValue value_type;

     typedef PairReference reference;

     typedef PairPointer 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::Key Key;

     /// The iterator to iterate on the keys.

     typedef typename Map::KeyIt KeyIt;

     /// The value type of the iterator.

     typedef typename Map::Value Value;

     /// The reference type of the iterator.

     typedef typename Map::Reference Reference;

     /// The pointer type of the iterator.

     typedef typename Map::Pointer Pointer;

     /// The const value type of the iterator.

     typedef typename Map::ConstValue ConstValue;

     /// The const reference type of the iterator.

     typedef typename Map::ConstReference ConstReference;

     /// The pointer type of the iterator.

     typedef typename Map::ConstPointer ConstPointer;

   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<Key, const Key&,

       Value, const Value&> PairValue;

     /// The reference type of map.

     typedef extended_pair<const Key&, const Key&, 

       ConstReference, ConstReference> PairReference;

     /// Dereference operator for the iterator.

     PairReference operator*() {

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

     }

     /// The pointer type of the iterator.

     class PairPointer {

       friend class MapConstIterator;

     private:

       PairReference data;

       PairPointer(const Key& key, ConstReference val) 

 	: data(key, val) {}

     public:

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

     };

     /// Arrow operator for the iterator.

     PairPointer operator->() {

       return PairPointer(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 PairValue value_type;

     typedef PairReference reference;

     typedef PairPointer 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::Key Key;

     /// 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.

     Key operator*() const {

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

     }

   public:

     // STL  compatibility typedefs.

     typedef std::input_iterator_tag iterator_category;

     typedef int difference_type;

     typedef Key value_type;

     typedef const Key& reference;

     typedef const Key* 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::Key Key;

     /// The iterator to iterate on the keys.

     typedef typename Map::KeyIt KeyIt;

     /// The value type of the iterator.

     typedef typename Map::Value Value;

     /// The reference type of the iterator.

     typedef typename Map::Reference Reference;

     /// The pointer type of the iterator.

     typedef typename Map::Pointer Pointer;

     /// The const value type of the iterator.

     typedef typename Map::ConstValue ConstValue;

     /// The const reference type of the iterator.

     typedef typename Map::ConstReference ConstReference;

     /// The pointer type of the iterator.

     typedef typename Map::ConstPointer ConstPointer;

   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.

     Reference operator*() const {

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

     }

     /// The arrow operator of the iterator.

     Pointer operator->() const {

       return &(operator*());

     }

   public:

     // STL  compatibility typedefs.

     typedef std::forward_iterator_tag iterator_category;

     typedef int difference_type;

     typedef Value value_type;

     typedef Reference reference;

     typedef Pointer 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::Key Key;

     /// The iterator to iterate on the keys.

     typedef typename Map::KeyIt KeyIt;

     /// The value type of the iterator.

     typedef typename Map::Value Value;

     /// The reference type of the iterator.

     typedef typename Map::Reference Reference;

     /// The pointer type of the iterator.

     typedef typename Map::Pointer Pointer;

     /// The const value type of the iterator.

     typedef typename Map::ConstValue ConstValue;

     /// The const reference type of the iterator.

     typedef typename Map::ConstReference ConstReference;

     /// The pointer type of the iterator.

     typedef typename Map::ConstPointer ConstPointer;

   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.

     ConstReference operator*() const {

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

     }

     /// The arrow operator of the iterator.

     ConstPointer operator->() const {

       return &(operator*());

     }

   public:

     // STL  compatibility typedefs.

     typedef std::input_iterator_tag iterator_category;

     typedef int difference_type;

     typedef Value value_type;

     typedef ConstReference reference;

     typedef ConstPointer 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::Key Key;

     /// The iterator to iterate on the keys.

     typedef typename Map::KeyIt KeyIt;

     /// The value type of the iterator.

     typedef typename Map::Value Value;

     /// The reference type of the iterator.

     typedef typename Map::Reference Reference;

     /// The pointer type of the iterator.

     typedef typename Map::Pointer Pointer;

     /// The const value type of the iterator.

     typedef typename Map::ConstValue ConstValue;

     /// The const reference type of the iterator.

     typedef typename Map::ConstReference ConstReference;

     /// The pointer type of the iterator.

     typedef typename Map::ConstPointer ConstPointer;

     /// 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 Value value_type;

     typedef ConstIterator const_iterator;

     typedef ConstReference const_reference;

     typedef ConstPointer 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::Key Key;

     /// The iterator to iterate on the keys.

     typedef typename Map::KeyIt KeyIt;

     /// The value type of the iterator.

     typedef typename Map::Value Value;

     /// The reference type of the iterator.

     typedef typename Map::Reference Reference;

     /// The pointer type of the iterator.

     typedef typename Map::Pointer Pointer;

     /// The const value type of the iterator.

     typedef typename Map::ConstValue ConstValue;

     /// The const reference type of the iterator.

     typedef typename Map::ConstReference ConstReference;

     /// The pointer type of the iterator.

     typedef typename Map::ConstPointer ConstPointer;

     /// 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 Value value_type;

     typedef ConstIterator const_iterator;

     typedef ConstReference const_reference;

     typedef ConstPointer 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::Key Key;

     /// The iterator to iterate on the keys.

     typedef typename Map::KeyIt KeyIt;

     /// The value type of the iterator.

     typedef typename Map::Value Value;

     /// The reference type of the iterator.

     typedef typename Map::Reference Reference;

     /// The pointer type of the iterator.

     typedef typename Map::Pointer Pointer;

     /// The const value type of the iterator.

     typedef typename Map::ConstValue ConstValue;

     /// The const reference type of the iterator.

     typedef typename Map::ConstReference ConstReference;

     /// The pointer type of the iterator.

     typedef typename Map::ConstPointer ConstPointer;

     /// 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 Value value_type;

     typedef Iterator iterator;

     typedef ConstIterator const_iterator;

     typedef Reference reference;

     typedef ConstReference const_reference;

     typedef Pointer pointer;

     typedef ConstPointer const_pointer;

     typedef int difference_type;

   };

   /// @}

 }

 #endif