Experimental autopackage specfile.
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
19 ///\brief Map utilities.
26 /// \addtogroup mutils
29 /// \brief General inversable map type.
31 /// This type provides simple inversable map functions.
32 /// The InversableMap wraps an arbitrary ReadWriteMap
33 /// and if a key is setted to a new value then store it
34 /// in the inverse map.
35 /// \param _Graph The graph type.
36 /// \param _Map The map to extend with inversable functionality.
41 class InversableMap : protected _Map {
47 /// The key type of InversableMap (Node, Edge, UndirEdge).
48 typedef typename _Map::Key Key;
49 /// The value type of the InversableMap.
50 typedef typename _Map::Value Value;
51 typedef std::map<Value, Key> InverseMap;
53 typedef typename _Map::ConstReference ConstReference;
55 /// \brief Constructor.
57 /// Construct a new InversableMap for the graph.
59 InversableMap(const Graph& graph) : Map(graph) {}
61 /// \brief The setter function of the map.
63 /// It sets the map and the inverse map to given key-value pair.
64 void set(const Key& key, const Value& val) {
65 Value oldval = Map::operator[](key);
66 typename InverseMap::iterator it = invMap.find(oldval);
67 if (it != invMap.end() && it->second == key) {
70 invMap.insert(make_pair(val, key));
74 /// \brief The getter function of the map.
76 /// It gives back the value associated with the key.
77 ConstReference operator[](const Key& key) const {
78 return Map::operator[](key);
81 /// \brief Add a new key to the map.
83 /// Add a new key to the map. It is called by the
84 /// \c AlterationNotifier.
85 virtual void add(const Key& key) {
89 /// \brief Erase the key from the map.
91 /// Erase the key to the map. It is called by the
92 /// \c AlterationNotifier.
93 virtual void erase(const Key& key) {
94 Value val = Map::operator[](key);
95 typename InverseMap::iterator it = invMap.find(val);
96 if (it != invMap.end() && it->second == key) {
102 /// \brief Clear the keys from the map and inverse map.
104 /// Clear the keys from the map and inverse map. It is called by the
105 /// \c AlterationNotifier.
106 virtual void clear() {
111 /// \brief It gives back the just readeable inverse map.
113 /// It gives back the just readeable inverse map.
114 const InverseMap& inverse() const {
125 /// \brief Provides a mutable, continous and unique descriptor for each
126 /// item in the graph.
128 /// The DescriptorMap class provides a mutable, continous and immutable
129 /// mapping for each item in the graph.
131 /// \param _Graph The graph class the \c DescriptorMap belongs to.
132 /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
134 /// \param _Map A ReadWriteMap mapping from the item type to integer.
141 class DescriptorMap : protected _Map {
147 /// The graph class of DescriptorMap.
148 typedef _Graph Graph;
150 /// The key type of DescriptorMap (Node, Edge, UndirEdge).
151 typedef typename _Map::Key Key;
152 /// The value type of DescriptorMap.
153 typedef typename _Map::Value Value;
155 typedef std::vector<Item> InverseMap;
157 /// \brief Constructor.
159 /// Constructor for creating descriptor map.
160 DescriptorMap(const Graph& _graph) : Map(_graph) {
164 /// \brief Add a new key to the map.
166 /// Add a new key to the map. It is called by the
167 /// \c AlterationNotifier.
168 virtual void add(const Item& item) {
170 Map::set(item, invMap.size());
171 invMap.push_back(item);
174 /// \brief Erase the key from the map.
176 /// Erase the key to the map. It is called by the
177 /// \c AlterationNotifier.
178 virtual void erase(const Item& item) {
179 Map::set(invMap.back(), Map::operator[](item));
180 invMap[Map::operator[](item)] = invMap.back();
184 /// \brief Build the unique map.
186 /// Build the unique map. It is called by the
187 /// \c AlterationNotifier.
188 virtual void build() {
191 for (getGraph()->first(it); it != INVALID; getGraph()->next(it)) {
192 Map::set(it, invMap.size());
193 invMap.push_back(it);
197 /// \brief Clear the keys from the map.
199 /// Clear the keys from the map. It is called by the
200 /// \c AlterationNotifier.
201 virtual void clear() {
206 /// \brief Gives back the \e descriptor of the item.
208 /// Gives back the mutable and unique \e descriptor of the map.
209 int operator[](const Item& item) const {
210 return Map::operator[](item);
213 /// \brief Gives back the inverse of the map.
215 /// Gives back the inverse of the map.
216 const InverseMap inverse() const {
224 /// Provides an immutable and unique id for each item in the graph.
226 /// The IdMap class provides an unique and immutable mapping for each item
229 template <typename _Graph, typename _Item>
232 typedef _Graph Graph;
236 /// \brief The class represents the inverse of the map.
238 /// The class represents the inverse of the map.
242 InverseMap(const Graph& _graph) : graph(_graph) {}
244 /// \brief Gives back the given item by its id.
246 /// Gives back the given item by its id.
248 Item operator[](int id) const { return graph->fromId(id, Item());}
253 /// \brief Constructor.
255 /// Constructor for creating id map.
256 IdMap(const Graph& _graph) : graph(&_graph) {}
258 /// \brief Gives back the \e id of the item.
260 /// Gives back the immutable and unique \e id of the map.
261 int operator[](const Item& item) const { return graph->id(item);}
263 /// \brief Gives back the inverse of the map.
265 /// Gives back the inverse of the map.
266 InverseMap inverse() const { return InverseMap(*graph);}