1.1 --- a/src/lemon/map_utils.h Wed May 04 13:07:10 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,311 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/lemon/map_utils.h - Part of LEMON, a generic C++ optimization library
1.6 - *
1.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.9 - *
1.10 - * Permission to use, modify and distribute this software is granted
1.11 - * provided that this copyright notice appears in all copies. For
1.12 - * precise terms see the accompanying LICENSE file.
1.13 - *
1.14 - * This software is provided "AS IS" with no warranty of any kind,
1.15 - * express or implied, and with no claim as to its suitability for any
1.16 - * purpose.
1.17 - *
1.18 - */
1.19 -
1.20 -
1.21 -///\ingroup mutils
1.22 -///\file
1.23 -///\brief Map utilities.
1.24 -
1.25 -#ifndef LEMON_MAP_UTILS_H
1.26 -#define LEMON_MAP_UTILS_H
1.27 -
1.28 -#include <map>
1.29 -#include <vector>
1.30 -
1.31 -#include <lemon/graph_utils.h>
1.32 -
1.33 -namespace lemon {
1.34 -
1.35 - /// \addtogroup mutils
1.36 - /// @{
1.37 -
1.38 -
1.39 - template <typename Map, typename Enable = void>
1.40 - struct ReferenceMapTraits {
1.41 - typedef typename Map::Value Value;
1.42 - typedef typename Map::Value& Reference;
1.43 - typedef const typename Map::Value& ConstReference;
1.44 - typedef typename Map::Value* Pointer;
1.45 - typedef const typename Map::Value* ConstPointer;
1.46 - };
1.47 -
1.48 - template <typename Map>
1.49 - struct ReferenceMapTraits<
1.50 - Map,
1.51 - typename enable_if<typename Map::FullTypeTag, void>::type
1.52 - > {
1.53 - typedef typename Map::Value Value;
1.54 - typedef typename Map::Reference Reference;
1.55 - typedef typename Map::ConstReference ConstReference;
1.56 - typedef typename Map::Pointer Pointer;
1.57 - typedef typename Map::ConstPointer ConstPointer;
1.58 - };
1.59 -
1.60 - /// \brief General inversable map type.
1.61 -
1.62 - /// This type provides simple inversable map functions.
1.63 - /// The InversableMap wraps an arbitrary ReadWriteMap
1.64 - /// and if a key is setted to a new value then store it
1.65 - /// in the inverse map.
1.66 - /// \param _Graph The graph type.
1.67 - /// \param _Map The map to extend with inversable functionality.
1.68 - template <
1.69 - typename _Graph,
1.70 - typename _Item,
1.71 - typename _Value,
1.72 - typename _Map
1.73 - = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>
1.74 - >
1.75 - class InversableMap : protected _Map {
1.76 -
1.77 - public:
1.78 -
1.79 - typedef _Map Map;
1.80 - typedef _Graph Graph;
1.81 - /// The key type of InversableMap (Node, Edge, UndirEdge).
1.82 - typedef typename _Map::Key Key;
1.83 - /// The value type of the InversableMap.
1.84 - typedef typename _Map::Value Value;
1.85 -
1.86 - typedef std::map<Value, Key> InverseMap;
1.87 -
1.88 - typedef typename _Map::ConstReference ConstReference;
1.89 -
1.90 - /// \brief Constructor.
1.91 - ///
1.92 - /// Construct a new InversableMap for the graph.
1.93 - ///
1.94 - InversableMap(const Graph& graph) : Map(graph) {}
1.95 -
1.96 - /// \brief The setter function of the map.
1.97 - ///
1.98 -
1.99 - void set(const Key& key, const Value& val) {
1.100 - Value oldval = Map::operator[](key);
1.101 - typename InverseMap::iterator it = invMap.find(oldval);
1.102 - if (it != invMap.end() && it->second == key) {
1.103 - invMap.erase(it);
1.104 - }
1.105 - invMap.insert(make_pair(val, key));
1.106 - Map::set(key, val);
1.107 - }
1.108 -
1.109 - /// \brief The getter function of the map.
1.110 - ///
1.111 - /// It gives back the value associated with the key.
1.112 - ConstReference operator[](const Key& key) const {
1.113 - return Map::operator[](key);
1.114 - }
1.115 -
1.116 - /// \brief Add a new key to the map.
1.117 - ///
1.118 - /// Add a new key to the map. It is called by the
1.119 - /// \c AlterationNotifier.
1.120 - virtual void add(const Key& key) {
1.121 - Map::add(key);
1.122 - }
1.123 -
1.124 - /// \brief Erase the key from the map.
1.125 - ///
1.126 - /// Erase the key to the map. It is called by the
1.127 - /// \c AlterationNotifier.
1.128 - virtual void erase(const Key& key) {
1.129 - Value val = Map::operator[](key);
1.130 - typename InverseMap::iterator it = invMap.find(val);
1.131 - if (it != invMap.end() && it->second == key) {
1.132 - invMap.erase(it);
1.133 - }
1.134 - Map::erase(key);
1.135 - }
1.136 -
1.137 - /// \brief Clear the keys from the map and inverse map.
1.138 - ///
1.139 - /// Clear the keys from the map and inverse map. It is called by the
1.140 - /// \c AlterationNotifier.
1.141 - virtual void clear() {
1.142 - invMap.clear();
1.143 - Map::clear();
1.144 - }
1.145 -
1.146 - /// \brief It gives back the just readeable inverse map.
1.147 - ///
1.148 - /// It gives back the just readeable inverse map.
1.149 - const InverseMap& inverse() const {
1.150 - return invMap;
1.151 - }
1.152 -
1.153 -
1.154 - private:
1.155 - InverseMap invMap;
1.156 - };
1.157 -
1.158 -
1.159 -
1.160 - /// \brief Provides a mutable, continous and unique descriptor for each
1.161 - /// item in the graph.
1.162 - ///
1.163 - /// The DescriptorMap class provides a mutable, continous and immutable
1.164 - /// mapping for each item in the graph.
1.165 - ///
1.166 - /// \param _Graph The graph class the \c DescriptorMap belongs to.
1.167 - /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
1.168 - /// UndirEdge.
1.169 - /// \param _Map A ReadWriteMap mapping from the item type to integer.
1.170 -
1.171 - template <
1.172 - typename _Graph,
1.173 - typename _Item,
1.174 - typename _Map = typename ItemSetTraits<_Graph, _Item>::template Map<int>
1.175 - >
1.176 - class DescriptorMap : protected _Map {
1.177 -
1.178 - typedef _Item Item;
1.179 - typedef _Map Map;
1.180 -
1.181 - public:
1.182 - /// The graph class of DescriptorMap.
1.183 - typedef _Graph Graph;
1.184 -
1.185 - /// The key type of DescriptorMap (Node, Edge, UndirEdge).
1.186 - typedef typename _Map::Key Key;
1.187 - /// The value type of DescriptorMap.
1.188 - typedef typename _Map::Value Value;
1.189 -
1.190 - typedef std::vector<Item> InverseMap;
1.191 -
1.192 - /// \brief Constructor.
1.193 - ///
1.194 - /// Constructor for creating descriptor map.
1.195 - DescriptorMap(const Graph& _graph) : Map(_graph) {
1.196 - build();
1.197 - }
1.198 -
1.199 - /// \brief Add a new key to the map.
1.200 - ///
1.201 - /// Add a new key to the map. It is called by the
1.202 - /// \c AlterationNotifier.
1.203 - virtual void add(const Item& item) {
1.204 - Map::add(item);
1.205 - Map::set(item, invMap.size());
1.206 - invMap.push_back(item);
1.207 - }
1.208 -
1.209 - /// \brief Erase the key from the map.
1.210 - ///
1.211 - /// Erase the key to the map. It is called by the
1.212 - /// \c AlterationNotifier.
1.213 - virtual void erase(const Item& item) {
1.214 - Map::set(invMap.back(), Map::operator[](item));
1.215 - invMap[Map::operator[](item)] = invMap.back();
1.216 - Map::erase(item);
1.217 - }
1.218 -
1.219 - /// \brief Build the unique map.
1.220 - ///
1.221 - /// Build the unique map. It is called by the
1.222 - /// \c AlterationNotifier.
1.223 - virtual void build() {
1.224 - Map::build();
1.225 - Item it;
1.226 - const typename Map::Graph* graph = Map::getGraph();
1.227 - for (graph->first(it); it != INVALID; graph->next(it)) {
1.228 - Map::set(it, invMap.size());
1.229 - invMap.push_back(it);
1.230 - }
1.231 - }
1.232 -
1.233 - /// \brief Clear the keys from the map.
1.234 - ///
1.235 - /// Clear the keys from the map. It is called by the
1.236 - /// \c AlterationNotifier.
1.237 - virtual void clear() {
1.238 - invMap.clear();
1.239 - Map::clear();
1.240 - }
1.241 -
1.242 - /// \brief Gives back the \e descriptor of the item.
1.243 - ///
1.244 - /// Gives back the mutable and unique \e descriptor of the map.
1.245 - int operator[](const Item& item) const {
1.246 - return Map::operator[](item);
1.247 - }
1.248 -
1.249 - /// \brief Gives back the inverse of the map.
1.250 - ///
1.251 - /// Gives back the inverse of the map.
1.252 - const InverseMap inverse() const {
1.253 - return invMap;
1.254 - }
1.255 -
1.256 - private:
1.257 - std::vector<Item> invMap;
1.258 - };
1.259 -
1.260 - /// Provides an immutable and unique id for each item in the graph.
1.261 -
1.262 - /// The IdMap class provides an unique and immutable mapping for each item
1.263 - /// in the graph.
1.264 - ///
1.265 - template <typename _Graph, typename _Item>
1.266 - class IdMap {
1.267 - public:
1.268 - typedef _Graph Graph;
1.269 - typedef int Value;
1.270 - typedef _Item Item;
1.271 - typedef _Item Key;
1.272 -
1.273 - /// \brief The class represents the inverse of the map.
1.274 - ///
1.275 - /// The class represents the inverse of the map.
1.276 - /// \see inverse()
1.277 - class InverseMap {
1.278 - public:
1.279 - /// \brief Constructor.
1.280 - ///
1.281 - /// Constructor for creating an id-to-item map.
1.282 - InverseMap(const Graph& _graph) : graph(&_graph) {}
1.283 - /// \brief Gives back the given item from its id.
1.284 - ///
1.285 - /// Gives back the given item from its id.
1.286 - ///
1.287 - Item operator[](int id) const { return graph->fromId(id, Item());}
1.288 - private:
1.289 - const Graph* graph;
1.290 - };
1.291 -
1.292 - /// \brief Constructor.
1.293 - ///
1.294 - /// Constructor for creating id map.
1.295 - IdMap(const Graph& _graph) : graph(&_graph) {}
1.296 -
1.297 - /// \brief Gives back the \e id of the item.
1.298 - ///
1.299 - /// Gives back the immutable and unique \e id of the map.
1.300 - int operator[](const Item& item) const { return graph->id(item);}
1.301 -
1.302 - /// \brief Gives back the inverse of the map.
1.303 - ///
1.304 - /// Gives back the inverse of the map.
1.305 - InverseMap inverse() const { return InverseMap(*graph);}
1.306 -
1.307 - private:
1.308 - const Graph* graph;
1.309 -
1.310 - };
1.311 -
1.312 -}
1.313 -
1.314 -#endif