Boost C++ Libraries

boost/graph/planar_detail/face_iterators.hpp

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