26 /// |
26 /// |
27 /// |
27 /// |
28 |
28 |
29 |
29 |
30 namespace lemon { |
30 namespace lemon { |
|
31 |
|
32 ///\ingroup maps |
|
33 /// |
|
34 /// \brief Dynamic iterable bool map. |
|
35 /// |
|
36 /// This class provides a special graph map type which can store |
|
37 /// for each graph item(node, edge, etc.) a bool value. For both |
|
38 /// the true and the false it is possible to iterate on the keys which |
|
39 /// mapped to the given value. |
|
40 /// |
|
41 /// \param _Graph The graph type. |
|
42 /// \param _Item One of the graph's item type, the key of the map. |
|
43 template <typename _Graph, typename _Item> |
|
44 class IterableBoolMap |
|
45 : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Parent { |
|
46 private: |
|
47 typedef _Graph Graph; |
|
48 typedef _Item Item; |
|
49 |
|
50 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt; |
|
51 typedef typename ItemSetTraits<Graph, Item> |
|
52 ::template Map<int>::Parent Parent; |
|
53 |
|
54 std::vector<Item> array; |
|
55 int sep; |
|
56 |
|
57 const Graph& graph; |
|
58 |
|
59 private: |
|
60 |
|
61 int position(const Item& item) const { |
|
62 return Parent::operator[](item); |
|
63 } |
|
64 |
|
65 public: |
|
66 |
|
67 /// Indicates that the map if reference map. |
|
68 typedef True ReferenceMapTag; |
|
69 |
|
70 /// The key type |
|
71 typedef Item Key; |
|
72 /// The value type |
|
73 typedef bool Value; |
|
74 /// The const reference type. |
|
75 typedef const Value& ConstReference; |
|
76 |
|
77 |
|
78 /// \brief Refernce to the value of the map. |
|
79 /// |
|
80 /// This class is near to similar to the bool type. It can |
|
81 /// be converted to bool and it has the same operators. |
|
82 class Reference { |
|
83 friend class IterableBoolMap; |
|
84 private: |
|
85 Reference(IterableBoolMap& map, const Key& key) |
|
86 : _key(key), _map(map) {} |
|
87 public: |
|
88 |
|
89 Reference& operator=(const Reference& value) { |
|
90 _map.set(_key, (bool)value); |
|
91 return *this; |
|
92 } |
|
93 |
|
94 operator bool() const { |
|
95 return static_cast<const IterableBoolMap&>(_map)[_key]; |
|
96 } |
|
97 |
|
98 Reference& operator=(bool value) { |
|
99 _map.set(_key, value); |
|
100 return *this; |
|
101 } |
|
102 Reference& operator&=(bool value) { |
|
103 _map.set(_key, _map[_key] & value); |
|
104 return *this; |
|
105 } |
|
106 Reference& operator|=(bool value) { |
|
107 _map.set(_key, _map[_key] | value); |
|
108 return *this; |
|
109 } |
|
110 Reference& operator^=(bool value) { |
|
111 _map.set(_key, _map[_key] ^ value); |
|
112 return *this; |
|
113 } |
|
114 private: |
|
115 Key _key; |
|
116 IterableBoolMap& _map; |
|
117 }; |
|
118 |
|
119 /// \brief Constructor of the Map with a default value. |
|
120 /// |
|
121 /// Constructor of the Map with a default value. |
|
122 IterableBoolMap(const Graph& _graph, bool def = false) |
|
123 : Parent(_graph), graph(_graph) { |
|
124 for (ItemIt it(graph); it != INVALID; ++it) { |
|
125 Parent::set(it, array.size()); |
|
126 array.push_back(it); |
|
127 } |
|
128 sep = (def ? array.size() : 0); |
|
129 } |
|
130 |
|
131 /// \brief Const subscript operator of the map. |
|
132 /// |
|
133 /// Const subscript operator of the map. |
|
134 bool operator[](const Item& item) const { |
|
135 return position(item) < sep; |
|
136 } |
|
137 |
|
138 /// \brief Subscript operator of the map. |
|
139 /// |
|
140 /// Subscript operator of the map. |
|
141 Reference operator[](const Item& item) { |
|
142 return Reference(*this, item); |
|
143 } |
|
144 |
|
145 /// \brief Set operation of the map. |
|
146 /// |
|
147 /// Set operation of the map. |
|
148 void set(const Item& item, bool value) { |
|
149 int pos = position(item); |
|
150 if (value) { |
|
151 if (pos < sep) return; |
|
152 Item tmp = array[sep]; |
|
153 array[sep] = item; |
|
154 Parent::set(item, sep); |
|
155 array[pos] = tmp; |
|
156 Parent::set(tmp, pos); |
|
157 ++sep; |
|
158 } else { |
|
159 if (pos >= sep) return; |
|
160 --sep; |
|
161 Item tmp = array[sep]; |
|
162 array[sep] = item; |
|
163 Parent::set(item, sep); |
|
164 array[pos] = tmp; |
|
165 Parent::set(tmp, pos); |
|
166 } |
|
167 } |
|
168 |
|
169 /// \brief Returns the number of the items mapped to true. |
|
170 /// |
|
171 /// Returns the number of the items mapped to true. |
|
172 int trueNum() const { |
|
173 return sep; |
|
174 } |
|
175 |
|
176 /// \brief Returns the number of the items mapped to false. |
|
177 /// |
|
178 /// Returns the number of the items mapped to false. |
|
179 int falseNum() const { |
|
180 return array.size() - sep; |
|
181 } |
|
182 |
|
183 /// \brief Iterator for the keys mapped to true. |
|
184 /// |
|
185 /// Iterator for the keys mapped to true. It works |
|
186 /// like a graph item iterator in the map, it can be converted |
|
187 /// the item type of the map, incremented with \c ++ operator, and |
|
188 /// if the iterator leave the last valid item it will be equal to |
|
189 /// \c INVALID. |
|
190 class TrueIt : public Item { |
|
191 public: |
|
192 typedef Item Parent; |
|
193 |
|
194 /// \brief Creates an iterator. |
|
195 /// |
|
196 /// Creates an iterator. It iterates on the |
|
197 /// keys which mapped to true. |
|
198 /// \param map The IterableIntMap |
|
199 TrueIt(const IterableBoolMap& _map) |
|
200 : Parent(_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID), |
|
201 map(&_map) {} |
|
202 |
|
203 /// \brief Invalid constructor \& conversion. |
|
204 /// |
|
205 /// This constructor initializes the item to be invalid. |
|
206 /// \sa Invalid for more details. |
|
207 TrueIt(Invalid) : Parent(INVALID), map(0) {} |
|
208 |
|
209 /// \brief Increment operator. |
|
210 /// |
|
211 /// Increment Operator. |
|
212 TrueIt& operator++() { |
|
213 int pos = map->position(*this); |
|
214 Parent::operator=(pos > 0 ? map->array[pos - 1] : INVALID); |
|
215 return *this; |
|
216 } |
|
217 |
|
218 |
|
219 private: |
|
220 const IterableBoolMap* map; |
|
221 }; |
|
222 |
|
223 /// \brief Iterator for the keys mapped to false. |
|
224 /// |
|
225 /// Iterator for the keys mapped to false. It works |
|
226 /// like a graph item iterator in the map, it can be converted |
|
227 /// the item type of the map, incremented with \c ++ operator, and |
|
228 /// if the iterator leave the last valid item it will be equal to |
|
229 /// \c INVALID. |
|
230 class FalseIt : public Item { |
|
231 public: |
|
232 typedef Item Parent; |
|
233 |
|
234 /// \brief Creates an iterator. |
|
235 /// |
|
236 /// Creates an iterator. It iterates on the |
|
237 /// keys which mapped to false. |
|
238 /// \param map The IterableIntMap |
|
239 FalseIt(const IterableBoolMap& _map) |
|
240 : Parent(_map.sep < _map.array.size() ? _map.array.back() : INVALID), |
|
241 map(&_map) {} |
|
242 |
|
243 /// \brief Invalid constructor \& conversion. |
|
244 /// |
|
245 /// This constructor initializes the item to be invalid. |
|
246 /// \sa Invalid for more details. |
|
247 FalseIt(Invalid) : Parent(INVALID), map(0) {} |
|
248 |
|
249 /// \brief Increment operator. |
|
250 /// |
|
251 /// Increment Operator. |
|
252 FalseIt& operator++() { |
|
253 int pos = map->position(*this); |
|
254 Parent::operator=(pos > map->sep ? map->array[pos - 1] : INVALID); |
|
255 return *this; |
|
256 } |
|
257 |
|
258 private: |
|
259 const IterableBoolMap* map; |
|
260 }; |
|
261 |
|
262 protected: |
|
263 |
|
264 virtual void add(const Item& item) { |
|
265 Parent::add(item); |
|
266 Parent::set(item, array.size()); |
|
267 array.push_back(item); |
|
268 } |
|
269 |
|
270 virtual void add(const std::vector<Item>& items) { |
|
271 Parent::add(items); |
|
272 for (int i = 0; i < (int)items.size(); ++i) { |
|
273 Parent::set(items[i], array.size()); |
|
274 array.push_back(items[i]); |
|
275 } |
|
276 } |
|
277 |
|
278 virtual void erase(const Item& item) { |
|
279 int pos = position(item); |
|
280 if (pos < sep) { |
|
281 --sep; |
|
282 Parent::set(array[sep], pos); |
|
283 array[pos] = array[sep]; |
|
284 Parent::set(array.back(), sep); |
|
285 array[sep] = array.back(); |
|
286 array.pop_back(); |
|
287 } else { |
|
288 Parent::set(array.back(), pos); |
|
289 array[pos] = array.back(); |
|
290 array.pop_back(); |
|
291 } |
|
292 Parent::erase(item); |
|
293 } |
|
294 |
|
295 virtual void erase(const std::vector<Item>& items) { |
|
296 for (int i = 0; i < (int)items.size(); ++i) { |
|
297 int pos = position(items[i]); |
|
298 if (pos < sep) { |
|
299 --sep; |
|
300 Parent::set(array[sep], pos); |
|
301 array[pos] = array[sep]; |
|
302 Parent::set(array.back(), sep); |
|
303 array[sep] = array.back(); |
|
304 array.pop_back(); |
|
305 } else { |
|
306 Parent::set(array.back(), pos); |
|
307 array[pos] = array.back(); |
|
308 array.pop_back(); |
|
309 } |
|
310 } |
|
311 Parent::erase(items); |
|
312 } |
|
313 |
|
314 virtual void build() { |
|
315 Parent::build(); |
|
316 for (ItemIt it(graph); it != INVALID; ++it) { |
|
317 Parent::set(it, array.size()); |
|
318 array.push_back(it); |
|
319 } |
|
320 sep = 0; |
|
321 } |
|
322 |
|
323 virtual void clear() { |
|
324 array.clear(); |
|
325 sep = 0; |
|
326 Parent::clear(); |
|
327 } |
|
328 |
|
329 }; |
31 |
330 |
32 ///\todo This is only a static map! |
|
33 ///\todo Undocumented. |
|
34 ///\param BaseMap is an interger map. |
|
35 template<class BaseMap> |
|
36 class IterableBoolMap |
|
37 { |
|
38 public: |
|
39 |
|
40 typedef typename BaseMap::Key Key; |
|
41 typedef bool Value; |
|
42 |
|
43 friend class RefType; |
|
44 friend class FalseIt; |
|
45 friend class TrueIt; |
|
46 |
|
47 private: |
|
48 BaseMap &cref; |
|
49 std::vector<Key> vals; |
|
50 int sep; //map[e] is true <=> cref[e]>=sep |
|
51 |
|
52 bool isTrue(Key k) {return cref[k]>=sep;} |
|
53 void swap(Key k, int s) |
|
54 { |
|
55 int ti=cref[k]; |
|
56 Key tk=vals[s]; |
|
57 cref[k]=s; vals[s]=k; |
|
58 cref[tk]=ti; vals[ti]=tk; |
|
59 } |
|
60 |
|
61 void setTrue(Key k) { if(cref[k]<sep) { sep--; swap(k,sep); } } |
|
62 void setFalse(Key k) { if(cref[k]>=sep) { swap(k,sep); sep++; } } |
|
63 |
|
64 public: |
|
65 ///\e |
|
66 void set(Key k,Value v) { if(v) setTrue(k); else setFalse(k);} |
|
67 ///Number of \c true items in the map |
|
68 |
|
69 ///Returns the number of \c true values in the map. |
|
70 ///This is a constant time operation. |
|
71 int countTrue() { return vals.size()-sep; } |
|
72 ///Number of \c false items in the map |
|
73 |
|
74 ///Returns the number of \c false values in the map. |
|
75 ///This is a constant time operation. |
|
76 int countFalse() { return sep; } |
|
77 |
|
78 ///\e |
|
79 class FalseIt |
|
80 { |
|
81 const IterableBoolMap &M; |
|
82 int i; |
|
83 public: |
|
84 ///\e |
|
85 explicit FalseIt(const IterableBoolMap &_M) : M(_M), i(0) { } |
|
86 ///\e |
|
87 FalseIt(Invalid) |
|
88 : M(*((IterableBoolMap*)(0))), i(std::numeric_limits<int>::max()) { } |
|
89 ///\e |
|
90 FalseIt &operator++() { ++i; return *this;} |
|
91 ///\e |
|
92 operator Key() const { return i<M.sep ? M.vals[i] : INVALID; } |
|
93 ///\e |
|
94 bool operator !=(Invalid) const { return i<M.sep; } |
|
95 ///\e |
|
96 bool operator ==(Invalid) const { return i>=M.sep; } |
|
97 }; |
|
98 ///\e |
|
99 class TrueIt |
|
100 { |
|
101 const IterableBoolMap &M; |
|
102 int i; |
|
103 public: |
|
104 ///\e |
|
105 explicit TrueIt(const IterableBoolMap &_M) |
|
106 : M(_M), i(M.vals.size()-1) { } |
|
107 ///\e |
|
108 TrueIt(Invalid) |
|
109 : M(*((IterableBoolMap*)(0))), i(-1) { } |
|
110 ///\e |
|
111 TrueIt &operator++() { --i; return *this;} |
|
112 ///\e |
|
113 operator Key() const { return i>=M.sep ? M.vals[i] : INVALID; } |
|
114 ///\e |
|
115 bool operator !=(Invalid) const { return i>=M.sep; } |
|
116 ///\e |
|
117 bool operator ==(Invalid) const { return i<M.sep; } |
|
118 }; |
|
119 |
|
120 ///\e |
|
121 class RefType |
|
122 { |
|
123 IterableBoolMap &M; |
|
124 Key k; |
|
125 public: |
|
126 RefType(IterableBoolMap &_M,Key _k) : M(_M), k(_k) { } |
|
127 |
|
128 operator Value() const |
|
129 { |
|
130 return M.isTrue(k); |
|
131 } |
|
132 Value operator = (Value v) const { M.set(k,v); return v; } |
|
133 }; |
|
134 |
|
135 public: |
|
136 explicit IterableBoolMap(BaseMap &_m,bool init=false) : cref(_m) |
|
137 { |
|
138 sep=0; |
|
139 for(typename BaseMap::MapIt i(cref);i!=INVALID; ++i) { |
|
140 i.set(sep); |
|
141 vals.push_back(i); |
|
142 sep++; |
|
143 } |
|
144 if(init) sep=0; |
|
145 } |
|
146 ///\e |
|
147 RefType operator[] (Key k) { return RefType(*this,k);} |
|
148 ///\e |
|
149 Value operator[] (Key k) const { return isTrue(k);} |
|
150 }; |
|
151 |
|
152 |
|
153 |
|
154 |
|
155 /// \addtogroup graph_maps |
|
156 /// @{ |
|
157 |
|
158 /// Iterable bool NodeMap |
|
159 |
|
160 /// This map can be used in the same way |
|
161 /// as the standard NodeMap<bool> of the |
|
162 /// given graph \c Graph. |
|
163 /// In addition, this class provides two iterators called \ref TrueIt |
|
164 /// and \ref FalseIt to iterate through the "true" and "false" nodes. |
|
165 template <class Graph> |
|
166 class IterableBoolNodeMap |
|
167 { |
|
168 typename Graph::template NodeMap<int> cmap; |
|
169 |
|
170 public: |
|
171 |
|
172 typedef IterableBoolMap<typename Graph::template NodeMap<int> > BimType; |
|
173 BimType imap; |
|
174 |
|
175 |
|
176 typedef typename BimType::RefType RefType; |
|
177 typedef typename Graph::Node Key; |
|
178 typedef bool Value; |
|
179 |
|
180 friend class FalseIt; |
|
181 friend class TrueIt; |
|
182 |
|
183 ///\e |
|
184 IterableBoolNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {} |
|
185 |
|
186 public: |
|
187 ///\e |
|
188 void set(Key k, bool v) { imap.set(k,v);} |
|
189 ///Number of \c true items in the map |
|
190 |
|
191 ///Returns the number of \c true values in the map. |
|
192 ///This is a constant time operation. |
|
193 int countTrue() { return imap.countTrue(); } |
|
194 ///Number of \c false items in the map |
|
195 |
|
196 ///Returns the number of \c false values in the map. |
|
197 ///This is a constant time operation. |
|
198 int countFalse() { return imap.countFalse(); } |
|
199 #ifdef DOXYGEN |
|
200 ///\e |
|
201 bool &operator[](Key k) { return imap[k];} |
|
202 ///\e |
|
203 const bool &operator[](Key k) const { return imap[k];} |
|
204 #else |
|
205 Value operator[](Key k) const { return imap[k];} |
|
206 RefType operator[](Key k) { return imap[k];} |
|
207 #endif |
|
208 ///Iterator for the "false" nodes |
|
209 class FalseIt : public BimType::FalseIt |
|
210 { |
|
211 public: |
|
212 ///\e |
|
213 explicit FalseIt(const IterableBoolNodeMap &m) |
|
214 : BimType::FalseIt(m.imap) { } |
|
215 ///\e |
|
216 FalseIt(Invalid i) : BimType::FalseIt(i) { } |
|
217 }; |
|
218 ///Iterator for the "true" nodes |
|
219 class TrueIt : public BimType::TrueIt |
|
220 { |
|
221 public: |
|
222 ///\e |
|
223 explicit TrueIt(const IterableBoolNodeMap &m) |
|
224 : BimType::TrueIt(m.imap) { } |
|
225 ///\e |
|
226 TrueIt(Invalid i) : BimType::TrueIt(i) { } |
|
227 }; |
|
228 }; |
|
229 |
|
230 /// Iterable bool UpperNodeMap |
|
231 |
|
232 /// This map can be used in the same way |
|
233 /// as the standard UpperNodeMap<bool> of the |
|
234 /// given graph \c Graph. |
|
235 /// In addition, this class provides two iterators called \ref TrueIt |
|
236 /// and \ref FalseIt to iterate through the "true" and "false" nodes. |
|
237 template <class Graph> |
|
238 class IterableBoolUpperNodeMap |
|
239 { |
|
240 typename Graph::template UpperNodeMap<int> cmap; |
|
241 |
|
242 public: |
|
243 |
|
244 typedef IterableBoolMap<typename Graph::template UpperNodeMap<int> > BimType; |
|
245 BimType imap; |
|
246 |
|
247 |
|
248 typedef typename BimType::RefType RefType; |
|
249 typedef typename Graph::Node Key; |
|
250 typedef bool Value; |
|
251 |
|
252 friend class FalseIt; |
|
253 friend class TrueIt; |
|
254 |
|
255 ///\e |
|
256 IterableBoolUpperNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {} |
|
257 |
|
258 public: |
|
259 ///\e |
|
260 void set(Key k, bool v) { imap.set(k,v);} |
|
261 ///Number of \c true items in the map |
|
262 |
|
263 ///Returns the number of \c true values in the map. |
|
264 ///This is a constant time operation. |
|
265 int countTrue() { return imap.countTrue(); } |
|
266 ///Number of \c false items in the map |
|
267 |
|
268 ///Returns the number of \c false values in the map. |
|
269 ///This is a constant time operation. |
|
270 int countFalse() { return imap.countFalse(); } |
|
271 #ifdef DOXYGEN |
|
272 ///\e |
|
273 bool &operator[](Key k) { return imap[k];} |
|
274 ///\e |
|
275 const bool &operator[](Key k) const { return imap[k];} |
|
276 #else |
|
277 Value operator[](Key k) const { return imap[k];} |
|
278 RefType operator[](Key k) { return imap[k];} |
|
279 #endif |
|
280 ///Iterator for the "false" nodes |
|
281 class FalseIt : public BimType::FalseIt |
|
282 { |
|
283 public: |
|
284 ///\e |
|
285 explicit FalseIt(const IterableBoolUpperNodeMap &m) |
|
286 : BimType::FalseIt(m.imap) { } |
|
287 ///\e |
|
288 FalseIt(Invalid i) : BimType::FalseIt(i) { } |
|
289 }; |
|
290 ///Iterator for the "true" nodes |
|
291 class TrueIt : public BimType::TrueIt |
|
292 { |
|
293 public: |
|
294 ///\e |
|
295 explicit TrueIt(const IterableBoolUpperNodeMap &m) |
|
296 : BimType::TrueIt(m.imap) { } |
|
297 ///\e |
|
298 TrueIt(Invalid i) : BimType::TrueIt(i) { } |
|
299 }; |
|
300 }; |
|
301 |
|
302 /// Iterable bool LowerNodeMap |
|
303 |
|
304 /// This map can be used in the same way |
|
305 /// as the standard LowerNodeMap<bool> of the |
|
306 /// given graph \c Graph. |
|
307 /// In addition, this class provides two iterators called \ref TrueIt |
|
308 /// and \ref FalseIt to iterate through the "true" and "false" nodes. |
|
309 template <class Graph> |
|
310 class IterableBoolLowerNodeMap |
|
311 { |
|
312 typename Graph::template LowerNodeMap<int> cmap; |
|
313 |
|
314 public: |
|
315 |
|
316 typedef IterableBoolMap<typename Graph::template LowerNodeMap<int> > BimType; |
|
317 BimType imap; |
|
318 |
|
319 |
|
320 typedef typename BimType::RefType RefType; |
|
321 typedef typename Graph::Node Key; |
|
322 typedef bool Value; |
|
323 |
|
324 friend class FalseIt; |
|
325 friend class TrueIt; |
|
326 |
|
327 ///\e |
|
328 IterableBoolLowerNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {} |
|
329 |
|
330 public: |
|
331 ///\e |
|
332 void set(Key k, bool v) { imap.set(k,v);} |
|
333 ///Number of \c true items in the map |
|
334 |
|
335 ///Returns the number of \c true values in the map. |
|
336 ///This is a constant time operation. |
|
337 int countTrue() { return imap.countTrue(); } |
|
338 ///Number of \c false items in the map |
|
339 |
|
340 ///Returns the number of \c false values in the map. |
|
341 ///This is a constant time operation. |
|
342 int countFalse() { return imap.countFalse(); } |
|
343 #ifdef DOXYGEN |
|
344 ///\e |
|
345 bool &operator[](Key k) { return imap[k];} |
|
346 ///\e |
|
347 const bool &operator[](Key k) const { return imap[k];} |
|
348 #else |
|
349 Value operator[](Key k) const { return imap[k];} |
|
350 RefType operator[](Key k) { return imap[k];} |
|
351 #endif |
|
352 ///Iterator for the "false" nodes |
|
353 class FalseIt : public BimType::FalseIt |
|
354 { |
|
355 public: |
|
356 ///\e |
|
357 explicit FalseIt(const IterableBoolLowerNodeMap &m) |
|
358 : BimType::FalseIt(m.imap) { } |
|
359 ///\e |
|
360 FalseIt(Invalid i) : BimType::FalseIt(i) { } |
|
361 }; |
|
362 ///Iterator for the "true" nodes |
|
363 class TrueIt : public BimType::TrueIt |
|
364 { |
|
365 public: |
|
366 ///\e |
|
367 explicit TrueIt(const IterableBoolLowerNodeMap &m) |
|
368 : BimType::TrueIt(m.imap) { } |
|
369 ///\e |
|
370 TrueIt(Invalid i) : BimType::TrueIt(i) { } |
|
371 }; |
|
372 }; |
|
373 |
|
374 /// Iterable bool EdgeMap |
|
375 |
|
376 /// This map can be used in the same way |
|
377 /// as the standard EdgeMap<bool> of the |
|
378 /// given graph \c Graph. |
|
379 /// In addition, this class provides two iterators called \ref TrueIt |
|
380 /// and \ref FalseIt to iterate through the "true" and "false" edges. |
|
381 template <class Graph> |
|
382 class IterableBoolEdgeMap |
|
383 { |
|
384 typename Graph::template EdgeMap<int> cmap; |
|
385 |
|
386 public: |
|
387 |
|
388 typedef IterableBoolMap<typename Graph::template EdgeMap<int> > BimType; |
|
389 BimType imap; |
|
390 |
|
391 |
|
392 typedef typename BimType::RefType RefType; |
|
393 typedef typename Graph::Edge Key; |
|
394 typedef bool Value; |
|
395 |
|
396 friend class FalseIt; |
|
397 friend class TrueIt; |
|
398 |
|
399 ///\e |
|
400 IterableBoolEdgeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {} |
|
401 |
|
402 public: |
|
403 ///\e |
|
404 void set(Key k, bool v) { imap.set(k,v);} |
|
405 ///Returns the number of \c true values in the map. |
|
406 ///This is a constant time operation. |
|
407 int countTrue() { return imap.countTrue(); } |
|
408 ///Number of \c false items in the map |
|
409 |
|
410 ///Returns the number of \c false values in the map. |
|
411 ///This is a constant time operation. |
|
412 int countFalse() { return imap.countFalse(); } |
|
413 #ifdef DOXYGEN |
|
414 ///\e |
|
415 bool &operator[](Key k) { return imap[k];} |
|
416 ///\e |
|
417 const bool &operator[](Key k) const { return imap[k];} |
|
418 #else |
|
419 Value operator[](Key k) const { return imap[k];} |
|
420 RefType operator[](Key k) { return imap[k];} |
|
421 #endif |
|
422 ///Iterator for the "false" edges |
|
423 class FalseIt : public BimType::FalseIt |
|
424 { |
|
425 public: |
|
426 ///\e |
|
427 explicit FalseIt(const IterableBoolEdgeMap &m) |
|
428 : BimType::FalseIt(m.imap) { } |
|
429 ///\e |
|
430 FalseIt(Invalid i) : BimType::FalseIt(i) { } |
|
431 }; |
|
432 ///Iterator for the "true" edges |
|
433 class TrueIt : public BimType::TrueIt |
|
434 { |
|
435 public: |
|
436 ///\e |
|
437 explicit TrueIt(const IterableBoolEdgeMap &m) |
|
438 : BimType::TrueIt(m.imap) { } |
|
439 ///\e |
|
440 TrueIt(Invalid i) : BimType::TrueIt(i) { } |
|
441 }; |
|
442 }; |
|
443 |
|
444 |
331 |
445 namespace _iterable_maps_bits { |
332 namespace _iterable_maps_bits { |
446 template <typename Item> |
333 template <typename Item> |
447 struct IterableIntMapNode { |
334 struct IterableIntMapNode { |
448 IterableIntMapNode() {} |
335 IterableIntMapNode() : value(-1) {} |
449 IterableIntMapNode(int _value) : value(_value) {} |
336 IterableIntMapNode(int _value) : value(_value) {} |
450 Item prev, next; |
337 Item prev, next; |
451 int value; |
338 int value; |
452 }; |
339 }; |
453 } |
340 } |