# HG changeset patch
# User deba
# Date 1138736028 0
# Node ID 6abf67b02ff5e5697839cf55797bcaf225fce4c5
# Parent  92b70deed0c53ab31f3f892a0275115fee9936ba
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

diff -r 92b70deed0c5 -r 6abf67b02ff5 lemon/graph_utils.h
--- a/lemon/graph_utils.h	Mon Jan 30 09:37:41 2006 +0000
+++ b/lemon/graph_utils.h	Tue Jan 31 19:33:48 2006 +0000
@@ -886,9 +886,15 @@
   /// The InvertableMap wraps an arbitrary ReadWriteMap 
   /// 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.
   template <
@@ -899,22 +905,83 @@
   template <typename _Graph, typename _Item, typename _Value>
 #endif
   class InvertableMap : protected _Map {
-
   public:
- 
-    typedef _Map Map;
-    typedef _Graph Graph;
 
     /// The key type of InvertableMap (Node, Edge, UEdge).
     typedef typename _Map::Key Key;
     /// The value type of the InvertableMap.
     typedef typename _Map::Value Value;
 
+  private:
+    
+    typedef _Map Map;
+    typedef _Graph Graph;
+
+    typedef std::map<Value, Key> Container;
+    Container invMap;    
+
+  public:
+ 
+
+
     /// \brief Constructor.
     ///
     /// Construct a new InvertableMap for the graph.
     ///
     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.
     ///
@@ -932,7 +999,8 @@
     /// \brief The getter function of the map.
     ///
     /// 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,11 +1043,6 @@
       Map::clear();
     }
 
-  private:
-    
-    typedef std::map<Value, Key> Container;
-    Container invMap;    
-
   public:
 
     /// \brief The inverse map type.
@@ -1140,6 +1203,13 @@
 
   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.
     ///
     /// Swaps the position of the two items in the map.
@@ -1193,7 +1263,7 @@
       /// \brief Size of the map.
       ///
       /// Returns the size of the map.
-      int size() const {
+      unsigned int size() const {
 	return inverted.invMap.size();
       }
       
@@ -1447,6 +1517,7 @@
 	Parent::add(key);
 	Parent::set(key, 0);
       }
+
       virtual void add(const std::vector<Key>& keys) {
 	Parent::add(keys);
 	for (int i = 0; i < (int)keys.size(); ++i) {
@@ -1487,10 +1558,22 @@
       ++deg[graph.target(edge)];
     }
 
+    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])];
+      }
+    }
+
     virtual void build() {
       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
 	deg[it] = countInEdges(graph, it);
@@ -1591,10 +1674,22 @@
       ++deg[graph.source(edge)];
     }
 
+    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])];
+      }
+    }
+
     virtual void build() {
       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
 	deg[it] = countOutEdges(graph, it);
diff -r 92b70deed0c5 -r 6abf67b02ff5 lemon/iterable_maps.h
--- a/lemon/iterable_maps.h	Mon Jan 30 09:37:41 2006 +0000
+++ b/lemon/iterable_maps.h	Tue Jan 31 19:33:48 2006 +0000
@@ -16,7 +16,11 @@
 
 #include <lemon/traits.h>
 #include <lemon/invalid.h>
+
 #include <vector>
+#include <map>
+
+#include <iterator>
 #include <limits>
 
 ///\ingroup maps
@@ -29,7 +33,7 @@
 
 namespace lemon {
 
-  ///\ingroup maps
+  ///\ingroup graph_maps
   ///
   /// \brief Dynamic iterable bool map.
   ///
@@ -45,35 +49,35 @@
     : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Parent {
   private:
     typedef _Graph Graph;
-    typedef _Item Item;
     
-    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
-    typedef typename ItemSetTraits<Graph, Item>
+    typedef typename ItemSetTraits<Graph, _Item>::ItemIt KeyIt;
+    typedef typename ItemSetTraits<Graph, _Item>
     ::template Map<int>::Parent Parent;
     
-    std::vector<Item> array;
+    std::vector<_Item> array;
     int sep;
 
     const Graph& graph;
 
-  private:
-
-    int position(const Item& item) const {
-      return Parent::operator[](item);
-    }
-
   public:
 
     /// Indicates that the map if reference map.
     typedef True ReferenceMapTag;
 
     /// The key type
-    typedef Item Key;
+    typedef _Item Key;
     /// The value type
     typedef bool Value;
     /// The const reference type.    
     typedef const Value& ConstReference;
 
+  private:
+
+    int position(const Key& key) const {
+      return Parent::operator[](key);
+    }
+
+  public:
 
     /// \brief Refernce to the value of the map.
     ///
@@ -121,7 +125,7 @@
     /// Constructor of the Map with a default value.
     IterableBoolMap(const Graph& _graph, bool def = false) 
       : Parent(_graph), graph(_graph) {
-      for (ItemIt it(graph); it != INVALID; ++it) {
+      for (KeyIt it(graph); it != INVALID; ++it) {
         Parent::set(it, array.size());
         array.push_back(it);
       }
@@ -131,51 +135,51 @@
     /// \brief Const subscript operator of the map.
     ///
     /// Const subscript operator of the map.
-    bool operator[](const Item& item) const {
-      return position(item) < sep;
+    bool operator[](const Key& key) const {
+      return position(key) < sep;
     }
 
     /// \brief Subscript operator of the map.
     ///
     /// Subscript operator of the map.
-    Reference operator[](const Item& item) {
-      return Reference(*this, item);
+    Reference operator[](const Key& key) {
+      return Reference(*this, key);
     }
 
     /// \brief Set operation of the map.
     ///
     /// Set operation of the map.
-    void set(const Item& item, bool value) {
-      int pos = position(item);
+    void set(const Key& key, bool value) {
+      int pos = position(key);
       if (value) {
         if (pos < sep) return;
-        Item tmp = array[sep];
-        array[sep] = item;
-        Parent::set(item, sep);
+        Key tmp = array[sep];
+        array[sep] = key;
+        Parent::set(key, sep);
         array[pos] = tmp;
         Parent::set(tmp, pos); 
         ++sep;
       } else {
         if (pos >= sep) return;
         --sep;
-        Item tmp = array[sep];
-        array[sep] = item;
-        Parent::set(item, sep);
+        Key tmp = array[sep];
+        array[sep] = key;
+        Parent::set(key, sep);
         array[pos] = tmp;
         Parent::set(tmp, pos);
       }
     }
 
-    /// \brief Returns the number of the items mapped to true.
+    /// \brief Returns the number of the keys mapped to true.
     ///
-    /// Returns the number of the items mapped to true.
+    /// Returns the number of the keys mapped to true.
     int trueNum() const {
       return sep;
     } 
     
-    /// \brief Returns the number of the items mapped to false.
+    /// \brief Returns the number of the keys mapped to false.
     ///
-    /// Returns the number of the items mapped to false.
+    /// Returns the number of the keys mapped to false.
     int falseNum() const {
       return array.size() - sep;
     }
@@ -184,12 +188,12 @@
     ///
     /// Iterator for the keys mapped to true. It works
     /// like a graph item iterator in the map, it can be converted
-    /// the item type of the map, incremented with \c ++ operator, and
-    /// if the iterator leave the last valid item it will be equal to 
+    /// the key type of the map, incremented with \c ++ operator, and
+    /// if the iterator leave the last valid key it will be equal to 
     /// \c INVALID.
-    class TrueIt : public Item {
+    class TrueIt : public Key {
     public:
-      typedef Item Parent;
+      typedef Key Parent;
       
       /// \brief Creates an iterator.
       ///
@@ -202,7 +206,7 @@
 
       /// \brief Invalid constructor \& conversion.
       ///
-      /// This constructor initializes the item to be invalid.
+      /// This constructor initializes the key to be invalid.
       /// \sa Invalid for more details.
       TrueIt(Invalid) : Parent(INVALID), map(0) {}
 
@@ -224,12 +228,12 @@
     ///
     /// Iterator for the keys mapped to false. It works
     /// like a graph item iterator in the map, it can be converted
-    /// the item type of the map, incremented with \c ++ operator, and
-    /// if the iterator leave the last valid item it will be equal to 
+    /// the key type of the map, incremented with \c ++ operator, and
+    /// if the iterator leave the last valid key it will be equal to 
     /// \c INVALID.
-    class FalseIt : public Item {
+    class FalseIt : public Key {
     public:
-      typedef Item Parent;
+      typedef Key Parent;
       
       /// \brief Creates an iterator.
       ///
@@ -237,12 +241,12 @@
       /// keys which mapped to false.
       /// \param map The IterableIntMap
       FalseIt(const IterableBoolMap& _map) 
-        : Parent(_map.sep < _map.array.size() ? _map.array.back() : INVALID), 
-          map(&_map) {}
+        : Parent(_map.sep < (int)_map.array.size() ? 
+                 _map.array.back() : INVALID), map(&_map) {}
 
       /// \brief Invalid constructor \& conversion.
       ///
-      /// This constructor initializes the item to be invalid.
+      /// This constructor initializes the key to be invalid.
       /// \sa Invalid for more details.
       FalseIt(Invalid) : Parent(INVALID), map(0) {}
 
@@ -259,24 +263,66 @@
       const IterableBoolMap* map;
     };
 
+    /// \brief Iterator for the keys mapped to a given value.
+    ///
+    /// Iterator for the keys mapped to a given value. It works
+    /// like a graph item iterator in the map, it can be converted
+    /// the key type of the map, incremented with \c ++ operator, and
+    /// if the iterator leave the last valid key it will be equal to 
+    /// \c INVALID.
+    class ItemIt : public Key {
+    public:
+      typedef Key Parent;
+      
+      /// \brief Creates an iterator.
+      ///
+      /// Creates an iterator. It iterates on the 
+      /// keys which mapped to false.
+      /// \param map The IterableIntMap
+      /// \param value Which elements should be iterated.
+      ItemIt(const IterableBoolMap& _map, bool value) 
+        : Parent(value ? (_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID) :
+                 (_map.sep < (int)_map.array.size() ? 
+                  _map.array.back() : INVALID)), map(&_map) {}
+
+      /// \brief Invalid constructor \& conversion.
+      ///
+      /// This constructor initializes the key to be invalid.
+      /// \sa Invalid for more details.
+      ItemIt(Invalid) : Parent(INVALID), map(0) {}
+
+      /// \brief Increment operator.
+      ///
+      /// Increment Operator.
+      ItemIt& operator++() {
+        int pos = map->position(*this);
+        int sep = pos >= map->sep ? map->sep : 0;
+        Parent::operator=(pos > sep ? map->array[pos - 1] : INVALID);
+        return *this;
+      }
+
+    private:
+      const IterableBoolMap* map;
+    };
+
   protected:
     
-    virtual void add(const Item& item) {
-      Parent::add(item);
-      Parent::set(item, array.size());
-      array.push_back(item);
+    virtual void add(const Key& key) {
+      Parent::add(key);
+      Parent::set(key, array.size());
+      array.push_back(key);
     }
 
-    virtual void add(const std::vector<Item>& items) {
-      Parent::add(items);
-      for (int i = 0; i < (int)items.size(); ++i) {
-        Parent::set(items[i], array.size());
-        array.push_back(items[i]);
+    virtual void add(const std::vector<Key>& keys) {
+      Parent::add(keys);
+      for (int i = 0; i < (int)keys.size(); ++i) {
+        Parent::set(keys[i], array.size());
+        array.push_back(keys[i]);
       }
     }
 
-    virtual void erase(const Item& item) {
-      int pos = position(item); 
+    virtual void erase(const Key& key) {
+      int pos = position(key); 
       if (pos < sep) {
         --sep;
         Parent::set(array[sep], pos);
@@ -289,12 +335,12 @@
         array[pos] = array.back();
         array.pop_back();
       }
-      Parent::erase(item);
+      Parent::erase(key);
     }
 
-    virtual void erase(const std::vector<Item>& items) {
-      for (int i = 0; i < (int)items.size(); ++i) {
-        int pos = position(items[i]); 
+    virtual void erase(const std::vector<Key>& keys) {
+      for (int i = 0; i < (int)keys.size(); ++i) {
+        int pos = position(keys[i]); 
         if (pos < sep) {
           --sep;
           Parent::set(array[sep], pos);
@@ -308,12 +354,12 @@
           array.pop_back();
         }
       }
-      Parent::erase(items);
+      Parent::erase(keys);
     }    
 
     virtual void build() {
       Parent::build();
-      for (ItemIt it(graph); it != INVALID; ++it) {
+      for (KeyIt it(graph); it != INVALID; ++it) {
         Parent::set(it, array.size());
         array.push_back(it);
       }
@@ -339,7 +385,7 @@
     };
   }
 
-  ///\ingroup maps
+  ///\ingroup graph_maps
   ///
   /// \brief Dynamic iterable integer map.
   ///
@@ -514,8 +560,8 @@
     /// \brief Gives back the maximal value plus one.
     ///
     /// Gives back the maximal value plus one.
-    int size() const {
-      return (int)first.size();
+    unsigned int size() const {
+      return first.size();
     }
     
     /// \brief Set operation of the map.
@@ -594,7 +640,7 @@
     }
 
     virtual void erase(const std::vector<Key>& keys) {
-      for (int i = 0; i < keys.size(); ++i) {
+      for (int i = 0; i < (int)keys.size(); ++i) {
         unlace(keys[i]);
       }
       Parent::erase(keys);
@@ -609,5 +655,240 @@
     std::vector<_Item> first;
   };
 
+  namespace _iterable_maps_bits {
+    template <typename Item, typename Value>
+    struct IterableValueMapNode {
+      IterableValueMapNode(Value _value = Value()) : value(_value) {}
+      Item prev, next;
+      Value value;
+    };
+  }
+
+  ///\ingroup graph_maps
+  ///
+  /// \brief Dynamic iterable map for comparable values.
+  ///
+  /// This class provides a special graph map type which can store
+  /// for each graph item(node, edge, etc.) a value. For each
+  /// value it is possible to iterate on the keys which mapped to the 
+  /// given value. The type stores for each value a linked list with
+  /// the items which mapped to the value, and the values are stored
+  /// in balanced binary tree. The values of the map can be accessed
+  /// with stl compatible forward iterator.
+  ///
+  /// This type is not reference map so it cannot be modified with
+  /// the subscription operator.
+  ///
+  /// \see InvertableMap
+  /// 
+  /// \param _Graph The graph type.
+  /// \param _Item One of the graph's item type, the key of the map.
+  /// \param _Value Any comparable value type.
+  template <typename _Graph, typename _Item, typename _Value>
+  class IterableValueMap : protected ItemSetTraits<_Graph, _Item> 
+  ::template Map<_iterable_maps_bits::IterableValueMapNode<_Item, _Value> >
+  ::Parent {
+  public:
+    typedef typename ItemSetTraits<_Graph, _Item> 
+    ::template Map<_iterable_maps_bits::IterableValueMapNode<_Item, _Value> >
+    ::Parent Parent;
+
+    /// The key type
+    typedef _Item Key;
+    /// The value type
+    typedef _Value Value;
+    /// The graph type
+    typedef _Graph Graph;
+
+    /// \brief Constructor of the Map with a given value.
+    ///
+    /// Constructor of the Map with a given value.
+    explicit IterableValueMap(const Graph& graph, 
+                              const Value& value = Value()) 
+      : Parent(graph, _iterable_maps_bits::IterableValueMapNode<_Item, 
+               _Value>(value)) {
+      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
+        lace(it);
+      }
+    }
+
+  private:
+    
+    void unlace(const Key& key) {
+      typename Parent::Value& node = Parent::operator[](key);
+      if (node.prev != INVALID) {
+	Parent::operator[](node.prev).next = node.next;	
+      } else {
+        if (node.next != INVALID) {
+          first[node.value] = node.next;
+        } else {
+          first.erase(node.value);
+        }
+      }
+      if (node.next != INVALID) {
+	Parent::operator[](node.next).prev = node.prev;
+      }
+    }
+
+    void lace(const Key& key) {
+      typename Parent::Value& node = Parent::operator[](key);
+      typename std::map<Value, Key>::iterator it = first.find(node.value);
+      if (it == first.end()) {
+        node.prev = node.next = INVALID;
+        if (node.next != INVALID) {
+          Parent::operator[](node.next).prev = key;	
+        }
+        first.insert(make_pair(node.value, key));
+      } else {
+        node.prev = INVALID;
+        node.next = it->second;
+        if (node.next != INVALID) {
+          Parent::operator[](node.next).prev = key;	
+        }
+        it->second = key;
+      }
+    }
+
+  public:
+
+    /// \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 IterableValueMap;
+    private:
+      ValueIterator(typename std::map<Value, Key>::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 std::map<Value, Key>::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(first.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(first.end());
+    }
+
+    /// \brief Set operation of the map.
+    ///
+    /// Set operation of the map.
+    void set(const Key& key, const Value& value) {
+      unlace(key);
+      Parent::operator[](key).value = value;
+      lace(key);
+    }
+
+    /// \brief Const subscript operator of the map.
+    ///
+    /// Const subscript operator of the map.
+    const Value& operator[](const Key& key) const {
+      return Parent::operator[](key).value;
+    }
+
+    /// \brief Iterator for the keys with the same value.
+    ///
+    /// Iterator for the keys with the same value. It works
+    /// like a graph item iterator in the map, it can be converted
+    /// the item type of the map, incremented with \c ++ operator, and
+    /// if the iterator leave the last valid item it will be equal to 
+    /// \c INVALID.
+    class ItemIt : public _Item {
+    public:
+      typedef _Item Parent;
+
+      /// \brief Invalid constructor \& conversion.
+      ///
+      /// This constructor initializes the item to be invalid.
+      /// \sa Invalid for more details.
+      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
+
+      /// \brief Creates an iterator with a value.
+      ///
+      /// Creates an iterator with a value. It iterates on the 
+      /// keys which have the given value.
+      /// \param map The IterableValueMap
+      /// \param value The value
+      ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) {
+        typename std::map<Value, Key>::const_iterator it = 
+          map.first.find(value); 
+	if (it == map.first.end()) {	  
+	  Parent::operator=(INVALID);
+	} else {
+	  Parent::operator=(it->second);
+	}
+      } 
+
+      /// \brief Increment operator.
+      ///
+      /// Increment Operator.
+      ItemIt& operator++() {
+	Parent::operator=(_map->IterableValueMap::Parent::
+			  operator[](static_cast<Parent&>(*this)).next);
+	return *this;
+      }
+
+
+    private:
+      const IterableValueMap* _map;
+    };
+
+  protected:
+    
+    virtual void erase(const Key& key) {
+      unlace(key);
+      Parent::erase(key);
+    }
+
+    virtual void erase(const std::vector<Key>& keys) {
+      for (int i = 0; i < (int)keys.size(); ++i) {
+        unlace(keys[i]);
+      }
+      Parent::erase(keys);
+    }
+
+    virtual void clear() {
+      first.clear();
+      Parent::clear();
+    }
+
+  private:
+    std::map<Value, Key> first;
+  };
+
   /// @}
 }