| //======================================================================= |
| // Copyright (c) Aaron Windsor 2007 |
| // |
| // Distributed under the Boost Software License, Version 1.0. (See |
| // accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| //======================================================================= |
| |
| #ifndef __FACE_ITERATORS_HPP__ |
| #define __FACE_ITERATORS_HPP__ |
| |
| #include <boost/iterator/iterator_facade.hpp> |
| #include <boost/mpl/bool.hpp> |
| #include <boost/graph/graph_traits.hpp> |
| |
| namespace boost |
| { |
| |
| //tags for defining traversal properties |
| |
| //VisitorType |
| struct lead_visitor {}; |
| struct follow_visitor {}; |
| |
| //TraversalType |
| struct single_side {}; |
| struct both_sides {}; |
| |
| //TraversalSubType |
| struct first_side {}; //for single_side |
| struct second_side {}; //for single_side |
| struct alternating {}; //for both_sides |
| |
| //Time |
| struct current_iteration {}; |
| struct previous_iteration {}; |
| |
| // Why TraversalType AND TraversalSubType? TraversalSubType is a function |
| // template parameter passed in to the constructor of the face iterator, |
| // whereas TraversalType is a class template parameter. This lets us decide |
| // at runtime whether to move along the first or second side of a bicomp (by |
| // assigning a face_iterator that has been constructed with TraversalSubType |
| // = first_side or second_side to a face_iterator variable) without any of |
| // the virtual function overhead that comes with implementing this |
| // functionality as a more structured form of type erasure. It also allows |
| // a single face_iterator to be the end iterator of two iterators traversing |
| // both sides of a bicomp. |
| |
| //ValueType is either graph_traits<Graph>::vertex_descriptor |
| //or graph_traits<Graph>::edge_descriptor |
| |
| |
| //forward declaration (defining defaults) |
| template <typename Graph, |
| typename FaceHandlesMap, |
| typename ValueType, |
| typename BicompSideToTraverse = single_side, |
| typename VisitorType = lead_visitor, |
| typename Time = current_iteration |
| > |
| class face_iterator; |
| |
| |
| |
| template <typename Graph, bool StoreEdge> |
| struct edge_storage |
| {}; |
| |
| template <typename Graph> |
| struct edge_storage <Graph, true> |
| { |
| typename graph_traits<Graph>::edge_descriptor value; |
| }; |
| |
| |
| |
| |
| //specialization for TraversalType = traverse_vertices |
| template <typename Graph, |
| typename FaceHandlesMap, |
| typename ValueType, |
| typename TraversalType, |
| typename VisitorType, |
| typename Time |
| > |
| |
| class face_iterator |
| : public boost::iterator_facade < face_iterator<Graph, |
| FaceHandlesMap, |
| ValueType, |
| TraversalType, |
| VisitorType, |
| Time |
| >, |
| ValueType, |
| boost::forward_traversal_tag, |
| ValueType |
| > |
| { |
| public: |
| |
| typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; |
| typedef typename graph_traits<Graph>::edge_descriptor edge_t; |
| typedef face_iterator |
| <Graph,FaceHandlesMap,ValueType,TraversalType,VisitorType,Time> self; |
| typedef typename FaceHandlesMap::value_type face_handle_t; |
| |
| face_iterator() : |
| m_lead(graph_traits<Graph>::null_vertex()), |
| m_follow(graph_traits<Graph>::null_vertex()) |
| {} |
| |
| template <typename TraversalSubType> |
| face_iterator(face_handle_t anchor_handle, |
| FaceHandlesMap face_handles, |
| TraversalSubType traversal_type): |
| m_follow(anchor_handle.get_anchor()), |
| m_face_handles(face_handles) |
| { |
| set_lead_dispatch(anchor_handle, traversal_type); |
| } |
| |
| template <typename TraversalSubType> |
| face_iterator(vertex_t anchor, |
| FaceHandlesMap face_handles, |
| TraversalSubType traversal_type): |
| m_follow(anchor), |
| m_face_handles(face_handles) |
| { |
| set_lead_dispatch(m_face_handles[anchor], traversal_type); |
| } |
| |
| private: |
| |
| friend class boost::iterator_core_access; |
| |
| |
| |
| |
| inline vertex_t get_first_vertex(face_handle_t anchor_handle, |
| current_iteration |
| ) |
| { |
| return anchor_handle.first_vertex(); |
| } |
| |
| inline vertex_t get_second_vertex(face_handle_t anchor_handle, |
| current_iteration |
| ) |
| { |
| return anchor_handle.second_vertex(); |
| } |
| |
| inline vertex_t get_first_vertex(face_handle_t anchor_handle, |
| previous_iteration |
| ) |
| { |
| return anchor_handle.old_first_vertex(); |
| } |
| |
| inline vertex_t get_second_vertex(face_handle_t anchor_handle, |
| previous_iteration |
| ) |
| { |
| return anchor_handle.old_second_vertex(); |
| } |
| |
| |
| |
| |
| |
| inline void set_lead_dispatch(face_handle_t anchor_handle, first_side) |
| { |
| m_lead = get_first_vertex(anchor_handle, Time()); |
| set_edge_to_first_dispatch(anchor_handle, ValueType(), Time()); |
| } |
| |
| inline void set_lead_dispatch(face_handle_t anchor_handle, second_side) |
| { |
| m_lead = get_second_vertex(anchor_handle, Time()); |
| set_edge_to_second_dispatch(anchor_handle, ValueType(), Time()); |
| } |
| |
| |
| |
| |
| |
| inline void set_edge_to_first_dispatch(face_handle_t anchor_handle, |
| edge_t, |
| current_iteration |
| ) |
| { |
| m_edge.value = anchor_handle.first_edge(); |
| } |
| |
| inline void set_edge_to_second_dispatch(face_handle_t anchor_handle, |
| edge_t, |
| current_iteration |
| ) |
| { |
| m_edge.value = anchor_handle.second_edge(); |
| } |
| |
| inline void set_edge_to_first_dispatch(face_handle_t anchor_handle, |
| edge_t, |
| previous_iteration |
| ) |
| { |
| m_edge.value = anchor_handle.old_first_edge(); |
| } |
| |
| inline void set_edge_to_second_dispatch(face_handle_t anchor_handle, |
| edge_t, |
| previous_iteration |
| ) |
| { |
| m_edge.value = anchor_handle.old_second_edge(); |
| } |
| |
| template<typename T> |
| inline void set_edge_to_first_dispatch(face_handle_t, vertex_t, T) |
| {} |
| |
| template<typename T> |
| inline void set_edge_to_second_dispatch(face_handle_t, vertex_t, T) |
| {} |
| |
| void increment() |
| { |
| face_handle_t curr_face_handle(m_face_handles[m_lead]); |
| vertex_t first = get_first_vertex(curr_face_handle, Time()); |
| vertex_t second = get_second_vertex(curr_face_handle, Time()); |
| if (first == m_follow) |
| { |
| m_follow = m_lead; |
| set_edge_to_second_dispatch(curr_face_handle, ValueType(), Time()); |
| m_lead = second; |
| } |
| else if (second == m_follow) |
| { |
| m_follow = m_lead; |
| set_edge_to_first_dispatch(curr_face_handle, ValueType(), Time()); |
| m_lead = first; |
| } |
| else |
| m_lead = m_follow = graph_traits<Graph>::null_vertex(); |
| } |
| |
| bool equal(self const& other) const |
| { |
| return m_lead == other.m_lead && m_follow == other.m_follow; |
| } |
| |
| ValueType dereference() const |
| { |
| return dereference_dispatch(VisitorType(), ValueType()); |
| } |
| |
| inline ValueType dereference_dispatch(lead_visitor, vertex_t) const |
| { return m_lead; } |
| |
| inline ValueType dereference_dispatch(follow_visitor, vertex_t) const |
| { return m_follow; } |
| |
| inline ValueType dereference_dispatch(lead_visitor, edge_t) const |
| { return m_edge.value; } |
| |
| inline ValueType dereference_dispatch(follow_visitor, edge_t) const |
| { return m_edge.value; } |
| |
| vertex_t m_lead; |
| vertex_t m_follow; |
| edge_storage<Graph, boost::is_same<ValueType, edge_t>::value > m_edge; |
| FaceHandlesMap m_face_handles; |
| }; |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| template <typename Graph, |
| typename FaceHandlesMap, |
| typename ValueType, |
| typename VisitorType, |
| typename Time |
| > |
| class face_iterator |
| <Graph, FaceHandlesMap, ValueType, both_sides, VisitorType, Time> |
| : public boost::iterator_facade< face_iterator<Graph, |
| FaceHandlesMap, |
| ValueType, |
| both_sides, |
| VisitorType, |
| Time>, |
| ValueType, |
| boost::forward_traversal_tag, |
| ValueType > |
| { |
| public: |
| |
| typedef face_iterator |
| <Graph,FaceHandlesMap,ValueType,both_sides,VisitorType,Time> self; |
| typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; |
| typedef typename FaceHandlesMap::value_type face_handle_t; |
| |
| face_iterator() {} |
| |
| face_iterator(face_handle_t anchor_handle, FaceHandlesMap face_handles): |
| first_itr(anchor_handle, face_handles, first_side()), |
| second_itr(anchor_handle, face_handles, second_side()), |
| first_is_active(true), |
| first_increment(true) |
| {} |
| |
| face_iterator(vertex_t anchor, FaceHandlesMap face_handles): |
| first_itr(face_handles[anchor], face_handles, first_side()), |
| second_itr(face_handles[anchor], face_handles, second_side()), |
| first_is_active(true), |
| first_increment(true) |
| {} |
| |
| private: |
| |
| friend class boost::iterator_core_access; |
| |
| typedef face_iterator |
| <Graph, FaceHandlesMap, ValueType, single_side, follow_visitor, Time> |
| inner_itr_t; |
| |
| void increment() |
| { |
| if (first_increment) |
| { |
| ++first_itr; |
| ++second_itr; |
| first_increment = false; |
| } |
| else if (first_is_active) |
| ++first_itr; |
| else |
| ++second_itr; |
| first_is_active = !first_is_active; |
| } |
| |
| bool equal(self const& other) const |
| { |
| //Want this iterator to be equal to the "end" iterator when at least |
| //one of the iterators has reached the root of the current bicomp. |
| //This isn't ideal, but it works. |
| |
| return (first_itr == other.first_itr || second_itr == other.second_itr); |
| } |
| |
| ValueType dereference() const |
| { |
| return first_is_active ? *first_itr : *second_itr; |
| } |
| |
| inner_itr_t first_itr; |
| inner_itr_t second_itr; |
| inner_itr_t face_end; |
| bool first_is_active; |
| bool first_increment; |
| |
| }; |
| |
| |
| } /* namespace boost */ |
| |
| |
| #endif //__FACE_ITERATORS_HPP__ |