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__