/* -*- C++ -*-
 * src/lemon/map_iterator.h - Part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2005 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