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