COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/map_utils.h @ 1139:f59038affc7e

Last change on this file since 1139:f59038affc7e was 1137:83a48cfd8553, checked in by Balazs Dezso, 19 years ago

IO moved to lemon.

File size: 7.2 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/map_utils.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
6 *
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.
10 *
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
13 * purpose.
14 *
15 */
16
17///\ingroup mutils
18///\file
19///\brief Map utilities.
20
21#include <map>
22
23
24namespace lemon {
25
26  /// \addtogroup mutils
27  /// @{
28
29  /// \brief General inversable map type.
30
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.
37  template <
38    typename _Graph,
39    typename _Map
40  >
41  class InversableMap : protected _Map {
42
43  public:
44    typedef _Graph Graph;
45
46    typedef _Map 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;
52   
53    typedef typename _Map::ConstReference ConstReference;
54
55    /// \brief Constructor.
56    ///
57    /// Construct a new InversableMap for the graph.
58    ///
59    InversableMap(const Graph& graph) : Map(graph) {}
60   
61    /// \brief The setter function of the map.
62    ///
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) {
68        invMap.erase(it);
69      }     
70      invMap.insert(make_pair(val, key));
71      Map::set(key, val);
72    }
73
74    /// \brief The getter function of the map.
75    ///
76    /// It gives back the value associated with the key.
77    ConstReference operator[](const Key& key) const {
78      return Map::operator[](key);
79    }
80
81    /// \brief Add a new key to the map.
82    ///
83    /// Add a new key to the map. It is called by the
84    /// \c AlterationNotifier.
85    virtual void add(const Key& key) {
86      Map::add(key);
87    }
88
89    /// \brief Erase the key from the map.
90    ///
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) {
97        invMap.erase(it);
98      }
99      Map::erase(key);
100    }
101
102    /// \brief Clear the keys from the map and inverse map.
103    ///
104    /// Clear the keys from the map and inverse map. It is called by the
105    /// \c AlterationNotifier.
106    virtual void clear() {
107      invMap.clear();
108      Map::clear();
109    }
110
111    /// \brief It gives back the just readeable inverse map.
112    ///
113    /// It gives back the just readeable inverse map.
114    const InverseMap& inverse() const {
115      return invMap;
116    }
117
118
119  private:
120    InverseMap invMap;   
121  };
122
123
124 
125  /// \brief Provides a mutable, continous and unique descriptor for each
126  /// item in the graph.
127  ///
128  /// The DescriptorMap class provides a mutable, continous and immutable
129  /// mapping for each item in the graph.
130  ///
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
133  /// UndirEdge.
134  /// \param _Map A ReadWriteMap mapping from the item type to integer.
135
136  template <
137    typename _Graph,   
138    typename _Item,
139    typename _Map
140  >
141  class DescriptorMap : protected _Map {
142
143    typedef _Item Item;
144    typedef _Map Map;
145
146  public:
147    /// The graph class of DescriptorMap.
148    typedef _Graph Graph;
149
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;
154
155    typedef std::vector<Item> InverseMap;
156
157    /// \brief Constructor.
158    ///
159    /// Constructor for creating descriptor map.
160    DescriptorMap(const Graph& _graph) : Map(_graph) {
161      build();
162    }
163
164    /// \brief Add a new key to the map.
165    ///
166    /// Add a new key to the map. It is called by the
167    /// \c AlterationNotifier.
168    virtual void add(const Item& item) {
169      Map::add(item);
170      Map::set(item, invMap.size());
171      invMap.push_back(item);
172    }
173
174    /// \brief Erase the key from the map.
175    ///
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();
181      Map::erase(item);
182    }
183
184    /// \brief Build the unique map.
185    ///
186    /// Build the unique map. It is called by the
187    /// \c AlterationNotifier.
188    virtual void build() {
189      Map::build();
190      Item it;
191      for (getGraph()->first(it); it != INVALID; getGraph()->next(it)) {
192        Map::set(it, invMap.size());
193        invMap.push_back(it);   
194      }     
195    }
196   
197    /// \brief Clear the keys from the map.
198    ///
199    /// Clear the keys from the map. It is called by the
200    /// \c AlterationNotifier.
201    virtual void clear() {
202      invMap.clear();
203      Map::clear();
204    }
205
206    /// \brief Gives back the \e descriptor of the item.
207    ///
208    /// Gives back the mutable and unique \e descriptor of the map.
209    int operator[](const Item& item) const {
210      return Map::operator[](item);
211    }
212   
213    /// \brief Gives back the inverse of the map.
214    ///
215    /// Gives back the inverse of the map.
216    const InverseMap inverse() const {
217      return invMap;
218    }
219
220  private:
221    vector<Item> invMap;
222  };
223 
224  /// Provides an immutable and unique id for each item in the graph.
225
226  /// The IdMap class provides an unique and immutable mapping for each item
227  /// in the graph.
228  ///
229  template <typename _Graph, typename _Item>
230  class IdMap {
231  public:
232    typedef _Graph Graph;
233    typedef int Value;
234    typedef _Item Item;
235
236    /// \brief The class represents the inverse of the map.
237    ///
238    /// The class represents the inverse of the map.
239    /// \see inverse()
240    class InverseMap {
241    protected:
242      InverseMap(const Graph& _graph) : graph(_graph) {}
243    public:
244      /// \brief Gives back the given item by its id.
245      ///
246      /// Gives back the given item by its id.
247      ///
248      Item operator[](int id) const { return graph->fromId(id, Item());}
249    private:
250      Graph* graph;
251    };
252
253    /// \brief Constructor.
254    ///
255    /// Constructor for creating id map.
256    IdMap(const Graph& _graph) : graph(&_graph) {}
257
258    /// \brief Gives back the \e id of the item.
259    ///
260    /// Gives back the immutable and unique \e id of the map.
261    int operator[](const Item& item) const { return graph->id(item);}
262
263    /// \brief Gives back the inverse of the map.
264    ///
265    /// Gives back the inverse of the map.
266    InverseMap inverse() const { return InverseMap(*graph);}
267
268  private:
269    const Graph* graph;
270
271  };
272
273
274
275}
276
Note: See TracBrowser for help on using the repository browser.