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

 *

 * GEOS - Geometry Engine Open Source

 * http://geos.osgeo.org

 *

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

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

 *

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

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

#include <geos/geom/Envelope.h>

#include <geos/geom/Coordinate.h>

#include <cmath>

#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

/* static public */

int

Key::computeQuadLevel(const Envelope& env)

{

    double dx = env.getWidth();

    double dy = env.getHeight();

    double dMax = dx > dy ? dx : dy;

    int level;

    frexp(dMax, &level);

#if GEOS_DEBUG

    std::cerr << "Maxdelta:" << dMax << " exponent:" << (level - 1) << std::endl;

#endif

    return level;

}

Key::Key(const Envelope& itemEnv)

    :

    pt(),

    level(0),

    env()

{

    computeKey(itemEnv);

}

const Coordinate&

Key::getPoint() const

{

    return pt;

}

int

Key::getLevel() const

{

    return level;

}

const Envelope&

Key::getEnvelope() const

{

    return env;

}

Coordinate*

Key::getCentre() const

{

    return new Coordinate(

               (env.getMinX() + env.getMaxX()) / 2,

               (env.getMinY() + env.getMaxY()) / 2

           );

}

/*public*/

void

Key::computeKey(const Envelope& itemEnv)

{

    level = computeQuadLevel(itemEnv);

    env.init(); // reset to null

    computeKey(level, itemEnv);

    // MD - would be nice to have a non-iterative form of this algorithm

    while(!env.contains(itemEnv)) {

        level += 1;

        computeKey(level, itemEnv);

    }

#if GEOS_DEBUG

    std::cerr << "Key::computeKey:" << std::endl;

    std::cerr << " itemEnv: " << itemEnv.toString() << std::endl;

    std::cerr << "  keyEnv: " << env.toString() << std::endl;

    std::cerr << "  keyLvl: " << level << std::endl;

#endif

}

void

Key::computeKey(int p_level, const Envelope& itemEnv)

{

    double quadSize = exp2(p_level);

    pt.x = std::floor(itemEnv.getMinX() / quadSize) * quadSize;

    pt.y = std::floor(itemEnv.getMinY() / quadSize) * quadSize;

    env.init(pt.x, pt.x + quadSize, pt.y, pt.y + quadSize);

}

} // namespace geos.index.quadtree

} // namespace geos.index

} // namespace geos