/* -*- C++ -*-
 * 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