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

 *

 * GEOS - Geometry Engine Open Source

 * http://geos.osgeo.org

 *

 * Copyright (C) 2005 Refractions Research Inc.

 * Copyright (C) 2001-2002 Vivid Solutions Inc.

 *

 * 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.

 *

 **********************************************************************

 *

 * Last port: operation/buffer/BufferSubgraph.java r378 (JTS-1.12)

 *

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

#include <geos/operation/buffer/BufferSubgraph.h>

#include <geos/util/TopologyException.h>

#include <geos/geom/Envelope.h>

#include <geos/geom/CoordinateSequence.h>

#include <geos/geomgraph/Node.h>

#include <geos/geomgraph/Edge.h>

#include <geos/geomgraph/DirectedEdge.h>

#include <geos/geomgraph/DirectedEdgeStar.h>

#include <geos/geomgraph/EdgeEndStar.h>

#include <geos/geom/Position.h>

#include <geos/util.h>

#include <cassert>

#include <vector>

#include <iostream>

#include <list>

#ifndef GEOS_DEBUG

#define GEOS_DEBUG 0

#endif

using namespace geos::geomgraph;

using namespace geos::algorithm;

using namespace geos::operation;

using namespace geos::geom;

namespace geos {

namespace operation { // geos.operation

namespace buffer { // geos.operation.buffer

// Argument is unused

BufferSubgraph::BufferSubgraph()

    :

    finder(),

    dirEdgeList(),

    nodes(),

    rightMostCoord(nullptr),

    env(nullptr)

{

}

BufferSubgraph::~BufferSubgraph()

{

    delete env;

}

/*public*/

void

BufferSubgraph::create(Node* node)

{

    addReachable(node);

    // We are assuming that dirEdgeList

    // contains *at least* ONE forward DirectedEdge

    finder.findEdge(&dirEdgeList);

    rightMostCoord = &(finder.getCoordinate());

    // this is what happen if no forward DirectedEdge

    // is passed to the RightmostEdgeFinder

    assert(rightMostCoord);

}

/*private*/

void

BufferSubgraph::addReachable(Node* startNode)

{

    std::vector<Node*> nodeStack;

    nodeStack.push_back(startNode);

    while(!nodeStack.empty()) {

        Node* node = nodeStack.back();

        nodeStack.pop_back();

        add(node, &nodeStack);

    }

}

/*private*/

void

BufferSubgraph::add(Node* node, std::vector<Node*>* nodeStack)

{

    node->setVisited(true);

    nodes.push_back(node);

    EdgeEndStar* ees = node->getEdges();

    EdgeEndStar::iterator it = ees->begin();

    EdgeEndStar::iterator endIt = ees->end();

    for(; it != endIt; ++it) {

        DirectedEdge* de = detail::down_cast<DirectedEdge*>(*it);

        dirEdgeList.push_back(de);

        DirectedEdge* sym = de->getSym();

        Node* symNode = sym->getNode();

        /*

         * NOTE: this is a depth-first traversal of the graph.

         * This will cause a large depth of recursion.

         * It might be better to do a breadth-first traversal.

         */

        if(! symNode->isVisited()) {

            nodeStack->push_back(symNode);

        }

    }

}

/*private*/

void

BufferSubgraph::clearVisitedEdges()

{

    for(std::size_t i = 0, n = dirEdgeList.size(); i < n; ++i) {

        DirectedEdge* de = dirEdgeList[i];

        de->setVisited(false);

    }

}

/*public*/

void

BufferSubgraph::computeDepth(int outsideDepth)

{

    clearVisitedEdges();

    // find an outside edge to assign depth to

    DirectedEdge* de = finder.getEdge();

#if GEOS_DEBUG

    std::cerr << "outside depth: " << outsideDepth << std::endl;

#endif

    //Node *n=de->getNode();

    //Label *label=de->getLabel();

    // right side of line returned by finder is on the outside

    de->setEdgeDepths(Position::RIGHT, outsideDepth);

    copySymDepths(de);

    //computeNodeDepth(n, de);

    computeDepths(de);

}

void

BufferSubgraph::computeNodeDepth(Node* n)

// throw(TopologyException *)

{

    // find a visited dirEdge to start at

    DirectedEdge* startEdge = nullptr;

    DirectedEdgeStar* ees = detail::down_cast<DirectedEdgeStar*>(n->getEdges());

    EdgeEndStar::iterator endIt = ees->end();

    EdgeEndStar::iterator it = ees->begin();

    for(; it != endIt; ++it) {

        DirectedEdge* de = detail::down_cast<DirectedEdge*>(*it);

        if(de->isVisited() || de->getSym()->isVisited()) {

            startEdge = de;

            break;

        }

    }

    // MD - testing  Result: breaks algorithm

    //if (startEdge==null) return;

    // only compute string append if assertion would fail

    if(startEdge == nullptr) {

        throw util::TopologyException(

            "unable to find edge to compute depths at",

            n->getCoordinate());

    }

    ees->computeDepths(startEdge);

    // copy depths to sym edges

    for(it = ees->begin(); it != endIt; ++it) {

        DirectedEdge* de = detail::down_cast<DirectedEdge*>(*it);

        de->setVisited(true);

        copySymDepths(de);

    }

}

/*private*/

void

BufferSubgraph::copySymDepths(DirectedEdge* de)

{

#if GEOS_DEBUG

    std::cerr << "copySymDepths: " << de->getDepth(Position::LEFT)

         << ", " << de->getDepth(Position::RIGHT)

         << std::endl;

#endif

    DirectedEdge* sym = de->getSym();

    sym->setDepth(Position::LEFT, de->getDepth(Position::RIGHT));

    sym->setDepth(Position::RIGHT, de->getDepth(Position::LEFT));

}

/*public*/

void

BufferSubgraph::findResultEdges()

{

#if GEOS_DEBUG

    std::cerr << "BufferSubgraph::findResultEdges got " << dirEdgeList.size() << " edges" << std::endl;

#endif

    for(std::size_t i = 0, n = dirEdgeList.size(); i < n; ++i) {

        DirectedEdge* de = dirEdgeList[i];

        /*

         * Select edges which have an interior depth on the RHS

         * and an exterior depth on the LHS.

         * Note that because of weird rounding effects there may be

         * edges which have negative depths!  Negative depths

         * count as "outside".

         */

        // <FIX> - handle negative depths

#if GEOS_DEBUG

        std::cerr << " dirEdge " << i << ": " << de->printEdge() << std::endl

             << "         depth right: " << de->getDepth(Position::RIGHT) << std::endl

             << "          depth left: " << de->getDepth(Position::LEFT) << std::endl

             << "    interiorAreaEdge: " << de->isInteriorAreaEdge() << std::endl;

#endif

        if(de->getDepth(Position::RIGHT) >= 1

                &&  de->getDepth(Position::LEFT) <= 0

                && !de->isInteriorAreaEdge()) {

            de->setInResult(true);

#if GEOS_DEBUG

            std::cerr << "   IN RESULT" << std::endl;

#endif

        }

    }

}

/*public*/

int

BufferSubgraph::compareTo(BufferSubgraph* graph)

{

    assert(rightMostCoord);

    if(rightMostCoord->x < graph->rightMostCoord->x) {

        return -1;

    }

    if(rightMostCoord->x > graph->rightMostCoord->x) {

        return 1;

    }

    return 0;

}

/*private*/

void

BufferSubgraph::computeDepths(DirectedEdge* startEdge)

{

    std::set<Node*> nodesVisited;

    std::list<Node*> nodeQueue; // Used to be a vector

    Node* startNode = startEdge->getNode();

    nodeQueue.push_back(startNode);

    //nodesVisited.push_back(startNode);

    nodesVisited.insert(startNode);

    startEdge->setVisited(true);

    while(! nodeQueue.empty()) {

        //System.out.println(nodes.size() + " queue: " + nodeQueue.size());

        Node* n = nodeQueue.front(); // [0];

        //nodeQueue.erase(nodeQueue.begin());

        nodeQueue.pop_front();

        nodesVisited.insert(n);

        // compute depths around node, starting at this edge since it has depths assigned

        computeNodeDepth(n);

        // add all adjacent nodes to process queue,

        // unless the node has been visited already

        EdgeEndStar* ees = n->getEdges();

        EdgeEndStar::iterator endIt = ees->end();

        EdgeEndStar::iterator it = ees->begin();

        for(; it != endIt; ++it) {

            DirectedEdge* de = detail::down_cast<DirectedEdge*>(*it);

            DirectedEdge* sym = de->getSym();

            if(sym->isVisited()) {

                continue;

            }

            Node* adjNode = sym->getNode();

            //if (! contains(nodesVisited,adjNode))

            if(nodesVisited.insert(adjNode).second) {

                nodeQueue.push_back(adjNode);

                //nodesVisited.insert(adjNode);

            }

        }

    }

}

/*private*/

bool

BufferSubgraph::contains(std::set<Node*>& nodeSet, Node* node)

{

    //bool result=false;

    if(nodeSet.find(node) != nodeSet.end()) {

        return true;

    }

    return false;

}

/*public*/

Envelope*

BufferSubgraph::getEnvelope()

{

    if(env == nullptr) {

        env = new Envelope();

        std::size_t const size = dirEdgeList.size();

        for(std::size_t i = 0; i < size; ++i) {

            DirectedEdge* dirEdge = dirEdgeList[i];

            const CoordinateSequence* pts = dirEdge->getEdge()->getCoordinates();

            std::size_t const n = pts->getSize() - 1;

            for(std::size_t j = 0; j < n; ++j) {

                env->expandToInclude(pts->getAt(j));

            }

        }

    }

    return env;

}

std::ostream&

operator<< (std::ostream& os, const BufferSubgraph& bs)

{

    os << "BufferSubgraph[" << &bs << "] "

       << bs.nodes.size() << " nodes, "

       << bs.dirEdgeList.size() << " directed edges" << std::endl;

    for(std::size_t i = 0, n = bs.nodes.size(); i < n; i++) {

        os << "  Node " << i << ": " << *(bs.nodes[i]) << std::endl;

    }

    for(std::size_t i = 0, n = bs.dirEdgeList.size(); i < n; i++) {

        os << "  DirEdge " << i << ": " << std::endl

           << bs.dirEdgeList[i]->printEdge() << std::endl;

    }

    return os;

}

} // namespace geos.operation.buffer

} // namespace geos.operation

} // namespace geos