| //======================================================================= | |
| // 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__ |