// Path: src/main/java/com/github/davidmoten/rtree/geometry/Geometries.java
// public final class Geometries {
// 
//     private Geometries() {
//         // prevent instantiation
//     }
// 
//     public static Point point(double x, double y) {
//         return PointDouble.create(x, y);
//     }
// 
//     public static Point point(float x, float y) {
//         return PointFloat.create(x, y);
//     }
// 
//     public static Point pointGeographic(double lon, double lat) {
//         return point(normalizeLongitudeDouble(lon), lat);
//     }
// 
//     public static Point pointGeographic(float lon, float lat) {
//         return point(normalizeLongitude(lon), lat);
//     }
// 
//     public static Rectangle rectangle(double x1, double y1, double x2, double y2) {
//         return rectangleDouble(x1, y1, x2, y2);
//     }
// 
//     public static Rectangle rectangle(float x1, float y1, float x2, float y2) {
//         return RectangleFloat.create(x1, y1, x2, y2);
//     }
// 
//     public static Rectangle rectangleGeographic(double lon1, double lat1, double lon2,
//             double lat2) {
//         return rectangleGeographic((float) lon1, (float) lat1, (float) lon2, (float) lat2);
//     }
// 
//     public static Rectangle rectangleGeographic(float lon1, float lat1, float lon2, float lat2) {
//         float x1 = normalizeLongitude(lon1);
//         float x2 = normalizeLongitude(lon2);
//         if (x2 < x1) {
//             x2 += 360;
//         }
//         return rectangle(x1, lat1, x2, lat2);
//     }
// 
//     private static Rectangle rectangleDouble(double x1, double y1, double x2, double y2) {
//         return  RectangleDouble.create(x1, y1, x2, y2);
//     }
// 
//     public static Circle circle(double x, double y, double radius) {
//         return CircleDouble.create(x, y, radius);
//     }
// 
//     public static Circle circle(float x, float y, float radius) {
//         return CircleFloat.create(x, y, radius);
//     }
// 
//     public static Line line(double x1, double y1, double x2, double y2) {
//         return LineDouble.create(x1, y1, x2, y2);
//     }
// 
//     public static Line line(float x1, float y1, float x2, float y2) {
//         return LineFloat.create(x1, y1, x2, y2);
//     }
// 
//     @VisibleForTesting
//     static double normalizeLongitude(double d) {
//         return normalizeLongitude((float) d);
//     }
// 
//     private static float normalizeLongitude(float d) {
//         if (d == -180.0f)
//             return -180.0f;
//         else {
//             float sign = Math.signum(d);
//             float x = Math.abs(d) / 360;
//             float x2 = (x - (float) Math.floor(x)) * 360;
//             if (x2 >= 180)
//                 x2 -= 360;
//             return x2 * sign;
//         }
//     }
// 
//     private static double normalizeLongitudeDouble(double d) {
//         if (d == -180.0f)
//             return -180.0d;
//         else {
//             double sign = Math.signum(d);
//             double x = Math.abs(d) / 360;
//             double x2 = (x - (float) Math.floor(x)) * 360;
//             if (x2 >= 180)
//                 x2 -= 360;
//             return x2 * sign;
//         }
//     }
// 
// }
// 
// Path: src/main/java/com/github/davidmoten/rtree/geometry/Rectangle.java
// public interface Rectangle extends Geometry, HasGeometry {
// 
//     double x1();
// 
//     double y1();
// 
//     double x2();
// 
//     double y2();
// 
//     double area();
// 
//     double intersectionArea(Rectangle r);
// 
//     double perimeter();
// 
//     Rectangle add(Rectangle r);
// 
//     boolean contains(double x, double y);
//     
//     boolean isDoublePrecision();
// 
// }


import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import com.github.davidmoten.guavamini.Preconditions;
import com.github.davidmoten.rtree.geometry.Geometries;
import com.github.davidmoten.rtree.geometry.HasGeometry;
import com.github.davidmoten.rtree.geometry.Rectangle;
package com.github.davidmoten.rtree.internal;



/**
 * @author dxm
 *
 */
public final class Util {

    private Util() {
        // prevent instantiation
    }

    /**
     * Returns the minimum bounding rectangle of a number of items. Benchmarks below
     * indicate that when the number of items is &gt;1 this method is more
     * performant than one using {@link Rectangle#add(Rectangle)}.
     * 
     * <pre>
     * Benchmark                             Mode  Samples         Score  Score error  Units
     * c.g.d.r.BenchmarksMbr.mbrList1       thrpt       10  48450492.301   436127.960  ops/s
     * c.g.d.r.BenchmarksMbr.mbrList2       thrpt       10  46658242.728   987901.581  ops/s
     * c.g.d.r.BenchmarksMbr.mbrList3       thrpt       10  40357809.306   937827.660  ops/s
     * c.g.d.r.BenchmarksMbr.mbrList4       thrpt       10  35930532.557   605535.237  ops/s
     * c.g.d.r.BenchmarksMbr.mbrOldList1    thrpt       10  55848118.198  1342997.309  ops/s
     * c.g.d.r.BenchmarksMbr.mbrOldList2    thrpt       10  25171873.903   395127.918  ops/s
     * c.g.d.r.BenchmarksMbr.mbrOldList3    thrpt       10  19222116.139   246965.178  ops/s
     * c.g.d.r.BenchmarksMbr.mbrOldList4    thrpt       10  14891862.638   198765.157  ops/s
     * </pre>
     * 
     * @param items
     *            items to bound
     * @return the minimum bounding rectangle containings items
     */
// Path: src/main/java/com/github/davidmoten/rtree/geometry/Geometries.java
// public final class Geometries {
// 
//     private Geometries() {
//         // prevent instantiation
//     }
// 
//     public static Point point(double x, double y) {
//         return PointDouble.create(x, y);
//     }
// 
//     public static Point point(float x, float y) {
//         return PointFloat.create(x, y);
//     }
// 
//     public static Point pointGeographic(double lon, double lat) {
//         return point(normalizeLongitudeDouble(lon), lat);
//     }
// 
//     public static Point pointGeographic(float lon, float lat) {
//         return point(normalizeLongitude(lon), lat);
//     }
// 
//     public static Rectangle rectangle(double x1, double y1, double x2, double y2) {
//         return rectangleDouble(x1, y1, x2, y2);
//     }
// 
//     public static Rectangle rectangle(float x1, float y1, float x2, float y2) {
//         return RectangleFloat.create(x1, y1, x2, y2);
//     }
// 
//     public static Rectangle rectangleGeographic(double lon1, double lat1, double lon2,
//             double lat2) {
//         return rectangleGeographic((float) lon1, (float) lat1, (float) lon2, (float) lat2);
//     }
// 
//     public static Rectangle rectangleGeographic(float lon1, float lat1, float lon2, float lat2) {
//         float x1 = normalizeLongitude(lon1);
//         float x2 = normalizeLongitude(lon2);
//         if (x2 < x1) {
//             x2 += 360;
//         }
//         return rectangle(x1, lat1, x2, lat2);
//     }
// 
//     private static Rectangle rectangleDouble(double x1, double y1, double x2, double y2) {
//         return  RectangleDouble.create(x1, y1, x2, y2);
//     }
// 
//     public static Circle circle(double x, double y, double radius) {
//         return CircleDouble.create(x, y, radius);
//     }
// 
//     public static Circle circle(float x, float y, float radius) {
//         return CircleFloat.create(x, y, radius);
//     }
// 
//     public static Line line(double x1, double y1, double x2, double y2) {
//         return LineDouble.create(x1, y1, x2, y2);
//     }
// 
//     public static Line line(float x1, float y1, float x2, float y2) {
//         return LineFloat.create(x1, y1, x2, y2);
//     }
// 
//     @VisibleForTesting
//     static double normalizeLongitude(double d) {
//         return normalizeLongitude((float) d);
//     }
// 
//     private static float normalizeLongitude(float d) {
//         if (d == -180.0f)
//             return -180.0f;
//         else {
//             float sign = Math.signum(d);
//             float x = Math.abs(d) / 360;
//             float x2 = (x - (float) Math.floor(x)) * 360;
//             if (x2 >= 180)
//                 x2 -= 360;
//             return x2 * sign;
//         }
//     }
// 
//     private static double normalizeLongitudeDouble(double d) {
//         if (d == -180.0f)
//             return -180.0d;
//         else {
//             double sign = Math.signum(d);
//             double x = Math.abs(d) / 360;
//             double x2 = (x - (float) Math.floor(x)) * 360;
//             if (x2 >= 180)
//                 x2 -= 360;
//             return x2 * sign;
//         }
//     }
// 
// }
// 
// Path: src/main/java/com/github/davidmoten/rtree/geometry/Rectangle.java
// public interface Rectangle extends Geometry, HasGeometry {
// 
//     double x1();
// 
//     double y1();
// 
//     double x2();
// 
//     double y2();
// 
//     double area();
// 
//     double intersectionArea(Rectangle r);
// 
//     double perimeter();
// 
//     Rectangle add(Rectangle r);
// 
//     boolean contains(double x, double y);
//     
//     boolean isDoublePrecision();
// 
// }


// Path: src/main/java/com/github/davidmoten/rtree/internal/Util.java
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import com.github.davidmoten.guavamini.Preconditions;
import com.github.davidmoten.rtree.geometry.Geometries;
import com.github.davidmoten.rtree.geometry.HasGeometry;
import com.github.davidmoten.rtree.geometry.Rectangle;

package com.github.davidmoten.rtree.internal;



/**
 * @author dxm
 *
 */
public final class Util {

    private Util() {
        // prevent instantiation
    }

    /**
     * Returns the minimum bounding rectangle of a number of items. Benchmarks below
     * indicate that when the number of items is &gt;1 this method is more
     * performant than one using {@link Rectangle#add(Rectangle)}.
     * 
     * <pre>
     * Benchmark                             Mode  Samples         Score  Score error  Units
     * c.g.d.r.BenchmarksMbr.mbrList1       thrpt       10  48450492.301   436127.960  ops/s
     * c.g.d.r.BenchmarksMbr.mbrList2       thrpt       10  46658242.728   987901.581  ops/s
     * c.g.d.r.BenchmarksMbr.mbrList3       thrpt       10  40357809.306   937827.660  ops/s
     * c.g.d.r.BenchmarksMbr.mbrList4       thrpt       10  35930532.557   605535.237  ops/s
     * c.g.d.r.BenchmarksMbr.mbrOldList1    thrpt       10  55848118.198  1342997.309  ops/s
     * c.g.d.r.BenchmarksMbr.mbrOldList2    thrpt       10  25171873.903   395127.918  ops/s
     * c.g.d.r.BenchmarksMbr.mbrOldList3    thrpt       10  19222116.139   246965.178  ops/s
     * c.g.d.r.BenchmarksMbr.mbrOldList4    thrpt       10  14891862.638   198765.157  ops/s
     * </pre>
     * 
     * @param items
     *            items to bound
     * @return the minimum bounding rectangle containings items
     */
    public static Rectangle mbr(Collection<? extends HasGeometry> items) {