<commit_before>/**********************************************************************
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.osgeo.org
 *
 * Copyright (C) 2020 <NAME> <<EMAIL>>
 *
 * This is free software; you can redistribute and/or modify it under
 * the terms of the GNU Lesser General Licence as published
 * by the Free Software Foundation.
 * See the COPYING file for more information.
 *
 *********************************************************************/

#include <geos/noding/snapround/HotPixelIndex.h>
#include <geos/index/kdtree/KdTree.h>
#include <geos/index/ItemVisitor.h>
#include <geos/geom/CoordinateSequence.h>

#include <algorithm> // for std::min and std::max
#include <cassert>
#include <memory>

using namespace geos::algorithm;
using namespace geos::geom;
using geos::index::kdtree::KdTree;
using geos::index::ItemVisitor;

namespace geos {
namespace noding { // geos.noding
namespace snapround { // geos.noding.snapround

/*public*/
HotPixelIndex::HotPixelIndex(const PrecisionModel* p_pm)
    :
    pm(p_pm),
    scaleFactor(p_pm->getScale()),
    index(new KdTree())
{
}


/*public*/
HotPixel*
HotPixelIndex::add(const Coordinate& p)
{
    Coordinate pRound = round(p);
    HotPixel* hp = find(pRound);

    /**
     * Hot Pixels which are added more than once
     * must have more than one vertex in them
     * and thus must be nodes.
     */
    if (hp != nullptr) {
        hp->setToNode();
        return hp;
    }
    /**
     * A pixel containing the point was not found, so create a new one.
     * It is initially set to NOT be a node
     * (but may become one later on).
     */

    // Store the HotPixel in a std::deque to avoid individually
    // allocating a pile of HotPixels on the heap and to
    // get them freed automatically as the std::deque
    // goes away when this HotPixelIndex is deleted.
    hotPixelQue.emplace_back(pRound, scaleFactor);

    // Pick up a pointer to the most recently added
    // HotPixel.
    hp = &(hotPixelQue.back());

    index->insert(hp->getCoordinate(), (void*)hp);
    return hp;
}

/*public*/
void
HotPixelIndex::add(const CoordinateSequence *pts)
{
    /*
    * Add the points to the tree in random order
    * to avoid getting an unbalanced tree from
    * spatially autocorrelated coordinates
    */
    std::vector<int> idxs;
    for (size_t i = 0, sz = pts->size(); i < sz; i++)
        idxs.push_back(i);

    std::random_shuffle(idxs.begin(), idxs.end());
    for (auto i : idxs) {
        add(pts->getAt(i));
    }
}

/*public*/
void
HotPixelIndex::add(const std::vector<geom::Coordinate>& pts)
{
    for (auto pt: pts) {
        add(pt);
    }
}

/*public*/
void
HotPixelIndex::addNodes(const CoordinateSequence *pts)
{
    for (size_t i = 0, sz = pts->size(); i < sz; i++) {
        HotPixel* hp = add(pts->getAt(i));
        hp->setToNode();
    }
}

/*public*/
void
HotPixelIndex::addNodes(const std::vector<geom::Coordinate>& pts)
{
    for (auto pt: pts) {
        HotPixel* hp = add(pt);
        hp->setToNode();
    }
}

/*private*/
HotPixel*
HotPixelIndex::find(const geom::Coordinate& pixelPt)<commit_msg>Randomize input to kdtree to avoid unbalanced tree<commit_after>/**********************************************************************
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.osgeo.org
 *
 * Copyright (C) 2020 <NAME> <<EMAIL>>
 *
 * This is free software; you can redistribute and/or modify it under
 * the terms of the GNU Lesser General Licence as published
 * by the Free Software Foundation.
 * See the COPYING file for more information.
 *
 *********************************************************************/

#include <geos/noding/snapround/HotPixelIndex.h>
#include <geos/index/kdtree/KdTree.h>
#include <geos/index/ItemVisitor.h>
#include <geos/geom/CoordinateSequence.h>

#include <algorithm> // for std::min and std::max
#include <cassert>
#include <memory>

using namespace geos::algorithm;
using namespace geos::geom;
using geos::index::kdtree::KdTree;
using geos::index::ItemVisitor;

namespace geos {
namespace noding { // geos.noding
namespace snapround { // geos.noding.snapround

/*public*/
HotPixelIndex::HotPixelIndex(const PrecisionModel* p_pm)
    :
    pm(p_pm),
    scaleFactor(p_pm->getScale()),
    index(new KdTree())
{
}


/*public*/
HotPixel*
HotPixelIndex::add(const Coordinate& p)
{
    Coordinate pRound = round(p);
    HotPixel* hp = find(pRound);

    /**
     * Hot Pixels which are added more than once
     * must have more than one vertex in them
     * and thus must be nodes.
     */
    if (hp != nullptr) {
        hp->setToNode();
        return hp;
    }
    /**
     * A pixel containing the point was not found, so create a new one.
     * It is initially set to NOT be a node
     * (but may become one later on).
     */

    // Store the HotPixel in a std::deque to avoid individually
    // allocating a pile of HotPixels on the heap and to
    // get them freed automatically as the std::deque
    // goes away when this HotPixelIndex is deleted.
    hotPixelQue.emplace_back(pRound, scaleFactor);

    // Pick up a pointer to the most recently added
    // HotPixel.
    hp = &(hotPixelQue.back());

    index->insert(hp->getCoordinate(), (void*)hp);
    return hp;
}

/*public*/
void
HotPixelIndex::add(const CoordinateSequence *pts)
{
    /*
    * Add the points to the tree in random order
    * to avoid getting an unbalanced tree from
    * spatially autocorrelated coordinates
    */
    std::vector<int> idxs;
    for (size_t i = 0, sz = pts->size(); i < sz; i++)
        idxs.push_back(i);

    std::random_shuffle(idxs.begin(), idxs.end());
    for (auto i : idxs) {
        add(pts->getAt(i));
    }
}

/*public*/
void
HotPixelIndex::add(const std::vector<geom::Coordinate>& pts)
{
    std::vector<int> idxs;
    for (size_t i = 0, sz = pts.size(); i < sz; i++)
        idxs.push_back(i);

    std::random_shuffle(idxs.begin(), idxs.end());

    for (auto i : idxs) {
        add(pts[i]);
    }
}

/*public*/
void
HotPixelIndex::addNodes(const CoordinateSequence *pts)
{
    for (size_t i = 0, sz = pts->size(); i < sz; i++) {
        HotPixel* hp = add(pts->getAt(i));
        hp->setToNode();
    }
}

/*public*/
void
HotPixelIndex::addNodes(const std::vector<geom::Coordinate>& pts)
{
    for (auto pt: pts) {
        HotPixel* hp = add(pt);
        hp->setToNode();
    }
}

/*private*/
HotPixel*
HotPixelIndex::find(const geom::Coordinate& pixelPt)
{'fraction_non_alphanumeric': 0.1735230436127436, 'fraction_numerical': 0.002010516548097742, 'mean_word_length': 3.221279373368146, 'pattern_counts': {'":': 0, '<': 35, '<?xml version=': 0, '>': 50, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3384760', 'n_tokens_mistral': 2137, 'n_tokens_neox': 2077, 'n_words': 610}