# HG changeset patch
# User deba
# Date 1115832985 0
# Node ID 3f45d58969d4e81b61dfcc1c260ade1ab9e25657
# Parent  c7fab5a1174ae0f8e31a66f5a0ad63f1a70f633f
Fixing invertable maps:
    InvertableMap
    DescriptorMap
    IdMap

diff -r c7fab5a1174a -r 3f45d58969d4 src/lemon/graph_utils.h
--- a/src/lemon/graph_utils.h	Wed May 11 16:55:18 2005 +0000
+++ b/src/lemon/graph_utils.h	Wed May 11 17:36:25 2005 +0000
@@ -22,6 +22,7 @@
 
 #include <lemon/invalid.h>
 #include <lemon/utility.h>
+#include <lemon/maps.h>
 
 ///\ingroup gutils
 ///\file
@@ -339,59 +340,6 @@
   /// \addtogroup graph_maps
   /// @{
 
-  /// Provides an immutable and unique id for each item in the graph.
-
-  /// The IdMap class provides an unique and immutable mapping for each item
-  /// in the graph.
-  ///
-  template <typename _Graph, typename _Item>
-  class IdMap {
-  public:
-    typedef _Graph Graph;
-    typedef int Value;
-    typedef _Item Item;
-    typedef _Item Key;
-
-    /// \brief The class represents the inverse of the map.
-    ///
-    /// The class represents the inverse of the map.
-    /// \see inverse()
-    class InverseMap {
-    public:
-      /// \brief Constructor.
-      ///
-      /// Constructor for creating an id-to-item map.
-      InverseMap(const Graph& _graph) : graph(&_graph) {}
-      /// \brief Gives back the given item from its id.
-      ///
-      /// Gives back the given item from its id.
-      /// 
-      Item operator[](int id) const { return graph->fromId(id, Item());}
-    private:
-      const Graph* graph;
-    };
-
-    /// \brief Constructor.
-    ///
-    /// Constructor for creating id map.
-    IdMap(const Graph& _graph) : graph(&_graph) {}
-
-    /// \brief Gives back the \e id of the item.
-    ///
-    /// Gives back the immutable and unique \e id of the map.
-    int operator[](const Item& item) const { return graph->id(item);}
-
-    /// \brief Gives back the inverse of the map.
-    ///
-    /// Gives back the inverse of the map.
-    InverseMap inverse() const { return InverseMap(*graph);} 
-
-  private:
-    const Graph* graph;
-
-  };
-
-  
   template <typename Map, typename Enable = void>
   struct ReferenceMapTraits {
     typedef typename Map::Value Value;
@@ -413,6 +361,69 @@
     typedef typename Map::ConstPointer ConstPointer;
   };
 
+
+  /// Provides an immutable and unique id for each item in the graph.
+
+  /// The IdMap class provides an unique and immutable mapping for each item
+  /// in the graph.
+  ///
+  template <typename _Graph, typename _Item>
+  class IdMap {
+  public:
+    typedef _Graph Graph;
+    typedef int Value;
+    typedef _Item Item;
+    typedef _Item Key;
+
+    /// \brief Constructor.
+    ///
+    /// Constructor for creating id map.
+    IdMap(const Graph& _graph) : graph(&_graph) {}
+
+    /// \brief Gives back the \e id of the item.
+    ///
+    /// Gives back the immutable and unique \e id of the map.
+    int operator[](const Item& item) const { return graph->id(item);}
+
+
+  private:
+    const Graph* graph;
+
+  public:
+
+    /// \brief The class represents the inverse of the map.
+    ///
+    /// The class represents the inverse of the map.
+    /// \see inverse()
+    class InverseMap {
+    public:
+      /// \brief Constructor.
+      ///
+      /// Constructor for creating an id-to-item map.
+      InverseMap(const Graph& _graph) : graph(&_graph) {}
+
+      /// \brief Constructor.
+      ///
+      /// Constructor for creating an id-to-item map.
+      InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
+
+      /// \brief Gives back the given item from its id.
+      ///
+      /// Gives back the given item from its id.
+      /// 
+      Item operator[](int id) const { return graph->fromId(id, Item());}
+    private:
+      const Graph* graph;
+    };
+
+    /// \brief Gives back the inverse of the map.
+    ///
+    /// Gives back the inverse of the map.
+    InverseMap inverse() const { return InverseMap(*graph);} 
+
+  };
+
+  
   /// \brief General inversable graph-map type.
 
   /// This type provides simple inversable map functions. 
@@ -426,35 +437,32 @@
     typename _Item, 
     typename _Value,
     typename _Map 
-    = typename ItemSetTraits<_Graph, _Item>::template Map<_Value> 
+    = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent 
   >
-  class InversableMap : protected _Map {
+  class InvertableMap : protected _Map {
 
   public:
  
     typedef _Map Map;
     typedef _Graph Graph;
-   /// The key type of InversableMap (Node, Edge, UndirEdge).
+
+    /// The key type of InvertableMap (Node, Edge, UndirEdge).
     typedef typename _Map::Key Key;
-    /// The value type of the InversableMap.
+    /// The value type of the InvertableMap.
     typedef typename _Map::Value Value;
 
-    typedef std::map<Value, Key> InverseMap;
-    
-    typedef typename _Map::ConstReference ConstReference;
-
     /// \brief Constructor.
     ///
-    /// Construct a new InversableMap for the graph.
+    /// Construct a new InvertableMap for the graph.
     ///
-    InversableMap(const Graph& graph) : Map(graph) {} 
+    InvertableMap(const Graph& graph) : Map(graph) {} 
     
     /// \brief The setter function of the map.
     ///
-
+    /// Sets the mapped value.
     void set(const Key& key, const Value& val) {
       Value oldval = Map::operator[](key);
-      typename InverseMap::iterator it = invMap.find(oldval);
+      typename Container::iterator it = invMap.find(oldval);
       if (it != invMap.end() && it->second == key) {
 	invMap.erase(it);
       }      
@@ -465,7 +473,7 @@
     /// \brief The getter function of the map.
     ///
     /// It gives back the value associated with the key.
-    ConstReference operator[](const Key& key) const {
+    const Value operator[](const Key& key) const {
       return Map::operator[](key);
     }
 
@@ -483,7 +491,7 @@
     /// \c AlterationNotifier.
     virtual void erase(const Key& key) {
       Value val = Map::operator[](key);
-      typename InverseMap::iterator it = invMap.find(val);
+      typename Container::iterator it = invMap.find(val);
       if (it != invMap.end() && it->second == key) {
 	invMap.erase(it);
       }
@@ -499,33 +507,69 @@
       Map::clear();
     }
 
+  private:
+    
+    typedef std::map<Value, Key> Container;
+    Container invMap;    
+
+  public:
+
+    /// \brief The inverse map type.
+    ///
+    /// The inverse of this map. The subscript operator of the map
+    /// gives back always the item what was last assigned to the value. 
+    class InverseMap {
+    public:
+      /// \brief Constructor of the InverseMap.
+      ///
+      /// Constructor of the InverseMap.
+      InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}
+
+      /// The value type of the InverseMap.
+      typedef typename InvertableMap::Key Value;
+      /// The key type of the InverseMap.
+      typedef typename InvertableMap::Value Key; 
+
+      /// \brief Subscript operator. 
+      ///
+      /// Subscript operator. It gives back always the item 
+      /// what was last assigned to the value.
+      Value operator[](const Key& key) const {
+	typename Container::const_iterator it = inverted.invMap.find(key);
+	return it->second;
+      }
+      
+    private:
+      const InvertableMap& inverted;
+    };
+
     /// \brief It gives back the just readeable inverse map.
     ///
     /// It gives back the just readeable inverse map.
-    const InverseMap& inverse() const {
-      return invMap;
+    InverseMap inverse() const {
+      return InverseMap(*this);
     } 
 
 
-  private:
-    InverseMap invMap;    
+    
   };
 
   /// \brief Provides a mutable, continuous and unique descriptor for each 
   /// item in the graph.
   ///
   /// The DescriptorMap class provides a mutable, continuous and immutable
-  /// mapping for each item in the graph.
+  /// mapping for each item in the graph. The value for an item may mutated
+  /// on each operation when the an item erased or added to graph.
   ///
   /// \param _Graph The graph class the \c DescriptorMap belongs to.
   /// \param _Item The Item is the Key of the Map. It may be Node, Edge or 
   /// UndirEdge.
   /// \param _Map A ReadWriteMap mapping from the item type to integer.
-
   template <
     typename _Graph,   
     typename _Item,
-    typename _Map = typename ItemSetTraits<_Graph, _Item>::template Map<int>
+    typename _Map 
+    = typename ItemSetTraits<_Graph, _Item>::template Map<int>::Parent
   >
   class DescriptorMap : protected _Map {
 
@@ -541,11 +585,9 @@
     /// The value type of DescriptorMap.
     typedef typename _Map::Value Value;
 
-    typedef std::vector<Item> InverseMap;
-
     /// \brief Constructor.
     ///
-    /// Constructor for creating descriptor map.
+    /// Constructor for descriptor map.
     DescriptorMap(const Graph& _graph) : Map(_graph) {
       build();
     }
@@ -567,6 +609,7 @@
     virtual void erase(const Item& item) {
       Map::set(invMap.back(), Map::operator[](item));
       invMap[Map::operator[](item)] = invMap.back();
+      invMap.pop_back();
       Map::erase(item);
     }
 
@@ -600,15 +643,47 @@
       return Map::operator[](item);
     }
     
+  private:
+
+    typedef std::vector<Item> Container;
+    Container invMap;
+
+  public:
+    /// \brief The inverse map type.
+    ///
+    /// The inverse map type.
+    class InverseMap {
+    public:
+      /// \brief Constructor of the InverseMap.
+      ///
+      /// Constructor of the InverseMap.
+      InverseMap(const DescriptorMap& _inverted) 
+	: inverted(_inverted) {}
+
+
+      /// The value type of the InverseMap.
+      typedef typename DescriptorMap::Key Value;
+      /// The key type of the InverseMap.
+      typedef typename DescriptorMap::Value Key; 
+
+      /// \brief Subscript operator. 
+      ///
+      /// Subscript operator. It gives back the item 
+      /// that the descriptor belongs to currently.
+      Value operator[](const Key& key) const {
+	return inverted.invMap[key];
+      }
+      
+    private:
+      const DescriptorMap& inverted;
+    };
+
     /// \brief Gives back the inverse of the map.
     ///
     /// Gives back the inverse of the map.
     const InverseMap inverse() const {
-      return invMap;
+      return InverseMap(*this);
     }
-
-  private:
-    std::vector<Item> invMap;
   };
 
   /// \brief Returns the source of the given edge.