/* -*- 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::KeyType KeyType;

    /// The iterator to iterate on the keys.

    typedef typename Map::KeyIt KeyIt;

    /// The value type of the iterator.

    typedef typename Map::ValueType ValueType;

    /// The reference type of the iterator.

    typedef typename Map::ReferenceType ReferenceType;

    /// The pointer type of the iterator.

    typedef typename Map::PointerType PointerType;

    /// The const value type of the iterator.

    typedef typename Map::ConstValueType ConstValueType;

    /// The const reference type of the iterator.

    typedef typename Map::ConstReferenceType ConstReferenceType;

    /// The pointer type of the iterator.

    typedef typename Map::ConstPointerType ConstPointerType;

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

    /// The iterator to iterate on the keys.

    typedef typename Map::KeyIt KeyIt;

    /// The value type of the iterator.

    typedef typename Map::ValueType ValueType;

    /// The reference type of the iterator.

    typedef typename Map::ReferenceType ReferenceType;

    /// The pointer type of the iterator.

    typedef typename Map::PointerType PointerType;

    /// The const value type of the iterator.

    typedef typename Map::ConstValueType ConstValueType;

    /// The const reference type of the iterator.

    typedef typename Map::ConstReferenceType ConstReferenceType;

    /// The pointer type of the iterator.

    typedef typename Map::ConstPointerType ConstPointerType;

  public:

    /// The value type of the iterator.

    typedef extended_pair<KeyType, const KeyType&,

      ValueType, const ValueType&> PairValueType;

    /// The reference type of the iterator. 

    typedef extended_pair<const KeyType&, const KeyType&, 

      ReferenceType, ReferenceType> PairReferenceType;

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

    PairReferenceType operator*() {

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

    }

    /// The pointer type of the iterator.

    class PairPointerType {

      friend class MapIterator;

    private:

      PairReferenceType data;

      PairPointerType(const KeyType& key, ReferenceType val) 

	: data(key, val) {}

    public:

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

    };

    /// Arrow operator for the iterator.

    PairPointerType operator->() {

      return PairPointerType(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 PairValueType value_type;

    typedef PairReferenceType reference;

    typedef PairPointerType 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::KeyType KeyType;

    /// The iterator to iterate on the keys.

    typedef typename Map::KeyIt KeyIt;

    /// The value type of the iterator.

    typedef typename Map::ValueType ValueType;

    /// The reference type of the iterator.

    typedef typename Map::ReferenceType ReferenceType;

    /// The pointer type of the iterator.

    typedef typename Map::PointerType PointerType;

    /// The const value type of the iterator.

    typedef typename Map::ConstValueType ConstValueType;

    /// The const reference type of the iterator.

    typedef typename Map::ConstReferenceType ConstReferenceType;

    /// The pointer type of the iterator.

    typedef typename Map::ConstPointerType ConstPointerType;

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

      ValueType, const ValueType&> PairValueType;

    /// The reference type of map.

    typedef extended_pair<const KeyType&, const KeyType&, 

      ConstReferenceType, ConstReferenceType> PairReferenceType;

    /// Dereference operator for the iterator.

    PairReferenceType operator*() {

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

    }

    /// The pointer type of the iterator.

    class PairPointerType {

      friend class MapConstIterator;

    private:

      PairReferenceType data;

      PairPointerType(const KeyType& key, ConstReferenceType val) 

	: data(key, val) {}

    public:

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

    };

    /// Arrow operator for the iterator.

    PairPointerType operator->() {

      return PairPointerType(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 PairValueType value_type;

    typedef PairReferenceType reference;

    typedef PairPointerType 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::KeyType KeyType;

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

    KeyType operator*() const {

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

    }

  public:

    // STL  compatibility typedefs.

    typedef std::input_iterator_tag iterator_category;

    typedef int difference_type;

    typedef KeyType value_type;

    typedef const KeyType& reference;

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

    /// The iterator to iterate on the keys.

    typedef typename Map::KeyIt KeyIt;

    /// The value type of the iterator.

    typedef typename Map::ValueType ValueType;

    /// The reference type of the iterator.

    typedef typename Map::ReferenceType ReferenceType;

    /// The pointer type of the iterator.

    typedef typename Map::PointerType PointerType;

    /// The const value type of the iterator.

    typedef typename Map::ConstValueType ConstValueType;

    /// The const reference type of the iterator.

    typedef typename Map::ConstReferenceType ConstReferenceType;

    /// The pointer type of the iterator.

    typedef typename Map::ConstPointerType ConstPointerType;

  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.

    ReferenceType operator*() const {

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

    }

    /// The arrow operator of the iterator.

    PointerType operator->() const {

      return &(operator*());

    }

  public:

    // STL  compatibility typedefs.

    typedef std::forward_iterator_tag iterator_category;

    typedef int difference_type;

    typedef ValueType value_type;

    typedef ReferenceType reference;

    typedef PointerType 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::KeyType KeyType;

    /// The iterator to iterate on the keys.

    typedef typename Map::KeyIt KeyIt;

    /// The value type of the iterator.

    typedef typename Map::ValueType ValueType;

    /// The reference type of the iterator.

    typedef typename Map::ReferenceType ReferenceType;

    /// The pointer type of the iterator.

    typedef typename Map::PointerType PointerType;

    /// The const value type of the iterator.

    typedef typename Map::ConstValueType ConstValueType;

    /// The const reference type of the iterator.

    typedef typename Map::ConstReferenceType ConstReferenceType;

    /// The pointer type of the iterator.

    typedef typename Map::ConstPointerType ConstPointerType;

  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.

    ConstReferenceType operator*() const {

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

    }

    /// The arrow operator of the iterator.

    ConstPointerType operator->() const {

      return &(operator*());

    }

  public:

    // STL  compatibility typedefs.

    typedef std::input_iterator_tag iterator_category;

    typedef int difference_type;

    typedef ValueType value_type;

    typedef ConstReferenceType reference;

    typedef ConstPointerType 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::KeyType KeyType;

    /// The iterator to iterate on the keys.

    typedef typename Map::KeyIt KeyIt;

    /// The value type of the iterator.

    typedef typename Map::ValueType ValueType;

    /// The reference type of the iterator.

    typedef typename Map::ReferenceType ReferenceType;

    /// The pointer type of the iterator.

    typedef typename Map::PointerType PointerType;

    /// The const value type of the iterator.

    typedef typename Map::ConstValueType ConstValueType;

    /// The const reference type of the iterator.

    typedef typename Map::ConstReferenceType ConstReferenceType;

    /// The pointer type of the iterator.

    typedef typename Map::ConstPointerType ConstPointerType;

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

    typedef ConstIterator const_iterator;

    typedef ConstReferenceType const_reference;

    typedef ConstPointerType 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::KeyType KeyType;

    /// The iterator to iterate on the keys.

    typedef typename Map::KeyIt KeyIt;

    /// The value type of the iterator.

    typedef typename Map::ValueType ValueType;

    /// The reference type of the iterator.

    typedef typename Map::ReferenceType ReferenceType;

    /// The pointer type of the iterator.

    typedef typename Map::PointerType PointerType;

    /// The const value type of the iterator.

    typedef typename Map::ConstValueType ConstValueType;

    /// The const reference type of the iterator.

    typedef typename Map::ConstReferenceType ConstReferenceType;

    /// The pointer type of the iterator.

    typedef typename Map::ConstPointerType ConstPointerType;

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

    typedef ConstIterator const_iterator;

    typedef ConstReferenceType const_reference;

    typedef ConstPointerType 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::KeyType KeyType;

    /// The iterator to iterate on the keys.

    typedef typename Map::KeyIt KeyIt;

    /// The value type of the iterator.

    typedef typename Map::ValueType ValueType;

    /// The reference type of the iterator.

    typedef typename Map::ReferenceType ReferenceType;

    /// The pointer type of the iterator.

    typedef typename Map::PointerType PointerType;

    /// The const value type of the iterator.

    typedef typename Map::ConstValueType ConstValueType;

    /// The const reference type of the iterator.

    typedef typename Map::ConstReferenceType ConstReferenceType;

    /// The pointer type of the iterator.

    typedef typename Map::ConstPointerType ConstPointerType;

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

    typedef Iterator iterator;

    typedef ConstIterator const_iterator;

    typedef ReferenceType reference;

    typedef ConstReferenceType const_reference;

    typedef PointerType pointer;

    typedef ConstPointerType const_pointer;

    typedef int difference_type;

  };

  /// @}

}

#endif