diff -r d8475431bbbb -r 8e85e6bbefdf lemon/bits/map_iterator.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/bits/map_iterator.h	Mon May 23 04:48:14 2005 +0000
@@ -0,0 +1,855 @@
+/* -*- 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