graph/planar_detail/face_iterators.hpp

0001 //=======================================================================
0002 // Copyright (c) Aaron Windsor 2007
0003 //
0004 // Distributed under the Boost Software License, Version 1.0. (See
0005 // accompanying file LICENSE_1_0.txt or copy at
0006 // http://www.boost.org/LICENSE_1_0.txt)
0007 //=======================================================================
0008
0009 #ifndef __FACE_ITERATORS_HPP__
0010 #define __FACE_ITERATORS_HPP__
0011
0012 #include <boost/iterator/iterator_facade.hpp>
0013 #include <boost/mpl/bool.hpp>
0014 #include <boost/graph/graph_traits.hpp>
0015
0016 namespace boost
0017 {
0018
0019 // tags for defining traversal properties
0020
0021 // VisitorType
0022 struct lead_visitor
0023 {
0024 };
0025 struct follow_visitor
0026 {
0027 };
0028
0029 // TraversalType
0030 struct single_side
0031 {
0032 };
0033 struct both_sides
0034 {
0035 };
0036
0037 // TraversalSubType
0038 struct first_side
0039 {
0040 }; // for single_side
0041 struct second_side
0042 {
0043 }; // for single_side
0044 struct alternating
0045 {
0046 }; // for both_sides
0047
0048 // Time
0049 struct current_iteration
0050 {
0051 };
0052 struct previous_iteration
0053 {
0054 };
0055
0056 // Why TraversalType AND TraversalSubType? TraversalSubType is a function
0057 // template parameter passed in to the constructor of the face iterator,
0058 // whereas TraversalType is a class template parameter. This lets us decide
0059 // at runtime whether to move along the first or second side of a bicomp (by
0060 // assigning a face_iterator that has been constructed with TraversalSubType
0061 // = first_side or second_side to a face_iterator variable) without any of
0062 // the virtual function overhead that comes with implementing this
0063 // functionality as a more structured form of type erasure. It also allows
0064 // a single face_iterator to be the end iterator of two iterators traversing
0065 // both sides of a bicomp.
0066
0067 // ValueType is either graph_traits<Graph>::vertex_descriptor
0068 // or graph_traits<Graph>::edge_descriptor
0069
0070 // forward declaration (defining defaults)
0071 template < typename Graph, typename FaceHandlesMap, typename ValueType,
0072     typename BicompSideToTraverse = single_side,
0073     typename VisitorType = lead_visitor, typename Time = current_iteration >
0074 class face_iterator;
0075
0076 template < typename Graph, bool StoreEdge > struct edge_storage
0077 {
0078 };
0079
0080 template < typename Graph > struct edge_storage< Graph, true >
0081 {
0082     typename graph_traits< Graph >::edge_descriptor value;
0083 };
0084
0085 // specialization for TraversalType = traverse_vertices
0086 template < typename Graph, typename FaceHandlesMap, typename ValueType,
0087     typename TraversalType, typename VisitorType, typename Time >
0088
0089 class face_iterator : public boost::iterator_facade<
0090                           face_iterator< Graph, FaceHandlesMap, ValueType,
0091                               TraversalType, VisitorType, Time >,
0092                           ValueType, boost::forward_traversal_tag, ValueType >
0093 {
0094 public:
0095     typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
0096     typedef typename graph_traits< Graph >::edge_descriptor edge_t;
0097     typedef face_iterator< Graph, FaceHandlesMap, ValueType, TraversalType,
0098         VisitorType, Time >
0099         self;
0100     typedef typename FaceHandlesMap::value_type face_handle_t;
0101
0102     face_iterator()
0103     : m_lead(graph_traits< Graph >::null_vertex())
0104     , m_follow(graph_traits< Graph >::null_vertex())
0105     {
0106     }
0107
0108     template < typename TraversalSubType >
0109     face_iterator(face_handle_t anchor_handle, FaceHandlesMap face_handles,
0110         TraversalSubType traversal_type)
0111     : m_follow(anchor_handle.get_anchor()), m_face_handles(face_handles)
0112     {
0113         set_lead_dispatch(anchor_handle, traversal_type);
0114     }
0115
0116     template < typename TraversalSubType >
0117     face_iterator(vertex_t anchor, FaceHandlesMap face_handles,
0118         TraversalSubType traversal_type)
0119     : m_follow(anchor), m_face_handles(face_handles)
0120     {
0121         set_lead_dispatch(m_face_handles[anchor], traversal_type);
0122     }
0123
0124 private:
0125     friend class boost::iterator_core_access;
0126
0127     inline vertex_t get_first_vertex(
0128         face_handle_t anchor_handle, current_iteration)
0129     {
0130         return anchor_handle.first_vertex();
0131     }
0132
0133     inline vertex_t get_second_vertex(
0134         face_handle_t anchor_handle, current_iteration)
0135     {
0136         return anchor_handle.second_vertex();
0137     }
0138
0139     inline vertex_t get_first_vertex(
0140         face_handle_t anchor_handle, previous_iteration)
0141     {
0142         return anchor_handle.old_first_vertex();
0143     }
0144
0145     inline vertex_t get_second_vertex(
0146         face_handle_t anchor_handle, previous_iteration)
0147     {
0148         return anchor_handle.old_second_vertex();
0149     }
0150
0151     inline void set_lead_dispatch(face_handle_t anchor_handle, first_side)
0152     {
0153         m_lead = get_first_vertex(anchor_handle, Time());
0154         set_edge_to_first_dispatch(anchor_handle, ValueType(), Time());
0155     }
0156
0157     inline void set_lead_dispatch(face_handle_t anchor_handle, second_side)
0158     {
0159         m_lead = get_second_vertex(anchor_handle, Time());
0160         set_edge_to_second_dispatch(anchor_handle, ValueType(), Time());
0161     }
0162
0163     inline void set_edge_to_first_dispatch(
0164         face_handle_t anchor_handle, edge_t, current_iteration)
0165     {
0166         m_edge.value = anchor_handle.first_edge();
0167     }
0168
0169     inline void set_edge_to_second_dispatch(
0170         face_handle_t anchor_handle, edge_t, current_iteration)
0171     {
0172         m_edge.value = anchor_handle.second_edge();
0173     }
0174
0175     inline void set_edge_to_first_dispatch(
0176         face_handle_t anchor_handle, edge_t, previous_iteration)
0177     {
0178         m_edge.value = anchor_handle.old_first_edge();
0179     }
0180
0181     inline void set_edge_to_second_dispatch(
0182         face_handle_t anchor_handle, edge_t, previous_iteration)
0183     {
0184         m_edge.value = anchor_handle.old_second_edge();
0185     }
0186
0187     template < typename T >
0188     inline void set_edge_to_first_dispatch(face_handle_t, vertex_t, T)
0189     {
0190     }
0191
0192     template < typename T >
0193     inline void set_edge_to_second_dispatch(face_handle_t, vertex_t, T)
0194     {
0195     }
0196
0197     void increment()
0198     {
0199         face_handle_t curr_face_handle(m_face_handles[m_lead]);
0200         vertex_t first = get_first_vertex(curr_face_handle, Time());
0201         vertex_t second = get_second_vertex(curr_face_handle, Time());
0202         if (first == m_follow)
0203         {
0204             m_follow = m_lead;
0205             set_edge_to_second_dispatch(curr_face_handle, ValueType(), Time());
0206             m_lead = second;
0207         }
0208         else if (second == m_follow)
0209         {
0210             m_follow = m_lead;
0211             set_edge_to_first_dispatch(curr_face_handle, ValueType(), Time());
0212             m_lead = first;
0213         }
0214         else
0215             m_lead = m_follow = graph_traits< Graph >::null_vertex();
0216     }
0217
0218     bool equal(self const& other) const
0219     {
0220         return m_lead == other.m_lead && m_follow == other.m_follow;
0221     }
0222
0223     ValueType dereference() const
0224     {
0225         return dereference_dispatch(VisitorType(), ValueType());
0226     }
0227
0228     inline ValueType dereference_dispatch(lead_visitor, vertex_t) const
0229     {
0230         return m_lead;
0231     }
0232
0233     inline ValueType dereference_dispatch(follow_visitor, vertex_t) const
0234     {
0235         return m_follow;
0236     }
0237
0238     inline ValueType dereference_dispatch(lead_visitor, edge_t) const
0239     {
0240         return m_edge.value;
0241     }
0242
0243     inline ValueType dereference_dispatch(follow_visitor, edge_t) const
0244     {
0245         return m_edge.value;
0246     }
0247
0248     vertex_t m_lead;
0249     vertex_t m_follow;
0250     edge_storage< Graph, boost::is_same< ValueType, edge_t >::value > m_edge;
0251     FaceHandlesMap m_face_handles;
0252 };
0253
0254 template < typename Graph, typename FaceHandlesMap, typename ValueType,
0255     typename VisitorType, typename Time >
0256 class face_iterator< Graph, FaceHandlesMap, ValueType, both_sides, VisitorType,
0257     Time >
0258 : public boost::iterator_facade< face_iterator< Graph, FaceHandlesMap,
0259                                      ValueType, both_sides, VisitorType, Time >,
0260       ValueType, boost::forward_traversal_tag, ValueType >
0261 {
0262 public:
0263     typedef face_iterator< Graph, FaceHandlesMap, ValueType, both_sides,
0264         VisitorType, Time >
0265         self;
0266     typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
0267     typedef typename FaceHandlesMap::value_type face_handle_t;
0268
0269     face_iterator() {}
0270
0271     face_iterator(face_handle_t anchor_handle, FaceHandlesMap face_handles)
0272     : first_itr(anchor_handle, face_handles, first_side())
0273     , second_itr(anchor_handle, face_handles, second_side())
0274     , first_is_active(true)
0275     , first_increment(true)
0276     {
0277     }
0278
0279     face_iterator(vertex_t anchor, FaceHandlesMap face_handles)
0280     : first_itr(face_handles[anchor], face_handles, first_side())
0281     , second_itr(face_handles[anchor], face_handles, second_side())
0282     , first_is_active(true)
0283     , first_increment(true)
0284     {
0285     }
0286
0287 private:
0288     friend class boost::iterator_core_access;
0289
0290     typedef face_iterator< Graph, FaceHandlesMap, ValueType, single_side,
0291         follow_visitor, Time >
0292         inner_itr_t;
0293
0294     void increment()
0295     {
0296         if (first_increment)
0297         {
0298             ++first_itr;
0299             ++second_itr;
0300             first_increment = false;
0301         }
0302         else if (first_is_active)
0303             ++first_itr;
0304         else
0305             ++second_itr;
0306         first_is_active = !first_is_active;
0307     }
0308
0309     bool equal(self const& other) const
0310     {
0311         // Want this iterator to be equal to the "end" iterator when at least
0312         // one of the iterators has reached the root of the current bicomp.
0313         // This isn't ideal, but it works.
0314
0315         return (first_itr == other.first_itr || second_itr == other.second_itr);
0316     }
0317
0318     ValueType dereference() const
0319     {
0320         return first_is_active ? *first_itr : *second_itr;
0321     }
0322
0323     inner_itr_t first_itr;
0324     inner_itr_t second_itr;
0325     inner_itr_t face_end;
0326     bool first_is_active;
0327     bool first_increment;
0328 };
0329
0330 } /* namespace boost */
0331
0332 #endif //__FACE_ITERATORS_HPP__