Fixing invertable maps:
authordeba
Wed, 11 May 2005 17:36:25 +0000
changeset 14133f45d58969d4
parent 1412 c7fab5a1174a
child 1414 01d9d6bc1284
Fixing invertable maps:
InvertableMap
DescriptorMap
IdMap
src/lemon/graph_utils.h
     1.1 --- a/src/lemon/graph_utils.h	Wed May 11 16:55:18 2005 +0000
     1.2 +++ b/src/lemon/graph_utils.h	Wed May 11 17:36:25 2005 +0000
     1.3 @@ -22,6 +22,7 @@
     1.4  
     1.5  #include <lemon/invalid.h>
     1.6  #include <lemon/utility.h>
     1.7 +#include <lemon/maps.h>
     1.8  
     1.9  ///\ingroup gutils
    1.10  ///\file
    1.11 @@ -339,59 +340,6 @@
    1.12    /// \addtogroup graph_maps
    1.13    /// @{
    1.14  
    1.15 -  /// Provides an immutable and unique id for each item in the graph.
    1.16 -
    1.17 -  /// The IdMap class provides an unique and immutable mapping for each item
    1.18 -  /// in the graph.
    1.19 -  ///
    1.20 -  template <typename _Graph, typename _Item>
    1.21 -  class IdMap {
    1.22 -  public:
    1.23 -    typedef _Graph Graph;
    1.24 -    typedef int Value;
    1.25 -    typedef _Item Item;
    1.26 -    typedef _Item Key;
    1.27 -
    1.28 -    /// \brief The class represents the inverse of the map.
    1.29 -    ///
    1.30 -    /// The class represents the inverse of the map.
    1.31 -    /// \see inverse()
    1.32 -    class InverseMap {
    1.33 -    public:
    1.34 -      /// \brief Constructor.
    1.35 -      ///
    1.36 -      /// Constructor for creating an id-to-item map.
    1.37 -      InverseMap(const Graph& _graph) : graph(&_graph) {}
    1.38 -      /// \brief Gives back the given item from its id.
    1.39 -      ///
    1.40 -      /// Gives back the given item from its id.
    1.41 -      /// 
    1.42 -      Item operator[](int id) const { return graph->fromId(id, Item());}
    1.43 -    private:
    1.44 -      const Graph* graph;
    1.45 -    };
    1.46 -
    1.47 -    /// \brief Constructor.
    1.48 -    ///
    1.49 -    /// Constructor for creating id map.
    1.50 -    IdMap(const Graph& _graph) : graph(&_graph) {}
    1.51 -
    1.52 -    /// \brief Gives back the \e id of the item.
    1.53 -    ///
    1.54 -    /// Gives back the immutable and unique \e id of the map.
    1.55 -    int operator[](const Item& item) const { return graph->id(item);}
    1.56 -
    1.57 -    /// \brief Gives back the inverse of the map.
    1.58 -    ///
    1.59 -    /// Gives back the inverse of the map.
    1.60 -    InverseMap inverse() const { return InverseMap(*graph);} 
    1.61 -
    1.62 -  private:
    1.63 -    const Graph* graph;
    1.64 -
    1.65 -  };
    1.66 -
    1.67 -  
    1.68    template <typename Map, typename Enable = void>
    1.69    struct ReferenceMapTraits {
    1.70      typedef typename Map::Value Value;
    1.71 @@ -413,6 +361,69 @@
    1.72      typedef typename Map::ConstPointer ConstPointer;
    1.73    };
    1.74  
    1.75 +
    1.76 +  /// Provides an immutable and unique id for each item in the graph.
    1.77 +
    1.78 +  /// The IdMap class provides an unique and immutable mapping for each item
    1.79 +  /// in the graph.
    1.80 +  ///
    1.81 +  template <typename _Graph, typename _Item>
    1.82 +  class IdMap {
    1.83 +  public:
    1.84 +    typedef _Graph Graph;
    1.85 +    typedef int Value;
    1.86 +    typedef _Item Item;
    1.87 +    typedef _Item Key;
    1.88 +
    1.89 +    /// \brief Constructor.
    1.90 +    ///
    1.91 +    /// Constructor for creating id map.
    1.92 +    IdMap(const Graph& _graph) : graph(&_graph) {}
    1.93 +
    1.94 +    /// \brief Gives back the \e id of the item.
    1.95 +    ///
    1.96 +    /// Gives back the immutable and unique \e id of the map.
    1.97 +    int operator[](const Item& item) const { return graph->id(item);}
    1.98 +
    1.99 +
   1.100 +  private:
   1.101 +    const Graph* graph;
   1.102 +
   1.103 +  public:
   1.104 +
   1.105 +    /// \brief The class represents the inverse of the map.
   1.106 +    ///
   1.107 +    /// The class represents the inverse of the map.
   1.108 +    /// \see inverse()
   1.109 +    class InverseMap {
   1.110 +    public:
   1.111 +      /// \brief Constructor.
   1.112 +      ///
   1.113 +      /// Constructor for creating an id-to-item map.
   1.114 +      InverseMap(const Graph& _graph) : graph(&_graph) {}
   1.115 +
   1.116 +      /// \brief Constructor.
   1.117 +      ///
   1.118 +      /// Constructor for creating an id-to-item map.
   1.119 +      InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
   1.120 +
   1.121 +      /// \brief Gives back the given item from its id.
   1.122 +      ///
   1.123 +      /// Gives back the given item from its id.
   1.124 +      /// 
   1.125 +      Item operator[](int id) const { return graph->fromId(id, Item());}
   1.126 +    private:
   1.127 +      const Graph* graph;
   1.128 +    };
   1.129 +
   1.130 +    /// \brief Gives back the inverse of the map.
   1.131 +    ///
   1.132 +    /// Gives back the inverse of the map.
   1.133 +    InverseMap inverse() const { return InverseMap(*graph);} 
   1.134 +
   1.135 +  };
   1.136 +
   1.137 +  
   1.138    /// \brief General inversable graph-map type.
   1.139  
   1.140    /// This type provides simple inversable map functions. 
   1.141 @@ -426,35 +437,32 @@
   1.142      typename _Item, 
   1.143      typename _Value,
   1.144      typename _Map 
   1.145 -    = typename ItemSetTraits<_Graph, _Item>::template Map<_Value> 
   1.146 +    = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent 
   1.147    >
   1.148 -  class InversableMap : protected _Map {
   1.149 +  class InvertableMap : protected _Map {
   1.150  
   1.151    public:
   1.152   
   1.153      typedef _Map Map;
   1.154      typedef _Graph Graph;
   1.155 -   /// The key type of InversableMap (Node, Edge, UndirEdge).
   1.156 +
   1.157 +    /// The key type of InvertableMap (Node, Edge, UndirEdge).
   1.158      typedef typename _Map::Key Key;
   1.159 -    /// The value type of the InversableMap.
   1.160 +    /// The value type of the InvertableMap.
   1.161      typedef typename _Map::Value Value;
   1.162  
   1.163 -    typedef std::map<Value, Key> InverseMap;
   1.164 -    
   1.165 -    typedef typename _Map::ConstReference ConstReference;
   1.166 -
   1.167      /// \brief Constructor.
   1.168      ///
   1.169 -    /// Construct a new InversableMap for the graph.
   1.170 +    /// Construct a new InvertableMap for the graph.
   1.171      ///
   1.172 -    InversableMap(const Graph& graph) : Map(graph) {} 
   1.173 +    InvertableMap(const Graph& graph) : Map(graph) {} 
   1.174      
   1.175      /// \brief The setter function of the map.
   1.176      ///
   1.177 -
   1.178 +    /// Sets the mapped value.
   1.179      void set(const Key& key, const Value& val) {
   1.180        Value oldval = Map::operator[](key);
   1.181 -      typename InverseMap::iterator it = invMap.find(oldval);
   1.182 +      typename Container::iterator it = invMap.find(oldval);
   1.183        if (it != invMap.end() && it->second == key) {
   1.184  	invMap.erase(it);
   1.185        }      
   1.186 @@ -465,7 +473,7 @@
   1.187      /// \brief The getter function of the map.
   1.188      ///
   1.189      /// It gives back the value associated with the key.
   1.190 -    ConstReference operator[](const Key& key) const {
   1.191 +    const Value operator[](const Key& key) const {
   1.192        return Map::operator[](key);
   1.193      }
   1.194  
   1.195 @@ -483,7 +491,7 @@
   1.196      /// \c AlterationNotifier.
   1.197      virtual void erase(const Key& key) {
   1.198        Value val = Map::operator[](key);
   1.199 -      typename InverseMap::iterator it = invMap.find(val);
   1.200 +      typename Container::iterator it = invMap.find(val);
   1.201        if (it != invMap.end() && it->second == key) {
   1.202  	invMap.erase(it);
   1.203        }
   1.204 @@ -499,33 +507,69 @@
   1.205        Map::clear();
   1.206      }
   1.207  
   1.208 +  private:
   1.209 +    
   1.210 +    typedef std::map<Value, Key> Container;
   1.211 +    Container invMap;    
   1.212 +
   1.213 +  public:
   1.214 +
   1.215 +    /// \brief The inverse map type.
   1.216 +    ///
   1.217 +    /// The inverse of this map. The subscript operator of the map
   1.218 +    /// gives back always the item what was last assigned to the value. 
   1.219 +    class InverseMap {
   1.220 +    public:
   1.221 +      /// \brief Constructor of the InverseMap.
   1.222 +      ///
   1.223 +      /// Constructor of the InverseMap.
   1.224 +      InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}
   1.225 +
   1.226 +      /// The value type of the InverseMap.
   1.227 +      typedef typename InvertableMap::Key Value;
   1.228 +      /// The key type of the InverseMap.
   1.229 +      typedef typename InvertableMap::Value Key; 
   1.230 +
   1.231 +      /// \brief Subscript operator. 
   1.232 +      ///
   1.233 +      /// Subscript operator. It gives back always the item 
   1.234 +      /// what was last assigned to the value.
   1.235 +      Value operator[](const Key& key) const {
   1.236 +	typename Container::const_iterator it = inverted.invMap.find(key);
   1.237 +	return it->second;
   1.238 +      }
   1.239 +      
   1.240 +    private:
   1.241 +      const InvertableMap& inverted;
   1.242 +    };
   1.243 +
   1.244      /// \brief It gives back the just readeable inverse map.
   1.245      ///
   1.246      /// It gives back the just readeable inverse map.
   1.247 -    const InverseMap& inverse() const {
   1.248 -      return invMap;
   1.249 +    InverseMap inverse() const {
   1.250 +      return InverseMap(*this);
   1.251      } 
   1.252  
   1.253  
   1.254 -  private:
   1.255 -    InverseMap invMap;    
   1.256 +    
   1.257    };
   1.258  
   1.259    /// \brief Provides a mutable, continuous and unique descriptor for each 
   1.260    /// item in the graph.
   1.261    ///
   1.262    /// The DescriptorMap class provides a mutable, continuous and immutable
   1.263 -  /// mapping for each item in the graph.
   1.264 +  /// mapping for each item in the graph. The value for an item may mutated
   1.265 +  /// on each operation when the an item erased or added to graph.
   1.266    ///
   1.267    /// \param _Graph The graph class the \c DescriptorMap belongs to.
   1.268    /// \param _Item The Item is the Key of the Map. It may be Node, Edge or 
   1.269    /// UndirEdge.
   1.270    /// \param _Map A ReadWriteMap mapping from the item type to integer.
   1.271 -
   1.272    template <
   1.273      typename _Graph,   
   1.274      typename _Item,
   1.275 -    typename _Map = typename ItemSetTraits<_Graph, _Item>::template Map<int>
   1.276 +    typename _Map 
   1.277 +    = typename ItemSetTraits<_Graph, _Item>::template Map<int>::Parent
   1.278    >
   1.279    class DescriptorMap : protected _Map {
   1.280  
   1.281 @@ -541,11 +585,9 @@
   1.282      /// The value type of DescriptorMap.
   1.283      typedef typename _Map::Value Value;
   1.284  
   1.285 -    typedef std::vector<Item> InverseMap;
   1.286 -
   1.287      /// \brief Constructor.
   1.288      ///
   1.289 -    /// Constructor for creating descriptor map.
   1.290 +    /// Constructor for descriptor map.
   1.291      DescriptorMap(const Graph& _graph) : Map(_graph) {
   1.292        build();
   1.293      }
   1.294 @@ -567,6 +609,7 @@
   1.295      virtual void erase(const Item& item) {
   1.296        Map::set(invMap.back(), Map::operator[](item));
   1.297        invMap[Map::operator[](item)] = invMap.back();
   1.298 +      invMap.pop_back();
   1.299        Map::erase(item);
   1.300      }
   1.301  
   1.302 @@ -600,15 +643,47 @@
   1.303        return Map::operator[](item);
   1.304      }
   1.305      
   1.306 +  private:
   1.307 +
   1.308 +    typedef std::vector<Item> Container;
   1.309 +    Container invMap;
   1.310 +
   1.311 +  public:
   1.312 +    /// \brief The inverse map type.
   1.313 +    ///
   1.314 +    /// The inverse map type.
   1.315 +    class InverseMap {
   1.316 +    public:
   1.317 +      /// \brief Constructor of the InverseMap.
   1.318 +      ///
   1.319 +      /// Constructor of the InverseMap.
   1.320 +      InverseMap(const DescriptorMap& _inverted) 
   1.321 +	: inverted(_inverted) {}
   1.322 +
   1.323 +
   1.324 +      /// The value type of the InverseMap.
   1.325 +      typedef typename DescriptorMap::Key Value;
   1.326 +      /// The key type of the InverseMap.
   1.327 +      typedef typename DescriptorMap::Value Key; 
   1.328 +
   1.329 +      /// \brief Subscript operator. 
   1.330 +      ///
   1.331 +      /// Subscript operator. It gives back the item 
   1.332 +      /// that the descriptor belongs to currently.
   1.333 +      Value operator[](const Key& key) const {
   1.334 +	return inverted.invMap[key];
   1.335 +      }
   1.336 +      
   1.337 +    private:
   1.338 +      const DescriptorMap& inverted;
   1.339 +    };
   1.340 +
   1.341      /// \brief Gives back the inverse of the map.
   1.342      ///
   1.343      /// Gives back the inverse of the map.
   1.344      const InverseMap inverse() const {
   1.345 -      return invMap;
   1.346 +      return InverseMap(*this);
   1.347      }
   1.348 -
   1.349 -  private:
   1.350 -    std::vector<Item> invMap;
   1.351    };
   1.352  
   1.353    /// \brief Returns the source of the given edge.