A strange compilation failure (under cygwin) is fixed.
Version 0.3 should be fixed as well.
2 * src/lemon/map_utils.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
20 ///\brief Map utilities.
22 #ifndef LEMON_MAP_UTILS_H
23 #define LEMON_MAP_UTILS_H
30 /// \addtogroup mutils
33 /// \brief General inversable map type.
35 /// This type provides simple inversable map functions.
36 /// The InversableMap wraps an arbitrary ReadWriteMap
37 /// and if a key is setted to a new value then store it
38 /// in the inverse map.
39 /// \param _Graph The graph type.
40 /// \param _Map The map to extend with inversable functionality.
45 class InversableMap : protected _Map {
51 /// The key type of InversableMap (Node, Edge, UndirEdge).
52 typedef typename _Map::Key Key;
53 /// The value type of the InversableMap.
54 typedef typename _Map::Value Value;
55 typedef std::map<Value, Key> InverseMap;
57 typedef typename _Map::ConstReference ConstReference;
59 /// \brief Constructor.
61 /// Construct a new InversableMap for the graph.
63 InversableMap(const Graph& graph) : Map(graph) {}
65 /// \brief The setter function of the map.
67 /// It sets the map and the inverse map to given key-value pair.
68 void set(const Key& key, const Value& val) {
69 Value oldval = Map::operator[](key);
70 typename InverseMap::iterator it = invMap.find(oldval);
71 if (it != invMap.end() && it->second == key) {
74 invMap.insert(make_pair(val, key));
78 /// \brief The getter function of the map.
80 /// It gives back the value associated with the key.
81 ConstReference operator[](const Key& key) const {
82 return Map::operator[](key);
85 /// \brief Add a new key to the map.
87 /// Add a new key to the map. It is called by the
88 /// \c AlterationNotifier.
89 virtual void add(const Key& key) {
93 /// \brief Erase the key from the map.
95 /// Erase the key to the map. It is called by the
96 /// \c AlterationNotifier.
97 virtual void erase(const Key& key) {
98 Value val = Map::operator[](key);
99 typename InverseMap::iterator it = invMap.find(val);
100 if (it != invMap.end() && it->second == key) {
106 /// \brief Clear the keys from the map and inverse map.
108 /// Clear the keys from the map and inverse map. It is called by the
109 /// \c AlterationNotifier.
110 virtual void clear() {
115 /// \brief It gives back the just readeable inverse map.
117 /// It gives back the just readeable inverse map.
118 const InverseMap& inverse() const {
129 /// \brief Provides a mutable, continous and unique descriptor for each
130 /// item in the graph.
132 /// The DescriptorMap class provides a mutable, continous and immutable
133 /// mapping for each item in the graph.
135 /// \param _Graph The graph class the \c DescriptorMap belongs to.
136 /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
138 /// \param _Map A ReadWriteMap mapping from the item type to integer.
145 class DescriptorMap : protected _Map {
151 /// The graph class of DescriptorMap.
152 typedef _Graph Graph;
154 /// The key type of DescriptorMap (Node, Edge, UndirEdge).
155 typedef typename _Map::Key Key;
156 /// The value type of DescriptorMap.
157 typedef typename _Map::Value Value;
159 typedef std::vector<Item> InverseMap;
161 /// \brief Constructor.
163 /// Constructor for creating descriptor map.
164 DescriptorMap(const Graph& _graph) : Map(_graph) {
168 /// \brief Add a new key to the map.
170 /// Add a new key to the map. It is called by the
171 /// \c AlterationNotifier.
172 virtual void add(const Item& item) {
174 Map::set(item, invMap.size());
175 invMap.push_back(item);
178 /// \brief Erase the key from the map.
180 /// Erase the key to the map. It is called by the
181 /// \c AlterationNotifier.
182 virtual void erase(const Item& item) {
183 Map::set(invMap.back(), Map::operator[](item));
184 invMap[Map::operator[](item)] = invMap.back();
188 /// \brief Build the unique map.
190 /// Build the unique map. It is called by the
191 /// \c AlterationNotifier.
192 virtual void build() {
195 const Graph* graph = Map::getGraph();
196 for (graph->first(it); it != INVALID; graph->next(it)) {
197 Map::set(it, invMap.size());
198 invMap.push_back(it);
202 /// \brief Clear the keys from the map.
204 /// Clear the keys from the map. It is called by the
205 /// \c AlterationNotifier.
206 virtual void clear() {
211 /// \brief Gives back the \e descriptor of the item.
213 /// Gives back the mutable and unique \e descriptor of the map.
214 int operator[](const Item& item) const {
215 return Map::operator[](item);
218 /// \brief Gives back the inverse of the map.
220 /// Gives back the inverse of the map.
221 const InverseMap inverse() const {
226 std::vector<Item> invMap;
229 /// Provides an immutable and unique id for each item in the graph.
231 /// The IdMap class provides an unique and immutable mapping for each item
234 template <typename _Graph, typename _Item>
237 typedef _Graph Graph;
241 /// \brief The class represents the inverse of the map.
243 /// The class represents the inverse of the map.
247 InverseMap(const Graph& _graph) : graph(&_graph) {}
249 /// \brief Gives back the given item by its id.
251 /// Gives back the given item by its id.
253 Item operator[](int id) const { return graph->fromId(id, Item());}
258 /// \brief Constructor.
260 /// Constructor for creating id map.
261 IdMap(const Graph& _graph) : graph(&_graph) {}
263 /// \brief Gives back the \e id of the item.
265 /// Gives back the immutable and unique \e id of the map.
266 int operator[](const Item& item) const { return graph->id(item);}
268 /// \brief Gives back the inverse of the map.
270 /// Gives back the inverse of the map.
271 InverseMap inverse() const { return InverseMap(*graph);}