// Path: src/main/java/com/eatthepath/jvptree/DistanceFunction.java
// public interface DistanceFunction<T> {
// 
//     /**
//      * Returns the distance between two points.
//      *
//      * @param firstPoint the first point
//      * @param secondPoint the second point
//      *
//      * @return the distance between the two points
//      */
//     double getDistance(T firstPoint, T secondPoint);
// }
// 
// Path: src/main/java/com/eatthepath/jvptree/ThresholdSelectionStrategy.java
// public interface ThresholdSelectionStrategy<P, E extends P> {
// 
//     /**
//      * Chooses a partitioning distance threshold appropriate for the given list of points. Implementations are allowed to
//      * reorder the list of points, but must not add or remove points from the list.
//      *
//      * @param points the points for which to choose a partitioning distance threshold
//      * @param origin the point from which the threshold distances should be calculated
//      * @param distanceFunction the function to be used to calculate distances between points
//      *
//      * @return a partitioning threshold distance appropriate for the given list of points; ideally, some points should
//      * be closer to the origin than the returned threshold, and some should be farther
//      */
//     double selectThreshold(List<E> points, P origin, DistanceFunction<P> distanceFunction);
// }


import java.util.ArrayList;
import java.util.List;
import com.eatthepath.jvptree.DistanceFunction;
import com.eatthepath.jvptree.ThresholdSelectionStrategy;
package com.eatthepath.jvptree.util;



/**
 * A threshold distance selection strategy that uses the median distance from the origin to a subset of the given list
 * of points as the threshold.
 *
 * @author <a href="https://github.com/jchambers">Jon Chambers</a>
 */
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
// Path: src/main/java/com/eatthepath/jvptree/DistanceFunction.java
// public interface DistanceFunction<T> {
// 
//     /**
//      * Returns the distance between two points.
//      *
//      * @param firstPoint the first point
//      * @param secondPoint the second point
//      *
//      * @return the distance between the two points
//      */
//     double getDistance(T firstPoint, T secondPoint);
// }
// 
// Path: src/main/java/com/eatthepath/jvptree/ThresholdSelectionStrategy.java
// public interface ThresholdSelectionStrategy<P, E extends P> {
// 
//     /**
//      * Chooses a partitioning distance threshold appropriate for the given list of points. Implementations are allowed to
//      * reorder the list of points, but must not add or remove points from the list.
//      *
//      * @param points the points for which to choose a partitioning distance threshold
//      * @param origin the point from which the threshold distances should be calculated
//      * @param distanceFunction the function to be used to calculate distances between points
//      *
//      * @return a partitioning threshold distance appropriate for the given list of points; ideally, some points should
//      * be closer to the origin than the returned threshold, and some should be farther
//      */
//     double selectThreshold(List<E> points, P origin, DistanceFunction<P> distanceFunction);
// }


// Path: src/main/java/com/eatthepath/jvptree/util/SamplingMedianDistanceThresholdSelectionStrategy.java
import java.util.ArrayList;
import java.util.List;
import com.eatthepath.jvptree.DistanceFunction;
import com.eatthepath.jvptree.ThresholdSelectionStrategy;

package com.eatthepath.jvptree.util;



/**
 * A threshold distance selection strategy that uses the median distance from the origin to a subset of the given list
 * of points as the threshold.
 *
 * @author <a href="https://github.com/jchambers">Jon Chambers</a>
 */
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) {