alpar@906: /* -*- C++ -*-
alpar@921:  * src/lemon/map_iterator.h - Part of LEMON, a generic C++ optimization library
alpar@906:  *
alpar@1164:  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1359:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@906:  *
alpar@906:  * Permission to use, modify and distribute this software is granted
alpar@906:  * provided that this copyright notice appears in all copies. For
alpar@906:  * precise terms see the accompanying LICENSE file.
alpar@906:  *
alpar@906:  * This software is provided "AS IS" with no warranty of any kind,
alpar@906:  * express or implied, and with no claim as to its suitability for any
alpar@906:  * purpose.
alpar@906:  *
alpar@906:  */
alpar@906: 
alpar@921: #ifndef LEMON_MAP_ITERATOR_H
alpar@921: #define LEMON_MAP_ITERATOR_H
deba@822: 
deba@844: #include <iterator>
deba@844: 
deba@1307: #include <lemon/bits/extended_pair.h>
alpar@1402: #include <lemon/graph_utils.h>
deba@822: 
deba@830: ///\ingroup graphmaps
deba@830: ///\file
deba@830: ///\brief Iterators on the maps.
deba@830: 
alpar@921: namespace lemon {
deba@822: 
deba@830:   /// \addtogroup graphmaps
deba@830:   /// @{
deba@830: 
deba@830:   /** The base class all of the map iterators.
deba@830:    *  The class defines the typedefs of the iterators,
deba@830:    *  simple step functions and equality operators.
deba@830:    */ 
deba@822: 
deba@1267:   template <
deba@1267:     typename _Graph,
deba@1267:     typename _Item>
deba@830:   class MapIteratorBase {
deba@822: 
deba@830:   protected:
deba@830: 
deba@1267:     /// The key type of the iterator.
deba@1267:     typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
deba@1267: 
deba@1267:     ItemIt it;
deba@830: 
deba@830:     /// Default constructor.
deba@830:     MapIteratorBase() {}
deba@830: 
deba@1267:     /// ItemIt initialized MapIteratorBase constructor.
deba@1267:     MapIteratorBase(const ItemIt _it) : it(_it) {}
deba@830: 
deba@830:   public:
deba@830: 
deba@830:     /// Stepping forward in the map.   
deba@830:     void increment() { 
deba@830:       ++it; 
deba@830:     }
deba@830: 
deba@830:     /// The equality operator of the map.
deba@1267:     bool operator==(const MapIteratorBase& _it) const {
deba@1267:       return _it.it == it;
deba@830:     }
deba@830: 	
deba@830:     /// The not-equality operator of the map.
deba@1267:     bool operator!=(const MapIteratorBase& _it) const {
deba@1267:       return !(*this == _it);
deba@830:     }
deba@830:   };
deba@830: 
deba@1267: 
deba@1267:   template <
deba@1267:     typename _Graph,
deba@1267:     typename _Item,
deba@1267:     typename _Map>
deba@1267:   class MapConstIterator;
deba@822: 
deba@822:   /** Compatible iterator with the stl maps' iterators.
deba@830:    * It iterates on pairs of a key and a value.
deba@822:    */
deba@1267:   template <
deba@1267:     typename _Graph,
deba@1267:     typename _Item,
deba@1267:     typename _Map>
deba@1267:   class MapIterator : public MapIteratorBase<_Graph, _Item> {
deba@830: 
deba@1267:     friend class MapConstIterator<_Graph, _Item, _Map>;
deba@822: 
deba@844: 
deba@822:   public:
deba@822: 
deba@844:     /// The iterator base class.
deba@1267:     typedef MapIteratorBase<_Graph, _Item> Parent;
deba@844: 
deba@1267:     typedef _Item Item;
deba@1267:     typedef _Map Map;
deba@1267:     typedef _Graph Graph;
deba@822: 
deba@1267:   protected:
deba@822: 
deba@1267:     typedef typename Parent::ItemIt ItemIt;
deba@1267: 
deba@1267:     typedef typename ReferenceMapTraits<_Map>::Value MapValue;
deba@1267:     typedef typename ReferenceMapTraits<_Map>::Reference MapReference;
deba@822:     
deba@822:   public:
deba@822: 
deba@844:     /// The value type of the iterator.
deba@1267:     typedef extended_pair<Item, const Item&,
deba@1267:       MapValue, const MapValue&> Value;
deba@844: 
deba@830:     /// The reference type of the iterator. 
deba@1267:     typedef extended_pair<const Item&, const Item&, 
deba@1267:       MapReference, MapReference> Reference;
deba@822: 
deba@830:     /// Default constructor. 
deba@830:     MapIterator() {}
deba@830: 
deba@830:     /// Constructor to initalize the iterators returned 
deba@830:     /// by the begin() and end().
deba@1267:     MapIterator(Map& _map, const ItemIt& _it) 
deba@1267:       : Parent(_it), map(&_map) {}
deba@830: 
deba@830:     /// Dereference operator for the iterator.
deba@1267:     Reference operator*() {
deba@1267:       return Reference(Parent::it, (*map)[Parent::it]);
deba@822:     }
deba@822: 
deba@830:     /// The pointer type of the iterator.
deba@1267:     class Pointer {
deba@822:       friend class MapIterator;
deba@1267:     protected:
deba@1267:       Reference data;
deba@1267:       Pointer(const Item& item, MapReference val) 
deba@1267: 	: data(item, val) {}
deba@822:     public:
deba@1267:       Reference* operator->() {return &data;}
deba@822:     };
deba@822: 
deba@830:     /// Arrow operator for the iterator.
deba@1267:     Pointer operator->() {
deba@1267:       return Pointer(Parent::it, (*map)[Parent::it]); 
deba@822:     }
deba@830: 	
deba@830:     /// The pre increment operator of the iterator.
deba@822:     MapIterator& operator++() { 
deba@1267:       Parent::increment(); 
deba@822:       return *this; 
deba@822:     }
deba@822: 
deba@830:     /// The post increment operator of the iterator.
deba@822:     MapIterator operator++(int) { 
deba@844:       MapIterator tmp(*this); 
deba@1267:       Parent::increment(); 
deba@822:       return tmp; 
deba@822:     }
deba@822: 
deba@1267:   protected:
deba@1267: 
deba@822:     Map* map;
deba@844: 
deba@844:   public:
deba@844:     // STL  compatibility typedefs.
deba@844:     typedef std::forward_iterator_tag iterator_category;
deba@844:     typedef int difference_type;
deba@1267:     typedef Value value_type;
deba@1267:     typedef Reference reference;
deba@1267:     typedef Pointer pointer;
deba@822:   };
deba@822: 
deba@822:   /** Compatible iterator with the stl maps' iterators.
deba@822:    *  It iterates on pairs of a key and a value.
deba@822:    */
deba@1267:   template <
deba@1267:     typename _Graph,
deba@1267:     typename _Item,
deba@1267:     typename _Map>
deba@1267:   class MapConstIterator : public MapIteratorBase<_Graph, _Item> {
deba@1267: 
deba@1267:   public:
deba@1267: 
deba@1267:     /// The iterator base class.
deba@1267:     typedef MapIteratorBase<_Graph, _Item> Parent;
deba@1267: 
deba@1267:     typedef _Graph Graph;
deba@1267:     typedef _Item Item;
deba@1267:     typedef _Map Map;
deba@1267: 
deba@1267:   protected:
deba@1267: 
deba@1267:     typedef typename Parent::ItemIt ItemIt;
deba@1267: 
deba@1267:     typedef typename ReferenceMapTraits<_Map>::Value MapValue;
deba@1267:     typedef typename ReferenceMapTraits<_Map>::ConstReference
deba@1267:     MapReference;
deba@830:     
deba@822:   public:
deba@822: 
deba@1267:     /// The value type of the iterator.
deba@1267:     typedef extended_pair<Item, const Item&,
deba@1267:       MapValue, const MapValue&> Value;
deba@844: 
deba@1267:     /// The reference type of the iterator. 
deba@1267:     typedef extended_pair<const Item&, const Item&, 
deba@1267:       MapReference, MapReference> Reference;
deba@822: 
deba@830:     /// Default constructor. 
deba@822:     MapConstIterator() {}
deba@822: 
deba@1267:     /// Constructor to initalize the iterators returned 
deba@1267:     /// by the begin() and end().
deba@1267:     MapConstIterator(const Map& _map, const ItemIt& _it) 
deba@1267:       : Parent(_it), map(&_map) {}
deba@822: 
deba@830:     /// Dereference operator for the iterator.
deba@1267:     Reference operator*() {
deba@1267:       return Reference(Parent::it, (*map)[Parent::it]);
deba@822:     }
deba@822: 
deba@830:     /// The pointer type of the iterator.
deba@1267:     class Pointer {
deba@822:       friend class MapConstIterator;
deba@1267:     protected:
deba@1267:       Reference data;
deba@1267:       Pointer(const Item& item, MapReference val) 
deba@1267: 	: data(item, val) {}
deba@822:     public:
deba@1267:       Reference* operator->() {return &data;}
deba@822:     };
deba@822: 
deba@830:     /// Arrow operator for the iterator.
deba@1267:     Pointer operator->() {
deba@1267:       return Pointer(Parent::it, ((*map)[Parent::it])); 
deba@822:     }
deba@1267: 	
deba@830:     /// The pre increment operator of the iterator.
deba@822:     MapConstIterator& operator++() { 
deba@1267:       Parent::increment(); 
deba@822:       return *this; 
deba@822:     }
deba@822: 
deba@830:     /// The post increment operator of the iterator.
deba@822:     MapConstIterator operator++(int) { 
deba@844:       MapConstIterator tmp(*this); 
deba@1267:       Parent::increment(); 
deba@822:       return tmp; 
deba@822:     }
deba@822: 
deba@1267:   protected:
deba@830:     const Map* map;
deba@844: 
deba@844:   public:
deba@844:     // STL  compatibility typedefs.
deba@1267:     typedef std::forward_iterator_tag iterator_category;
deba@844:     typedef int difference_type;
deba@1267:     typedef Value value_type;
deba@1267:     typedef Reference reference;
deba@1267:     typedef Pointer pointer;
deba@830:   };
deba@1267:  
deba@1267:   /** The class makes the ItemIt to an stl compatible iterator
deba@830:    *  with dereferencing operator.
deba@830:    */
deba@1267:   template <
deba@1267:     typename _Graph,
deba@1267:     typename _Item>
deba@1267:   class MapConstKeyIterator : public MapIteratorBase<_Graph, _Item> {
deba@830: 
deba@830:   public:
deba@830: 
deba@844:     /// The iterator base class.
deba@1267:     typedef MapIteratorBase<_Graph, _Item> Parent;
deba@844:  
deba@1267:     typedef _Graph Graph;
deba@1267:     typedef _Item Item;
deba@1267: 
deba@1267:   protected:
deba@830:     /// The iterator to iterate on the keys.
deba@1267:     typedef typename Parent::ItemIt ItemIt;
deba@830: 
deba@830:   public:
deba@830: 
deba@1267:     typedef Item Value;
deba@1267:     typedef const Item& Reference;
deba@1267:     typedef const Item* Pointer;
deba@1267: 
deba@830:     /// Default constructor.
deba@1267:     MapConstKeyIterator() {}
deba@830: 
deba@1267:     /// ItemIt initialized iterator.
deba@1267:     MapConstKeyIterator(const ItemIt& pit) : Parent(pit) {}
deba@830: 
deba@830:     /// The pre increment operator of the iterator.
deba@1267:     MapConstKeyIterator& operator++() {
deba@1267:       Parent::increment(); 
deba@830:       return *this; 
deba@822:     }
deba@822: 
deba@830:     /// The post increment operator of the iterator.
deba@1267:     MapConstKeyIterator operator++(int) {
deba@1267:       MapConstKeyIterator tmp(*this);
deba@1267:       Parent::increment();
deba@830:       return tmp;
deba@822:     }
deba@830: 
deba@830:     /// The dereferencing operator of the iterator.
deba@1267:     Item operator*() const {
deba@1267:       return static_cast<Item>(Parent::it);
deba@822:     }
deba@844: 
deba@844:   public:
deba@844:     // STL  compatibility typedefs.
deba@844:     typedef std::input_iterator_tag iterator_category;
deba@844:     typedef int difference_type;
deba@1267:     typedef Value value_type;
deba@1267:     typedef Reference reference;
deba@1267:     typedef Pointer pointer;
deba@830:   };
deba@830: 
deba@1267:   template <
deba@1267:     typename _Graph, 
deba@1267:     typename _Item,
deba@1267:     typename _Map>
deba@1267:   class MapConstValueIterator;
deba@830: 
deba@844:   /** MapValueIterator creates an stl compatible iterator
deba@844:    *  for the values.
deba@844:    */
deba@1267:   template <
deba@1267:     typename _Graph,
deba@1267:     typename _Item,
deba@1267:     typename _Map>
deba@1267:   class MapValueIterator : public MapIteratorBase<_Graph, _Item> {
deba@830: 
deba@1267:     friend class MapConstValueIterator<_Graph, _Item, _Map>;
deba@830: 
deba@830:   public:
deba@830: 
deba@844:     /// The iterator base class.
deba@1267:     typedef MapIteratorBase<_Graph, _Item> Parent;
deba@844: 
deba@1267:     typedef _Graph Graph;
deba@1267:     typedef _Item Item;
deba@1267:     typedef _Map Map;
deba@1267: 
deba@1267:   protected:
deba@1267: 
deba@830:     /// The iterator to iterate on the keys.
deba@1267:     typedef typename Parent::ItemIt ItemIt;
deba@830: 
deba@830:     /// The value type of the iterator.
deba@1267:     typedef typename ReferenceMapTraits<Map>::Value MapValue;
deba@830:     /// The reference type of the iterator.
deba@1267:     typedef typename ReferenceMapTraits<Map>::Reference MapReference;
deba@830:     /// The pointer type of the iterator.
deba@1267:     typedef typename ReferenceMapTraits<Map>::Pointer MapPointer;
deba@830: 
deba@830:   public:
deba@830: 
deba@1267:     typedef MapValue Value;
deba@1267:     typedef MapReference Reference;
deba@1267:     typedef MapPointer Pointer;
deba@1267: 
deba@830:     /// Default constructor.
deba@830:     MapValueIterator() {}
deba@830: 
deba@1267:     /// Map and ItemIt initialized iterator.
deba@1267:     MapValueIterator(Map& _map, const ItemIt& _it) 
deba@1267:       : Parent(_it), map(&_map) {}
deba@830:     
deba@830: 
deba@830:     /// The pre increment operator of the iterator.
deba@830:     MapValueIterator& operator++() {
deba@1267:       Parent::increment(); 
deba@830:       return *this; 
deba@830:     }
deba@830: 
deba@830:     /// The post increment operator of the iterator.
deba@830:     MapValueIterator operator++(int) {
deba@830:       MapValueIterator tmp(*this);
deba@1267:       Parent::increment();
deba@830:       return tmp;
deba@830:     }
deba@830: 
deba@830:     /// The dereferencing operator of the iterator.
alpar@987:     Reference operator*() const {
deba@1267:       return (*map)[Parent::it];
deba@830:     }
deba@830: 
deba@830:     /// The arrow operator of the iterator.
alpar@987:     Pointer operator->() const {
deba@830:       return &(operator*());
deba@830:     }
deba@830: 
deba@1267:   protected:
deba@1267: 
deba@1267:     Map* map;
deba@1267: 
deba@844:   public:
deba@844:     // STL  compatibility typedefs.
deba@844:     typedef std::forward_iterator_tag iterator_category;
deba@844:     typedef int difference_type;
alpar@987:     typedef Value value_type;
alpar@987:     typedef Reference reference;
alpar@987:     typedef Pointer pointer;
deba@830:   };
deba@830: 
deba@844:   /** MapValueIterator creates an stl compatible iterator
deba@1267:    *  for the values.
deba@844:    */
deba@1267:   template <
deba@1267:     typename _Graph,
deba@1267:     typename _Item,
deba@1267:     typename _Map>
deba@1267:   class MapConstValueIterator : public MapIteratorBase<_Graph, _Item> {
deba@830: 
deba@830:   public:
deba@830: 
deba@844:     /// The iterator base class.
deba@1267:     typedef MapIteratorBase<_Graph, _Item> Parent;
deba@844: 
deba@1267:     typedef _Graph Graph;
deba@1267:     typedef _Item Item;
deba@1267:     typedef _Map Map;
deba@1267: 
deba@1267:   protected:
deba@1267: 
deba@830:     /// The iterator to iterate on the keys.
deba@1267:     typedef typename Parent::ItemIt ItemIt;
deba@830: 
deba@830:     /// The value type of the iterator.
deba@1267:     typedef typename ReferenceMapTraits<Map>::Value MapValue;
deba@830:     /// The reference type of the iterator.
deba@1267:     typedef typename ReferenceMapTraits<Map>::ConstReference MapReference;
deba@830:     /// The pointer type of the iterator.
deba@1267:     typedef typename ReferenceMapTraits<Map>::ConstPointer MapPointer;
deba@830: 
deba@830:   public:
deba@830: 
deba@1267:     typedef MapValue Value;
deba@1267:     typedef MapReference Reference;
deba@1267:     typedef MapPointer Pointer;
deba@1267: 
deba@830:     /// Default constructor.
deba@830:     MapConstValueIterator() {}
deba@830: 
deba@1267:     /// Map and ItemIt initialized iterator.
deba@1267:     MapConstValueIterator(const Map& _map, const ItemIt& _it) 
deba@1267:       : Parent(_it), map(&_map) {}
deba@1267:     
deba@830: 
deba@830:     /// The pre increment operator of the iterator.
deba@830:     MapConstValueIterator& operator++() {
deba@1267:       Parent::increment(); 
deba@830:       return *this; 
deba@830:     }
deba@830: 
deba@830:     /// The post increment operator of the iterator.
deba@830:     MapConstValueIterator operator++(int) {
deba@830:       MapConstValueIterator tmp(*this);
deba@1267:       Parent::increment();
deba@830:       return tmp;
deba@830:     }
deba@830: 
deba@830:     /// The dereferencing operator of the iterator.
deba@1267:     Reference operator*() const {
deba@1267:       return (*map)[Parent::it];
deba@830:     }
deba@830: 
deba@830:     /// The arrow operator of the iterator.
deba@1267:     Pointer operator->() const {
deba@830:       return &(operator*());
deba@830:     }
deba@830: 
deba@1267:   protected:
deba@1267: 
deba@1267:     const Map* map;
deba@1267: 
deba@844:   public:
deba@844:     // STL  compatibility typedefs.
deba@1267:     typedef std::forward_iterator_tag iterator_category;
deba@844:     typedef int difference_type;
alpar@987:     typedef Value value_type;
deba@1267:     typedef Reference reference;
deba@1267:     typedef Pointer pointer;
deba@822:   };
deba@822: 
deba@830: 
deba@830:   /** This class makes from a map an iteratable set
deba@830:    *  which contains all the keys of the map.
deba@830:    */
deba@1267:   template <typename _Graph, typename _Item>
deba@830:   class MapConstKeySet {
deba@830: 
deba@830:   public:
deba@830: 
deba@1267:     typedef _Graph Graph;
deba@830:     /// The key type of the iterator.
deba@1267:     typedef _Item Item;
deba@830:     /// The iterator to iterate on the keys.
deba@830: 
deba@1267:   protected:
deba@844: 
deba@1267:     typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
deba@844: 
deba@1267:   public:
deba@844: 
deba@830:     /// The map initialized const key set.
deba@1267:     MapConstKeySet(const Graph& _graph) : graph(&_graph) {}
deba@830: 
deba@830:     /// The const iterator of the set.
deba@1267:     typedef MapConstKeyIterator<_Graph, _Item> ConstIterator;
deba@1267: 
deba@1267:     typedef typename ConstIterator::Value Value;
deba@1267:     /// The reference type of the iterator.
deba@1267:     typedef typename ConstIterator::Reference ConstReference;
deba@1267:     /// The pointer type of the iterator.
deba@1267:     typedef typename ConstIterator::Pointer ConstPointer;
deba@830: 
deba@830:     /// It gives back the const iterator pointed to the first element.
deba@830:     ConstIterator begin() const {
deba@1267:       return ConstIterator(ItemIt(*graph));
deba@830:     }
deba@830:             
deba@830:     /// It gives back the const iterator pointed to the first ivalid element.
deba@830:     ConstIterator end() const {
deba@1267:       return ConstIterator(ItemIt(INVALID));
deba@830:     }
deba@1267: 
deba@1267:   protected:
deba@1267: 
deba@1267:     const Graph* graph;
deba@844:  
deba@844:   public:
deba@844:     // STL  compatibility typedefs.
alpar@987:     typedef Value value_type;
deba@844:     typedef ConstIterator const_iterator;
alpar@987:     typedef ConstReference const_reference;
alpar@987:     typedef ConstPointer const_pointer;
deba@844:     typedef int difference_type;
deba@830:   };
deba@830: 
deba@830:   /** This class makes from a map an iteratable set
deba@830:    *  which contains all the values of the map.
deba@830:    *  The values cannot be modified.
deba@830:    */
deba@1267:   template <typename _Graph, typename _Item, typename _Map>
deba@830:   class MapConstValueSet {
deba@830: 
deba@1267:   public:
deba@1267:     
deba@1267:     typedef _Graph Graph;
deba@1267:     typedef _Item Item;
deba@1267:     typedef _Map Map;
deba@1267: 
deba@1267:   protected:
deba@1267: 
deba@1267:     /// The iterator to iterate on the keys.
deba@1267:     typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
deba@830: 
deba@830:   public:
deba@830: 
deba@830:     /// The map initialized const value set.
deba@1267:     MapConstValueSet(const Graph& _graph, const Map& _map) 
deba@1267:       : graph(&_graph), map(&_map) {}
deba@830: 
deba@830:     /// The const iterator of the set.
deba@1267:     typedef MapConstValueIterator<_Graph, _Item, _Map> ConstIterator;
deba@1267: 
deba@1267:     typedef typename ConstIterator::Value Value;
deba@1267:     typedef typename ConstIterator::Reference ConstReference;
deba@1267:     typedef typename ConstIterator::Pointer ConstPointer;
deba@830: 
deba@830:     /// It gives back the const iterator pointed to the first element.
deba@830:     ConstIterator begin() const {
deba@1267:       return ConstIterator(*map, ItemIt(*graph));
deba@830:     }
deba@830: 
deba@830:     /// It gives back the const iterator pointed to the first invalid element.
deba@830:     ConstIterator end() const {
deba@1267:       return ConstIterator(*map, ItemIt(INVALID));
deba@830:     }
deba@844: 
deba@1267:   protected:
deba@1267:     
deba@1267:     const Map* map;
deba@1267:     const Graph * graph;
deba@1267: 
deba@844:   public:
deba@844:     // STL  compatibility typedefs.
alpar@987:     typedef Value value_type;
deba@844:     typedef ConstIterator const_iterator;
alpar@987:     typedef ConstReference const_reference;
alpar@987:     typedef ConstPointer const_pointer;
deba@844:     typedef int difference_type;
deba@830:   };
deba@830: 
deba@830: 
deba@830:   /** This class makes from a map an iteratable set
deba@830:    *  which contains all the values of the map.
deba@830:    *  The values can be modified.
deba@830:    */
deba@1267:   template <typename _Graph, typename _Item, typename _Map>
deba@830:   class MapValueSet {
deba@830: 
deba@1267:   public:
deba@1267:     
deba@1267:     typedef _Graph Graph;
deba@1267:     typedef _Item Item;
deba@1267:     typedef _Map Map;
deba@1267: 
deba@1267:   protected:
deba@1267: 
deba@1267:     /// The iterator to iterate on the keys.
deba@1267:     typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
deba@830: 
deba@830:   public:
deba@830: 
deba@1267:     /// The map initialized const value set.
deba@1267:     MapValueSet(const Graph& _graph, Map& _map) 
deba@1271:       : map(&_map), graph(&_graph) {}
deba@830: 
deba@830:     /// The const iterator of the set.
deba@1267:     typedef MapValueIterator<_Graph, _Item, _Map> Iterator;
deba@1267:     /// The const iterator of the set.
deba@1267:     typedef MapConstValueIterator<_Graph, _Item, _Map> ConstIterator;
deba@1267: 
deba@1267:     typedef typename ConstIterator::Value Value;
deba@1267:     typedef typename Iterator::Reference Reference;
deba@1267:     typedef typename Iterator::Pointer Pointer;
deba@1267:     typedef typename ConstIterator::Reference ConstReference;
deba@1267:     typedef typename ConstIterator::Pointer ConstPointer;
deba@830: 
deba@830:     /// It gives back the const iterator pointed to the first element.
deba@830:     ConstIterator begin() const {
deba@1267:       return ConstIterator(*map, ItemIt(*graph));
deba@830:     }
deba@830: 
deba@830:     /// It gives back the const iterator pointed to the first invalid element.
deba@830:     ConstIterator end() const {
deba@1267:       return ConstIterator(*map, ItemIt(INVALID));
deba@830:     }
deba@830: 
deba@830:     /// It gives back the iterator pointed to the first element.
deba@830:     Iterator begin() {
deba@1267:       return Iterator(*map, ItemIt(*graph));
deba@830:     }
deba@830: 
deba@830:     /// It gives back the iterator pointed to the first invalid element.
deba@830:     Iterator end() {
deba@1267:       return Iterator(*map, ItemIt(INVALID));
deba@830:     }
deba@1267: 
deba@1267:   protected:
deba@1267:     
deba@1267:     Map* map;
deba@1267:     const Graph * graph;
deba@1267: 
deba@1267:   public:
deba@1267:     // STL  compatibility typedefs.
deba@1267:     typedef Value value_type;
deba@1267:     typedef Iterator iterator;
deba@1267:     typedef ConstIterator const_iterator;
deba@1267:     typedef Reference reference;
deba@1267:     typedef ConstReference const_reference;
deba@1267:     typedef Pointer pointer;
deba@1267:     typedef ConstPointer const_pointer;
deba@1267:     typedef int difference_type;
deba@1267: 
deba@1267:   };
deba@1267: 
deba@1267:   /** This class makes from a map an iteratable set
deba@1267:    *  which contains all the values of the map.
deba@1267:    *  The values can be modified.
deba@1267:    */
deba@1267:   template <
deba@1267:     typename _Graph, 
deba@1267:     typename _Item,
deba@1267:     typename _Map
deba@1267:     >
deba@1267:   class MapSet {
deba@1267:   public:    
deba@1267: 
deba@1267:     typedef _Graph Graph;
deba@1267:     typedef _Item Item;
deba@1267:     typedef _Map Map;
deba@1267: 
deba@1267:   protected:
deba@1267: 
deba@1267:     typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
deba@1267: 
deba@1267:   public:
deba@1267: 
deba@1267:     /// The map initialized value set.
deba@1267:     MapSet(const Graph& _graph, Map& _map) : graph(&_graph), map(&_map) {}
deba@1267: 
deba@1267:     /// The const iterator of the set.
deba@1267:     typedef MapIterator<_Graph, _Item, _Map> Iterator;
deba@1267:     typedef MapConstIterator<_Graph, _Item, _Map> ConstIterator;
deba@1267: 
deba@1267:     typedef typename ConstIterator::Value Value;
deba@1267:     typedef typename Iterator::Reference Reference;
deba@1267:     typedef typename Iterator::Pointer Pointer;
deba@1267:     typedef typename ConstIterator::Reference ConstReference;
deba@1267:     typedef typename ConstIterator::Pointer ConstPointer;
deba@1267: 
deba@1267: 
deba@1267:     /// It gives back the const iterator pointed to the first element.
deba@1267:     ConstIterator begin() const {
deba@1267:       return ConstIterator(*map, ItemIt(*graph));
deba@1267:     }
deba@1267: 
deba@1267:     /// It gives back the const iterator pointed to the first invalid element.
deba@1267:     ConstIterator end() const {
deba@1267:       return ConstIterator(*map, ItemIt(INVALID));
deba@1267:     }
deba@1267: 
deba@1267:     /// The iterator of the set.
deba@1267: 
deba@1267:     /// It gives back the iterator pointed to the first element.
deba@1267:     Iterator begin() {
deba@1267:       return Iterator(*map, ItemIt(*graph));
deba@1267:     }
deba@1267: 
deba@1267:     /// It gives back the iterator pointed to the first invalid element.
deba@1267:     Iterator end() {
deba@1267:       return Iterator(*map, ItemIt(INVALID));
deba@1267:     }
deba@1267: 
deba@1267:   protected:
deba@1267:     
deba@1267:     const Graph* graph;
deba@1267:     Map* map;
deba@830:             
deba@844:   public:
deba@844:     // STL  compatibility typedefs.
alpar@987:     typedef Value value_type;
deba@844:     typedef Iterator iterator;
deba@844:     typedef ConstIterator const_iterator;
alpar@987:     typedef Reference reference;
alpar@987:     typedef ConstReference const_reference;
alpar@987:     typedef Pointer pointer;
alpar@987:     typedef ConstPointer const_pointer;
deba@844:     typedef int difference_type;
deba@844: 
deba@830:   };
deba@830: 
deba@1267:   template <
deba@1267:     typename _Graph, 
deba@1267:     typename _Item,
deba@1267:     typename _Map
deba@1267:     >
deba@1267:   class ConstMapSet {
deba@1267:     
deba@1267:     typedef _Graph Graph;
deba@1267:     typedef _Map Map;
deba@1267: 
deba@1267:     const Graph* graph;
deba@1267:     const Map* map;
deba@1267: 
deba@1267:   public:
deba@1267: 
deba@1267:     typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
deba@1267: 
deba@1267: 
deba@1267:     /// The map initialized value set.
deba@1267:     ConstMapSet(const Graph& _graph, const Map& _map) 
deba@1267:       : graph(&_graph), map(&_map) {}
deba@1267: 
deba@1267:     /// The const iterator of the set.
deba@1267:     typedef MapConstIterator<_Graph, _Item, _Map> ConstIterator;
deba@1267: 
deba@1267:     typedef typename ConstIterator::Value Value;
deba@1267:     typedef typename ConstIterator::Reference ConstReference;
deba@1267:     typedef typename ConstIterator::Pointer ConstPointer;
deba@1267: 
deba@1267: 
deba@1267:     /// It gives back the const iterator pointed to the first element.
deba@1267:     ConstIterator begin() const {
deba@1267:       return ConstIterator(*map, ItemIt(*graph));
deba@1267:     }
deba@1267: 
deba@1267:     /// It gives back the const iterator pointed to the first invalid element.
deba@1267:     ConstIterator end() const {
deba@1267:       return ConstIterator(*map, ItemIt(INVALID));
deba@1267:     }
deba@1267:             
deba@1267:   public:
deba@1267:     // STL  compatibility typedefs.
deba@1267:     typedef Value value_type;
deba@1267:     typedef ConstIterator const_iterator;
deba@1267:     typedef ConstReference const_reference;
deba@1267:     typedef ConstPointer const_pointer;
deba@1267:     typedef int difference_type;
deba@1267: 
deba@1267:   };
deba@1267: 
deba@1267:   template <typename _Map>
deba@1267:   class IterableMapExtender : public _Map {
deba@1267:   public:
deba@1267: 
deba@1267:     typedef _Map Parent;
deba@1267:     typedef Parent Map;
deba@1267:     typedef typename Map::Graph Graph;
deba@1267:     typedef typename Map::Key Item;
deba@1267:     typedef typename Map::Value Value;
deba@1267: 
deba@1267:     typedef MapSet<Graph, Item, Map> MapSet;
deba@1267: 
deba@1267:     IterableMapExtender() : Parent() {}
deba@1267: 
deba@1267:     IterableMapExtender(const Graph& graph) : Parent(graph) {}
deba@1267: 
deba@1267:     IterableMapExtender(const Graph& graph, const Value& value) 
deba@1267:       : Parent(graph, value) {}
deba@1267: 
deba@1267:     MapSet mapSet() { 
deba@1267:       return MapSet(*Parent::getGraph(), *this); 
deba@1267:     }
deba@1267: 
deba@1267:     typedef ConstMapSet<Graph, Item, Map> ConstMapSet;
deba@1267: 
deba@1267:     ConstMapSet mapSet() const { 
deba@1267:       return ConstMapSet(*Parent::getGraph(), *this); 
deba@1267:     }
deba@1267: 
deba@1267:     typedef MapConstKeySet<Graph, Item> ConstKeySet;
deba@1267:  
deba@1267:     ConstKeySet keySet() const {
deba@1267:       return ConstKeySet(*Parent::getGraph());
deba@1267:     }
deba@1267: 
deba@1267:     typedef MapValueSet<Graph, Item, Map> ValueSet;
deba@1267:  
deba@1267:     ValueSet valueSet() {
deba@1267:       return ValueSet(*Parent::getGraph(), *this);
deba@1267:     }
deba@1267: 
deba@1267:     typedef MapConstValueSet<Graph, Item, Map> ConstValueSet;
deba@1267:  
deba@1267:     ConstValueSet valueSet() const {
deba@1267:       return ConstValueSet(*Parent::getGraph(), *this);
deba@1267:     }
deba@1267: 
deba@1267:   };
deba@1267: 
deba@830:   /// @}
deba@830: 
deba@822: }
deba@822: 
deba@822: #endif