// Path: src/main/java/com/eatthepath/jvptree/util/SamplingMedianDistanceThresholdSelectionStrategy.java
// public class SamplingMedianDistanceThresholdSelectionStrategy<P, E extends P> extends MedianDistanceThresholdSelectionStrategy<P, E> implements ThresholdSelectionStrategy<P, E> {
// 
//     private final int numberOfSamples;
// 
//     public static final int DEFAULT_NUMBER_OF_SAMPLES = 32;
// 
//     /**
//      * Constructs a threshold selector that uses up to a default ({@value DEFAULT_NUMBER_OF_SAMPLES}) number of samples
//      * from a list of points to choose a median distance.
//      */
//     public SamplingMedianDistanceThresholdSelectionStrategy() {
//         this(DEFAULT_NUMBER_OF_SAMPLES);
//     }
// 
//     /**
//      * Constructs a threshold selector that uses up to the given number of samples from a list of points to choose a
//      * median distance.
//      *
//      * @param numberOfSamples the maximum number of samples to use when choosing a median distance
//      */
//     public SamplingMedianDistanceThresholdSelectionStrategy(final int numberOfSamples) {
//         this.numberOfSamples = numberOfSamples;
//     }
// 
//     /**
//      * Returns the median distance of a subset of the given points from the given origin. The given list of points may
//      * be partially sorted in the process.
//      *
//      * @param points the list of points from which a median distance will be chosen
//      * @param origin the point from which distances to other points will be calculated
//      * @param distanceFunction the function to be used to calculate the distance between the origin and other points
//      *
//      * @return the median distance from the origin to the given list of points
//      */
//     @Override
//     public double selectThreshold(final List<E> points, final P origin, final DistanceFunction<P> distanceFunction) {
//         return super.selectThreshold(this.getSampledPoints(points), origin, distanceFunction);
//     }
// 
//     /**
//      * Chooses a subset of points from which to calculate a median by sampling the given list.
//      *
//      * @param points the points from which to choose a subset of points
//      *
//      * @return a list containing at most the number of points chosen at construction time
//      */
//     List<E> getSampledPoints(final List<E> points) {
//         final List<E> sampledPoints;
// 
//         if (points.size() > this.numberOfSamples) {
//             sampledPoints = new ArrayList<>(this.numberOfSamples);
//             final int step = points.size() / this.numberOfSamples;
// 
//             for (int i = 0; i < this.numberOfSamples; i++) {
//                 sampledPoints.add(points.get(i * step));
//             }
//         } else {
//             sampledPoints = points;
//         }
// 
//         return sampledPoints;
//     }
// }


import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import com.eatthepath.jvptree.util.SamplingMedianDistanceThresholdSelectionStrategy;
package com.eatthepath.jvptree;



/**
 * <p>A vantage-point tree (or vp-tree) is a binary space partitioning collection of points in a metric space. The main
 * feature of vantage point trees is that they allow for k-nearest-neighbor searches in any metric space in
 * <em>O(log(n))</em> time.</p>
 *
 * <p>Vantage point trees recursively partition points by choosing a &quot;vantage point&quot; and a distance threshold;
 * points are then partitioned into one collection that contains all of the points closer to the vantage point than the
 * chosen threshold and one collection that contains all of the points farther away than the chosen threshold.</p>
 *
 * <p>A {@linkplain DistanceFunction distance function} that satisfies the properties of a metric space must be provided
 * when constructing a vantage point tree. Callers may also specify a threshold selection strategy (a sampling median
 * strategy is used by default) and a node size to tune the ratio of nodes searched to points inspected per node.
 * Vantage point trees may be constructed with or without an initial collection of points, though specifying a
 * collection of points at construction time is the most efficient approach.</p>
 *
 * @author <a href="https://github.com/jchambers">Jon Chambers</a>
 *
 * @param <P> the base type of points between which distances can be measured
 * @param <E> the specific type of point contained in this vantage point tree
 */
public class VPTree<P, E extends P> implements SpatialIndex<P, E> {

    private final DistanceFunction<P> distanceFunction;
    private final ThresholdSelectionStrategy<P, E> thresholdSelectionStrategy;
    private final int nodeCapacity;

    private VPTreeNode<P, E> rootNode;

    public static final int DEFAULT_NODE_CAPACITY = 32;

    private static final PointFilter<Object> NO_OP_POINT_FILTER = new PointFilter<Object>() {

        @Override
        public boolean allowPoint(final Object point) {
            return true;
        }
    };

    /**
     * Constructs a new vp-tree that uses the given distance function and is initially empty. The constructed tree will
     * use a default {@link SamplingMedianDistanceThresholdSelectionStrategy} and node capacity
     * ({@value VPTree#DEFAULT_NODE_CAPACITY} points).
     *
     * @param distanceFunction the distance function to use to calculate the distance between points
     */
    public VPTree(final DistanceFunction<P> distanceFunction) {
        this(distanceFunction, (Collection<E>) null);
    }

    /**
     * Constructs a new vp-tree that uses the given distance function and is initially populated with the given
     * collection of points. The constructed tree will use a default
     * {@link SamplingMedianDistanceThresholdSelectionStrategy} and node capacity
     * ({@value VPTree#DEFAULT_NODE_CAPACITY} points).
     *
     * @param distanceFunction the distance function to use to calculate the distance between points
     * @param points the points with which this tree should be initially populated; may be {@code null}
     */
    public VPTree(final DistanceFunction<P> distanceFunction, final Collection<E> points) {
        this(distanceFunction, new SamplingMedianDistanceThresholdSelectionStrategy<P, E>(
// Path: src/main/java/com/eatthepath/jvptree/util/SamplingMedianDistanceThresholdSelectionStrategy.java
// public class SamplingMedianDistanceThresholdSelectionStrategy<P, E extends P> extends MedianDistanceThresholdSelectionStrategy<P, E> implements ThresholdSelectionStrategy<P, E> {
// 
//     private final int numberOfSamples;
// 
//     public static final int DEFAULT_NUMBER_OF_SAMPLES = 32;
// 
//     /**
//      * Constructs a threshold selector that uses up to a default ({@value DEFAULT_NUMBER_OF_SAMPLES}) number of samples
//      * from a list of points to choose a median distance.
//      */
//     public SamplingMedianDistanceThresholdSelectionStrategy() {
//         this(DEFAULT_NUMBER_OF_SAMPLES);
//     }
// 
//     /**
//      * Constructs a threshold selector that uses up to the given number of samples from a list of points to choose a
//      * median distance.
//      *
//      * @param numberOfSamples the maximum number of samples to use when choosing a median distance
//      */
//     public SamplingMedianDistanceThresholdSelectionStrategy(final int numberOfSamples) {
//         this.numberOfSamples = numberOfSamples;
//     }
// 
//     /**
//      * Returns the median distance of a subset of the given points from the given origin. The given list of points may
//      * be partially sorted in the process.
//      *
//      * @param points the list of points from which a median distance will be chosen
//      * @param origin the point from which distances to other points will be calculated
//      * @param distanceFunction the function to be used to calculate the distance between the origin and other points
//      *
//      * @return the median distance from the origin to the given list of points
//      */
//     @Override
//     public double selectThreshold(final List<E> points, final P origin, final DistanceFunction<P> distanceFunction) {
//         return super.selectThreshold(this.getSampledPoints(points), origin, distanceFunction);
//     }
// 
//     /**
//      * Chooses a subset of points from which to calculate a median by sampling the given list.
//      *
//      * @param points the points from which to choose a subset of points
//      *
//      * @return a list containing at most the number of points chosen at construction time
//      */
//     List<E> getSampledPoints(final List<E> points) {
//         final List<E> sampledPoints;
// 
//         if (points.size() > this.numberOfSamples) {
//             sampledPoints = new ArrayList<>(this.numberOfSamples);
//             final int step = points.size() / this.numberOfSamples;
// 
//             for (int i = 0; i < this.numberOfSamples; i++) {
//                 sampledPoints.add(points.get(i * step));
//             }
//         } else {
//             sampledPoints = points;
//         }
// 
//         return sampledPoints;
//     }
// }


// Path: src/main/java/com/eatthepath/jvptree/VPTree.java
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import com.eatthepath.jvptree.util.SamplingMedianDistanceThresholdSelectionStrategy;

package com.eatthepath.jvptree;



/**
 * <p>A vantage-point tree (or vp-tree) is a binary space partitioning collection of points in a metric space. The main
 * feature of vantage point trees is that they allow for k-nearest-neighbor searches in any metric space in
 * <em>O(log(n))</em> time.</p>
 *
 * <p>Vantage point trees recursively partition points by choosing a &quot;vantage point&quot; and a distance threshold;
 * points are then partitioned into one collection that contains all of the points closer to the vantage point than the
 * chosen threshold and one collection that contains all of the points farther away than the chosen threshold.</p>
 *
 * <p>A {@linkplain DistanceFunction distance function} that satisfies the properties of a metric space must be provided
 * when constructing a vantage point tree. Callers may also specify a threshold selection strategy (a sampling median
 * strategy is used by default) and a node size to tune the ratio of nodes searched to points inspected per node.
 * Vantage point trees may be constructed with or without an initial collection of points, though specifying a
 * collection of points at construction time is the most efficient approach.</p>
 *
 * @author <a href="https://github.com/jchambers">Jon Chambers</a>
 *
 * @param <P> the base type of points between which distances can be measured
 * @param <E> the specific type of point contained in this vantage point tree
 */
public class VPTree<P, E extends P> implements SpatialIndex<P, E> {

    private final DistanceFunction<P> distanceFunction;
    private final ThresholdSelectionStrategy<P, E> thresholdSelectionStrategy;
    private final int nodeCapacity;

    private VPTreeNode<P, E> rootNode;

    public static final int DEFAULT_NODE_CAPACITY = 32;

    private static final PointFilter<Object> NO_OP_POINT_FILTER = new PointFilter<Object>() {

        @Override
        public boolean allowPoint(final Object point) {
            return true;
        }
    };

    /**
     * Constructs a new vp-tree that uses the given distance function and is initially empty. The constructed tree will
     * use a default {@link SamplingMedianDistanceThresholdSelectionStrategy} and node capacity
     * ({@value VPTree#DEFAULT_NODE_CAPACITY} points).
     *
     * @param distanceFunction the distance function to use to calculate the distance between points
     */
    public VPTree(final DistanceFunction<P> distanceFunction) {
        this(distanceFunction, (Collection<E>) null);
    }

    /**
     * Constructs a new vp-tree that uses the given distance function and is initially populated with the given
     * collection of points. The constructed tree will use a default
     * {@link SamplingMedianDistanceThresholdSelectionStrategy} and node capacity
     * ({@value VPTree#DEFAULT_NODE_CAPACITY} points).
     *
     * @param distanceFunction the distance function to use to calculate the distance between points
     * @param points the points with which this tree should be initially populated; may be {@code null}
     */
    public VPTree(final DistanceFunction<P> distanceFunction, final Collection<E> points) {
        this(distanceFunction, new SamplingMedianDistanceThresholdSelectionStrategy<P, E>(
                SamplingMedianDistanceThresholdSelectionStrategy.DEFAULT_NUMBER_OF_SAMPLES),