diff -r d8475431bbbb -r 8e85e6bbefdf src/lemon/bits/map_iterator.h
--- a/src/lemon/bits/map_iterator.h	Sat May 21 21:04:57 2005 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,855 +0,0 @@
-/* -*- 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