public static <T, S extends Geometry> Entry<T,S> entry(T object, S geometry) {
    return EntryDefault.entry(object, geometry);
} public static Circle circle(double x, double y, double radius) {
    return CircleDouble.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 Point point(double x, double y) {
    return PointDouble.create(x, y);
} public static Rectangle rectangle(double x1, double y1, double x2, double y2) {
    return rectangleDouble(x1, y1, x2, y2);
} public static final Func2<Point, Circle, Boolean> pointIntersectsCircle = new Func2<Point, Circle, Boolean>() {
    @Override
    public Boolean call(Point point, Circle circle) {
        return circleIntersectsPoint.call(circle, point);
    }
}; public static final Func2<Rectangle, Circle, Boolean> rectangleIntersectsCircle = new Func2<Rectangle, Circle, Boolean>() {
    @Override
    public Boolean call(Rectangle rectangle, Circle circle) {
        return circleIntersectsRectangle.call(circle, rectangle);
    }
}; public final class FactoryFlatBuffers<T, S extends Geometry> implements Factory<T, S> {
    private final Func1<? super T, byte[]> serializer;
    private final Func1<byte[], ? extends T> deserializer;

    public FactoryFlatBuffers(Func1<? super T, byte[]> serializer, Func1<byte[], ? extends T> deserializer) {
        Preconditions.checkNotNull(serializer);
        Preconditions.checkNotNull(deserializer);
        this.serializer = serializer;
        this.deserializer = deserializer;
    }

    @Override
    public Leaf<T, S> createLeaf(List<Entry<T, S>> entries, Context<T, S> context) {
        return new LeafFlatBuffers<T, S>(entries, context, serializer, deserializer);
    }

    @Override
    public NonLeaf<T, S> createNonLeaf(List<? extends Node<T, S>> children, Context<T, S> context) {
        return new NonLeafDefault<T, S>(children, context);
    }

    @Override
    public Entry<T, S> createEntry(T value, S geometry) {
        return Entries.entry(value, geometry);
    }

    public Func1<? super T, byte[]> serializer() {
        return serializer;
    }

    public Func1<byte[], ? extends T> deserializer() {
        return deserializer;
    }

} public interface Circle extends Geometry {

    double x();

    double y();

    double radius();

    boolean intersects(Circle c);

    boolean intersects(Point point);

    boolean intersects(Line line);

} 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;
        }
    }

} 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();
} public final class Intersects {

    private Intersects() {
        // prevent instantiation
    }

    public static final Func2<Rectangle, Circle, Boolean> rectangleIntersectsCircle = new Func2<Rectangle, Circle, Boolean>() {
        @Override
        public Boolean call(Rectangle rectangle, Circle circle) {
            return circleIntersectsRectangle.call(circle, rectangle);
        }
    };

    public static final Func2<Circle, Rectangle, Boolean> circleIntersectsRectangle = new Func2<Circle, Rectangle, Boolean>() {
        @Override
        public Boolean call(Circle circle, Rectangle rectangle) {
            return circle.intersects(rectangle);
        }
    };

    public static final Func2<Point, Circle, Boolean> pointIntersectsCircle = new Func2<Point, Circle, Boolean>() {
        @Override
        public Boolean call(Point point, Circle circle) {
            return circleIntersectsPoint.call(circle, point);
        }
    };

    public static final Func2<Circle, Point, Boolean> circleIntersectsPoint = new Func2<Circle, Point, Boolean>() {
        @Override
        public Boolean call(Circle circle, Point point) {
            return circle.intersects(point);
        }
    };

    public static final Func2<Circle, Circle, Boolean> circleIntersectsCircle = new Func2<Circle, Circle, Boolean>() {
        @Override
        public Boolean call(Circle a, Circle b) {
            return a.intersects(b);
        }
    };

    public static final Func2<Line, Line, Boolean> lineIntersectsLine = new Func2<Line, Line, Boolean>() {
        @Override
        public Boolean call(Line a, Line b) {
            return a.intersects(b);
        }
    };

    public static final Func2<Line, Rectangle, Boolean> lineIntersectsRectangle = new Func2<Line, Rectangle, Boolean>() {
        @Override
        public Boolean call(Line a, Rectangle r) {
            return rectangleIntersectsLine.call(r, a);
        }
    };

    public static final Func2<Rectangle, Line, Boolean> rectangleIntersectsLine = new Func2<Rectangle, Line, Boolean>() {
        @Override
        public Boolean call(Rectangle r, Line a) {
            return a.intersects(r);
        }
    };

    public static final Func2<Line, Circle, Boolean> lineIntersectsCircle = new Func2<Line, Circle, Boolean>() {
        @Override
        public Boolean call(Line a, Circle c) {
            return circleIntersectsLine.call(c, a);
        }
    };

    public static final Func2<Circle, Line, Boolean> circleIntersectsLine = new Func2<Circle, Line, Boolean>() {
        @Override
        public Boolean call(Circle c, Line a) {
            return a.intersects(c);
        }
    };

    public static final Func2<Line, Point, Boolean> lineIntersectsPoint = new Func2<Line, Point, Boolean>() {

        @Override
        public Boolean call(Line line, Point point) {
            return pointIntersectsLine.call(point, line);
        }
    };

    public static final Func2<Point, Line, Boolean> pointIntersectsLine = new Func2<Point, Line, Boolean>() {

        @Override
        public Boolean call(Point point, Line line) {
            return line.intersects(point);
        }
    };

    public static final Func2<Geometry, Line, Boolean> geometryIntersectsLine = new Func2<Geometry, Line, Boolean>() {

        @Override
        public Boolean call(Geometry geometry, Line line) {
            if (geometry instanceof Line)
                return line.intersects((Line) geometry);
            else if (geometry instanceof Circle)
                return line.intersects((Circle) geometry);
            else if (geometry instanceof Point)
                return line.intersects((Point) geometry);
            else if (geometry instanceof Rectangle)
                return line.intersects((Rectangle) geometry);
            else
                throw new RuntimeException("unrecognized geometry: " + geometry);
        }
    };

    public static final Func2<Geometry, Circle, Boolean> geometryIntersectsCircle = new Func2<Geometry, Circle, Boolean>() {

        @Override
        public Boolean call(Geometry geometry, Circle circle) {
            if (geometry instanceof Line)
                return circle.intersects((Line) geometry);
            else if (geometry instanceof Circle)
                return circle.intersects((Circle) geometry);
            else if (geometry instanceof Point)
                return circle.intersects((Point) geometry);
            else if (geometry instanceof Rectangle)
                return circle.intersects((Rectangle) geometry);
            else
                throw new RuntimeException("unrecognized geometry: " + geometry);
        }
    };

    public static final Func2<Circle, Geometry, Boolean> circleIntersectsGeometry = new Func2<Circle, Geometry, Boolean>() {

        @Override
        public Boolean call(Circle circle, Geometry geometry) {
            return geometryIntersectsCircle.call(geometry, circle);
        }
    };

    public static final Func2<Geometry, Rectangle, Boolean> geometryIntersectsRectangle = new Func2<Geometry, Rectangle, Boolean>() {

        @Override
        public Boolean call(Geometry geometry, Rectangle r) {
            if (geometry instanceof Line)
                return geometry.intersects(r);
            else if (geometry instanceof Circle)
                return geometry.intersects(r);
            else if (geometry instanceof Point)
                return geometry.intersects(r);
            else if (geometry instanceof Rectangle)
                return r.intersects((Rectangle) geometry);
            else
                throw new RuntimeException("unrecognized geometry: " + geometry);
        }
    };

    public static final Func2<Rectangle, Geometry, Boolean> rectangleIntersectsGeometry = new Func2<Rectangle, Geometry, Boolean>() {

        @Override
        public Boolean call(Rectangle r, Geometry geometry) {
            return geometryIntersectsRectangle.call(geometry, r);
        }
    };

    public static final Func2<Geometry, Point, Boolean> geometryIntersectsPoint = new Func2<Geometry, Point, Boolean>() {

        @Override
        public Boolean call(Geometry geometry, Point point) {
            return geometryIntersectsRectangle.call(geometry, point.mbr());
        }
    };

    public static final Func2<Point, Geometry, Boolean> pointIntersectsGeometry = new Func2<Point, Geometry, Boolean>() {

        @Override
        public Boolean call(Point point, Geometry geometry) {
            return geometryIntersectsPoint.call(geometry, point);
        }
    };

} public interface Point extends Rectangle {

    double x();

    double y();

} 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();

} public final class EntryDefault<T, S extends Geometry> implements Entry<T, S> {
    private final T value;
    private final S geometry;

    /**
     * Constructor.
     * 
     * @param value
     *            the value of the entry
     * @param geometry
     *            the geometry of the value
     */
    public EntryDefault(T value, S geometry) {
        Preconditions.checkNotNull(geometry);
        this.value = value;
        this.geometry = geometry;
    }

    /**
     * Factory method.
     * 
     * @param <T>
     *            type of value
     * @param <S>
     *            type of geometry
     * @param value
     *            object being given a spatial context
     * @param geometry
     *            geometry associated with the value
     * @return entry wrapping value and associated geometry
     */
    public static <T, S extends Geometry> Entry<T, S> entry(T value, S geometry) {
        return new EntryDefault<T, S>(value, geometry);
    }

    /**
     * Returns the value wrapped by this {@link EntryDefault}.
     * 
     * @return the entry value
     */
    @Override
    public T value() {
        return value;
    }

    @Override
    public S geometry() {
        return geometry;
    }

    @Override
    public String toString() {
        String builder = "Entry [value=" + value + ", geometry=" + geometry + "]";
        return builder;
    }

    @Override
    public int hashCode() {
        return Objects.hash(value, geometry);
    }

    @Override
    public boolean equals(Object obj) {
        @SuppressWarnings("rawtypes")
        Optional<EntryDefault> other = ObjectsHelper.asClass(obj, EntryDefault.class);
        if (other.isPresent()) {
            return Objects.equals(value, other.get().value)
                    && Objects.equals(geometry, other.get().geometry);
        } else
            return false;
    }

} public final class Functions {

    private Functions() {
        // prevent instantiation
    }
    
    public static <T> Func1<T, T> identity() {
        return t -> t;
    }

    public static <T> Func1<T, Boolean> alwaysTrue() {
        return t -> true;
    }

    public static <T> Func1<T, Boolean> alwaysFalse() {
        return t -> false;
    }
    
}
import static com.github.davidmoten.rtree.Entries.entry;
import static com.github.davidmoten.rtree.geometry.Geometries.circle;
import static com.github.davidmoten.rtree.geometry.Geometries.line;
import static com.github.davidmoten.rtree.geometry.Geometries.point;
import static com.github.davidmoten.rtree.geometry.Geometries.rectangle;
import static com.github.davidmoten.rtree.geometry.Intersects.pointIntersectsCircle;
import static com.github.davidmoten.rtree.geometry.Intersects.rectangleIntersectsCircle;
import static java.util.Arrays.asList;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertNotNull;
import static org.junit.Assert.assertTrue;
import java.io.File;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.nio.channels.FileLock;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Optional;
import java.util.Set;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;
import org.junit.Test;
import com.github.davidmoten.guavamini.Lists;
import com.github.davidmoten.guavamini.Sets;
import com.github.davidmoten.rtree.fbs.FactoryFlatBuffers;
import com.github.davidmoten.rtree.geometry.Circle;
import com.github.davidmoten.rtree.geometry.Geometries;
import com.github.davidmoten.rtree.geometry.Geometry;
import com.github.davidmoten.rtree.geometry.HasGeometry;
import com.github.davidmoten.rtree.geometry.Intersects;
import com.github.davidmoten.rtree.geometry.Point;
import com.github.davidmoten.rtree.geometry.Rectangle;
import com.github.davidmoten.rtree.internal.EntryDefault;
import com.github.davidmoten.rtree.internal.Functions;
import rx.Observable;
import rx.Subscriber;
import rx.functions.Action1;
import rx.functions.Func1;
import rx.functions.Func2;
import rx.observables.GroupedObservable;
package com.github.davidmoten.rtree;






public class RTreeTest {

    private static final double PRECISION = 0.000001;

    @Test
    public void testInstantiation() {
        RTree<Object, Geometry> tree = RTree.create();
        assertTrue(tree.entries().isEmpty().toBlocking().single());
    }

    @Test
    public void testSearchEmptyTree() {
        RTree<Object, Geometry> tree = RTree.create();
        assertTrue(tree.search(r(1)).isEmpty().toBlocking().single());
    }

    @Test
    public void testSearchOnOneItem() {
        RTree<Object, Rectangle> tree = RTree.create();
        Entry<Object, Rectangle> entry = e(1);
        tree = tree.add(entry);
        assertEquals(Arrays.asList(entry), tree.search(r(1)).toList().toBlocking().single());
    }

    @Test
    public void testTreeWithOneItemIsNotEmpty() {
        RTree<Object, Geometry> tree = RTree.create().add(e(1));
        assertFalse(tree.isEmpty());
    }

    // @Test(expected = IOException.class)
    public void testSaveFileException() throws IOException {
        FileLock lock = null;
        RandomAccessFile file = null;
        try {
            String filename = "target/locked.png";
            File f = new File(filename);
            f.createNewFile();
            file = new RandomAccessFile(f, "rw");
            lock = file.getChannel().lock();
            RTree.create().visualize(600, 600).save(filename, "PNG");
        } finally {
            try {
                lock.release();
                file.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

    @Test
    public void testVisualizerWithEmptyTree() {
        RTree<Object, Geometry> tree = RTree.create();
        tree.visualize(600, 600).save("target/tree.png", "PNG");
    }

    @Test
    public void testBulkLoadingEmpty() {
        RTree<Object, Point> tree = RTree.create(new ArrayList<Entry<Object, Point>>());
        assertTrue(tree.entries().isEmpty().toBlocking().single());
    }

    @Test
    public void testBulkLoadingWithOneItemIsNotEmpty() {
        RTree<Object, Rectangle> tree = RTree.create(Arrays.asList(e(1)));
        assertFalse(tree.isEmpty());
    }

    @Test
    public void testBulkLoadingEntryCount() {
        List<Entry<Integer, Geometry>> entries = new ArrayList<Entry<Integer, Geometry>>(10000);
        for (int i = 1; i <= 10000; i++) {
            Point point = nextPoint();
            // System.out.println("point(" + point.x() + "," + point.y() +
            // "),");
            entries.add(new EntryDefault<Integer, Geometry>(i, point));
        }
        RTree<Integer, Geometry> tree = RTree.create(entries);
        int entrySize = tree.entries().count().toBlocking().single();
        System.out.println("entry count: " + entrySize);
        assertEquals(entrySize, entries.size());
    }

    @Test
    public void testSearchOnOneItemOnBulkLoadingRTree() {
        Entry<Object, Rectangle> entry = e(1);
        RTree<Object, Rectangle> tree = RTree.create(Arrays.asList(entry));
        assertEquals(Arrays.asList(entry), tree.search(r(1)).toList().toBlocking().single());
    }

    @Test
    public void testAddObservable() {
        Entry<Object, Rectangle> e1 = e(1);
        Entry<Object, Rectangle> e2 = e2(1);

        RTree<Object, Rectangle> tree = RTree.maxChildren(4).<Object, Rectangle>create().add(e1)
                .add(e2).delete(e1);
        RTree<Object, Rectangle> emptyTree = RTree.maxChildren(4).create();
        rx.Observable<?> deletedtree = emptyTree.add(tree.entries());
        assertEquals(2, (int) deletedtree.count().toBlocking().single());
    }

    @Test
    public void testPerformanceAndEntriesCount() {

        long repeats = Long.parseLong(System.getProperty("r", "1"));
        long n = Long.parseLong(System.getProperty("n", "10000"));
        RTree<Object, Geometry> tree = null;
        while (--repeats >= 0) {
            long t = System.currentTimeMillis();
            tree = createRandomRTree(n);
            long diff = System.currentTimeMillis() - t;
            System.out.println("inserts/second = " + ((double) n / diff * 1000));
        }
        assertEquals(n, (int) tree.entries().count().toBlocking().single());

        long t = System.currentTimeMillis();
        Entry<Object, Geometry> entry = tree.search(rectangle(0, 0, 500, 500)).first().toBlocking()