/**********************************************************************

 *

 * GEOS - Geometry Engine Open Source

 * http://geos.osgeo.org

 *

 * Copyright (C) 2022 Paul Ramsey <pramsey@cleverelephant.ca>

 * Copyright (c) 2022 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/coverage/TPVWSimplifier.h>

#include <geos/coverage/Corner.h>

#include <geos/geom/Coordinate.h>

#include <geos/geom/CoordinateSequence.h>

#include <geos/geom/Envelope.h>

#include <geos/geom/Geometry.h>

#include <geos/geom/GeometryFactory.h>

#include <geos/geom/LineString.h>

#include <geos/geom/MultiLineString.h>

#include <geos/simplify/LinkedLine.h>

using geos::geom::Coordinate;

using geos::geom::CoordinateSequence;

using geos::geom::Envelope;

using geos::geom::Geometry;

using geos::geom::GeometryFactory;

using geos::geom::LineString;

using geos::geom::MultiLineString;

using geos::simplify::LinkedLine;

namespace geos {

namespace coverage { // geos.coverage

typedef TPVWSimplifier::Edge Edge;

typedef TPVWSimplifier::EdgeIndex EdgeIndex;

/* public static */

std::unique_ptr<MultiLineString>

TPVWSimplifier::simplify(

    const MultiLineString* lines,

    double distanceTolerance)

{

    TPVWSimplifier simp(lines, distanceTolerance);

    std::unique_ptr<MultiLineString> result = simp.simplify();

    return result;

}

/* public static */

std::unique_ptr<MultiLineString>

TPVWSimplifier::simplify(

    const MultiLineString* p_lines,

    std::vector<bool>& p_freeRings,

    const MultiLineString* p_constraintLines,

    double distanceTolerance)

{

    TPVWSimplifier simp(p_lines, distanceTolerance);

    simp.setFreeRingIndices(p_freeRings);

    simp.setConstraints(p_constraintLines);

    std::unique_ptr<MultiLineString> result = simp.simplify();

    return result;

}

/* public */

TPVWSimplifier::TPVWSimplifier(

    const MultiLineString* lines,

    double distanceTolerance)

    : inputLines(lines)

    , areaTolerance(distanceTolerance*distanceTolerance)

    , geomFactory(inputLines->getFactory())

    , constraintLines(nullptr)

    {}

/* private */

void

TPVWSimplifier::setConstraints(const MultiLineString* constraints)

{

    constraintLines = constraints;

}

/* public */

void

TPVWSimplifier::setFreeRingIndices(std::vector<bool>& freeRing)

{

    //XXX Assert: bit set has same size as number of lines.

    isFreeRing = freeRing;

}

/* private */

std::unique_ptr<MultiLineString>

TPVWSimplifier::simplify()

{

    std::vector<bool> emptyList;

    std::vector<Edge> edges = createEdges(inputLines, isFreeRing);

    std::vector<Edge> constraintEdges = createEdges(constraintLines, emptyList);

    EdgeIndex edgeIndex;

    edgeIndex.add(edges);

    edgeIndex.add(constraintEdges);

    std::vector<std::unique_ptr<LineString>> result;

    for (auto& edge : edges) {

        std::unique_ptr<CoordinateSequence> ptsSimp = edge.simplify(edgeIndex);

        auto ls = geomFactory->createLineString(std::move(ptsSimp));

        result.emplace_back(ls.release());

    }

    return geomFactory->createMultiLineString(std::move(result));

}

/* private */

std::vector<Edge>

TPVWSimplifier::createEdges(

    const MultiLineString* lines,

    std::vector<bool>& freeRing)

{

    std::vector<Edge> edges;

    if (lines == nullptr)

        return edges;

    for (std::size_t i = 0; i < lines->getNumGeometries(); i++) {

        const LineString* line = lines->getGeometryN(i);

        bool isFree = freeRing.empty() ? false : freeRing[i];

        edges.emplace_back(line, isFree, areaTolerance);

    }

    return edges;

}

/************************************************************************/

TPVWSimplifier::Edge::Edge(const LineString* p_inputLine, bool p_isFreeRing, double p_areaTolerance)

    : areaTolerance(p_areaTolerance)

    , isFreeRing(p_isFreeRing)

    , envelope(p_inputLine->getEnvelopeInternal())

    , nbPts(p_inputLine->getNumPoints())

    , linkedLine(*(p_inputLine->getCoordinatesRO()))

    , vertexIndex(*(p_inputLine->getCoordinatesRO()))

    , minEdgeSize(p_inputLine->getCoordinatesRO()->isRing() ? 3 : 2)

{

    // linkedLine = new LinkedLine(pts);

    // minEdgeSize = linkedLine.isRing() ? 3 : 2;

    // vertexIndex = new VertexSequencePackedRtree(pts);

    //-- remove ring duplicate final vertex

    if (linkedLine.isRing()) {

        vertexIndex.remove(nbPts-1);

    }

}

/* private */

const Coordinate&

TPVWSimplifier::Edge::getCoordinate(std::size_t index) const

{

    return linkedLine.getCoordinate(index);

}

/* public */

const Envelope*

TPVWSimplifier::Edge::getEnvelopeInternal() const

{

    return envelope;

}

/* public */

std::size_t

TPVWSimplifier::Edge::size() const

{

    return linkedLine.size();

}

/* private */

std::unique_ptr<CoordinateSequence>

TPVWSimplifier::Edge::simplify(EdgeIndex& edgeIndex)

{

    Corner::PriorityQueue cornerQueue;

    createQueue(cornerQueue);

    while (! cornerQueue.empty() && size() > minEdgeSize) {

        //Corner corner = cornerQueue.poll();

        Corner corner = cornerQueue.top();

        cornerQueue.pop();

        //-- a corner may no longer be valid due to removal of adjacent corners

        if (corner.isRemoved())

            continue;

        //System.out.println(corner.toLineString(edge));

        //-- done when all small corners are removed

        if (corner.getArea() > areaTolerance)

            break;

        if (isRemovable(corner, edgeIndex) ) {

            removeCorner(corner, cornerQueue);

        }

    }

    return linkedLine.getCoordinates();

}

/* private */

void

TPVWSimplifier::Edge::createQueue(Corner::PriorityQueue& cornerQueue)

{

    std::size_t minIndex = (linkedLine.isRing() && isFreeRing) ? 0 : 1;

    std::size_t maxIndex = nbPts - 1;

    for (std::size_t i = minIndex; i < maxIndex; i++) {

        addCorner(i, cornerQueue);

    }

    return;

}

/* private */

void

TPVWSimplifier::Edge::addCorner(

    std::size_t i,

    Corner::PriorityQueue& cornerQueue)

{

    if (isFreeRing || (i != 0 && i != nbPts-1)) {

        Corner corner(&linkedLine, i);

        if (corner.getArea() <= areaTolerance) {

            cornerQueue.push(corner);

        }

    }

}

/* private */

bool

TPVWSimplifier::Edge::isRemovable(

    Corner& corner,

    EdgeIndex& edgeIndex) const

{

    Envelope cornerEnv = corner.envelope();

    //-- check nearby lines for violating intersections

    //-- the query also returns this line for checking

    std::vector<const Edge*> edgeHits = edgeIndex.query(cornerEnv);

    for (const Edge* edge : edgeHits) {

        if (hasIntersectingVertex(corner, cornerEnv, *edge))

            return false;

    //-- check if corner base equals line (2-pts)

    //-- if so, don't remove corner, since that would collapse to the line

        if (edge != this && edge->size() == 2) {

            // TODO xxxxxx make linkedLine coordinates local

            // to linkedline and return a reference, update

            // simplify to clone reference at final step

            auto linePts = edge->linkedLine.getCoordinates();

            if (corner.isBaseline(linePts->getAt(0), linePts->getAt(1)))

                return false;

        }

    }

    return true;

}

/* private */

bool

TPVWSimplifier::Edge::hasIntersectingVertex(

    const Corner& corner,

    const Envelope& cornerEnv,

    const Edge& edge) const

{

    std::vector<std::size_t> result = edge.query(cornerEnv);

    for (std::size_t index : result) {

        const Coordinate& v = edge.getCoordinate(index);

        // ok if corner touches another line - should only happen at endpoints

        if (corner.isVertex(v))

            continue;

        //--- does corner triangle contain vertex?

        if (corner.intersects(v))

            return true;

    }

    return false;

}

/* private */

std::vector<std::size_t>

TPVWSimplifier::Edge::query(const Envelope& cornerEnv) const

{

    std::vector<std::size_t> result;

    vertexIndex.query(cornerEnv, result);

    return result;

}

/* private */

void

TPVWSimplifier::Edge::removeCorner(

    Corner& corner,

    Corner::PriorityQueue& cornerQueue)

{

    std::size_t index = corner.getIndex();

    std::size_t prev = linkedLine.prev(index);

    std::size_t next = linkedLine.next(index);

    linkedLine.remove(index);

    vertexIndex.remove(index);

    //-- potentially add the new corners created

    addCorner(prev, cornerQueue);

    addCorner(next, cornerQueue);

}

/************************************************************************/

/* public */

void

TPVWSimplifier::EdgeIndex::add(std::vector<Edge>& edges)

{

    for (Edge& edge : edges) {

        index.insert(&edge);

    }

}

/* public */

std::vector<const Edge*>

TPVWSimplifier::EdgeIndex::query(const Envelope& queryEnv)

{

    std::vector<const Edge*> hits;

    index.query(queryEnv, hits);

    return hits;

}

} // geos.coverage

} // geos