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

 *

 * GEOS - Geometry Engine Open Source

 * http://geos.osgeo.org

 *

 * Copyright (C) 2011 Sandro Santilli <strk@kbt.io>

 * Copyright (C) 2006 Refractions Research 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/union/CascadedPolygonUnion.java r487 (JTS-1.12+)

 * Includes custom code to deal with https://trac.osgeo.org/geos/ticket/837

 *

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

#include <geos/geom/Geometry.h>

#include <geos/geom/GeometryFactory.h>

#include <geos/geom/MultiPolygon.h>

#include <geos/geom/Polygon.h>

#include <geos/index/strtree/TemplateSTRtree.h>

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

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

#include <geos/operation/union/CascadedPolygonUnion.h>

#include <geos/operation/valid/IsValidOp.h>

#include <geos/operation/valid/IsSimpleOp.h>

#include <geos/util/TopologyException.h>

// std

#include <cassert>

#include <cstddef>

#include <sstream>

#include <string>

namespace geos {

namespace operation { // geos.operation

namespace geounion {  // geos.operation.geounion

// ////////////////////////////////////////////////////////////////////////////

std::unique_ptr<geom::Geometry>

CascadedPolygonUnion::Union(std::vector<geom::Polygon*>* polys)

{

    CascadedPolygonUnion op(polys);

    return op.Union();

}

std::unique_ptr<geom::Geometry>

CascadedPolygonUnion::Union(std::vector<geom::Polygon*>* polys, UnionStrategy* unionFun)

{

    CascadedPolygonUnion op(polys, unionFun);

    return op.Union();

}

std::unique_ptr<geom::Geometry>

CascadedPolygonUnion::Union(const geom::MultiPolygon* multipoly)

{

    std::vector<geom::Polygon*> polys;

    for(const auto& g : *multipoly) {

        polys.push_back(dynamic_cast<geom::Polygon*>(g.get()));

    }

    CascadedPolygonUnion op(&polys);

    return op.Union();

}

std::unique_ptr<geom::Geometry>

CascadedPolygonUnion::Union()

{

    if(inputPolys->empty()) {

        return nullptr;

    }

    geomFactory = inputPolys->front()->getFactory();

    /*

     * A spatial index to organize the collection

     * into groups of close geometries.

     * This makes unioning more efficient, since vertices are more likely

     * to be eliminated on each round.

     */

    index::strtree::TemplateSTRtree<const geom::Geometry*> index(10, inputPolys->size());

    for (const auto& p : *inputPolys) {

        index.insert(p);

    }

    // TODO avoid creating this vector and run binaryUnion off the iterators directly

    std::vector<const geom::Geometry*> geoms(index.items().begin(), index.items().end());

    return binaryUnion(geoms, 0, geoms.size());

}

std::unique_ptr<geom::Geometry>

CascadedPolygonUnion::binaryUnion(const std::vector<const geom::Geometry*> & geoms,

                                  std::size_t start, std::size_t end)

{

    if(end - start == 0) {

        return nullptr;

    }

    else if(end - start == 1) {

        return unionSafe(geoms[start], nullptr);

    }

    else if(end - start == 2) {

        return unionSafe(geoms[start], geoms[start + 1]);

    }

    else {

        // recurse on both halves of the list

        std::size_t mid = (end + start) / 2;

        std::unique_ptr<geom::Geometry> g0(binaryUnion(geoms, start, mid));

        std::unique_ptr<geom::Geometry> g1(binaryUnion(geoms, mid, end));

        return unionSafe(std::move(g0), std::move(g1));

    }

}

std::unique_ptr<geom::Geometry>

CascadedPolygonUnion::unionSafe(const geom::Geometry* g0, const geom::Geometry* g1) const

{

    if(g0 != nullptr && g1 != nullptr) {

        return unionActual(g0, g1);

    }

    if(g1 != nullptr) {

        return g1->clone();

    }

    if(g0 != nullptr) {

        return g0->clone();

    }

    return nullptr;

}

std::unique_ptr<geom::Geometry>

CascadedPolygonUnion::unionSafe(std::unique_ptr<geom::Geometry> && g0, std::unique_ptr<geom::Geometry> && g1)

{

    if(g0 == nullptr && g1 == nullptr) {

        return nullptr;

    }

    if(g0 == nullptr) {

        return std::move(g1);

    }

    if(g1 == nullptr) {

        return std::move(g0);

    }

    return unionActual(std::move(g0), std::move(g1));

}

std::unique_ptr<geom::Geometry>

CascadedPolygonUnion::unionActual(const geom::Geometry* g0, const geom::Geometry* g1) const

{

    std::unique_ptr<geom::Geometry> ug;

    ug = unionFunction->Union(g0, g1);

    return restrictToPolygons(std::move(ug));

}

std::unique_ptr<geom::Geometry>

CascadedPolygonUnion::unionActual(std::unique_ptr<geom::Geometry> && g0, std::unique_ptr<geom::Geometry> && g1) const

{

    std::unique_ptr<geom::Geometry> ug;

    ug = unionFunction->Union(std::move(g0), std::move(g1));

    return restrictToPolygons(std::move(ug));

}

std::unique_ptr<geom::Geometry>

CascadedPolygonUnion::restrictToPolygons(std::unique_ptr<geom::Geometry> g)

{

    using namespace geom;

    if(g->isPolygonal()) {

        return g;

    }

    auto gfact = g->getFactory();

    auto coordDim = g->getCoordinateDimension();

    auto coll = dynamic_cast<GeometryCollection*>(g.get());

    if (coll) {

        // Release polygons from the collection and re-form into MultiPolygon

        auto components = coll->releaseGeometries();

        components.erase(std::remove_if(components.begin(), components.end(), [](const std::unique_ptr<Geometry> & cmp) {

            return !cmp->isPolygonal();

        }), components.end());

        return gfact->createMultiPolygon(std::move(components));

    } else {

        // Not polygonal and not a collection? No polygons here.

        return gfact->createPolygon(coordDim);

    }

}

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

std::unique_ptr<geom::Geometry>

ClassicUnionStrategy::Union(const geom::Geometry* g0, const geom::Geometry* g1)

{

    try {

        return operation::overlayng::OverlayNGRobust::Overlay(g0, g1, operation::overlayng::OverlayNG::UNION);

    }

    catch (const util::TopologyException &ex) {

        ::geos::ignore_unused_variable_warning(ex);

        // union-by-buffer only works for polygons

        if (g0->getDimension() != 2 || g1->getDimension() != 2)

          throw;

        return unionPolygonsByBuffer(g0, g1);

    }

}

bool

ClassicUnionStrategy::isFloatingPrecision() const

{

  return true;

}

/*private*/

std::unique_ptr<geom::Geometry>

ClassicUnionStrategy::unionPolygonsByBuffer(const geom::Geometry* g0, const geom::Geometry* g1)

{

    std::vector<std::unique_ptr<geom::Geometry>> geoms;

    geoms.push_back(g0->clone());

    geoms.push_back(g1->clone());

    std::unique_ptr<geom::GeometryCollection> coll = g0->getFactory()->createGeometryCollection(std::move(geoms));

    return coll->buffer(0);

}

} // namespace geos.operation.union

} // namespace geos.operation

} // namespace geos