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

 *

 * 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/Node.java rev 1.8 (JTS-1.10)

 *

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

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

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

#include <geos/geom/Envelope.h>

#include <string>

#include <sstream>

#include <cassert>

#include <memory>

#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

/* public static */

std::unique_ptr<Node>

Node::createNode(const Envelope& env)

{

    Key key(env);

    std::unique_ptr<Envelope> envelope(new Envelope(key.getEnvelope()));

    std::unique_ptr<Node> node(

        new Node(std::move(envelope), key.getLevel())

    );

    return node;

}

/* static public */

std::unique_ptr<Node>

Node::createExpanded(std::unique_ptr<Node> node, const Envelope& addEnv)

{

    Envelope expandEnv(addEnv);

    if(node.get()) {  // should this be asserted ?

        expandEnv.expandToInclude(node->getEnvelope());

    }

#if GEOS_DEBUG

    std::cerr << "Node::createExpanded computed " << expandEnv.toString() << std::endl;

#endif

    std::unique_ptr<Node> largerNode = createNode(expandEnv);

    if(node.get()) {  // should this be asserted ?

        largerNode->insertNode(std::move(node));

    }

    return largerNode;

}

/*public*/

Node*

Node::getNode(const Envelope* searchEnv)

{

    int subnodeIndex = getSubnodeIndex(searchEnv, centre);

    // if subquadIndex is -1 searchEnv is not contained in a subquad

    if(subnodeIndex != -1) {

        // create the quad if it does not exist

        Node* node = getSubnode(subnodeIndex);

        // recursively search the found/created quad

        return node->getNode(searchEnv);

    }

    else {

        return this;

    }

}

/*public*/

NodeBase*

Node::find(const Envelope* searchEnv)

{

    int subnodeIndex = getSubnodeIndex(searchEnv, centre);

    if(subnodeIndex == -1) {

        return this;

    }

    if(subnodes[static_cast<std::size_t>(subnodeIndex)] != nullptr) {

        // query lies in subquad, so search it

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

        return node->find(searchEnv);

    }

    // no existing subquad, so return this one anyway

    return this;

}

void

Node::insertNode(std::unique_ptr<Node> node)

{

    assert(env->contains(node->getEnvelope()));

    int index = getSubnodeIndex(node->getEnvelope(), centre);

    assert(index >= 0);

    if(node->level == level - 1) {

        // We take ownership of node

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

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

        //System.out.println("inserted");

    }

    else {

        // the quad is not a direct child, so make a new child

        // quad to contain it and recursively insert the quad

        std::unique_ptr<Node> childNode(createSubnode(index));

        // childNode takes ownership of node

        childNode->insertNode(std::move(node));

        // We take ownership of childNode

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

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

    }

}

Node*

Node::getSubnode(int index)

{

    assert(index >= 0 && index < 4);

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

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

    }

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

}

std::unique_ptr<Node>

Node::createSubnode(int index)

{

    // create a new subquad in the appropriate quadrant

    double minx = 0.0;

    double maxx = 0.0;

    double miny = 0.0;

    double maxy = 0.0;

    switch(index) {

    case 0:

        minx = env->getMinX();

        maxx = centre.x;

        miny = env->getMinY();

        maxy = centre.y;

        break;

    case 1:

        minx = centre.x;

        maxx = env->getMaxX();

        miny = env->getMinY();

        maxy = centre.y;

        break;

    case 2:

        minx = env->getMinX();

        maxx = centre.x;

        miny = centre.y;

        maxy = env->getMaxY();

        break;

    case 3:

        minx = centre.x;

        maxx = env->getMaxX();

        miny = centre.y;

        maxy = env->getMaxY();

        break;

    }

    std::unique_ptr<Envelope> sqEnv(new Envelope(minx, maxx, miny, maxy));

    std::unique_ptr<Node> node(new Node(std::move(sqEnv), level - 1));

    return node;

}

std::string

Node::toString() const

{

    std::ostringstream os;

    os << "L" << level << " " << env->toString() << " Ctr[" << centre.toString() << "]";

    os << " " << NodeBase::toString();

    return os.str();

}

} // namespace geos.index.quadtree

} // namespace geos.index

} // namespace geos