COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/map_utils.h @ 1284:b941d044f87b

Last change on this file since 1284:b941d044f87b was 1267:a93f94dbe3d3, checked in by Balazs Dezso, 15 years ago

First version of iterable maps.

File size: 8.3 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#include <vector>
27
28#include <lemon/graph_utils.h>
29
30namespace lemon {
31
32  /// \addtogroup mutils
33  /// @{
34
35
36  template <typename Map, typename Enable = void>
37  struct ReferenceMapTraits {
38    typedef typename Map::Value Value;
39    typedef typename Map::Value& Reference;
40    typedef const typename Map::Value& ConstReference;
41    typedef typename Map::Value* Pointer;
42    typedef const typename Map::Value* ConstPointer;
43  };
44
45  template <typename Map>
46  struct ReferenceMapTraits<
47    Map,
48    typename enable_if<typename Map::FullTypeTag, void>::type
49  > {
50    typedef typename Map::Value Value;
51    typedef typename Map::Reference Reference;
52    typedef typename Map::ConstReference ConstReference;
53    typedef typename Map::Pointer Pointer;
54    typedef typename Map::ConstPointer ConstPointer;
55  };
56
57  /// \brief General inversable map type.
58
59  /// This type provides simple inversable map functions.
60  /// The InversableMap wraps an arbitrary ReadWriteMap
61  /// and if a key is setted to a new value then store it
62  /// in the inverse map.
63  /// \param _Graph The graph type.
64  /// \param _Map The map to extend with inversable functionality.
65  template <
66    typename _Graph,
67    typename _Item,
68    typename _Value,
69    typename _Map
70    = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>
71  >
72  class InversableMap : protected _Map {
73
74  public:
75 
76    typedef _Map Map;
77    typedef _Graph Graph;
78   /// The key type of InversableMap (Node, Edge, UndirEdge).
79    typedef typename _Map::Key Key;
80    /// The value type of the InversableMap.
81    typedef typename _Map::Value Value;
82
83    typedef std::map<Value, Key> InverseMap;
84   
85    typedef typename _Map::ConstReference ConstReference;
86
87    /// \brief Constructor.
88    ///
89    /// Construct a new InversableMap for the graph.
90    ///
91    InversableMap(const Graph& graph) : Map(graph) {}
92   
93    /// \brief The setter function of the map.
94    ///
95
96    void set(const Key& key, const Value& val) {
97      Value oldval = Map::operator[](key);
98      typename InverseMap::iterator it = invMap.find(oldval);
99      if (it != invMap.end() && it->second == key) {
100        invMap.erase(it);
101      }     
102      invMap.insert(make_pair(val, key));
103      Map::set(key, val);
104    }
105
106    /// \brief The getter function of the map.
107    ///
108    /// It gives back the value associated with the key.
109    ConstReference operator[](const Key& key) const {
110      return Map::operator[](key);
111    }
112
113    /// \brief Add a new key to the map.
114    ///
115    /// Add a new key to the map. It is called by the
116    /// \c AlterationNotifier.
117    virtual void add(const Key& key) {
118      Map::add(key);
119    }
120
121    /// \brief Erase the key from the map.
122    ///
123    /// Erase the key to the map. It is called by the
124    /// \c AlterationNotifier.
125    virtual void erase(const Key& key) {
126      Value val = Map::operator[](key);
127      typename InverseMap::iterator it = invMap.find(val);
128      if (it != invMap.end() && it->second == key) {
129        invMap.erase(it);
130      }
131      Map::erase(key);
132    }
133
134    /// \brief Clear the keys from the map and inverse map.
135    ///
136    /// Clear the keys from the map and inverse map. It is called by the
137    /// \c AlterationNotifier.
138    virtual void clear() {
139      invMap.clear();
140      Map::clear();
141    }
142
143    /// \brief It gives back the just readeable inverse map.
144    ///
145    /// It gives back the just readeable inverse map.
146    const InverseMap& inverse() const {
147      return invMap;
148    }
149
150
151  private:
152    InverseMap invMap;   
153  };
154
155
156 
157  /// \brief Provides a mutable, continous and unique descriptor for each
158  /// item in the graph.
159  ///
160  /// The DescriptorMap class provides a mutable, continous and immutable
161  /// mapping for each item in the graph.
162  ///
163  /// \param _Graph The graph class the \c DescriptorMap belongs to.
164  /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
165  /// UndirEdge.
166  /// \param _Map A ReadWriteMap mapping from the item type to integer.
167
168  template <
169    typename _Graph,   
170    typename _Item,
171    typename _Map = typename ItemSetTraits<_Graph, _Item>::template Map<int>
172  >
173  class DescriptorMap : protected _Map {
174
175    typedef _Item Item;
176    typedef _Map Map;
177
178  public:
179    /// The graph class of DescriptorMap.
180    typedef _Graph Graph;
181
182    /// The key type of DescriptorMap (Node, Edge, UndirEdge).
183    typedef typename _Map::Key Key;
184    /// The value type of DescriptorMap.
185    typedef typename _Map::Value Value;
186
187    typedef std::vector<Item> InverseMap;
188
189    /// \brief Constructor.
190    ///
191    /// Constructor for creating descriptor map.
192    DescriptorMap(const Graph& _graph) : Map(_graph) {
193      build();
194    }
195
196    /// \brief Add a new key to the map.
197    ///
198    /// Add a new key to the map. It is called by the
199    /// \c AlterationNotifier.
200    virtual void add(const Item& item) {
201      Map::add(item);
202      Map::set(item, invMap.size());
203      invMap.push_back(item);
204    }
205
206    /// \brief Erase the key from the map.
207    ///
208    /// Erase the key to the map. It is called by the
209    /// \c AlterationNotifier.
210    virtual void erase(const Item& item) {
211      Map::set(invMap.back(), Map::operator[](item));
212      invMap[Map::operator[](item)] = invMap.back();
213      Map::erase(item);
214    }
215
216    /// \brief Build the unique map.
217    ///
218    /// Build the unique map. It is called by the
219    /// \c AlterationNotifier.
220    virtual void build() {
221      Map::build();
222      Item it;
223      const Graph* graph = Map::getGraph();
224      for (graph->first(it); it != INVALID; graph->next(it)) {
225        Map::set(it, invMap.size());
226        invMap.push_back(it);   
227      }     
228    }
229   
230    /// \brief Clear the keys from the map.
231    ///
232    /// Clear the keys from the map. It is called by the
233    /// \c AlterationNotifier.
234    virtual void clear() {
235      invMap.clear();
236      Map::clear();
237    }
238
239    /// \brief Gives back the \e descriptor of the item.
240    ///
241    /// Gives back the mutable and unique \e descriptor of the map.
242    int operator[](const Item& item) const {
243      return Map::operator[](item);
244    }
245   
246    /// \brief Gives back the inverse of the map.
247    ///
248    /// Gives back the inverse of the map.
249    const InverseMap inverse() const {
250      return invMap;
251    }
252
253  private:
254    std::vector<Item> invMap;
255  };
256 
257  /// Provides an immutable and unique id for each item in the graph.
258
259  /// The IdMap class provides an unique and immutable mapping for each item
260  /// in the graph.
261  ///
262  template <typename _Graph, typename _Item>
263  class IdMap {
264  public:
265    typedef _Graph Graph;
266    typedef int Value;
267    typedef _Item Item;
268    typedef _Item Key;
269
270    /// \brief The class represents the inverse of the map.
271    ///
272    /// The class represents the inverse of the map.
273    /// \see inverse()
274    class InverseMap {
275    public:
276      /// \brief Constructor.
277      ///
278      /// Constructor for creating an id-to-item map.
279      InverseMap(const Graph& _graph) : graph(&_graph) {}
280      /// \brief Gives back the given item from its id.
281      ///
282      /// Gives back the given item from its id.
283      ///
284      Item operator[](int id) const { return graph->fromId(id, Item());}
285    private:
286      const Graph* graph;
287    };
288
289    /// \brief Constructor.
290    ///
291    /// Constructor for creating id map.
292    IdMap(const Graph& _graph) : graph(&_graph) {}
293
294    /// \brief Gives back the \e id of the item.
295    ///
296    /// Gives back the immutable and unique \e id of the map.
297    int operator[](const Item& item) const { return graph->id(item);}
298
299    /// \brief Gives back the inverse of the map.
300    ///
301    /// Gives back the inverse of the map.
302    InverseMap inverse() const { return InverseMap(*graph);}
303
304  private:
305    const Graph* graph;
306
307  };
308
309}
310
311#endif
Note: See TracBrowser for help on using the repository browser.