COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/map_utils.h @ 1237:2414b5ab7684

Last change on this file since 1237:2414b5ab7684 was 1237:2414b5ab7684, checked in by Alpar Juttner, 15 years ago

Constructor of IdMap?<G,I>::InverseMap? made public

File size: 7.4 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/map_utils.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 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
18///\ingroup mutils
19///\file
20///\brief Map utilities.
21
22#ifndef LEMON_MAP_UTILS_H
23#define LEMON_MAP_UTILS_H
24
25#include <map>
26
27
28namespace lemon {
29
30  /// \addtogroup mutils
31  /// @{
32
33  /// \brief General inversable map type.
34
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.
41  template <
42    typename _Graph,
43    typename _Map
44  >
45  class InversableMap : protected _Map {
46
47  public:
48    typedef _Graph Graph;
49
50    typedef _Map 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;
56   
57    typedef typename _Map::ConstReference ConstReference;
58
59    /// \brief Constructor.
60    ///
61    /// Construct a new InversableMap for the graph.
62    ///
63    InversableMap(const Graph& graph) : Map(graph) {}
64   
65    /// \brief The setter function of the map.
66    ///
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) {
72        invMap.erase(it);
73      }     
74      invMap.insert(make_pair(val, key));
75      Map::set(key, val);
76    }
77
78    /// \brief The getter function of the map.
79    ///
80    /// It gives back the value associated with the key.
81    ConstReference operator[](const Key& key) const {
82      return Map::operator[](key);
83    }
84
85    /// \brief Add a new key to the map.
86    ///
87    /// Add a new key to the map. It is called by the
88    /// \c AlterationNotifier.
89    virtual void add(const Key& key) {
90      Map::add(key);
91    }
92
93    /// \brief Erase the key from the map.
94    ///
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) {
101        invMap.erase(it);
102      }
103      Map::erase(key);
104    }
105
106    /// \brief Clear the keys from the map and inverse map.
107    ///
108    /// Clear the keys from the map and inverse map. It is called by the
109    /// \c AlterationNotifier.
110    virtual void clear() {
111      invMap.clear();
112      Map::clear();
113    }
114
115    /// \brief It gives back the just readeable inverse map.
116    ///
117    /// It gives back the just readeable inverse map.
118    const InverseMap& inverse() const {
119      return invMap;
120    }
121
122
123  private:
124    InverseMap invMap;   
125  };
126
127
128 
129  /// \brief Provides a mutable, continous and unique descriptor for each
130  /// item in the graph.
131  ///
132  /// The DescriptorMap class provides a mutable, continous and immutable
133  /// mapping for each item in the graph.
134  ///
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
137  /// UndirEdge.
138  /// \param _Map A ReadWriteMap mapping from the item type to integer.
139
140  template <
141    typename _Graph,   
142    typename _Item,
143    typename _Map
144  >
145  class DescriptorMap : protected _Map {
146
147    typedef _Item Item;
148    typedef _Map Map;
149
150  public:
151    /// The graph class of DescriptorMap.
152    typedef _Graph Graph;
153
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;
158
159    typedef std::vector<Item> InverseMap;
160
161    /// \brief Constructor.
162    ///
163    /// Constructor for creating descriptor map.
164    DescriptorMap(const Graph& _graph) : Map(_graph) {
165      build();
166    }
167
168    /// \brief Add a new key to the map.
169    ///
170    /// Add a new key to the map. It is called by the
171    /// \c AlterationNotifier.
172    virtual void add(const Item& item) {
173      Map::add(item);
174      Map::set(item, invMap.size());
175      invMap.push_back(item);
176    }
177
178    /// \brief Erase the key from the map.
179    ///
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();
185      Map::erase(item);
186    }
187
188    /// \brief Build the unique map.
189    ///
190    /// Build the unique map. It is called by the
191    /// \c AlterationNotifier.
192    virtual void build() {
193      Map::build();
194      Item it;
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);   
199      }     
200    }
201   
202    /// \brief Clear the keys from the map.
203    ///
204    /// Clear the keys from the map. It is called by the
205    /// \c AlterationNotifier.
206    virtual void clear() {
207      invMap.clear();
208      Map::clear();
209    }
210
211    /// \brief Gives back the \e descriptor of the item.
212    ///
213    /// Gives back the mutable and unique \e descriptor of the map.
214    int operator[](const Item& item) const {
215      return Map::operator[](item);
216    }
217   
218    /// \brief Gives back the inverse of the map.
219    ///
220    /// Gives back the inverse of the map.
221    const InverseMap inverse() const {
222      return invMap;
223    }
224
225  private:
226    std::vector<Item> invMap;
227  };
228 
229  /// Provides an immutable and unique id for each item in the graph.
230
231  /// The IdMap class provides an unique and immutable mapping for each item
232  /// in the graph.
233  ///
234  template <typename _Graph, typename _Item>
235  class IdMap {
236  public:
237    typedef _Graph Graph;
238    typedef int Value;
239    typedef _Item Item;
240
241    /// \brief The class represents the inverse of the map.
242    ///
243    /// The class represents the inverse of the map.
244    /// \see inverse()
245    class InverseMap {
246    public:
247      /// \brief Constructor.
248      ///
249      /// Constructor for creating an id-to-item map.
250      InverseMap(const Graph& _graph) : graph(&_graph) {}
251      /// \brief Gives back the given item from its id.
252      ///
253      /// Gives back the given item from its id.
254      ///
255      Item operator[](int id) const { return graph->fromId(id, Item());}
256    private:
257      const Graph* graph;
258    };
259
260    /// \brief Constructor.
261    ///
262    /// Constructor for creating id map.
263    IdMap(const Graph& _graph) : graph(&_graph) {}
264
265    /// \brief Gives back the \e id of the item.
266    ///
267    /// Gives back the immutable and unique \e id of the map.
268    int operator[](const Item& item) const { return graph->id(item);}
269
270    /// \brief Gives back the inverse of the map.
271    ///
272    /// Gives back the inverse of the map.
273    InverseMap inverse() const { return InverseMap(*graph);}
274
275  private:
276    const Graph* graph;
277
278  };
279
280}
281
282#endif
Note: See TracBrowser for help on using the repository browser.