/* -*- C++ -*-

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

  *

  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, 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/bits/extended_pair.h>

 #include <lemon/graph_utils.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 _Graph,

     typename _Item>

   class MapIteratorBase {

   protected:

     /// The key type of the iterator.

     typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;

     ItemIt it;

     /// Default constructor.

     MapIteratorBase() {}

     /// ItemIt initialized MapIteratorBase constructor.

     MapIteratorBase(const ItemIt _it) : it(_it) {}

   public:

     /// Stepping forward in the map.   

     void increment() { 

       ++it; 

     }

     /// The equality operator of the map.

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

       return _it.it == it;

     }

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

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

       return !(*this == _it);

     }

   };

   template <

     typename _Graph,

     typename _Item,

     typename _Map>

   class MapConstIterator;

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

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

    */

   template <

     typename _Graph,

     typename _Item,

     typename _Map>

   class MapIterator : public MapIteratorBase<_Graph, _Item> {

     friend class MapConstIterator<_Graph, _Item, _Map>;

   public:

     /// The iterator base class.

     typedef MapIteratorBase<_Graph, _Item> Parent;

     typedef _Item Item;

     typedef _Map Map;

     typedef _Graph Graph;

   protected:

     typedef typename Parent::ItemIt ItemIt;

     typedef typename ReferenceMapTraits<_Map>::Value MapValue;

     typedef typename ReferenceMapTraits<_Map>::Reference MapReference;

   public:

     /// The value type of the iterator.

     typedef extended_pair<Item, const Item&,

       MapValue, const MapValue&> Value;

     /// The reference type of the iterator. 

     typedef extended_pair<const Item&, const Item&, 

       MapReference, MapReference> Reference;

     /// Default constructor. 

     MapIterator() {}

     /// Constructor to initalize the iterators returned 

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

     MapIterator(Map& _map, const ItemIt& _it) 

       : Parent(_it), map(&_map) {}

     /// Dereference operator for the iterator.

     Reference operator*() {

       return Reference(Parent::it, (*map)[Parent::it]);

     }

     /// The pointer type of the iterator.

     class Pointer {

       friend class MapIterator;

     protected:

       Reference data;

       Pointer(const Item& item, MapReference val) 

 	: data(item, val) {}

     public:

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

     };

     /// Arrow operator for the iterator.

     Pointer operator->() {

       return Pointer(Parent::it, (*map)[Parent::it]); 

     }

     /// The pre increment operator of the iterator.

     MapIterator& operator++() { 

       Parent::increment(); 

       return *this; 

     }

     /// The post increment operator of the iterator.

     MapIterator operator++(int) { 

       MapIterator tmp(*this); 

       Parent::increment(); 

       return tmp; 

     }

   protected:

     Map* map;

   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;

   };

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

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

    */

   template <

     typename _Graph,

     typename _Item,

     typename _Map>

   class MapConstIterator : public MapIteratorBase<_Graph, _Item> {

   public:

     /// The iterator base class.

     typedef MapIteratorBase<_Graph, _Item> Parent;

     typedef _Graph Graph;

     typedef _Item Item;

     typedef _Map Map;

   protected:

     typedef typename Parent::ItemIt ItemIt;

     typedef typename ReferenceMapTraits<_Map>::Value MapValue;

     typedef typename ReferenceMapTraits<_Map>::ConstReference

     MapReference;

   public:

     /// The value type of the iterator.

     typedef extended_pair<Item, const Item&,

       MapValue, const MapValue&> Value;

     /// The reference type of the iterator. 

     typedef extended_pair<const Item&, const Item&, 

       MapReference, MapReference> Reference;

     /// Default constructor. 

     MapConstIterator() {}

     /// Constructor to initalize the iterators returned 

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

     MapConstIterator(const Map& _map, const ItemIt& _it) 

       : Parent(_it), map(&_map) {}

     /// Dereference operator for the iterator.

     Reference operator*() {

       return Reference(Parent::it, (*map)[Parent::it]);

     }

     /// The pointer type of the iterator.

     class Pointer {

       friend class MapConstIterator;

     protected:

       Reference data;

       Pointer(const Item& item, MapReference val) 

 	: data(item, val) {}

     public:

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

     };

     /// Arrow operator for the iterator.

     Pointer operator->() {

       return Pointer(Parent::it, ((*map)[Parent::it])); 

     }

     /// The pre increment operator of the iterator.

     MapConstIterator& operator++() { 

       Parent::increment(); 

       return *this; 

     }

     /// The post increment operator of the iterator.

     MapConstIterator operator++(int) { 

       MapConstIterator tmp(*this); 

       Parent::increment(); 

       return tmp; 

     }

   protected:

     const Map* map;

   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;

   };

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

    *  with dereferencing operator.

    */

   template <

     typename _Graph,

     typename _Item>

   class MapConstKeyIterator : public MapIteratorBase<_Graph, _Item> {

   public:

     /// The iterator base class.

     typedef MapIteratorBase<_Graph, _Item> Parent;

     typedef _Graph Graph;

     typedef _Item Item;

   protected:

     /// The iterator to iterate on the keys.

     typedef typename Parent::ItemIt ItemIt;

   public:

     typedef Item Value;

     typedef const Item& Reference;

     typedef const Item* Pointer;

     /// Default constructor.

     MapConstKeyIterator() {}

     /// ItemIt initialized iterator.

     MapConstKeyIterator(const ItemIt& pit) : Parent(pit) {}

     /// The pre increment operator of the iterator.

     MapConstKeyIterator& operator++() {

       Parent::increment(); 

       return *this; 

     }

     /// The post increment operator of the iterator.

     MapConstKeyIterator operator++(int) {

       MapConstKeyIterator tmp(*this);

       Parent::increment();

       return tmp;

     }

     /// The dereferencing operator of the iterator.

     Item operator*() const {

       return static_cast<Item>(Parent::it);

     }

   public:

     // STL  compatibility typedefs.

     typedef std::input_iterator_tag iterator_category;

     typedef int difference_type;

     typedef Value value_type;

     typedef Reference reference;

     typedef Pointer pointer;

   };

   template <

     typename _Graph, 

     typename _Item,

     typename _Map>

   class MapConstValueIterator;

   /** MapValueIterator creates an stl compatible iterator

    *  for the values.

    */

   template <

     typename _Graph,

     typename _Item,

     typename _Map>

   class MapValueIterator : public MapIteratorBase<_Graph, _Item> {

     friend class MapConstValueIterator<_Graph, _Item, _Map>;

   public:

     /// The iterator base class.

     typedef MapIteratorBase<_Graph, _Item> Parent;

     typedef _Graph Graph;

     typedef _Item Item;

     typedef _Map Map;

   protected:

     /// The iterator to iterate on the keys.

     typedef typename Parent::ItemIt ItemIt;

     /// The value type of the iterator.

     typedef typename ReferenceMapTraits<Map>::Value MapValue;

     /// The reference type of the iterator.

     typedef typename ReferenceMapTraits<Map>::Reference MapReference;

     /// The pointer type of the iterator.

     typedef typename ReferenceMapTraits<Map>::Pointer MapPointer;

   public:

     typedef MapValue Value;

     typedef MapReference Reference;

     typedef MapPointer Pointer;

     /// Default constructor.

     MapValueIterator() {}

     /// Map and ItemIt initialized iterator.

     MapValueIterator(Map& _map, const ItemIt& _it) 

       : Parent(_it), map(&_map) {}

     /// The pre increment operator of the iterator.

     MapValueIterator& operator++() {

       Parent::increment(); 

       return *this; 

     }

     /// The post increment operator of the iterator.

     MapValueIterator operator++(int) {

       MapValueIterator tmp(*this);

       Parent::increment();

       return tmp;

     }

     /// The dereferencing operator of the iterator.

     Reference operator*() const {

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

     }

     /// The arrow operator of the iterator.

     Pointer operator->() const {

       return &(operator*());

     }

   protected:

     Map* map;

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

    */

   template <

     typename _Graph,

     typename _Item,

     typename _Map>

   class MapConstValueIterator : public MapIteratorBase<_Graph, _Item> {

   public:

     /// The iterator base class.

     typedef MapIteratorBase<_Graph, _Item> Parent;

     typedef _Graph Graph;

     typedef _Item Item;

     typedef _Map Map;

   protected:

     /// The iterator to iterate on the keys.

     typedef typename Parent::ItemIt ItemIt;

     /// The value type of the iterator.

     typedef typename ReferenceMapTraits<Map>::Value MapValue;

     /// The reference type of the iterator.

     typedef typename ReferenceMapTraits<Map>::ConstReference MapReference;

     /// The pointer type of the iterator.

     typedef typename ReferenceMapTraits<Map>::ConstPointer MapPointer;

   public:

     typedef MapValue Value;

     typedef MapReference Reference;

     typedef MapPointer Pointer;

     /// Default constructor.

     MapConstValueIterator() {}

     /// Map and ItemIt initialized iterator.

     MapConstValueIterator(const Map& _map, const ItemIt& _it) 

       : Parent(_it), map(&_map) {}

     /// The pre increment operator of the iterator.

     MapConstValueIterator& operator++() {

       Parent::increment(); 

       return *this; 

     }

     /// The post increment operator of the iterator.

     MapConstValueIterator operator++(int) {

       MapConstValueIterator tmp(*this);

       Parent::increment();

       return tmp;

     }

     /// The dereferencing operator of the iterator.

     Reference operator*() const {

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

     }

     /// The arrow operator of the iterator.

     Pointer operator->() const {

       return &(operator*());

     }

   protected:

     const Map* map;

   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;

   };

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

    *  which contains all the keys of the map.

    */

   template <typename _Graph, typename _Item>

   class MapConstKeySet {

   public:

     typedef _Graph Graph;

     /// The key type of the iterator.

     typedef _Item Item;

     /// The iterator to iterate on the keys.

   protected:

     typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;

   public:

     /// The map initialized const key set.

     MapConstKeySet(const Graph& _graph) : graph(&_graph) {}

     /// The const iterator of the set.

     typedef MapConstKeyIterator<_Graph, _Item> ConstIterator;

     typedef typename ConstIterator::Value Value;

     /// The reference type of the iterator.

     typedef typename ConstIterator::Reference ConstReference;

     /// The pointer type of the iterator.

     typedef typename ConstIterator::Pointer ConstPointer;

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

     ConstIterator begin() const {

       return ConstIterator(ItemIt(*graph));

     }

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

     ConstIterator end() const {

       return ConstIterator(ItemIt(INVALID));

     }

   protected:

     const Graph* graph;

   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 _Graph, typename _Item, typename _Map>

   class MapConstValueSet {

   public:

     typedef _Graph Graph;

     typedef _Item Item;

     typedef _Map Map;

   protected:

     /// The iterator to iterate on the keys.

     typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;

   public:

     /// The map initialized const value set.

     MapConstValueSet(const Graph& _graph, const Map& _map) 

       : graph(&_graph), map(&_map) {}

     /// The const iterator of the set.

     typedef MapConstValueIterator<_Graph, _Item, _Map> ConstIterator;

     typedef typename ConstIterator::Value Value;

     typedef typename ConstIterator::Reference ConstReference;

     typedef typename ConstIterator::Pointer ConstPointer;

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

     ConstIterator begin() const {

       return ConstIterator(*map, ItemIt(*graph));

     }

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

     ConstIterator end() const {

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

     }

   protected:

     const Map* map;

     const Graph * graph;

   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 _Graph, typename _Item, typename _Map>

   class MapValueSet {

   public:

     typedef _Graph Graph;

     typedef _Item Item;

     typedef _Map Map;

   protected:

     /// The iterator to iterate on the keys.

     typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;

   public:

     /// The map initialized const value set.

     MapValueSet(const Graph& _graph, Map& _map) 

       : map(&_map), graph(&_graph) {}

     /// The const iterator of the set.

     typedef MapValueIterator<_Graph, _Item, _Map> Iterator;

     /// The const iterator of the set.

     typedef MapConstValueIterator<_Graph, _Item, _Map> ConstIterator;

     typedef typename ConstIterator::Value Value;

     typedef typename Iterator::Reference Reference;

     typedef typename Iterator::Pointer Pointer;

     typedef typename ConstIterator::Reference ConstReference;

     typedef typename ConstIterator::Pointer ConstPointer;

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

     ConstIterator begin() const {

       return ConstIterator(*map, ItemIt(*graph));

     }

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

     ConstIterator end() const {

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

     }

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

     Iterator begin() {

       return Iterator(*map, ItemIt(*graph));

     }

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

     Iterator end() {

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

     }

   protected:

     Map* map;

     const Graph * graph;

   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;

   };

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

    *  which contains all the values of the map.

    *  The values can be modified.

    */

   template <

     typename _Graph, 

     typename _Item,

     typename _Map

     >

   class MapSet {

   public:    

     typedef _Graph Graph;

     typedef _Item Item;

     typedef _Map Map;

   protected:

     typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;

   public:

     /// The map initialized value set.

     MapSet(const Graph& _graph, Map& _map) : graph(&_graph), map(&_map) {}

     /// The const iterator of the set.

     typedef MapIterator<_Graph, _Item, _Map> Iterator;

     typedef MapConstIterator<_Graph, _Item, _Map> ConstIterator;

     typedef typename ConstIterator::Value Value;

     typedef typename Iterator::Reference Reference;

     typedef typename Iterator::Pointer Pointer;

     typedef typename ConstIterator::Reference ConstReference;

     typedef typename ConstIterator::Pointer ConstPointer;

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

     ConstIterator begin() const {

       return ConstIterator(*map, ItemIt(*graph));

     }

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

     ConstIterator end() const {

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

     }

     /// The iterator of the set.

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

     Iterator begin() {

       return Iterator(*map, ItemIt(*graph));

     }

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

     Iterator end() {

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

     }

   protected:

     const Graph* graph;

     Map* map;

   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;

   };

   template <

     typename _Graph, 

     typename _Item,

     typename _Map

     >

   class ConstMapSet {

     typedef _Graph Graph;

     typedef _Map Map;

     const Graph* graph;

     const Map* map;

   public:

     typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;

     /// The map initialized value set.

     ConstMapSet(const Graph& _graph, const Map& _map) 

       : graph(&_graph), map(&_map) {}

     /// The const iterator of the set.

     typedef MapConstIterator<_Graph, _Item, _Map> ConstIterator;

     typedef typename ConstIterator::Value Value;

     typedef typename ConstIterator::Reference ConstReference;

     typedef typename ConstIterator::Pointer ConstPointer;

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

     ConstIterator begin() const {

       return ConstIterator(*map, ItemIt(*graph));

     }

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

     ConstIterator end() const {

       return ConstIterator(*map, ItemIt(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;

   };

   template <typename _Map>

   class IterableMapExtender : public _Map {

   public:

     typedef _Map Parent;

     typedef Parent Map;

     typedef typename Map::Graph Graph;

     typedef typename Map::Key Item;

     typedef typename Map::Value Value;

     typedef MapSet<Graph, Item, Map> MapSet;

     IterableMapExtender() : Parent() {}

     IterableMapExtender(const Graph& graph) : Parent(graph) {}

     IterableMapExtender(const Graph& graph, const Value& value) 

       : Parent(graph, value) {}

     MapSet mapSet() { 

       return MapSet(*Parent::getGraph(), *this); 

     }

     typedef ConstMapSet<Graph, Item, Map> ConstMapSet;

     ConstMapSet mapSet() const { 

       return ConstMapSet(*Parent::getGraph(), *this); 

     }

     typedef MapConstKeySet<Graph, Item> ConstKeySet;

     ConstKeySet keySet() const {

       return ConstKeySet(*Parent::getGraph());

     }

     typedef MapValueSet<Graph, Item, Map> ValueSet;

     ValueSet valueSet() {

       return ValueSet(*Parent::getGraph(), *this);

     }

     typedef MapConstValueSet<Graph, Item, Map> ConstValueSet;

     ConstValueSet valueSet() const {

       return ConstValueSet(*Parent::getGraph(), *this);

     }

   };

   /// @}

 }

 #endif