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

 *

 * 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/MaximalEdgeRing.h>

#include <geos/operation/overlayng/OverlayEdge.h>

#include <geos/geom/Location.h>

#include <geos/geom/Coordinate.h>

#include <geos/geom/CoordinateSequence.h>

#include <geos/geom/GeometryFactory.h>

#include <geos/util/TopologyException.h>

#include <geos/algorithm/locate/IndexedPointInAreaLocator.h>

#include <geos/io/WKTWriter.h>

#include <cassert>

namespace geos {      // geos

namespace operation { // geos.operation

namespace overlayng { // geos.operation.overlayng

using namespace geos::geom;

/*public static*/

void

MaximalEdgeRing::linkResultAreaMaxRingAtNode(OverlayEdge* nodeEdge)

{

    // assertion is only valid if building a polygonal geometry (ie not a coverage)

    assert(nodeEdge->isInResultArea());

    /**

     * Since the node edge is an out-edge,

     * make it the last edge to be linked

     * by starting at the next edge.

     * The node edge cannot be an in-edge as well,

     * but the next one may be the first in-edge.

     */

    OverlayEdge* endOut = nodeEdge->oNextOE();

    OverlayEdge* currOut = endOut;

    int state = STATE_FIND_INCOMING;

    OverlayEdge* currResultIn = nullptr;

    do {

        /**

        * If an edge is linked this node has already been processed

        * so can skip further processing

        */

        if (currResultIn != nullptr && currResultIn->isResultMaxLinked())

            return;

        switch (state) {

            case STATE_FIND_INCOMING: {

                OverlayEdge* currIn = currOut->symOE();

                if (! currIn->isInResultArea())

                    break;

                currResultIn = currIn;

                state = STATE_LINK_OUTGOING;

                break;

            }

            case STATE_LINK_OUTGOING: {

                if (! currOut->isInResultArea())

                    break;

                // link the in edge to the out edge

                currResultIn->setNextResultMax(currOut);

                state = STATE_FIND_INCOMING;

                break;

            }

        }

        currOut = currOut->oNextOE();

    }

    while (currOut != endOut);

    if (state == STATE_LINK_OUTGOING) {

        throw util::TopologyException("no outgoing edge found", nodeEdge->getCoordinate());

    }

}

/*private*/

void

MaximalEdgeRing::attachEdges(OverlayEdge* p_startEdge)

{

    OverlayEdge* edge = p_startEdge;

    do {

        if (edge == nullptr)

            throw util::TopologyException("Ring edge is null");

        if (edge->getEdgeRingMax() == this)

            throw util::TopologyException("Ring edge visited twice", edge->getCoordinate());

        if (edge->nextResultMax() == nullptr) {

            throw util::TopologyException("Ring edge missing", edge->dest());

        }

        edge->setEdgeRingMax(this);

        edge = edge->nextResultMax();

    }

    while (edge != p_startEdge);

}

/*public*/

std::vector<std::unique_ptr<OverlayEdgeRing>>

MaximalEdgeRing::buildMinimalRings(const GeometryFactory* geometryFactory)

{

    linkMinimalRings();

    std::vector<std::unique_ptr<OverlayEdgeRing>> outOERs;

    OverlayEdge* e = startEdge;

    do {

        if (e->getEdgeRing() == nullptr) {

            outOERs.emplace_back(new OverlayEdgeRing(e, geometryFactory));

        }

        e = e->nextResultMax();

    }

    while (e != startEdge);

    return outOERs;

}

/*private*/

void

MaximalEdgeRing::linkMinimalRings()

{

    OverlayEdge* e = startEdge;

    do {

        linkMinRingEdgesAtNode(e, this);

        e = e->nextResultMax();

    }

    while (e != startEdge);

}

/*private static*/

void

MaximalEdgeRing::linkMinRingEdgesAtNode(OverlayEdge* nodeEdge, MaximalEdgeRing* maxRing)

{

    /**

     * The node edge is an out-edge,

     * so it is the first edge linked

     * with the next CCW in-edge

     */

    OverlayEdge* endOut = nodeEdge;

    OverlayEdge* currMaxRingOut = endOut;

    OverlayEdge* currOut = endOut->oNextOE();

    do {

        if (isAlreadyLinked(currOut->symOE(), maxRing))

            return;

        if (currMaxRingOut == nullptr) {

            currMaxRingOut = selectMaxOutEdge(currOut, maxRing);

        }

        else {

            currMaxRingOut = linkMaxInEdge(currOut, currMaxRingOut, maxRing);

        }

        currOut = currOut->oNextOE();

    }

    while (currOut != endOut);

    if (currMaxRingOut != nullptr) {

        throw util::TopologyException("Unmatched edge found during min-ring linking", nodeEdge->getCoordinate());

    }

}

/*private static*/

bool

MaximalEdgeRing::isAlreadyLinked(OverlayEdge* edge, MaximalEdgeRing* maxRing)

{

    bool isLinked = (edge->getEdgeRingMax() == maxRing) &&

                    (edge->isResultLinked());

    return isLinked;

}

/*private static*/

OverlayEdge*

MaximalEdgeRing::selectMaxOutEdge(OverlayEdge* currOut, MaximalEdgeRing* maxEdgeRing)

{

    // select if currOut edge is part of this max ring

    if (currOut->getEdgeRingMax() ==  maxEdgeRing)

        return currOut;

    // otherwise skip this edge

    return nullptr;

}

/*private static*/

OverlayEdge*

MaximalEdgeRing::linkMaxInEdge(OverlayEdge* currOut, OverlayEdge* currMaxRingOut, MaximalEdgeRing* maxEdgeRing)

{

    OverlayEdge* currIn = currOut->symOE();

    if (currIn->getEdgeRingMax() !=  maxEdgeRing)

        return currMaxRingOut;

    currIn->setNextResult(currMaxRingOut);

    return nullptr;

}

/*public*/

std::ostream&

operator<<(std::ostream& os, const MaximalEdgeRing& mer)

{

    CoordinateSequence coords;

    OverlayEdge* edge = mer.startEdge;

    do {

        coords.add(edge->orig());

        if (edge->nextResultMax() == nullptr)

            break;

        edge = edge->nextResultMax();

    }

    while (edge != mer.startEdge);

    coords.add(edge->dest());

    std::string wkt = io::WKTWriter::toLineString(coords);

    os << wkt;

    return os;

}

} // namespace geos.operation.overlayng

} // namespace geos.operation

} // namespace geos