COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/deba/map_utils.h @ 1124:12623f7ecb37

Last change on this file since 1124:12623f7ecb37 was 1115:444f69240539, checked in by Balazs Dezso, 20 years ago

Some changes in the IO and map utilities.

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