// Path: src/main/java/com/github/davidmoten/rtree/geometry/Geometry.java
// public interface Geometry {
// 
//     /**
//      * <p>
//      * Returns the distance to the given {@link Rectangle}. For a {@link Rectangle}
//      * this might be Euclidean distance but for an EPSG4326 lat-long Rectangle might
//      * be great-circle distance. The distance function should satisfy the following
//      * properties:
//      * </p>
//      * 
//      * <p>
//      * <code>distance(r) &gt;= 0</code>
//      * </p>
//      * 
//      * <p>
//      * <code>if r1 contains r2 then distance(r1)&lt;=distance(r2)</code>
//      * </p>
//      * 
//      * 
//      * @param r
//      *            rectangle to measure distance to
//      * @return distance to the rectangle r from the geometry
//      */
//     double distance(Rectangle r);
// 
//     /**
//      * Returns the minimum bounding rectangle of this geometry.
//      * 
//      * @return minimum bounding rectangle
//      */
//     Rectangle mbr();
// 
//     boolean intersects(Rectangle r);
// 
//     boolean isDoublePrecision();
// }
// 
// Path: src/main/java/com/github/davidmoten/rtree/internal/Comparators.java
// public final class Comparators {
// 
//     private Comparators() {
//         // prevent instantiation
//     }
// 
//     public static <T extends HasGeometry> Comparator<HasGeometry> overlapAreaThenAreaIncreaseThenAreaComparator(
//             final Rectangle r, final List<T> list) {
//         return new Comparator<HasGeometry>() {
// 
//             @Override
//             public int compare(HasGeometry g1, HasGeometry g2) {
//                 int value = Double.compare(overlapArea(r, list, g1), overlapArea(r, list, g2));
//                 if (value == 0) {
//                     value = Double.compare(areaIncrease(r, g1), areaIncrease(r, g2));
//                     if (value == 0) {
//                         value = Double.compare(area(r, g1), area(r, g2));
//                     }
//                 }
//                 return value;
//             }
//         };
//     }
// 
//     private static double area(final Rectangle r, HasGeometry g1) {
//         return g1.geometry().mbr().add(r).area();
//     }
// 
//     public static <T extends HasGeometry> Comparator<HasGeometry> areaIncreaseThenAreaComparator(
//             final Rectangle r) {
//         return new Comparator<HasGeometry>() {
//             @Override
//             public int compare(HasGeometry g1, HasGeometry g2) {
//                 int value = Double.compare(areaIncrease(r, g1), areaIncrease(r, g2));
//                 if (value == 0) {
//                     value = Double.compare(area(r, g1), area(r, g2));
//                 }
//                 return value;
//             }
//         };
//     }
// 
//     private static float overlapArea(Rectangle r, List<? extends HasGeometry> list, HasGeometry g) {
//         Rectangle gPlusR = g.geometry().mbr().add(r);
//         float m = 0;
//         for (HasGeometry other : list) {
//             if (other != g) {
//                 m += gPlusR.intersectionArea(other.geometry().mbr());
//             }
//         }
//         return m;
//     }
// 
//     private static double areaIncrease(Rectangle r, HasGeometry g) {
//         Rectangle gPlusR = g.geometry().mbr().add(r);
//         return gPlusR.area() - g.geometry().mbr().area();
//     }
// 
//     /**
//      * <p>
//      * Returns a comparator that can be used to sort entries returned by search
//      * methods. For example:
//      * </p>
//      * <p>
//      * <code>search(100).toSortedList(ascendingDistance(r))</code>
//      * </p>
//      * 
//      * @param <T>
//      *            the value type
//      * @param <S>
//      *            the entry type
//      * @param r
//      *            rectangle to measure distance to
//      * @return a comparator to sort by ascending distance from the rectangle
//      */
//     public static <T, S extends Geometry> Comparator<Entry<T, S>> ascendingDistance(
//             final Rectangle r) {
//         return new Comparator<Entry<T, S>>() {
//             @Override
//             public int compare(Entry<T, S> e1, Entry<T, S> e2) {
//                 return Double.compare(e1.geometry().distance(r), e2.geometry().distance(r));
//             }
//         };
//     }
// 
// }


import static java.util.Collections.min;
import java.util.List;
import com.github.davidmoten.rtree.geometry.Geometry;
import com.github.davidmoten.rtree.internal.Comparators;
package com.github.davidmoten.rtree;




/**
 * Uses minimal area increase to select a node from a list.
 *
 */
public final class SelectorMinimalAreaIncrease implements Selector {

    @Override
// Path: src/main/java/com/github/davidmoten/rtree/geometry/Geometry.java
// public interface Geometry {
// 
//     /**
//      * <p>
//      * Returns the distance to the given {@link Rectangle}. For a {@link Rectangle}
//      * this might be Euclidean distance but for an EPSG4326 lat-long Rectangle might
//      * be great-circle distance. The distance function should satisfy the following
//      * properties:
//      * </p>
//      * 
//      * <p>
//      * <code>distance(r) &gt;= 0</code>
//      * </p>
//      * 
//      * <p>
//      * <code>if r1 contains r2 then distance(r1)&lt;=distance(r2)</code>
//      * </p>
//      * 
//      * 
//      * @param r
//      *            rectangle to measure distance to
//      * @return distance to the rectangle r from the geometry
//      */
//     double distance(Rectangle r);
// 
//     /**
//      * Returns the minimum bounding rectangle of this geometry.
//      * 
//      * @return minimum bounding rectangle
//      */
//     Rectangle mbr();
// 
//     boolean intersects(Rectangle r);
// 
//     boolean isDoublePrecision();
// }
// 
// Path: src/main/java/com/github/davidmoten/rtree/internal/Comparators.java
// public final class Comparators {
// 
//     private Comparators() {
//         // prevent instantiation
//     }
// 
//     public static <T extends HasGeometry> Comparator<HasGeometry> overlapAreaThenAreaIncreaseThenAreaComparator(
//             final Rectangle r, final List<T> list) {
//         return new Comparator<HasGeometry>() {
// 
//             @Override
//             public int compare(HasGeometry g1, HasGeometry g2) {
//                 int value = Double.compare(overlapArea(r, list, g1), overlapArea(r, list, g2));
//                 if (value == 0) {
//                     value = Double.compare(areaIncrease(r, g1), areaIncrease(r, g2));
//                     if (value == 0) {
//                         value = Double.compare(area(r, g1), area(r, g2));
//                     }
//                 }
//                 return value;
//             }
//         };
//     }
// 
//     private static double area(final Rectangle r, HasGeometry g1) {
//         return g1.geometry().mbr().add(r).area();
//     }
// 
//     public static <T extends HasGeometry> Comparator<HasGeometry> areaIncreaseThenAreaComparator(
//             final Rectangle r) {
//         return new Comparator<HasGeometry>() {
//             @Override
//             public int compare(HasGeometry g1, HasGeometry g2) {
//                 int value = Double.compare(areaIncrease(r, g1), areaIncrease(r, g2));
//                 if (value == 0) {
//                     value = Double.compare(area(r, g1), area(r, g2));
//                 }
//                 return value;
//             }
//         };
//     }
// 
//     private static float overlapArea(Rectangle r, List<? extends HasGeometry> list, HasGeometry g) {
//         Rectangle gPlusR = g.geometry().mbr().add(r);
//         float m = 0;
//         for (HasGeometry other : list) {
//             if (other != g) {
//                 m += gPlusR.intersectionArea(other.geometry().mbr());
//             }
//         }
//         return m;
//     }
// 
//     private static double areaIncrease(Rectangle r, HasGeometry g) {
//         Rectangle gPlusR = g.geometry().mbr().add(r);
//         return gPlusR.area() - g.geometry().mbr().area();
//     }
// 
//     /**
//      * <p>
//      * Returns a comparator that can be used to sort entries returned by search
//      * methods. For example:
//      * </p>
//      * <p>
//      * <code>search(100).toSortedList(ascendingDistance(r))</code>
//      * </p>
//      * 
//      * @param <T>
//      *            the value type
//      * @param <S>
//      *            the entry type
//      * @param r
//      *            rectangle to measure distance to
//      * @return a comparator to sort by ascending distance from the rectangle
//      */
//     public static <T, S extends Geometry> Comparator<Entry<T, S>> ascendingDistance(
//             final Rectangle r) {
//         return new Comparator<Entry<T, S>>() {
//             @Override
//             public int compare(Entry<T, S> e1, Entry<T, S> e2) {
//                 return Double.compare(e1.geometry().distance(r), e2.geometry().distance(r));
//             }
//         };
//     }
// 
// }


// Path: src/main/java/com/github/davidmoten/rtree/SelectorMinimalAreaIncrease.java
import static java.util.Collections.min;
import java.util.List;
import com.github.davidmoten.rtree.geometry.Geometry;
import com.github.davidmoten.rtree.internal.Comparators;

package com.github.davidmoten.rtree;




/**
 * Uses minimal area increase to select a node from a list.
 *
 */
public final class SelectorMinimalAreaIncrease implements Selector {

    @Override
    public <T, S extends Geometry> Node<T, S> select(Geometry g, List<? extends Node<T, S>> nodes) {