Changeset 830:89dfa3bece81 in lemon-0.x for src

Timestamp:

09/12/04 21:32:21 (20 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1128

Message:

KeySet? and ValueSet? are inserted into the map structures.
They makes possible the iterating on the keys or values only.

Location:

src/hugo

Files:

• Makefile.am (modified) (1 diff)
• array_map.h (modified) (1 diff)
• map_iterator.h (modified) (6 diffs)
• sym_map_factory.h (deleted)
• vector_map.h (modified) (1 diff)

src/hugo/Makefile.am

@@ -24 +24 @@
         smart_graph.h                                                   \
         sym_map.h                                                       \
-        sym_map_factory.h                                               \
         time_measure.h                                                  \
         unionfind.h                                                     \

src/hugo/array_map.h

@@ -252 +252 @@
     }
 
+    /// 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:
       

src/hugo/map_iterator.h

@@ -5 +5 @@
 #include <hugo/extended_pair.h>
 
+///\ingroup graphmaps
+///\file
+///\brief Iterators on the maps.
+
 namespace hugo {
 
-
-  template <typename Map>
-  class MapIterator;
-
-  template <typename Map>
-  class MapConstIterator;
-
-  /** Compatible iterator with the stl maps' iterators.
-   *  It iterates on pairs of a key and a value.
-   */
-  template <typename Map>  
-  class MapIterator {
-    //    friend class Map;
-    friend class MapConstIterator<Map>;
-
-  public:
-
+  /// \addtogroup graphmaps
+  /// @{
+
+  /** The base class all of the map iterators.
+   *  The class defines the typedefs of the iterators,
+   *  simple step functions and equality operators.
+   */ 
+
+  template <typename Map>
+  class MapIteratorBase {
+
+  public:
     /// The key type of the iterator.
     typedef typename Map::KeyType KeyType;
@@ -42 +41 @@
     /// The pointer type of the iterator.
     typedef typename Map::ConstPointerType ConstPointerType;
+
+  protected:
+
+    KeyIt it;
+
+    /// Default constructor.
+    MapIteratorBase() {}
+
+    /// KeyIt initialized MapIteratorBase constructor.
+    MapIteratorBase(const KeyIt pit) : it(pit) {}
+
+  public:
+
+    /// Stepping forward in the map.   
+    void increment() { 
+      ++it; 
+    }
+
+    /// The equality operator of the map.
+    bool operator==(const MapIteratorBase& pit) const {
+      return pit.it == it;
+    }
+        
+    /// The not-equality operator of the map.
+    bool operator!=(const MapIteratorBase& pit) const {
+      return !(*this == pit);
+    }
+  };
+
+  template <typename Map> class MapConstIterator;
+
+  /** Compatible iterator with the stl maps' iterators.
+   * It iterates on pairs of a key and a value.
+   */
+  template <typename Map>  
+  class MapIterator : public MapIteratorBase<Map> {
+
+    friend class MapConstIterator<Map>;
+
+  public:
+
+    /// The key type of the iterator.
+    typedef typename Map::KeyType KeyType;
+    /// The iterator to iterate on the keys.
+    typedef typename Map::KeyIt KeyIt;
+
+    /// The value type of the iterator.
+    typedef typename Map::ValueType ValueType;
+    /// The reference type of the iterator.
+    typedef typename Map::ReferenceType ReferenceType;
+    /// The pointer type of the iterator.
+    typedef typename Map::PointerType PointerType;
+
+    /// The const value type of the iterator.
+    typedef typename Map::ConstValueType ConstValueType;
+    /// The const reference type of the iterator.
+    typedef typename Map::ConstReferenceType ConstReferenceType;
+    /// The pointer type of the iterator.
+    typedef typename Map::ConstPointerType ConstPointerType;
     
   public:
 
-    /** 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;
@@ -76 +131 @@
     };
 
-    /** 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;
   };
 
@@ -130 +157 @@
    */
   template <typename Map>
-  class MapConstIterator {
-    // friend class Map;
-    friend class MapIterator<Map>;
-
+  class MapConstIterator : public MapIteratorBase<Map> {
+    
   public:
 
@@ -157 +182 @@
   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;
@@ -189 +216 @@
     };
 
-    /** 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);
-    }
-
-    /** The equality operator of the map.
-     */
-    bool operator==(const MapConstIterator& p_it) const {
-      return p_it.it == it;
-    }
-        
-    /** The not-equality operator of the map.
-     */
-    bool operator!=(const MapConstIterator& p_it) const {
-      return !(*this == p_it);
-    }
-        
   private:
     const Map* map;
-    KeyIt it;
-  };
+  };
+
+  /** 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 post increment operator of the iterator.
+    MapKeyIterator operator++(int) {
+      MapKeyIterator tmp(*this);
+      increment();
+      return tmp;
+    }
+
+    /// 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;
+
+  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));
+    }
+            
+  };
+
+  /// @}
 
 }

src/hugo/vector_map.h

@@ -203 +203 @@
     }
 
+    /// 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: