1 | /* -*- C++ -*- |
---|
2 | * lemon/iterable_maps.h - Part of LEMON, a generic C++ optimization library |
---|
3 | * |
---|
4 | * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
---|
5 | * (Egervary Research Group on Combinatorial Optimization, 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 | #include <vector> |
---|
18 | #include <limits> |
---|
19 | |
---|
20 | ///\ingroup maps |
---|
21 | ///\file |
---|
22 | ///\brief Maps that makes it possible to iterate through the keys having |
---|
23 | ///a certain value |
---|
24 | /// |
---|
25 | /// |
---|
26 | |
---|
27 | |
---|
28 | namespace lemon { |
---|
29 | |
---|
30 | ///\todo This is only a static map! |
---|
31 | ///\param BaseMap is an interger map. |
---|
32 | template<class BaseMap> |
---|
33 | class IterableBoolMap |
---|
34 | { |
---|
35 | public: |
---|
36 | |
---|
37 | typedef typename BaseMap::Key Key; |
---|
38 | typedef bool Value; |
---|
39 | |
---|
40 | friend class RefType; |
---|
41 | friend class FalseIt; |
---|
42 | friend class TrueIt; |
---|
43 | |
---|
44 | private: |
---|
45 | BaseMap &cref; |
---|
46 | std::vector<Key> vals; |
---|
47 | int sep; //map[e] is true <=> cref[e]>=sep |
---|
48 | |
---|
49 | bool isTrue(Key k) {return cref[k]>=sep;} |
---|
50 | void swap(Key k, int s) |
---|
51 | { |
---|
52 | int ti=cref[k]; |
---|
53 | Key tk=vals[s]; |
---|
54 | cref[k]=s; vals[s]=k; |
---|
55 | cref[tk]=ti; vals[ti]=tk; |
---|
56 | } |
---|
57 | |
---|
58 | void setTrue(Key k) { if(cref[k]<sep) { sep--; swap(k,sep); } } |
---|
59 | void setFalse(Key k) { if(cref[k]>=sep) { swap(k,sep); sep++; } } |
---|
60 | |
---|
61 | public: |
---|
62 | ///\e |
---|
63 | void set(Key k,Value v) { if(v) setTrue(k); else setFalse(k);} |
---|
64 | |
---|
65 | ///\e |
---|
66 | class FalseIt |
---|
67 | { |
---|
68 | const IterableBoolMap &M; |
---|
69 | int i; |
---|
70 | public: |
---|
71 | explicit FalseIt(const IterableBoolMap &_M) : M(_M), i(0) { } |
---|
72 | FalseIt(Invalid) |
---|
73 | : M(*((IterableBoolMap*)(0))), i(std::numeric_limits<int>::max()) { } |
---|
74 | FalseIt &operator++() { ++i; return *this;} |
---|
75 | operator Key() const { return i<M.sep ? M.vals[i] : INVALID; } |
---|
76 | bool operator !=(Invalid) const { return i<M.sep; } |
---|
77 | bool operator ==(Invalid) const { return i>=M.sep; } |
---|
78 | }; |
---|
79 | ///\e |
---|
80 | class TrueIt |
---|
81 | { |
---|
82 | const IterableBoolMap &M; |
---|
83 | int i; |
---|
84 | public: |
---|
85 | explicit TrueIt(const IterableBoolMap &_M) |
---|
86 | : M(_M), i(M.vals.size()-1) { } |
---|
87 | TrueIt(Invalid) |
---|
88 | : M(*((IterableBoolMap*)(0))), i(-1) { } |
---|
89 | TrueIt &operator++() { --i; return *this;} |
---|
90 | operator Key() const { return i>=M.sep ? M.vals[i] : INVALID; } |
---|
91 | bool operator !=(Invalid) const { return i>=M.sep; } |
---|
92 | bool operator ==(Invalid) const { return i<M.sep; } |
---|
93 | }; |
---|
94 | |
---|
95 | ///\e |
---|
96 | class RefType |
---|
97 | { |
---|
98 | IterableBoolMap &M; |
---|
99 | Key k; |
---|
100 | public: |
---|
101 | RefType(IterableBoolMap &_M,Key _k) : M(_M), k(_k) { } |
---|
102 | |
---|
103 | operator Value() const |
---|
104 | { |
---|
105 | return M.isTrue(k); |
---|
106 | } |
---|
107 | Value operator = (Value v) const { M.set(k,v); return v; } |
---|
108 | }; |
---|
109 | |
---|
110 | public: |
---|
111 | explicit IterableBoolMap(BaseMap &_m,bool init=false) : cref(_m) |
---|
112 | { |
---|
113 | sep=0; |
---|
114 | for(typename BaseMap::MapSet::iterator i=cref.mapSet().begin(); |
---|
115 | i!=cref.mapSet().end(); |
---|
116 | ++i) { |
---|
117 | i->second=sep; |
---|
118 | vals.push_back(i->first); |
---|
119 | sep++; |
---|
120 | } |
---|
121 | if(init) sep=0; |
---|
122 | } |
---|
123 | RefType operator[] (Key k) { return RefType(*this,k);} |
---|
124 | Value operator[] (Key k) const { return isTrue(k);} |
---|
125 | }; |
---|
126 | |
---|
127 | |
---|
128 | |
---|
129 | |
---|
130 | /// \addtogroup graph_maps |
---|
131 | /// @{ |
---|
132 | |
---|
133 | /// Iterable bool NodeMap |
---|
134 | |
---|
135 | /// This map can be used in the same way |
---|
136 | /// as the standard NodeMap<bool> of the |
---|
137 | /// given graph \c Graph. |
---|
138 | /// In addition, this class provides two iterators called \ref TrueIt |
---|
139 | /// and \ref FalseIt to iterate through the "true" and "false" nodes. |
---|
140 | template <class Graph> |
---|
141 | class IterableBoolNodeMap |
---|
142 | { |
---|
143 | typename Graph::NodeMap<int> cmap; |
---|
144 | |
---|
145 | public: |
---|
146 | |
---|
147 | typedef IterableBoolMap<typename Graph::NodeMap<int> > BimType; |
---|
148 | BimType imap; |
---|
149 | |
---|
150 | |
---|
151 | typedef typename BimType::RefType RefType; |
---|
152 | typedef typename Graph::Node Key; |
---|
153 | typedef bool Value; |
---|
154 | |
---|
155 | friend class FalseIt; |
---|
156 | friend class TrueIt; |
---|
157 | |
---|
158 | ///\e |
---|
159 | IterableBoolNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {} |
---|
160 | |
---|
161 | public: |
---|
162 | ///\e |
---|
163 | void set(Key k, bool v) { imap.set(k,v);} |
---|
164 | #ifdef DOXYGEN |
---|
165 | ///\e |
---|
166 | bool &operator[](Key k) { return imap[k];} |
---|
167 | ///\e |
---|
168 | const bool &operator[](Key k) const { return imap[k];} |
---|
169 | #else |
---|
170 | Value operator[](Key k) const { return imap[k];} |
---|
171 | RefType operator[](Key k) { return imap[k];} |
---|
172 | #endif |
---|
173 | ///Iterator for the "false" nodes |
---|
174 | class FalseIt : public BimType::FalseIt |
---|
175 | { |
---|
176 | public: |
---|
177 | explicit FalseIt(const IterableBoolNodeMap &m) |
---|
178 | : BimType::FalseIt(m.imap) { } |
---|
179 | FalseIt(Invalid i) : BimType::FalseIt(i) { } |
---|
180 | }; |
---|
181 | ///Iterator for the "true" nodes |
---|
182 | class TrueIt : public BimType::TrueIt |
---|
183 | { |
---|
184 | public: |
---|
185 | explicit TrueIt(const IterableBoolNodeMap &m) |
---|
186 | : BimType::TrueIt(m.imap) { } |
---|
187 | TrueIt(Invalid i) : BimType::TrueIt(i) { } |
---|
188 | }; |
---|
189 | }; |
---|
190 | |
---|
191 | /// Iterable bool EdgeMap |
---|
192 | |
---|
193 | /// This map can be used in the same way |
---|
194 | /// as the standard EdgeMap<bool> of the |
---|
195 | /// given graph \c Graph. |
---|
196 | /// In addition, this class provides two iterators called \ref TrueIt |
---|
197 | /// and \ref FalseIt to iterate through the "true" and "false" edges. |
---|
198 | template <class Graph> |
---|
199 | class IterableBoolEdgeMap |
---|
200 | { |
---|
201 | typename Graph::EdgeMap<int> cmap; |
---|
202 | |
---|
203 | public: |
---|
204 | |
---|
205 | typedef IterableBoolMap<typename Graph::EdgeMap<int> > BimType; |
---|
206 | BimType imap; |
---|
207 | |
---|
208 | |
---|
209 | typedef typename BimType::RefType RefType; |
---|
210 | typedef typename Graph::Edge Key; |
---|
211 | typedef bool Value; |
---|
212 | |
---|
213 | friend class FalseIt; |
---|
214 | friend class TrueIt; |
---|
215 | |
---|
216 | ///\e |
---|
217 | IterableBoolEdgeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {} |
---|
218 | |
---|
219 | public: |
---|
220 | ///\e |
---|
221 | void set(Key k, bool v) { imap.set(k,v);} |
---|
222 | #ifdef DOXYGEN |
---|
223 | ///\e |
---|
224 | bool &operator[](Key k) { return imap[k];} |
---|
225 | ///\e |
---|
226 | const bool &operator[](Key k) const { return imap[k];} |
---|
227 | #else |
---|
228 | Value operator[](Key k) const { return imap[k];} |
---|
229 | RefType operator[](Key k) { return imap[k];} |
---|
230 | #endif |
---|
231 | ///Iterator for the "false" edges |
---|
232 | class FalseIt : public BimType::FalseIt |
---|
233 | { |
---|
234 | public: |
---|
235 | explicit FalseIt(const IterableBoolEdgeMap &m) |
---|
236 | : BimType::FalseIt(m.imap) { } |
---|
237 | FalseIt(Invalid i) : BimType::FalseIt(i) { } |
---|
238 | }; |
---|
239 | ///Iterator for the "true" edges |
---|
240 | class TrueIt : public BimType::TrueIt |
---|
241 | { |
---|
242 | public: |
---|
243 | explicit TrueIt(const IterableBoolEdgeMap &m) |
---|
244 | : BimType::TrueIt(m.imap) { } |
---|
245 | TrueIt(Invalid i) : BimType::TrueIt(i) { } |
---|
246 | }; |
---|
247 | }; |
---|
248 | |
---|
249 | /// @} |
---|
250 | } |
---|