Changeset 1931:6abf67b02ff5 in lemon-0.x for lemon/graph_utils.h

Timestamp:

01/31/06 20:33:48 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

New iterable map with comparable values

it uses linked lists and balanced binary tree

IterableBoolMap? has ItemIt? type as the other iterable maps

InvertableMap? got ValueIterator?

File:

• lemon/graph_utils.h (modified) (11 diffs)

lemon/graph_utils.h

@@ -887 +887 @@
   /// and if a key is set to a new value then store it
   /// in the inverse map.
+  ///
+  /// The values of the map can be accessed
+  /// with stl compatible forward iterator.
+  ///
   /// \param _Graph The graph type.
   /// \param _Item The item type of the graph.
   /// \param _Value The value type of the map.
+  ///
+  /// \see IterableValueMap
 #ifndef DOXYGEN
   /// \param _Map A ReadWriteMap mapping from the item type to integer.
@@ -900 +906 @@
 #endif
   class InvertableMap : protected _Map {
-
-  public:
- 
-    typedef _Map Map;
-    typedef _Graph Graph;
+  public:
 
     /// The key type of InvertableMap (Node, Edge, UEdge).
@@ -911 +913 @@
     typedef typename _Map::Value Value;
 
+  private:
+    
+    typedef _Map Map;
+    typedef _Graph Graph;
+
+    typedef std::map<Value, Key> Container;
+    Container invMap;    
+
+  public:
+ 
+
+
     /// \brief Constructor.
     ///
@@ -916 +930 @@
     ///
     InvertableMap(const Graph& graph) : Map(graph) {} 
+
+    /// \brief Forward iterator for values.
+    ///
+    /// This iterator is an stl compatible forward
+    /// iterator on the values of the map. The values can
+    /// be accessed in the [beginValue, endValue) range.
+    ///
+    class ValueIterator 
+      : public std::iterator<std::forward_iterator_tag, Value> {
+      friend class InvertableMap;
+    private:
+      ValueIterator(typename Container::const_iterator _it) 
+        : it(_it) {}
+    public:
+      
+      ValueIterator() {}
+
+      ValueIterator& operator++() { ++it; return *this; }
+      ValueIterator operator++(int) { 
+        ValueIterator tmp(*this); 
+        operator++();
+        return tmp; 
+      }
+
+      const Value& operator*() const { return it->first; }
+      const Value* operator->() const { return &(it->first); }
+
+      bool operator==(ValueIterator jt) const { return it == jt.it; }
+      bool operator!=(ValueIterator jt) const { return it != jt.it; }
+      
+    private:
+      typename Container::const_iterator it;
+    };
+
+    /// \brief Returns an iterator to the first value.
+    ///
+    /// Returns an stl compatible iterator to the 
+    /// first value of the map. The values of the
+    /// map can be accessed in the [beginValue, endValue)
+    /// range.
+    ValueIterator beginValue() const {
+      return ValueIterator(invMap.begin());
+    }
+
+    /// \brief Returns an iterator after the last value.
+    ///
+    /// Returns an stl compatible iterator after the 
+    /// last value of the map. The values of the
+    /// map can be accessed in the [beginValue, endValue)
+    /// range.
+    ValueIterator endValue() const {
+      return ValueIterator(invMap.end());
+    }
     
     /// \brief The setter function of the map.
@@ -933 +1000 @@
     ///
     /// It gives back the value associated with the key.
-    Value operator[](const Key& key) const {
+    typename MapTraits<Map>::ConstReturnValue 
+    operator[](const Key& key) const {
       return Map::operator[](key);
     }
@@ -975 +1043 @@
       Map::clear();
     }
-
-  private:
-    
-    typedef std::map<Value, Key> Container;
-    Container invMap;    
 
   public:
@@ -1141 +1204 @@
   public:
 
+    /// \brief Returns the maximal value plus one.
+    ///
+    /// Returns the maximal value plus one in the map.
+    unsigned int size() const {
+      return invMap.size();
+    }
+
     /// \brief Swaps the position of the two items in the map.
     ///
@@ -1194 +1264 @@
       ///
       /// Returns the size of the map.
-      int size() const {
+      unsigned int size() const {
         return inverted.invMap.size();
       }
@@ -1448 +1518 @@
         Parent::set(key, 0);
       }
+
       virtual void add(const std::vector<Key>& keys) {
         Parent::add(keys);
@@ -1488 +1559 @@
     }
 
+    virtual void add(const std::vector<Edge>& edges) {
+      for (int i = 0; i < (int)edges.size(); ++i) {
+        ++deg[graph.target(edges[i])];
+      }
+    }
+
     virtual void erase(const Edge& edge) {
       --deg[graph.target(edge)];
+    }
+
+    virtual void erase(const std::vector<Edge>& edges) {
+      for (int i = 0; i < (int)edges.size(); ++i) {
+        --deg[graph.target(edges[i])];
+      }
     }
 
@@ -1592 +1675 @@
     }
 
+    virtual void add(const std::vector<Edge>& edges) {
+      for (int i = 0; i < (int)edges.size(); ++i) {
+        ++deg[graph.source(edges[i])];
+      }
+    }
+
     virtual void erase(const Edge& edge) {
       --deg[graph.source(edge)];
+    }
+
+    virtual void erase(const std::vector<Edge>& edges) {
+      for (int i = 0; i < (int)edges.size(); ++i) {
+        --deg[graph.source(edges[i])];
+      }
     }