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 
face_iterator()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>
face_iterator(face_handle_t anchor_handle,FaceHandlesMap face_handles,TraversalSubType traversal_type)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>
face_iterator(vertex_t anchor,FaceHandlesMap face_handles,TraversalSubType traversal_type)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 
get_first_vertex(face_handle_t anchor_handle,current_iteration)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 
get_second_vertex(face_handle_t anchor_handle,current_iteration)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 
get_first_vertex(face_handle_t anchor_handle,previous_iteration)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 
get_second_vertex(face_handle_t anchor_handle,previous_iteration)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 
set_lead_dispatch(face_handle_t anchor_handle,first_side)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 
set_lead_dispatch(face_handle_t anchor_handle,second_side)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 
set_edge_to_first_dispatch(face_handle_t anchor_handle,edge_t,current_iteration)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 
set_edge_to_second_dispatch(face_handle_t anchor_handle,edge_t,current_iteration)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 
set_edge_to_first_dispatch(face_handle_t anchor_handle,edge_t,previous_iteration)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 
set_edge_to_second_dispatch(face_handle_t anchor_handle,edge_t,previous_iteration)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>
set_edge_to_first_dispatch(face_handle_t,vertex_t,T)221     inline void set_edge_to_first_dispatch(face_handle_t, vertex_t, T)
222     {}
223 
224     template<typename T>
set_edge_to_second_dispatch(face_handle_t,vertex_t,T)225     inline void set_edge_to_second_dispatch(face_handle_t, vertex_t, T)
226     {}
227 
increment()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 
equal(self const & other) const249     bool equal(self const& other) const
250     {
251       return m_lead == other.m_lead && m_follow == other.m_follow;
252     }
253 
dereference() const254     ValueType dereference() const
255     {
256       return dereference_dispatch(VisitorType(), ValueType());
257     }
258 
dereference_dispatch(lead_visitor,vertex_t) const259     inline ValueType dereference_dispatch(lead_visitor, vertex_t) const
260     { return m_lead; }
261 
dereference_dispatch(follow_visitor,vertex_t) const262     inline ValueType dereference_dispatch(follow_visitor, vertex_t) const
263     { return m_follow; }
264 
dereference_dispatch(lead_visitor,edge_t) const265     inline ValueType dereference_dispatch(lead_visitor, edge_t) const
266     { return m_edge.value; }
267 
dereference_dispatch(follow_visitor,edge_t) const268     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 
face_iterator()310     face_iterator() {}
311 
face_iterator(face_handle_t anchor_handle,FaceHandlesMap face_handles)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 
face_iterator(vertex_t anchor,FaceHandlesMap face_handles)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 
increment()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 
equal(self const & other) const349     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 
dereference() const358     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__
376