# HG changeset patch
# User deba
# Date 1095017541 0
# Node ID 89dfa3bece81019cff46d002279177361eb80993
# Parent  ef91373d37a8b87b2ff4b874b26ca0d598594bc7
KeySet and ValueSet are inserted into the map structures.
They makes possible the iterating on the keys or values only.

diff -r ef91373d37a8 -r 89dfa3bece81 src/hugo/Makefile.am
--- a/src/hugo/Makefile.am	Thu Sep 09 09:40:45 2004 +0000
+++ b/src/hugo/Makefile.am	Sun Sep 12 19:32:21 2004 +0000
@@ -23,7 +23,6 @@
 	minlengthpaths.h                                                \
 	smart_graph.h							\
 	sym_map.h                                                       \
-	sym_map_factory.h                                               \
 	time_measure.h							\
 	unionfind.h							\
 	vector_map.h                                                    \
diff -r ef91373d37a8 -r 89dfa3bece81 src/hugo/array_map.h
--- a/src/hugo/array_map.h	Thu Sep 09 09:40:45 2004 +0000
+++ b/src/hugo/array_map.h	Sun Sep 12 19:32:21 2004 +0000
@@ -251,6 +251,30 @@
       return ConstIterator(*this, INVALID);
     }
 
+    /// The KeySet of the Map.
+    typedef MapConstKeySet<ArrayMap> ConstKeySet;
+
+    /// KeySet getter function.
+    ConstKeySet keySet() const {
+      return ConstKeySet(*this); 
+    }
+
+    /// The ConstValueSet of the Map.
+    typedef MapConstValueSet<ArrayMap> ConstValueSet;
+
+    /// ConstValueSet getter function.
+    ConstValueSet valueSet() const {
+      return ConstValueSet(*this);
+    }
+
+    /// The ValueSet of the Map.
+    typedef MapValueSet<ArrayMap> ValueSet;
+
+    /// ValueSet getter function.
+    ValueSet valueSet() {
+      return ValueSet(*this);
+    }
+
   private:
       
     void allocate_memory() {
diff -r ef91373d37a8 -r 89dfa3bece81 src/hugo/map_iterator.h
--- a/src/hugo/map_iterator.h	Thu Sep 09 09:40:45 2004 +0000
+++ b/src/hugo/map_iterator.h	Sun Sep 12 19:32:21 2004 +0000
@@ -4,21 +4,79 @@
 
 #include <hugo/extended_pair.h>
 
+///\ingroup graphmaps
+///\file
+///\brief Iterators on the maps.
+
 namespace hugo {
 
+  /// \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 MapIterator;
+  class MapIteratorBase {
 
-  template <typename Map>
-  class MapConstIterator;
+  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.
+   * It iterates on pairs of a key and a value.
    */
   template <typename Map>  
-  class MapIterator {
-    //    friend class Map;
+  class MapIterator : public MapIteratorBase<Map> {
+
     friend class MapConstIterator<Map>;
 
   public:
@@ -44,27 +102,24 @@
     
   public:
 
-    /** Constructor to initalize the the iterators returned
-     *  by the begin() and end().
-     */
-    MapIterator (Map& pmap, const KeyIt& pit) 
-      : map(&pmap), it(pit) {}
-
-  public:
-
-    /** Default constructor. 
-     */
-    MapIterator() {}
-
+    /// The reference type of the iterator. 
     typedef extended_pair<const KeyType&, const KeyType&, 
       ReferenceType, ReferenceType> PairReferenceType;
 
-    /** Dereference operator for map.
-     */	 
+    /// Default constructor. 
+    MapIterator() {}
+
+    /// Constructor to initalize the iterators returned 
+    /// by the begin() and end().
+    MapIterator(Map& pmap, const KeyIt& pit) 
+      : MapIteratorBase<Map>(pit), map(&pmap) {}
+
+    /// Dereference operator for the iterator.
     PairReferenceType operator*() {
       return PairReferenceType(it, (*map)[it]);
     }
 
+    /// The pointer type of the iterator.
     class PairPointerType {
       friend class MapIterator;
     private:
@@ -75,64 +130,34 @@
       PairReferenceType* operator->() {return &data;}
     };
 
-    /** Arrow operator for map.
-     */	 
+    /// Arrow operator for the iterator.
     PairPointerType operator->() {
       return PairPointerType(it, ((*map)[it])); 
     }
-
-    /** The pre increment operator of the map.
-     */
+	
+    /// The pre increment operator of the iterator.
     MapIterator& operator++() { 
-      ++it; 
+      increment(); 
       return *this; 
     }
 
-    /** The post increment operator of the map.
-     */
+    /// The post increment operator of the iterator.
     MapIterator operator++(int) { 
       MapIterator tmp(it); 
-      ++it; 
+      increment(); 
       return tmp; 
     }
 
-    /** The equality operator of the map.
-     */
-    bool operator==(const MapIterator& p_it) const {
-      return p_it.it == it;
-    }
-	
-    /** The not-equality operator of the map.
-     */
-    bool operator!=(const MapIterator& p_it) const {
-      return !(*this == p_it);
-    }
-
-    /** The equality operator of the map.
-     */
-    bool operator==(const MapConstIterator<Map>& p_it) const {
-      return p_it.it == it;
-    }
-	
-    /** The not-equality operator of the map.
-     */
-    bool operator!=(const MapConstIterator<Map>& p_it) const {
-      return !(*this == p_it);
-    }
-	
   private:
     Map* map;
-    KeyIt it;
   };
 
   /** Compatible iterator with the stl maps' iterators.
    *  It iterates on pairs of a key and a value.
    */
   template <typename Map>
-  class MapConstIterator {
-    // friend class Map;
-    friend class MapIterator<Map>;
-
+  class MapConstIterator : public MapIteratorBase<Map> {
+    
   public:
 
     /// The key type of the iterator.
@@ -156,28 +181,30 @@
 
   public:    
 
-    /** Constructor to initalize the the iterators returned
-     *  by the begin() and end().
-     */
-
-    MapConstIterator (const Map& pmap, const KeyIt& pit) 
-      : map(&pmap), it(pit) {}
-
-  public:
-
-    /** Default constructor. 
-     */
+    /// Default constructor. 
     MapConstIterator() {}
 
+    /// Constructor to initalize the the iterators returned
+    ///  by the begin() and end().
+    MapConstIterator(const Map& pmap, const KeyIt& pit) 
+      : MapIteratorBase<Map>(pit), map(&pmap) {}
+
+    /// Constructor to create const iterator from a non const.
+    MapConstIterator(const MapIterator<Map>& pit) {
+      it = pit.it;
+      map = pit.map;
+    }
+
+    /// The reference type of map.
     typedef extended_pair<const KeyType&, const KeyType&, 
       ConstReferenceType, ConstReferenceType> PairReferenceType;
 
-    /** Dereference operator for map.
-     */	 
+    /// Dereference operator for the iterator.
     PairReferenceType operator*() {
       return PairReferenceType(it, (*map)[it]);
     }
 
+    /// The pointer type of the iterator.
     class PairPointerType {
       friend class MapConstIterator;
     private:
@@ -188,56 +215,322 @@
       PairReferenceType* operator->() {return &data;}
     };
 
-    /** Arrow operator for map.
-     */	 
+    /// Arrow operator for the iterator.
     PairPointerType operator->() {
       return PairPointerType(it, ((*map)[it])); 
     }
 
-    /** The pre increment operator of the map.
-     */
+    /// The pre increment operator of the iterator.
     MapConstIterator& operator++() { 
-      ++it; 
+      increment(); 
       return *this; 
     }
 
-    /** The post increment operator of the map.
-     */
+    /// The post increment operator of the iterator.
     MapConstIterator operator++(int) { 
       MapConstIterator<Map> tmp(it); 
-      ++it; 
+      increment(); 
       return tmp; 
     }
 
-    /** The equality operator of the map.
-     */
-    bool operator==(const MapIterator<Map>& p_it) const {
-      return p_it.it == it;
-    }
-	
-    /** The not-equality operator of the map.
-     */
-    bool operator!=(const MapIterator<Map>& p_it) const {
-      return !(*this == p_it);
+  private:
+    const Map* map;
+  };
+
+  /** The class makes the KeyIt to an stl compatible iterator
+   *  with dereferencing operator.
+   */
+  template <typename Map>
+  class MapKeyIterator : public MapIteratorBase<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;
+
+  public:
+
+    /// Default constructor.
+    MapKeyIterator() {}
+
+    /// KeyIt initialized iterator.
+    MapKeyIterator(const KeyIt& pit) : MapIteratorBase<Map>(pit) {}
+
+    /// The pre increment operator of the iterator.
+    MapKeyIterator& operator++() {
+      increment(); 
+      return *this; 
     }
 
-    /** The equality operator of the map.
-     */
-    bool operator==(const MapConstIterator& p_it) const {
-      return p_it.it == it;
+    /// The post increment operator of the iterator.
+    MapKeyIterator operator++(int) {
+      MapKeyIterator tmp(*this);
+      increment();
+      return tmp;
     }
-	
-    /** The not-equality operator of the map.
-     */
-    bool operator!=(const MapConstIterator& p_it) const {
-      return !(*this == p_it);
+
+    /// The dereferencing operator of the iterator.
+    KeyType operator*() const {
+      return static_cast<KeyType>(it);
     }
-	
+  };
+
+  template <typename Map> class MapConstValueIterator;
+
+  template <typename Map>
+  class MapValueIterator : public MapIteratorBase<Map> {
+
+    friend class MapConstValueIterator<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;
+
   private:
+
+    Map* map;
+
+  public:
+
+    /// Default constructor.
+    MapValueIterator() {}
+
+    /// Map and KeyIt initialized iterator.
+    MapValueIterator(Map& pmap, const KeyIt& pit) 
+      : MapIteratorBase<Map>(pit), map(&pmap) {}
+    
+
+    /// The pre increment operator of the iterator.
+    MapValueIterator& operator++() {
+      increment(); 
+      return *this; 
+    }
+
+    /// The post increment operator of the iterator.
+    MapValueIterator operator++(int) {
+      MapValueIterator tmp(*this);
+      increment();
+      return tmp;
+    }
+
+    /// The dereferencing operator of the iterator.
+    ReferenceType operator*() const {
+      return (*map)[it];
+    }
+
+    /// The arrow operator of the iterator.
+    PointerType operator->() const {
+      return &(operator*());
+    }
+
+  };
+
+
+  template <typename Map>
+  class MapConstValueIterator : public MapIteratorBase<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;
+
+  private:
+
     const Map* map;
-    KeyIt it;
+
+  public:
+
+    /// Default constructor.
+    MapConstValueIterator() {}
+
+    /// Constructor to create const iterator from a non const.
+    MapConstValueIterator(const MapValueIterator<Map>& pit) {
+      it = pit.it;
+      map = pit.map;
+    }
+
+    /// Map and KeyIt initialized iterator.
+    MapConstValueIterator(const Map& pmap, const KeyIt& pit) 
+      : MapIteratorBase<Map>(pit), map(&pmap) {}
+
+    /// The pre increment operator of the iterator.
+    MapConstValueIterator& operator++() {
+      increment(); 
+      return *this; 
+    }
+
+    /// The post increment operator of the iterator.
+    MapConstValueIterator operator++(int) {
+      MapConstValueIterator tmp(*this);
+      increment();
+      return tmp;
+    }
+
+    /// The dereferencing operator of the iterator.
+    ConstReferenceType operator*() const {
+      return (*map)[it];
+    }
+
+    /// The arrow operator of the iterator.
+    ConstPointerType operator->() const {
+      return &(operator*());
+    }
+
   };
 
+
+  /** 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 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));
+    }
+  };
+
+  /** 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 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));
+    }
+  };
+
+
+  /** 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 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));
+    }
+            
+  };
+
+  /// @}
+
 }
 
 #endif
diff -r ef91373d37a8 -r 89dfa3bece81 src/hugo/sym_map_factory.h
--- a/src/hugo/sym_map_factory.h	Thu Sep 09 09:40:45 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,112 +0,0 @@
-// -*- c++ -*-
-#ifndef SYM_MAP_FACTORY_H
-#define SYM_MAP_FACTORY_H
-
-namespace hugo {
-
-  template <typename Graph, typename Edge, typename EdgeIt>
-  class SymEdgeIt : public EdgeIt {
-  public:
-
-    SymEdgeIt() 
-      : EdgeIt() {}
-
-    SymEdgeIt(const Graph& graph) 
-      : EdgeIt(graph) {
-      while ( n != -1 && (n & 1)) {
-	EdgeIt::operator++();
-      }
-    }
-
-    SymEdgeIt(Invalid invalid) 
-      : EdgeIt(invalid) {}
-
-    SymEdgeIt(const Graph& graph, Edge edge)
-      : EdgeIt(graph, edge) {}
-
-    SymEdgeIt& operator++() {
-      EdgeIt::operator++();
-      while ( n != -1 && (n & 1)) {
-	EdgeIt::operator++();
-      }
-      return *this;
-    }
-  };
-
-  template <typename MapRegistry, template <typename> class MapFactory>
-  class SymMapFactory {
-
-  public:
-		
-    typedef typename MapRegistry::Graph Graph;
-    typedef typename MapRegistry::KeyType KeyType;
-    typedef typename MapRegistry::KeyIt KeyIt;
-
-    typedef typename MapRegistry::MapBase MapBase;
-
-    template <typename V>
-    class Map : public MapFactory<MapRegistry>::template Map<V> {
-
-      typedef typename MapFactory<MapRegistry>::template Map<V> MapImpl;
-    public:
-
-      typedef V Value;
-
-      Map() : MapImpl() {}
-
-      Map(const Graph& g, MapRegistry& r) : MapImpl(g, r) {}
-
-      Map(const Graph& g, MapRegistry& r, const Value& v) 
-	: MapImpl(g, r, v) {}
-
-      Map(const Map& copy) : MapImpl(static_cast<const MapImpl&>(copy)) {}
-
-      template <typename CMap> Map(const CMap& copy) : MapImpl(copy) {}
-
-      Map& operator=(const Map& copy) {
-	MapImpl::operator=(static_cast<const MapImpl&>(copy));
-	return *this;
-      }
-
-      template <typename CMap> Map& operator=(const CMap& copy) {
-	MapImpl::operator=(copy);
-	return *this;
-      }
-   
-      Value& operator[](const KeyType& key) {
-	int id = MapBase::getGraph()->id(key);	
-	return MapImpl::operator[](id >> 1);
-      } 
-		
-      const Value& operator[](const KeyType& key) const {
-	int id = MapBase::getGraph()->id(key);
-	return MapImpl::operator[](id >> 1);
-      }
-	
-      const Value& get(const KeyType& key) const {
-	int id = MapBase::getGraph()->id(key);
-	return MapImpl::operator[](id >> 1);
-      } 
-		
-      void set(const KeyType& key, const Value& val) {
-	int id = MapBase::getGraph()->id(key);
-	MapImpl::operator[](id >> 1) = val;
-      }
-		
-      void add(const KeyType& key) {
-	int id = MapBase::getGraph()->id(key);
-	if (id & 1) return;
-	MapImpl::add(key);
-      }
-		
-      void erase(const KeyType& key) {
-	int id = MapBase::getGraph()->id(key);
-	if (id & 1) return;
-	MapImpl::add(key);
-      }
-
-
-    };  
-  };
-}
-#endif
diff -r ef91373d37a8 -r 89dfa3bece81 src/hugo/vector_map.h
--- a/src/hugo/vector_map.h	Thu Sep 09 09:40:45 2004 +0000
+++ b/src/hugo/vector_map.h	Sun Sep 12 19:32:21 2004 +0000
@@ -202,6 +202,31 @@
       return ConstIterator(*this, INVALID);
     }
 
+    /// The KeySet of the Map.
+    typedef MapConstKeySet<VectorMap> ConstKeySet;
+
+    /// KeySet getter function.
+    ConstKeySet keySet() const {
+      return ConstKeySet(*this); 
+    }
+
+    /// The ConstValueSet of the Map.
+    typedef MapConstValueSet<VectorMap> ConstValueSet;
+
+    /// ConstValueSet getter function.
+    ConstValueSet valueSet() const {
+      return ConstValueSet(*this);
+    }
+
+    /// The ValueSet of the Map.
+    typedef MapValueSet<VectorMap> ValueSet;
+
+    /// ValueSet getter function.
+    ValueSet valueSet() {
+      return ValueSet(*this);
+    }
+
+
   private:
 		
     Container container;