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.