Changeset 1413:3f45d58969d4 in lemon-0.x for src/lemon/graph_utils.h

Timestamp:

05/11/05 19:36:25 (19 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Fixing invertable maps:

InvertableMap?
DescriptorMap?
IdMap?

File:

• src/lemon/graph_utils.h (modified) (13 diffs)

src/lemon/graph_utils.h

@@ -23 +23 @@
 #include <lemon/invalid.h>
 #include <lemon/utility.h>
+#include <lemon/maps.h>
 
 ///\ingroup gutils
@@ -340 +341 @@
   /// @{
 
-  /// 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 {
@@ -414 +362 @@
   };
 
+
+  /// 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.
 
@@ -427 +438 @@
     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:
@@ -435 +446 @@
     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.
-    ///
-    InversableMap(const Graph& graph) : Map(graph) {} 
+    /// Construct a new InvertableMap for the 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);
@@ -466 +474 @@
     ///
     /// 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);
     }
@@ -484 +492 @@
     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);
@@ -500 +508 @@
     }
 
+  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;    
+    
   };
 
@@ -516 +559 @@
   ///
   /// 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.
@@ -522 +566 @@
   /// 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 {
@@ -542 +586 @@
     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();
@@ -568 +610 @@
       Map::set(invMap.back(), Map::operator[](item));
       invMap[Map::operator[](item)] = invMap.back();
+      invMap.pop_back();
       Map::erase(item);
     }
@@ -601 +644 @@
     }
     
+  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;
-    }
-
-  private:
-    std::vector<Item> invMap;
+      return InverseMap(*this);
+    }
   };