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

#include <geos/index/bintree/Root.h>
#include <geos/index/bintree/Node.h>
#include <geos/index/bintree/Interval.h>
#include <geos/index/quadtree/IntervalSize.h>

#include <cstddef>
#include <cassert>

namespace geos {
namespace index { // geos.index
namespace bintree { // geos.index.bintree

double Root::origin = 0.0;

void
Root::insert(Interval* itemInterval, void* item)
{
    int index = getSubnodeIndex(itemInterval, origin);
    // if index is -1, itemEnv must contain the origin.
    if(index == -1) {
        add(item);
        return;
    }

    /**
     * the item must be contained in one interval, so insert it into the
     * tree for that interval (which may not yet exist)
     */
    Node* node = subnode[index];

    /**
     *  If the subnode 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->getInterval()->contains(itemInterval)) {
        Node* largerNode = Node::createExpanded(node, itemInterval);
//		delete subnode[index];
        subnode[index] = largerNode;
    }
    /**
    * At this point we have a subnode which exists and must contain
    * contains the env for the item.  Insert the item into the tree.
    */
    insertContained(subnode[index], itemInterval, item);
    //System.out.println("depth = " + root.depth() + " size = " + root.size());
}

void
Root::insertContained(Node* tree, Interval* itemInterval, void* item)
{
    using geos::index::quadtree::IntervalSize;

    assert(tree->getInterval()->contains(itemInterval));

    /**
     * Do NOT create a new node for zero-area intervals - this would lead
     * to infinite recursion. Instead, use a heuristic of simply returning
     * the smallest existing node containing the query
     */
    bool isZeroArea = IntervalSize::isZeroWidth(itemInterval->getMin(),
                      itemInterval->getMax());
    NodeBase* node;
    if(isZeroArea) {
        node = tree->find(itemInterval);
    }
    else {
        node = tree->getNode(itemInterval);
    }
    node->add(item);
}

} // namespace geos.index.bintree
} // namespace geos.index
} // namespace geos