COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/deba/map_utils.h @ 1059:bd97feae7d90

Last change on this file since 1059:bd97feae7d90 was 1037:3eaff8d04171, checked in by Balazs Dezso, 19 years ago

graph_io under construction
This is a working version, but needs more improvments.

todo:

documention + fix the file format
improve the exception system

add some possible asserts

tutorials

File size: 3.6 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 gutils
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    /// Constructor.
53
54    /// Construct a new InversableMap for the graph.
55    ///
56    InversableMap(const Graph& graph) : Map(graph) {}
57   
58    /// The setter function of the map.
59
60    /// It sets the map and the inverse map
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  // unique, continous, mutable
99
100  template <
101    typename _Graph,   
102    typename _Item,
103    typename _ItemIt,
104    typename _Map
105  >
106  class DescriptorMap : protected _Map {
107  public:
108    typedef _Graph Graph;
109    typedef _Item Item;
110    typedef _ItemIt ItemIt;
111    typedef _Map Map;
112
113
114    typedef typename _Map::Key Key;
115    typedef typename _Map::Value Value;
116
117    typedef vector<Item> InverseMap;
118
119    DescriptorMap(const Graph& _graph) : Map(_graph) {
120      build();
121    }
122
123    virtual void add(const Item& item) {
124      Map::add(item);
125      Map::set(item, inv_map.size());
126      inv_map.push_back(item);
127    }
128
129    virtual void erase(const Item& item) {
130      Map::set(inv_map.back(), Map::operator[](item));
131      inv_map[Map::operator[](item)] = inv_map.back();
132      Map::erase(item);
133    }
134
135    virtual void build() {
136      Map::build();
137      for (ItemIt it(*Map::getGraph()); it != INVALID; ++it) {
138        Map::set(it, inv_map.size());
139        inv_map.push_back(it); 
140      }     
141    }
142   
143    virtual void clear() {
144      inv_map.clear();
145      Map::clear();
146    }
147
148    int operator[](const Item& item) const {
149      return Map::operator[](item);
150    }
151
152   
153    const InverseMap inverse() const {
154      return inv_map;
155    }
156
157  private:
158    vector<Item> inv_map;
159  };
160
161  // unique, immutable => IDMap
162 
163 
164
165}
166
Note: See TracBrowser for help on using the repository browser.