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

 *

 * GEOS - Geometry Engine Open Source

 * http://geos.osgeo.org

 *

 * Copyright (C) 2006 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: index/quadtree/Root.java rev 1.7 (JTS-1.10)

 *

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

#include <geos/index/quadtree/Root.h>

#include <geos/index/quadtree/Node.h>

#include <geos/index/quadtree/IntervalSize.h>

#include <geos/geom/Coordinate.h>

#include <geos/geom/Envelope.h>

#include <geos/util/IllegalArgumentException.h>

#include <cassert>

#ifndef GEOS_DEBUG

#define GEOS_DEBUG 0

#endif

#if GEOS_DEBUG

#include <iostream>

#endif

using namespace geos::geom;

namespace geos {

namespace index { // geos.index

namespace quadtree { // geos.index.quadtree

// the singleton root quad is centred at the origin.

//Coordinate* Root::origin=new Coordinate(0.0, 0.0);

const Coordinate Root::origin(0.0, 0.0);

/*public*/

void

Root::insert(const Envelope* itemEnv, void* item)

{

#if GEOS_DEBUG

    std::cerr << "Root(" << this << ")::insert(" << itemEnv->toString() << ", " << item << ") called" << std::endl;

#endif

    if (!itemEnv->isfinite()) {

        throw util::IllegalArgumentException("Non-finite envelope bounds passed to index insert");

    }

    int index = getSubnodeIndex(itemEnv, origin);

    // if index is -1, itemEnv must cross the X or Y axis.

    if(index == -1) {

#if GEOS_DEBUG

        std::cerr << "  -1 subnode index" << std::endl;

#endif

        add(item);

        return;

    }

    /*

     * the item must be contained in one quadrant, so insert it into the

     * tree for that quadrant (which may not yet exist)

     */

    Node* node = subnodes[static_cast<std::size_t>(index)];

#if GEOS_DEBUG

    std::cerr << "(" << this << ") subnode[" << index << "] @ " << node << std::endl;

#endif

    /*

     *  If the subquad doesn't exist or this item is not contained in it,

     *  have to expand the tree upward to contain the item.

     */

    if(node == nullptr || !node->getEnvelope()->contains(itemEnv)) {

        std::unique_ptr<Node> snode(node);  // may be NULL

        node = nullptr;

        subnodes[static_cast<std::size_t>(index)] = nullptr;

        std::unique_ptr<Node> largerNode =

            Node::createExpanded(std::move(snode), *itemEnv);

#if GEOS_DEBUG

        std::cerr << "(" << this << ") created expanded node " << largerNode.get() << " containing previously reported subnode"

                  << std::endl;

#endif

        // Previous subnode was passed as a child of the larger one

        assert(!subnodes[static_cast<std::size_t>(index)]);

        subnodes[static_cast<std::size_t>(index)] = largerNode.release();

    }

#if GEOS_DEBUG

    std::cerr << "(" << this << ") calling insertContained with subnode " << subnodes[index] << std::endl;

#endif

    /*

     * At this point we have a subquad which exists and must contain

     * contains the env for the item.  Insert the item into the tree.

     */

    insertContained(subnodes[static_cast<std::size_t>(index)], itemEnv, item);

#if GEOS_DEBUG

    std::cerr << "(" << this << ") done calling insertContained with subnode " << subnodes[index] << std::endl;

#endif

    //System.out.println("depth = " + root.depth() + " size = " + root.size());

    //System.out.println(" size = " + size());

}

/*private*/

void

Root::insertContained(Node* tree, const Envelope* itemEnv, void* item)

{

    assert(tree->getEnvelope()->contains(itemEnv));

    /*

     * Do NOT create a new quad for zero-area envelopes - this would lead

     * to infinite recursion. Instead, use a heuristic of simply returning

     * the smallest existing quad containing the query

     */

    bool isZeroX = IntervalSize::isZeroWidth(itemEnv->getMinX(),

                   itemEnv->getMaxX());

    bool isZeroY = IntervalSize::isZeroWidth(itemEnv->getMinY(),

                   itemEnv->getMaxY());

    NodeBase* node;

    if(isZeroX || isZeroY) {

        node = tree->find(itemEnv);

    }

    else {

        node = tree->getNode(itemEnv);

    }

    node->add(item);

}

} // namespace geos.index.quadtree

} // namespace geos.index

} // namespace geos