/**********************************************************************
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.osgeo.org
 *
 * Copyright (C) 2020 Paul Ramsey <pramsey@cleverelephant.ca>
 *
 * This is free software; you can redistribute and/or modify it under
 * the terms of the GNU Lesser General Public Licence as published
 * by the Free Software Foundation.
 * See the COPYING file for more information.
 *
 **********************************************************************/

#include <geos/operation/overlayng/OverlayLabeller.h>
#include <geos/operation/overlayng/OverlayEdge.h>
#include <geos/operation/overlayng/OverlayNG.h>
#include <geos/operation/overlayng/InputGeometry.h>
#include <geos/geom/Coordinate.h>
#include <geos/geom/Position.h>
#include <geos/geom/CoordinateSequence.h>
#include <geos/util/Assert.h>
#include <geos/util/TopologyException.h>

#include <sstream>


namespace geos {      // geos
namespace operation { // geos.operation
namespace overlayng { // geos.operation.overlayng


using namespace geos::geom;

/*public*/
void
OverlayLabeller::computeLabelling()
{
    std::vector<OverlayEdge*> nodes = graph->getNodeEdges();
    labelAreaNodeEdges(nodes);
    labelConnectedLinearEdges();

    //TODO: is there a way to avoid scanning all edges in these steps?
    /**
     * At this point collapsed edges labeled with location UNKNOWN
     * must be disconnected from the area edges of the parent.
     * They can be located based on their parent ring role (shell or hole).
     */
    labelCollapsedEdges();
    labelConnectedLinearEdges();

    labelDisconnectedEdges();
}


/*private*/
void
OverlayLabeller::labelAreaNodeEdges(std::vector<OverlayEdge*>& nodes)
{
    for (OverlayEdge* nodeEdge : nodes) {
        propagateAreaLocations(nodeEdge, 0);
        if (inputGeometry->hasEdges(1)) {
            propagateAreaLocations(nodeEdge, 1);
        }
    }
}

/*public*/
void
OverlayLabeller::propagateAreaLocations(OverlayEdge* nodeEdge, uint8_t geomIndex)
{
    /*
     * Only propagate for area geometries
     */
    if (!inputGeometry->isArea(geomIndex))
        return;

    /**
     * No need to propagate if node has only one edge.
     * This handles dangling edges created by overlap limiting
     */
    if (nodeEdge->degree() == 1)
        return;

    OverlayEdge* eStart = findPropagationStartEdge(nodeEdge, geomIndex);
    // no labelled edge found, so nothing to propagate
    if (eStart == nullptr)
        return;

    // initialize currLoc to location of L side
    Location currLoc = eStart->getLocation(geomIndex, Position::LEFT);
    OverlayEdge* e = eStart->oNextOE();

    do {
        OverlayLabel* label = e->getLabel();
        if (!label->isBoundary(geomIndex)) {
            /**
            * If this is not a Boundary edge for this input area,
            * its location is now known relative to this input area
            */
            label->setLocationLine(geomIndex, currLoc);
        }
        else {
            util::Assert::isTrue(label->hasSides(geomIndex));
            /**
             *  This is a boundary edge for the input area geom.
             *  Update the current location from its labels.
             *  Also check for topological consistency.
             */
            Location locRight = e->getLocation(geomIndex, Position::RIGHT);
            if (locRight != currLoc) {
                std::stringstream ss;
                ss << "side location conflict at ";
                ss << e->getCoordinate().toString();
                ss << ". This can occur if the input geometry is invalid.";
                throw util::TopologyException(ss.str());
            }
            Location locLeft = e->getLocation(geomIndex, Position::LEFT);
            if (locLeft == Location::NONE) {
                util::Assert::shouldNeverReachHere("found single null side");
            }
            currLoc = locLeft;
        }
        e = e->oNextOE();
    } while (e != eStart);
}

/*private*/
OverlayEdge*
OverlayLabeller::findPropagationStartEdge(OverlayEdge* nodeEdge, uint8_t geomIndex)
{
    OverlayEdge* eStart = nodeEdge;
    do {
        const OverlayLabel* label = eStart->getLabel();
        if (label->isBoundary(geomIndex)) {
            util::Assert::isTrue(label->hasSides(geomIndex));
            return eStart;
        }
        eStart = static_cast<OverlayEdge*>(eStart->oNext());
    } while (eStart != nodeEdge);
    return nullptr;
}

/*private*/
void
OverlayLabeller::labelCollapsedEdges()
{
    for (OverlayEdge* edge : edges) {
        if (edge->getLabel()->isLineLocationUnknown(0)) {
            labelCollapsedEdge(edge, 0);
        }
        if (edge->getLabel()->isLineLocationUnknown(1)) {
            labelCollapsedEdge(edge, 1);
        }
    }
}

/*private*/
void
OverlayLabeller::labelCollapsedEdge(OverlayEdge* edge, uint8_t geomIndex)
{
    OverlayLabel* label = edge->getLabel();
    if (! label->isCollapse(geomIndex))
        return;
    /**
    * This must be a collapsed edge which is disconnected
    * from any area edges (e.g. a fully collapsed shell or hole).
    * It can be labeled according to its parent source ring role.
    */
    label->setLocationCollapse(geomIndex);
}

/*private*/
void
OverlayLabeller::labelConnectedLinearEdges()
{
    //TODO: can these be merged to avoid two scans?
    propagateLinearLocations(0);
    if (inputGeometry->hasEdges(1)) {
        propagateLinearLocations(1);
    }
}

/*private*/
void
OverlayLabeller::propagateLinearLocations(uint8_t geomIndex)
{
    std::vector<OverlayEdge*> linearEdges = findLinearEdgesWithLocation(edges, geomIndex);
    if (linearEdges.empty()) return;

    std::deque<OverlayEdge*> edgeStack;
    edgeStack.insert(edgeStack.begin(), linearEdges.begin(), linearEdges.end());
    bool isInputLine = inputGeometry->isLine(geomIndex);
    // traverse connected linear edges, labeling unknown ones
    while (! edgeStack.empty()) {
        OverlayEdge* lineEdge = edgeStack.front();
        edgeStack.pop_front();

        // for any edges around origin with unknown location for this geomIndex,
        // add those edges to stack to continue traversal
        propagateLinearLocationAtNode(lineEdge, geomIndex, isInputLine, edgeStack);
    }
}

/*private static*/
void
OverlayLabeller::propagateLinearLocationAtNode(OverlayEdge* eNode,
                                               uint8_t geomIndex, bool isInputLine,
                                               std::deque<OverlayEdge*>& edgeStack)
{
    Location lineLoc = eNode->getLabel()->getLineLocation(geomIndex);
    /**
    * If the parent geom is a Line
    * then only propagate EXTERIOR locations.
    */
    if (isInputLine && lineLoc != Location::EXTERIOR)
        return;

    OverlayEdge* e = eNode->oNextOE();
    do {
        OverlayLabel* label = e->getLabel();
        if (label->isLineLocationUnknown(geomIndex)) {
            /**
             * If edge is not a boundary edge,
             * its location is now known for this area
             */
            label->setLocationLine(geomIndex, lineLoc);
            /**
             * Add sym edge to stack for graph traversal
             * (Don't add e itself, since e origin node has now been scanned)
             */
            edgeStack.push_front(e->symOE());
      }
      e = e->oNextOE();
    }
    while (e != eNode);
}

/*private static*/
std::vector<OverlayEdge*>
OverlayLabeller::findLinearEdgesWithLocation(const std::vector<OverlayEdge*>& edges, uint8_t geomIndex)
{
    std::vector<OverlayEdge*> linearEdges;
    for (OverlayEdge* edge : edges) {
        OverlayLabel* lbl = edge->getLabel();
        // keep if linear with known location
        if (lbl->isLinear(geomIndex) && !lbl->isLineLocationUnknown(geomIndex)) {
            linearEdges.push_back(edge);
        }
    }
    return linearEdges;
}

/*private*/
void
OverlayLabeller::labelDisconnectedEdges()
{
    for (OverlayEdge* edge : edges) {
        if (edge->getLabel()->isLineLocationUnknown(0)) {
            labelDisconnectedEdge(edge, 0);
        }
        if (edge->getLabel()->isLineLocationUnknown(1)) {
            labelDisconnectedEdge(edge, 1);
        }
    }
}

/*private*/
void
OverlayLabeller::labelDisconnectedEdge(OverlayEdge* edge, uint8_t geomIndex)
{
    OverlayLabel* label = edge->getLabel();

    /**
    * if target geom is not an area then
    * edge must be EXTERIOR, since to be
    * INTERIOR it would have been labelled
    * when it was created.
    */
    if (!inputGeometry->isArea(geomIndex)) {
        label->setLocationAll(geomIndex, Location::EXTERIOR);
        return;
    }

    /**
    * Locate edge in input area using a Point-In-Poly check.
    * This should be safe even with precision reduction,
    * because since the edge has remained disconnected
    * its interior-exterior relationship
    * can be determined relative to the original input geometry.
    */
    Location edgeLoc = locateEdgeBothEnds(geomIndex, edge);
    label->setLocationAll(geomIndex, edgeLoc);
}

/*private*/
Location
OverlayLabeller::locateEdge(uint8_t geomIndex, OverlayEdge* edge)
{
    Location loc = inputGeometry->locatePointInArea(geomIndex, edge->orig());
    Location edgeLoc = loc != Location::EXTERIOR ? Location::INTERIOR : Location::EXTERIOR;
    return edgeLoc;
}

/*private*/
Location
OverlayLabeller::locateEdgeBothEnds(uint8_t geomIndex, OverlayEdge* edge)
{
    /*
    * To improve the robustness of the point location,
    * check both ends of the edge.
    * Edge is only labelled INTERIOR if both ends are.
    */
    Location locOrig = inputGeometry->locatePointInArea(geomIndex, edge->orig());
    Location locDest = inputGeometry->locatePointInArea(geomIndex, edge->dest());
    bool isInt = locOrig != Location::EXTERIOR && locDest != Location::EXTERIOR;
    Location edgeLoc = isInt ? Location::INTERIOR : Location::EXTERIOR;
    return edgeLoc;
}

/*public*/
void
OverlayLabeller::markResultAreaEdges(int overlayOpCode)
{
    for (OverlayEdge* edge : edges) {
        markInResultArea(edge, overlayOpCode);
    }
}

/*public*/
void
OverlayLabeller::markInResultArea(OverlayEdge* e, int overlayOpCode)
{
    const OverlayLabel* label = e->getLabel();
    if (label->isBoundaryEither() && OverlayNG::isResultOfOp(overlayOpCode,
        label->getLocationBoundaryOrLine(0, Position::RIGHT, e->isForward()),
        label->getLocationBoundaryOrLine(1, Position::RIGHT, e->isForward())))
    {
        e->markInResultArea();
    }
}

/*public*/
void
OverlayLabeller::unmarkDuplicateEdgesFromResultArea()
{
    for (OverlayEdge* edge : edges) {
        if (edge->isInResultAreaBoth()) {
            edge->unmarkFromResultAreaBoth();
        }
    }
}






} // namespace geos.operation.overlayng
} // namespace geos.operation
} // namespace geos