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