/**********************************************************************
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.osgeo.org
 *
 * Copyright (C) 2021 Paul Ramsey <pramsey@cleverelephant.ca>
 * Copyright (C) 2021 Martin Davis
 *
 * 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/algorithm/LineIntersector.h>
#include <geos/algorithm/Orientation.h>
#include <geos/algorithm/PointLocation.h>
#include <geos/algorithm/PolygonNodeTopology.h>
#include <geos/geom/Coordinate.h>
#include <geos/geom/Geometry.h>
#include <geos/geom/LinearRing.h>
#include <geos/geom/Location.h>
#include <geos/geom/Polygon.h>
#include <geos/noding/BasicSegmentString.h>
#include <geos/noding/MCIndexNoder.h>
#include <geos/noding/SegmentString.h>
#include <geos/operation/valid/PolygonIntersectionAnalyzer.h>
#include <geos/operation/valid/PolygonRing.h>
#include <geos/operation/valid/PolygonTopologyAnalyzer.h>
#include <geos/operation/valid/RepeatedPointRemover.h>
#include <geos/util/IllegalArgumentException.h>

using namespace geos::geom;
using geos::noding::SegmentString;

namespace geos {      // geos
namespace operation { // geos.operation
namespace valid {     // geos.operation.valid


/* public */
PolygonTopologyAnalyzer::PolygonTopologyAnalyzer(const Geometry* geom, bool p_isInvertedRingValid)
    : isInvertedRingValid(p_isInvertedRingValid)
    , segInt(p_isInvertedRingValid)
    , disconnectionPt(Coordinate::getNull())
{
    if (geom->isEmpty()){
        return;
    }
    // Code copied in from analyze()
    std::vector<SegmentString*> segStrings = createSegmentStrings(geom, p_isInvertedRingValid);
    polyRings = getPolygonRings(segStrings);
    // Code copied in from analyzeIntersections()
    noding::MCIndexNoder noder;
    noder.setSegmentIntersector(&segInt);
    noder.computeNodes(&segStrings);
    if (segInt.hasDoubleTouch()) {
        disconnectionPt = segInt.getDoubleTouchLocation();
    }
}


/* public static */
CoordinateXY
PolygonTopologyAnalyzer::findSelfIntersection(const LinearRing* ring)
{
    PolygonTopologyAnalyzer ata(ring, false);
    if (ata.hasInvalidIntersection())
        return ata.getInvalidLocation();
    return Coordinate::getNull();
}

/* public static */
bool
PolygonTopologyAnalyzer::isRingNested(const LinearRing* test,
    const LinearRing* target)
{
    const CoordinateXY& p0 = test->getCoordinatesRO()->getAt<CoordinateXY>(0);
    const CoordinateSequence* targetPts = target->getCoordinatesRO();
    Location loc = algorithm::PointLocation::locateInRing(p0, *targetPts);
    if (loc == Location::EXTERIOR) return false;
    if (loc == Location::INTERIOR) return true;

    /**
     * The start point is on the boundary of the ring.
     * Use the topology at the node to check if the segment
     * is inside or outside the ring.
     */
    const CoordinateXY& p1 = findNonEqualVertex(test, p0);
    return isIncidentSegmentInRing(&p0, &p1, targetPts);
}

/* private static */
const CoordinateXY&
PolygonTopologyAnalyzer::findNonEqualVertex(const LinearRing* ring, const CoordinateXY& p)
{
    std::size_t i = 1;
    const CoordinateSequence& ringPts = *ring->getCoordinatesRO();
    const CoordinateXY* next = &(ringPts.getAt<CoordinateXY>(i));
    while (next->equals2D(p) && i < ring->getNumPoints() - 1) {
        i += 1;
        next = &(ringPts.getAt<CoordinateXY>(i));
    }
    return ringPts.getAt<CoordinateXY>(i);
}

/* private static */
bool
PolygonTopologyAnalyzer::isIncidentSegmentInRing(
    const CoordinateXY* p0, const CoordinateXY* p1,
    const CoordinateSequence* ringPts)
{
    std::size_t index = intersectingSegIndex(ringPts, p0);
    const CoordinateXY* rPrev = &findRingVertexPrev(ringPts, index, *p0);
    const CoordinateXY* rNext = &findRingVertexNext(ringPts, index, *p0);
    /**
    * If ring orientation is not normalized, flip the corner orientation
    */
    bool isInteriorOnRight = ! algorithm::Orientation::isCCW(ringPts);
    if (! isInteriorOnRight) {
        const CoordinateXY* temp = rPrev;
        rPrev = rNext;
        rNext = temp;
    }
    return algorithm::PolygonNodeTopology::isInteriorSegment(p0, rPrev, rNext, p1);
}

/* private static */
const CoordinateXY&
PolygonTopologyAnalyzer::findRingVertexPrev(const CoordinateSequence* ringPts, std::size_t index, const CoordinateXY& node)
{
    std::size_t iPrev = index;
    const CoordinateXY* prev = &(ringPts->getAt<CoordinateXY>(iPrev));
    while (prev->equals2D(node)) {
      iPrev = ringIndexPrev(ringPts, iPrev);
      prev = &(ringPts->getAt<CoordinateXY>(iPrev));
    }
    return ringPts->getAt<CoordinateXY>(iPrev);
}

/* private static */
const CoordinateXY&
PolygonTopologyAnalyzer::findRingVertexNext(const CoordinateSequence* ringPts, std::size_t index, const CoordinateXY& node)
{
    //-- safe, since index is always the start of a ring segment
    std::size_t iNext = index + 1;
    const CoordinateXY* next = &(ringPts->getAt<CoordinateXY>(iNext));
    while (next->equals2D(node)) {
      iNext = ringIndexNext(ringPts, iNext);
      next = &(ringPts->getAt<CoordinateXY>(iNext));
    }
    return ringPts->getAt<CoordinateXY>(iNext);
}

/* private static */
std::size_t
PolygonTopologyAnalyzer::ringIndexPrev(const CoordinateSequence* ringPts, std::size_t index)
{
    if (index == 0) {
        return ringPts->getSize() - 2;
    }
    return index - 1;
}

/* private static */
std::size_t
PolygonTopologyAnalyzer::ringIndexNext(const CoordinateSequence* ringPts, std::size_t index)
{
    if (index >= ringPts->getSize() - 2) {
        return 0;
    }
    return index + 1;
}

/* private static */
std::size_t
PolygonTopologyAnalyzer::intersectingSegIndex(const CoordinateSequence* ringPts,
    const CoordinateXY* pt)
{
    algorithm::LineIntersector li;
    for (std::size_t i = 0; i < ringPts->size() - 1; i++) {
      if ( algorithm::PointLocation::isOnSegment(*pt, ringPts->getAt<CoordinateXY>(i), ringPts->getAt<CoordinateXY>(i+1)) ) {
        //-- check if pt is the start point of the next segment
        if (pt->equals2D(ringPts->getAt<CoordinateXY>(i + 1))) {
          return i + 1;
        }
        return i;
      }
    }
    throw util::IllegalArgumentException("Segment vertex does not intersect ring");
}

/* public */
bool
PolygonTopologyAnalyzer::isInteriorDisconnected()
{
    /**
     * May already be set by a double-touching hole
     */
    if (!disconnectionPt.isNull()) {
        return true;
    }
    if (isInvertedRingValid) {
        checkInteriorDisconnectedBySelfTouch();
        if (!disconnectionPt.isNull()) {
            return true;
        }
    }
    checkInteriorDisconnectedByHoleCycle();
    if (!disconnectionPt.isNull()) {
        return true;
    }
    return false;
}


/* public */
void
PolygonTopologyAnalyzer::checkInteriorDisconnectedBySelfTouch()
{
    if (! polyRings.empty()) {
        const CoordinateXY* dPt = PolygonRing::findInteriorSelfNode(polyRings);
        if (dPt)
            disconnectionPt = *dPt;
    }
}


/* public */
void
PolygonTopologyAnalyzer::checkInteriorDisconnectedByHoleCycle()
{
    /**
    * PolyRings will be null for empty, no hole or LinearRing inputs
    */
    if (! polyRings.empty()) {
        const CoordinateXY* dPt = PolygonRing::findHoleCycleLocation(polyRings);
        if (dPt)
            disconnectionPt = *dPt;
    }
}


/* private static */
std::vector<SegmentString*>
PolygonTopologyAnalyzer::createSegmentStrings(const Geometry* geom, bool bIsInvertedRingValid)
{
    std::vector<SegmentString*> segStrings;
    int typeId = geom->getGeometryTypeId();
    if (typeId == GEOS_LINEARRING) {
        const LinearRing* ring = static_cast<const LinearRing*>(geom);
        segStrings.push_back(createSegString(ring, nullptr));
        return segStrings;
    }
    if (! (typeId == GEOS_POLYGON || typeId == GEOS_MULTIPOLYGON)) {
        throw util::IllegalArgumentException("Cannot process non-polygonal input");
    }
    for (std::size_t i = 0; i < geom->getNumGeometries(); i++) {
        const Polygon* poly = static_cast<const Polygon*>(geom->getGeometryN(i));
        if (poly->isEmpty()) continue;
        bool hasHoles = poly->getNumInteriorRing() > 0;

        //--- polygons with no holes do not need connected interior analysis
        PolygonRing* shellRing = nullptr;
        if (hasHoles || bIsInvertedRingValid) {
            shellRing = createPolygonRing(poly->getExteriorRing());
        }
        segStrings.push_back(createSegString(poly->getExteriorRing(), shellRing));

        for (std::size_t j = 0 ; j < poly->getNumInteriorRing(); j++) {
            const LinearRing* hole = poly->getInteriorRingN(j);
            if (hole->isEmpty()) continue;
            PolygonRing* holeRing = createPolygonRing(hole, static_cast<int>(j), shellRing);
            segStrings.push_back(createSegString(hole, holeRing));
        }
    }
    return segStrings;
}


/* private */
PolygonRing*
PolygonTopologyAnalyzer::createPolygonRing(const LinearRing* p_ring)
{
    polyRingStore.emplace_back(p_ring);
    return &(polyRingStore.back());
}


/* private */
PolygonRing*
PolygonTopologyAnalyzer::createPolygonRing(const LinearRing* p_ring, int p_index, PolygonRing* p_shell)
{
    polyRingStore.emplace_back(p_ring, p_index, p_shell);
    return &(polyRingStore.back());
}


/* private static */
std::vector<PolygonRing*>
PolygonTopologyAnalyzer::getPolygonRings(const std::vector<SegmentString*>& segStrings)
{
    std::vector<PolygonRing*> polygonRings;
    for (SegmentString* ss : segStrings) {

        PolygonRing* polyRing = const_cast<PolygonRing*>(static_cast<const PolygonRing*>(ss->getData()));
        if (polyRing != nullptr) {
            polygonRings.push_back(polyRing);
        }
    }
    return polygonRings;
}


/* private static */
SegmentString*
PolygonTopologyAnalyzer::createSegString(const LinearRing* ring, const PolygonRing* polyRing)
{
    // Let the input LinearRing retain ownership of the
    // CoordinateSequence, and pass it directly into the BasicSegmentString
    // constructor.
    CoordinateSequence* pts = const_cast<CoordinateSequence*>(ring->getCoordinatesRO());

    // Repeated points must be removed for accurate intersection detection
    // So, in this case we create a de-duped copy of the CoordinateSequence
    // and manage the lifecycle locally. This we pass on to the SegmentString
    if (pts->hasRepeatedPoints()) {
        std::unique_ptr<CoordinateSequence> newPts = RepeatedPointRemover::removeRepeatedPoints(pts);
        pts = newPts.get();
        coordSeqStore.emplace_back(newPts.release());
    }

    // Allocate the BasicSegmentString in the store and return a
    // pointer into the store. This way we don't have to track the
    // individual SegmentStrings, they just go away when the
    // PolygonTopologyAnalyzer deallocates.
    segStringStore.emplace_back(pts, polyRing);
    SegmentString* ss = static_cast<SegmentString*>(&(segStringStore.back()));
    return ss;
}


} // namespace geos.operation.valid
} // namespace geos.operation
} // namespace geos