]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | //======================================================================= |
2 | // Copyright (c) Aaron Windsor 2007 | |
3 | // | |
4 | // Distributed under the Boost Software License, Version 1.0. (See | |
5 | // accompanying file LICENSE_1_0.txt or copy at | |
6 | // http://www.boost.org/LICENSE_1_0.txt) | |
7 | //======================================================================= | |
8 | ||
9 | #ifndef __FACE_ITERATORS_HPP__ | |
10 | #define __FACE_ITERATORS_HPP__ | |
11 | ||
12 | #include <boost/iterator/iterator_facade.hpp> | |
13 | #include <boost/mpl/bool.hpp> | |
14 | #include <boost/graph/graph_traits.hpp> | |
15 | ||
16 | namespace boost | |
17 | { | |
18 | ||
19 | //tags for defining traversal properties | |
20 | ||
21 | //VisitorType | |
22 | struct lead_visitor {}; | |
23 | struct follow_visitor {}; | |
24 | ||
25 | //TraversalType | |
26 | struct single_side {}; | |
27 | struct both_sides {}; | |
28 | ||
29 | //TraversalSubType | |
30 | struct first_side {}; //for single_side | |
31 | struct second_side {}; //for single_side | |
32 | struct alternating {}; //for both_sides | |
33 | ||
34 | //Time | |
35 | struct current_iteration {}; | |
36 | struct previous_iteration {}; | |
37 | ||
38 | // Why TraversalType AND TraversalSubType? TraversalSubType is a function | |
39 | // template parameter passed in to the constructor of the face iterator, | |
40 | // whereas TraversalType is a class template parameter. This lets us decide | |
41 | // at runtime whether to move along the first or second side of a bicomp (by | |
42 | // assigning a face_iterator that has been constructed with TraversalSubType | |
43 | // = first_side or second_side to a face_iterator variable) without any of | |
44 | // the virtual function overhead that comes with implementing this | |
45 | // functionality as a more structured form of type erasure. It also allows | |
46 | // a single face_iterator to be the end iterator of two iterators traversing | |
47 | // both sides of a bicomp. | |
48 | ||
49 | //ValueType is either graph_traits<Graph>::vertex_descriptor | |
50 | //or graph_traits<Graph>::edge_descriptor | |
51 | ||
52 | ||
53 | //forward declaration (defining defaults) | |
54 | template <typename Graph, | |
55 | typename FaceHandlesMap, | |
56 | typename ValueType, | |
57 | typename BicompSideToTraverse = single_side, | |
58 | typename VisitorType = lead_visitor, | |
59 | typename Time = current_iteration | |
60 | > | |
61 | class face_iterator; | |
62 | ||
63 | ||
64 | ||
65 | template <typename Graph, bool StoreEdge> | |
66 | struct edge_storage | |
67 | {}; | |
68 | ||
69 | template <typename Graph> | |
70 | struct edge_storage <Graph, true> | |
71 | { | |
72 | typename graph_traits<Graph>::edge_descriptor value; | |
73 | }; | |
74 | ||
75 | ||
76 | ||
77 | ||
78 | //specialization for TraversalType = traverse_vertices | |
79 | template <typename Graph, | |
80 | typename FaceHandlesMap, | |
81 | typename ValueType, | |
82 | typename TraversalType, | |
83 | typename VisitorType, | |
84 | typename Time | |
85 | > | |
86 | ||
87 | class face_iterator | |
88 | : public boost::iterator_facade < face_iterator<Graph, | |
89 | FaceHandlesMap, | |
90 | ValueType, | |
91 | TraversalType, | |
92 | VisitorType, | |
93 | Time | |
94 | >, | |
95 | ValueType, | |
96 | boost::forward_traversal_tag, | |
97 | ValueType | |
98 | > | |
99 | { | |
100 | public: | |
101 | ||
102 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; | |
103 | typedef typename graph_traits<Graph>::edge_descriptor edge_t; | |
104 | typedef face_iterator | |
105 | <Graph,FaceHandlesMap,ValueType,TraversalType,VisitorType,Time> self; | |
106 | typedef typename FaceHandlesMap::value_type face_handle_t; | |
107 | ||
108 | face_iterator() : | |
109 | m_lead(graph_traits<Graph>::null_vertex()), | |
110 | m_follow(graph_traits<Graph>::null_vertex()) | |
111 | {} | |
112 | ||
113 | template <typename TraversalSubType> | |
114 | face_iterator(face_handle_t anchor_handle, | |
115 | FaceHandlesMap face_handles, | |
116 | TraversalSubType traversal_type): | |
117 | m_follow(anchor_handle.get_anchor()), | |
118 | m_face_handles(face_handles) | |
119 | { | |
120 | set_lead_dispatch(anchor_handle, traversal_type); | |
121 | } | |
122 | ||
123 | template <typename TraversalSubType> | |
124 | face_iterator(vertex_t anchor, | |
125 | FaceHandlesMap face_handles, | |
126 | TraversalSubType traversal_type): | |
127 | m_follow(anchor), | |
128 | m_face_handles(face_handles) | |
129 | { | |
130 | set_lead_dispatch(m_face_handles[anchor], traversal_type); | |
131 | } | |
132 | ||
133 | private: | |
134 | ||
135 | friend class boost::iterator_core_access; | |
136 | ||
137 | ||
138 | ||
139 | ||
140 | inline vertex_t get_first_vertex(face_handle_t anchor_handle, | |
141 | current_iteration | |
142 | ) | |
143 | { | |
144 | return anchor_handle.first_vertex(); | |
145 | } | |
146 | ||
147 | inline vertex_t get_second_vertex(face_handle_t anchor_handle, | |
148 | current_iteration | |
149 | ) | |
150 | { | |
151 | return anchor_handle.second_vertex(); | |
152 | } | |
153 | ||
154 | inline vertex_t get_first_vertex(face_handle_t anchor_handle, | |
155 | previous_iteration | |
156 | ) | |
157 | { | |
158 | return anchor_handle.old_first_vertex(); | |
159 | } | |
160 | ||
161 | inline vertex_t get_second_vertex(face_handle_t anchor_handle, | |
162 | previous_iteration | |
163 | ) | |
164 | { | |
165 | return anchor_handle.old_second_vertex(); | |
166 | } | |
167 | ||
168 | ||
169 | ||
170 | ||
171 | ||
172 | inline void set_lead_dispatch(face_handle_t anchor_handle, first_side) | |
173 | { | |
174 | m_lead = get_first_vertex(anchor_handle, Time()); | |
175 | set_edge_to_first_dispatch(anchor_handle, ValueType(), Time()); | |
176 | } | |
177 | ||
178 | inline void set_lead_dispatch(face_handle_t anchor_handle, second_side) | |
179 | { | |
180 | m_lead = get_second_vertex(anchor_handle, Time()); | |
181 | set_edge_to_second_dispatch(anchor_handle, ValueType(), Time()); | |
182 | } | |
183 | ||
184 | ||
185 | ||
186 | ||
187 | ||
188 | inline void set_edge_to_first_dispatch(face_handle_t anchor_handle, | |
189 | edge_t, | |
190 | current_iteration | |
191 | ) | |
192 | { | |
193 | m_edge.value = anchor_handle.first_edge(); | |
194 | } | |
195 | ||
196 | inline void set_edge_to_second_dispatch(face_handle_t anchor_handle, | |
197 | edge_t, | |
198 | current_iteration | |
199 | ) | |
200 | { | |
201 | m_edge.value = anchor_handle.second_edge(); | |
202 | } | |
203 | ||
204 | inline void set_edge_to_first_dispatch(face_handle_t anchor_handle, | |
205 | edge_t, | |
206 | previous_iteration | |
207 | ) | |
208 | { | |
209 | m_edge.value = anchor_handle.old_first_edge(); | |
210 | } | |
211 | ||
212 | inline void set_edge_to_second_dispatch(face_handle_t anchor_handle, | |
213 | edge_t, | |
214 | previous_iteration | |
215 | ) | |
216 | { | |
217 | m_edge.value = anchor_handle.old_second_edge(); | |
218 | } | |
219 | ||
220 | template<typename T> | |
221 | inline void set_edge_to_first_dispatch(face_handle_t, vertex_t, T) | |
222 | {} | |
223 | ||
224 | template<typename T> | |
225 | inline void set_edge_to_second_dispatch(face_handle_t, vertex_t, T) | |
226 | {} | |
227 | ||
228 | void increment() | |
229 | { | |
230 | face_handle_t curr_face_handle(m_face_handles[m_lead]); | |
231 | vertex_t first = get_first_vertex(curr_face_handle, Time()); | |
232 | vertex_t second = get_second_vertex(curr_face_handle, Time()); | |
233 | if (first == m_follow) | |
234 | { | |
235 | m_follow = m_lead; | |
236 | set_edge_to_second_dispatch(curr_face_handle, ValueType(), Time()); | |
237 | m_lead = second; | |
238 | } | |
239 | else if (second == m_follow) | |
240 | { | |
241 | m_follow = m_lead; | |
242 | set_edge_to_first_dispatch(curr_face_handle, ValueType(), Time()); | |
243 | m_lead = first; | |
244 | } | |
245 | else | |
246 | m_lead = m_follow = graph_traits<Graph>::null_vertex(); | |
247 | } | |
248 | ||
249 | bool equal(self const& other) const | |
250 | { | |
251 | return m_lead == other.m_lead && m_follow == other.m_follow; | |
252 | } | |
253 | ||
254 | ValueType dereference() const | |
255 | { | |
256 | return dereference_dispatch(VisitorType(), ValueType()); | |
257 | } | |
258 | ||
259 | inline ValueType dereference_dispatch(lead_visitor, vertex_t) const | |
260 | { return m_lead; } | |
261 | ||
262 | inline ValueType dereference_dispatch(follow_visitor, vertex_t) const | |
263 | { return m_follow; } | |
264 | ||
265 | inline ValueType dereference_dispatch(lead_visitor, edge_t) const | |
266 | { return m_edge.value; } | |
267 | ||
268 | inline ValueType dereference_dispatch(follow_visitor, edge_t) const | |
269 | { return m_edge.value; } | |
270 | ||
271 | vertex_t m_lead; | |
272 | vertex_t m_follow; | |
273 | edge_storage<Graph, boost::is_same<ValueType, edge_t>::value > m_edge; | |
274 | FaceHandlesMap m_face_handles; | |
275 | }; | |
276 | ||
277 | ||
278 | ||
279 | ||
280 | ||
281 | ||
282 | ||
283 | ||
284 | ||
285 | template <typename Graph, | |
286 | typename FaceHandlesMap, | |
287 | typename ValueType, | |
288 | typename VisitorType, | |
289 | typename Time | |
290 | > | |
291 | class face_iterator | |
292 | <Graph, FaceHandlesMap, ValueType, both_sides, VisitorType, Time> | |
293 | : public boost::iterator_facade< face_iterator<Graph, | |
294 | FaceHandlesMap, | |
295 | ValueType, | |
296 | both_sides, | |
297 | VisitorType, | |
298 | Time>, | |
299 | ValueType, | |
300 | boost::forward_traversal_tag, | |
301 | ValueType > | |
302 | { | |
303 | public: | |
304 | ||
305 | typedef face_iterator | |
306 | <Graph,FaceHandlesMap,ValueType,both_sides,VisitorType,Time> self; | |
307 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; | |
308 | typedef typename FaceHandlesMap::value_type face_handle_t; | |
309 | ||
310 | face_iterator() {} | |
311 | ||
312 | face_iterator(face_handle_t anchor_handle, FaceHandlesMap face_handles): | |
313 | first_itr(anchor_handle, face_handles, first_side()), | |
314 | second_itr(anchor_handle, face_handles, second_side()), | |
315 | first_is_active(true), | |
316 | first_increment(true) | |
317 | {} | |
318 | ||
319 | face_iterator(vertex_t anchor, FaceHandlesMap face_handles): | |
320 | first_itr(face_handles[anchor], face_handles, first_side()), | |
321 | second_itr(face_handles[anchor], face_handles, second_side()), | |
322 | first_is_active(true), | |
323 | first_increment(true) | |
324 | {} | |
325 | ||
326 | private: | |
327 | ||
328 | friend class boost::iterator_core_access; | |
329 | ||
330 | typedef face_iterator | |
331 | <Graph, FaceHandlesMap, ValueType, single_side, follow_visitor, Time> | |
332 | inner_itr_t; | |
333 | ||
334 | void increment() | |
335 | { | |
336 | if (first_increment) | |
337 | { | |
338 | ++first_itr; | |
339 | ++second_itr; | |
340 | first_increment = false; | |
341 | } | |
342 | else if (first_is_active) | |
343 | ++first_itr; | |
344 | else | |
345 | ++second_itr; | |
346 | first_is_active = !first_is_active; | |
347 | } | |
348 | ||
349 | bool equal(self const& other) const | |
350 | { | |
351 | //Want this iterator to be equal to the "end" iterator when at least | |
352 | //one of the iterators has reached the root of the current bicomp. | |
353 | //This isn't ideal, but it works. | |
354 | ||
355 | return (first_itr == other.first_itr || second_itr == other.second_itr); | |
356 | } | |
357 | ||
358 | ValueType dereference() const | |
359 | { | |
360 | return first_is_active ? *first_itr : *second_itr; | |
361 | } | |
362 | ||
363 | inner_itr_t first_itr; | |
364 | inner_itr_t second_itr; | |
365 | inner_itr_t face_end; | |
366 | bool first_is_active; | |
367 | bool first_increment; | |
368 | ||
369 | }; | |
370 | ||
371 | ||
372 | } /* namespace boost */ | |
373 | ||
374 | ||
375 | #endif //__FACE_ITERATORS_HPP__ |