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