//=======================================================================

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

