// Boost.Geometry (aka GGL, Generic Geometry Library)

// Copyright (c) 2007-2011 Barend Gehrels, Amsterdam, the Netherlands.

// Use, modification and distribution is subject to 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 BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSE_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSE_HPP


#include <cstddef>

#include <boost/range.hpp>

#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
#include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
#include <boost/geometry/core/access.hpp>
#include <boost/geometry/core/coordinate_dimension.hpp>
#include <boost/geometry/geometries/concepts/check.hpp>


#if defined(BOOST_GEOMETRY_DEBUG_INTERSECTION) || defined(BOOST_GEOMETRY_OVERLAY_REPORT_WKT)
#  include <string>
#  include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
#  include <boost/geometry/domains/gis/io/wkt/wkt.hpp>
#endif



namespace boost { namespace geometry
{


#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace overlay
{

template <typename Turn, typename Operation>
inline void debug_traverse(Turn const& turn, Operation op, std::string const& header)
{
#ifdef BOOST_GEOMETRY_DEBUG_TRAVERSE
    std::cout << header
        << " at " << op.seg_id
        << " op: " << operation_char(op.operation)
        << " vis: " << visited_char(op.visited)
        << " of:  " << operation_char(turn.operations[0].operation)
        << operation_char(turn.operations[1].operation)
        << std::endl;

    if (boost::contains(header, "Finished"))
    {
        std::cout << std::endl;
    }
#endif
}


template <typename Turns>
inline void clear_visit_info(Turns& turns)
{
    typedef typename boost::range_value<Turns>::type tp_type;

    for (typename boost::range_iterator<Turns>::type
        it = boost::begin(turns);
        it != boost::end(turns);
        ++it)
    {
        for (typename boost::range_iterator
            <
                typename tp_type::container_type
            >::type op_it = boost::begin(it->operations);
            op_it != boost::end(it->operations);
            ++op_it)
        {
            op_it->visited.clear();
        }
        it->discarded = false;
    }
}


template <typename Info, typename Turn>
inline void set_visited_for_continue(Info& info, Turn const& turn)
{
    // On "continue", set "visited" for ALL directions
    if (turn.operation == detail::overlay::operation_continue)
    {
        for (typename boost::range_iterator
            <
                typename Info::container_type
            >::type it = boost::begin(info.operations);
            it != boost::end(info.operations);
            ++it)
        {
            if (it->visited.none())
            {
                it->visited.set_visited();
            }
        }
    }
}


template
<
    bool Reverse1, bool Reverse2,
    typename GeometryOut,
    typename G1,
    typename G2,
    typename Turns,
    typename IntersectionInfo
>
inline bool assign_next_ip(G1 const& g1, G2 const& g2,
            Turns& turns,
            typename boost::range_iterator<Turns>::type& ip,
            GeometryOut& current_output,
            IntersectionInfo& info,
            segment_identifier& seg_id)
{
    info.visited.set_visited();
    set_visited_for_continue(*ip, info);

    // If there is no next IP on this segment
    if (info.enriched.next_ip_index < 0)
    {
        if (info.enriched.travels_to_vertex_index < 0 || info.enriched.travels_to_ip_index < 0) return false;

        BOOST_ASSERT(info.enriched.travels_to_vertex_index >= 0);
        BOOST_ASSERT(info.enriched.travels_to_ip_index >= 0);

        if (info.seg_id.source_index == 0)
        {
            geometry::copy_segments<Reverse1>(g1, info.seg_id,
                    info.enriched.travels_to_vertex_index,
                    current_output);
        }
        else
        {
            geometry::copy_segments<Reverse2>(g2, info.seg_id,
                    info.enriched.travels_to_vertex_index,
                    current_output);
        }
        seg_id = info.seg_id;
        ip = boost::begin(turns) + info.enriched.travels_to_ip_index;
    }
    else
    {
        ip = boost::begin(turns) + info.enriched.next_ip_index;
        seg_id = info.seg_id;
    }

    geometry::append(current_output, ip->point);
    return true;
}


inline bool select_source(operation_type operation, int source1, int source2)
{
    return (operation == operation_intersection && source1 != source2)
        || (operation == operation_union && source1 == source2)
        ;
}


template
<
    typename Turn,
    typename Iterator
>
inline bool select_next_ip(operation_type operation,
            Turn& turn,
            segment_identifier const& seg_id,
            Iterator& selected)
{
    if (turn.discarded)
    {
        return false;
    }
    bool has_tp = false;
    selected = boost::end(turn.operations);
    for (Iterator it = boost::begin(turn.operations);
        it != boost::end(turn.operations);
        ++it)
    {
        if (it->visited.started())
        {
            selected = it;
            //std::cout << " RETURN";
            return true;
        }

        // In some cases there are two alternatives.
        // For "ii", take the other one (alternate)
        //           UNLESS the other one is already visited
        // For "uu", take the same one (see above);
        // For "cc", take either one, but if there is a starting one,
        //           take that one.
        if (   (it->operation == operation_continue
                && (! has_tp || it->visited.started()
                    )
                )
            || (it->operation == operation
                && ! it->visited.finished()
                && (! has_tp
                    || select_source(operation,
                            it->seg_id.source_index, seg_id.source_index)
                    )
                )
            )
        {
            selected = it;
            debug_traverse(turn, *it, " Candidate");
            has_tp = true;
        }
    }

    if (has_tp)
    {
       debug_traverse(turn, *selected, "  Accepted");
    }


    return has_tp;
}



template
<
    typename Rings,
    typename Turns,
    typename Operation,
    typename Geometry1,
    typename Geometry2
>
inline void backtrack(std::size_t size_at_start, bool& fail,
            Rings& rings, typename boost::range_value<Rings>::type& ring,
            Turns& turns, Operation& operation,

#ifdef BOOST_GEOMETRY_OVERLAY_REPORT_WKT
            std::string const& reason,
            Geometry1 const& geometry1,
            Geometry2 const& geometry2
#else
            std::string const& reason,
            Geometry1 const& ,
            Geometry2 const&
#endif
            )
{
#ifdef BOOST_GEOMETRY_DEBUG_ENRICH
    std::cout << " REJECT " << reason << std::endl;
#endif
    fail = true;

    // Make bad output clean
    rings.resize(size_at_start);
    ring.clear();

    // Reject this as a starting point
    operation.visited.set_rejected();

    // And clear all visit info
    clear_visit_info(turns);

    /***
    int c = 0;
    for (int i = 0; i < turns.size(); i++)
    {
        for (int j = 0; j < 2; j++)
        {
            if (turns[i].operations[j].visited.rejected())
            {
                c++;
            }
        }
    }
    std::cout << "BACKTRACK (" << reason << " )"
        << " " << c << " of " << turns.size() << " rejected"
        << std::endl;
    ***/



#ifdef BOOST_GEOMETRY_OVERLAY_REPORT_WKT
    std::cout << " BT (" << reason << " )";
    std::cout
        << geometry::wkt(geometry1) << std::endl
        << geometry::wkt(geometry2) << std::endl;
#endif

}

}} // namespace detail::overlay
#endif // DOXYGEN_NO_DETAIL


/*!
    \brief Traverses through intersection points / geometries
    \ingroup overlay
 */
template
<
    bool Reverse1, bool Reverse2,
    typename Geometry1,
    typename Geometry2,
    typename Turns,
    typename Rings
>
inline void traverse(Geometry1 const& geometry1,
            Geometry2 const& geometry2,
            detail::overlay::operation_type operation,
            Turns& turns, Rings& rings)
{
    typedef typename boost::range_iterator<Turns>::type turn_iterator;
    typedef typename boost::range_value<Turns>::type turn_type;
    typedef typename boost::range_iterator
        <
            typename turn_type::container_type
        >::type turn_operation_iterator_type;

    std::size_t size_at_start = boost::size(rings);

    bool fail = false;
    do
    {
        fail = false;
        // Iterate through all unvisited points
        for (turn_iterator it = boost::begin(turns);
            ! fail && it != boost::end(turns);
            ++it)
        {
            // Skip discarded ones
            if (! (it->is_discarded() || it->blocked()))
            {
                for (turn_operation_iterator_type iit = boost::begin(it->operations);
                    ! fail && iit != boost::end(it->operations);
                    ++iit)
                {
                    if (iit->visited.none()
                        && ! iit->visited.rejected()
                        && (iit->operation == operation
                            || iit->operation == detail::overlay::operation_continue)
                        )
                    {
                        set_visited_for_continue(*it, *iit);

                        typename boost::range_value<Rings>::type current_output;
                        geometry::append(current_output, it->point);

                        turn_iterator current = it;
                        turn_operation_iterator_type current_iit = iit;
                        segment_identifier current_seg_id;

                        if (! detail::overlay::assign_next_ip<Reverse1, Reverse2>(
                                    geometry1, geometry2,
                                    turns,
                                    current, current_output,
                                    *iit, current_seg_id))
                        {
                            detail::overlay::backtrack(
                                size_at_start, fail,
                                rings, current_output, turns, *current_iit,
                                "No next IP",
                                geometry1, geometry2);
                        }

                        if (! detail::overlay::select_next_ip(
                                        operation,
                                        *current,
                                        current_seg_id,
                                        current_iit))
                        {
                            detail::overlay::backtrack(
                                size_at_start, fail,
                                rings, current_output, turns, *iit,
                                "Dead end at start",
                                geometry1, geometry2);
                        }
                        else
                        {

                            iit->visited.set_started();
                            detail::overlay::debug_traverse(*it, *iit, "-> Started");
                            detail::overlay::debug_traverse(*current, *current_iit, "Selected  ");


                            unsigned int i = 0;

                            while (current_iit != iit && ! fail)
                            {
                                if (current_iit->visited.visited())
                                {
                                    // It visits a visited node again, without passing the start node.
                                    // This makes it suspicious for endless loops
                                    detail::overlay::backtrack(
                                        size_at_start, fail,
                                        rings,  current_output, turns, *iit,
                                        "Visit again",
                                        geometry1, geometry2);
                                }
                                else
                                {


                                    // We assume clockwise polygons only, non self-intersecting, closed.
                                    // However, the input might be different, and checking validity
                                    // is up to the library user.

                                    // Therefore we make here some sanity checks. If the input
                                    // violates the assumptions, the output polygon will not be correct
                                    // but the routine will stop and output the current polygon, and
                                    // will continue with the next one.

                                    // Below three reasons to stop.
                                    detail::overlay::assign_next_ip<Reverse1, Reverse2>(
                                        geometry1, geometry2,
                                        turns, current, current_output,
                                        *current_iit, current_seg_id);

                                    if (! detail::overlay::select_next_ip(
                                                operation,
                                                *current,
                                                current_seg_id,
                                                current_iit))
                                    {
                                        // Should not occur in valid (non-self-intersecting) polygons
                                        // Should not occur in self-intersecting polygons without spikes
                                        // Might occur in polygons with spikes
                                        detail::overlay::backtrack(
                                            size_at_start, fail,
                                            rings,  current_output, turns, *iit,
                                            "Dead end",
                                            geometry1, geometry2);
                                    }
                                    detail::overlay::debug_traverse(*current, *current_iit, "Selected  ");

                                    if (i++ > 2 + 2 * turns.size())
                                    {
                                        // Sanity check: there may be never more loops
                                        // than turn points.
                                        // Turn points marked as "ii" can be visited twice.
                                        detail::overlay::backtrack(
                                            size_at_start, fail,
                                            rings,  current_output, turns, *iit,
                                            "Endless loop",
                                            geometry1, geometry2);
                                    }
                                }
                            }

                            if (! fail)
                            {
                                iit->visited.set_finished();
                                detail::overlay::debug_traverse(*current, *iit, "->Finished");
                                rings.push_back(current_output);
                            }
                        }
                    }
                }
            }
        }
    } while (fail);
}


}} // namespace boost::geometry


#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSE_HPP