1 //=======================================================================
2 // Copyright (c) Aaron Windsor 2007
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 //=======================================================================
9 #ifndef __FACE_ITERATORS_HPP__
10 #define __FACE_ITERATORS_HPP__
12 #include <boost/iterator/iterator_facade.hpp>
13 #include <boost/mpl/bool.hpp>
14 #include <boost/graph/graph_traits.hpp>
19 //tags for defining traversal properties
22 struct lead_visitor {};
23 struct follow_visitor {};
26 struct single_side {};
30 struct first_side {}; //for single_side
31 struct second_side {}; //for single_side
32 struct alternating {}; //for both_sides
35 struct current_iteration {};
36 struct previous_iteration {};
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.
49 //ValueType is either graph_traits<Graph>::vertex_descriptor
50 //or graph_traits<Graph>::edge_descriptor
53 //forward declaration (defining defaults)
54 template <typename Graph,
55 typename FaceHandlesMap,
57 typename BicompSideToTraverse = single_side,
58 typename VisitorType = lead_visitor,
59 typename Time = current_iteration
65 template <typename Graph, bool StoreEdge>
69 template <typename Graph>
70 struct edge_storage <Graph, true>
72 typename graph_traits<Graph>::edge_descriptor value;
78 //specialization for TraversalType = traverse_vertices
79 template <typename Graph,
80 typename FaceHandlesMap,
82 typename TraversalType,
88 : public boost::iterator_facade < face_iterator<Graph,
96 boost::forward_traversal_tag,
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;
109 m_lead(graph_traits<Graph>::null_vertex()),
110 m_follow(graph_traits<Graph>::null_vertex())
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)
120 set_lead_dispatch(anchor_handle, traversal_type);
123 template <typename TraversalSubType>
124 face_iterator(vertex_t anchor,
125 FaceHandlesMap face_handles,
126 TraversalSubType traversal_type):
128 m_face_handles(face_handles)
130 set_lead_dispatch(m_face_handles[anchor], traversal_type);
135 friend class boost::iterator_core_access;
140 inline vertex_t get_first_vertex(face_handle_t anchor_handle,
144 return anchor_handle.first_vertex();
147 inline vertex_t get_second_vertex(face_handle_t anchor_handle,
151 return anchor_handle.second_vertex();
154 inline vertex_t get_first_vertex(face_handle_t anchor_handle,
158 return anchor_handle.old_first_vertex();
161 inline vertex_t get_second_vertex(face_handle_t anchor_handle,
165 return anchor_handle.old_second_vertex();
172 inline void set_lead_dispatch(face_handle_t anchor_handle, first_side)
174 m_lead = get_first_vertex(anchor_handle, Time());
175 set_edge_to_first_dispatch(anchor_handle, ValueType(), Time());
178 inline void set_lead_dispatch(face_handle_t anchor_handle, second_side)
180 m_lead = get_second_vertex(anchor_handle, Time());
181 set_edge_to_second_dispatch(anchor_handle, ValueType(), Time());
188 inline void set_edge_to_first_dispatch(face_handle_t anchor_handle,
193 m_edge.value = anchor_handle.first_edge();
196 inline void set_edge_to_second_dispatch(face_handle_t anchor_handle,
201 m_edge.value = anchor_handle.second_edge();
204 inline void set_edge_to_first_dispatch(face_handle_t anchor_handle,
209 m_edge.value = anchor_handle.old_first_edge();
212 inline void set_edge_to_second_dispatch(face_handle_t anchor_handle,
217 m_edge.value = anchor_handle.old_second_edge();
221 inline void set_edge_to_first_dispatch(face_handle_t, vertex_t, T)
225 inline void set_edge_to_second_dispatch(face_handle_t, vertex_t, T)
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)
236 set_edge_to_second_dispatch(curr_face_handle, ValueType(), Time());
239 else if (second == m_follow)
242 set_edge_to_first_dispatch(curr_face_handle, ValueType(), Time());
246 m_lead = m_follow = graph_traits<Graph>::null_vertex();
249 bool equal(self const& other) const
251 return m_lead == other.m_lead && m_follow == other.m_follow;
254 ValueType dereference() const
256 return dereference_dispatch(VisitorType(), ValueType());
259 inline ValueType dereference_dispatch(lead_visitor, vertex_t) const
262 inline ValueType dereference_dispatch(follow_visitor, vertex_t) const
265 inline ValueType dereference_dispatch(lead_visitor, edge_t) const
266 { return m_edge.value; }
268 inline ValueType dereference_dispatch(follow_visitor, edge_t) const
269 { return m_edge.value; }
273 edge_storage<Graph, boost::is_same<ValueType, edge_t>::value > m_edge;
274 FaceHandlesMap m_face_handles;
285 template <typename Graph,
286 typename FaceHandlesMap,
288 typename VisitorType,
292 <Graph, FaceHandlesMap, ValueType, both_sides, VisitorType, Time>
293 : public boost::iterator_facade< face_iterator<Graph,
300 boost::forward_traversal_tag,
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;
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)
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)
328 friend class boost::iterator_core_access;
330 typedef face_iterator
331 <Graph, FaceHandlesMap, ValueType, single_side, follow_visitor, Time>
340 first_increment = false;
342 else if (first_is_active)
346 first_is_active = !first_is_active;
349 bool equal(self const& other) const
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.
355 return (first_itr == other.first_itr || second_itr == other.second_itr);
358 ValueType dereference() const
360 return first_is_active ? *first_itr : *second_itr;
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;
372 } /* namespace boost */
375 #endif //__FACE_ITERATORS_HPP__