COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/map_utils.h @ 1199:19eae67d97d5

Last change on this file since 1199:19eae67d97d5 was 1199:19eae67d97d5, checked in by Alpar Juttner, 15 years ago

Missing #ifndef-#define

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