lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From nkn...@apache.org
Subject [19/34] lucene-solr git commit: LUCENE-6997: refactors lucene-spatial module to a new lucene-spatial-extras module, and refactors sandbox GeoPointField and queries to lucene-spatial module
Date Fri, 05 Feb 2016 17:05:14 GMT
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/50a2f754/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/DateNRStrategyTest.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/DateNRStrategyTest.java b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/DateNRStrategyTest.java
new file mode 100644
index 0000000..7cd4723
--- /dev/null
+++ b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/DateNRStrategyTest.java
@@ -0,0 +1,143 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.spatial.prefix;
+
+import java.io.IOException;
+import java.util.Calendar;
+
+import com.carrotsearch.randomizedtesting.annotations.Repeat;
+import com.spatial4j.core.shape.Shape;
+import org.apache.lucene.spatial.prefix.tree.DateRangePrefixTree;
+import org.apache.lucene.spatial.prefix.tree.NumberRangePrefixTree.UnitNRShape;
+import org.apache.lucene.spatial.query.SpatialOperation;
+import org.junit.Before;
+import org.junit.Test;
+
+import static com.carrotsearch.randomizedtesting.RandomizedTest.randomBoolean;
+import static com.carrotsearch.randomizedtesting.RandomizedTest.randomIntBetween;
+
+public class DateNRStrategyTest extends RandomSpatialOpStrategyTestCase {
+
+  static final int ITERATIONS = 10;
+
+  DateRangePrefixTree tree;
+
+  long randomCalWindowMs;
+
+  @Before
+  public void setUp() throws Exception {
+    super.setUp();
+    tree = DateRangePrefixTree.INSTANCE;
+    if (randomBoolean()) {
+      strategy = new NumberRangePrefixTreeStrategy(tree, "dateRange");
+    } else {
+      //Test the format that existed <= Lucene 5.0
+      strategy = new NumberRangePrefixTreeStrategy(tree, "dateRange") {
+        @Override
+        protected CellToBytesRefIterator newCellToBytesRefIterator() {
+          return new CellToBytesRefIterator50();
+        }
+      };
+    }
+    Calendar tmpCal = tree.newCal();
+    int randomCalWindowField = randomIntBetween(1, Calendar.ZONE_OFFSET - 1);//we're not allowed to add zone offset
+    tmpCal.add(randomCalWindowField, 2_000);
+    randomCalWindowMs = Math.max(2000L, tmpCal.getTimeInMillis());
+  }
+
+  @Test
+  @Repeat(iterations = ITERATIONS)
+  public void testIntersects() throws IOException {
+    testOperationRandomShapes(SpatialOperation.Intersects);
+  }
+
+  @Test
+  @Repeat(iterations = ITERATIONS)
+  public void testWithin() throws IOException {
+    testOperationRandomShapes(SpatialOperation.IsWithin);
+  }
+
+  @Test
+  @Repeat(iterations = ITERATIONS)
+  public void testContains() throws IOException {
+    testOperationRandomShapes(SpatialOperation.Contains);
+  }
+
+  @Test
+  public void testWithinSame() throws IOException {
+    final Calendar cal = tree.newCal();
+    testOperation(
+        tree.toShape(cal),
+        SpatialOperation.IsWithin,
+        tree.toShape(cal), true);//is within itself
+  }
+
+  @Test
+  public void testWorld() throws IOException {
+    testOperation(
+        tree.toShape(tree.newCal()),//world matches everything
+        SpatialOperation.Contains,
+        tree.toShape(randomCalendar()), true);
+  }
+
+  @Test
+  public void testBugInitIterOptimization() throws Exception {
+    //bug due to fast path initIter() optimization
+    testOperation(
+        tree.parseShape("[2014-03-27T23 TO 2014-04-01T01]"),
+        SpatialOperation.Intersects,
+        tree.parseShape("[2014-04 TO 2014-04-01T02]"), true);
+  }
+
+  @Override
+  protected Shape randomIndexedShape() {
+    Calendar cal1 = randomCalendar();
+    UnitNRShape s1 = tree.toShape(cal1);
+    if (rarely()) {
+      return s1;
+    }
+    try {
+      Calendar cal2 = randomCalendar();
+      UnitNRShape s2 = tree.toShape(cal2);
+      if (cal1.compareTo(cal2) < 0) {
+        return tree.toRangeShape(s1, s2);
+      } else {
+        return tree.toRangeShape(s2, s1);
+      }
+    } catch (IllegalArgumentException e) {
+      assert e.getMessage().startsWith("Differing precision");
+      return s1;
+    }
+  }
+
+  private Calendar randomCalendar() {
+    Calendar cal = tree.newCal();
+    cal.setTimeInMillis(random().nextLong() % randomCalWindowMs);
+    try {
+      tree.clearFieldsAfter(cal, random().nextInt(Calendar.FIELD_COUNT+1)-1);
+    } catch (AssertionError e) {
+      if (!e.getMessage().equals("Calendar underflow"))
+        throw e;
+    }
+    return cal;
+  }
+
+  @Override
+  protected Shape randomQueryShape() {
+    return randomIndexedShape();
+  }
+}

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/50a2f754/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/HeatmapFacetCounterTest.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/HeatmapFacetCounterTest.java b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/HeatmapFacetCounterTest.java
new file mode 100644
index 0000000..124af79
--- /dev/null
+++ b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/HeatmapFacetCounterTest.java
@@ -0,0 +1,252 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.spatial.prefix;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+
+import com.carrotsearch.randomizedtesting.annotations.Repeat;
+import com.spatial4j.core.context.SpatialContext;
+import com.spatial4j.core.context.SpatialContextFactory;
+import com.spatial4j.core.distance.DistanceUtils;
+import com.spatial4j.core.shape.Circle;
+import com.spatial4j.core.shape.Point;
+import com.spatial4j.core.shape.Rectangle;
+import com.spatial4j.core.shape.Shape;
+import com.spatial4j.core.shape.SpatialRelation;
+import com.spatial4j.core.shape.impl.RectangleImpl;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.TotalHitCountCollector;
+import org.apache.lucene.spatial.StrategyTestCase;
+import org.apache.lucene.spatial.prefix.tree.QuadPrefixTree;
+import org.apache.lucene.spatial.prefix.tree.SpatialPrefixTree;
+import org.apache.lucene.util.Bits;
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Test;
+
+import static com.carrotsearch.randomizedtesting.RandomizedTest.atMost;
+import static com.carrotsearch.randomizedtesting.RandomizedTest.randomIntBetween;
+
+public class HeatmapFacetCounterTest extends StrategyTestCase {
+
+  SpatialPrefixTree grid;
+
+  int cellsValidated;
+  int cellValidatedNonZero;
+
+  @Before
+  public void setUp() throws Exception {
+    super.setUp();
+    cellsValidated = cellValidatedNonZero = 0;
+    ctx = SpatialContext.GEO;
+    grid = new QuadPrefixTree(ctx, randomIntBetween(1, 8));
+    strategy = new RecursivePrefixTreeStrategy(grid, getTestClass().getSimpleName());
+    if (rarely()) {
+      ((PrefixTreeStrategy) strategy).setPointsOnly(true);
+    }
+  }
+
+  @After
+  public void after() {
+    log.info("Validated " + cellsValidated + " cells, " + cellValidatedNonZero + " non-zero");
+  }
+
+  @Test
+  public void testStatic() throws IOException {
+    //Some specific tests (static, not random).
+    adoc("0", ctx.makeRectangle(179.8, -170, -90, -80));//barely crosses equator
+    adoc("1", ctx.makePoint(-180, -85));//a pt within the above rect
+    adoc("2", ctx.makePoint(172, -85));//a pt to left of rect
+    commit();
+
+    validateHeatmapResultLoop(ctx.makeRectangle(+170, +180, -90, -85), 1, 100);
+    validateHeatmapResultLoop(ctx.makeRectangle(-180, -160, -89, -50), 1, 100);
+    validateHeatmapResultLoop(ctx.makeRectangle(179, 179, -89, -50), 1, 100);//line
+    // We could test anything and everything at this point... I prefer we leave that to random testing and then
+    // add specific tests if we find a bug.
+  }
+
+  @Test
+  public void testQueryCircle() throws IOException {
+    //overwrite setUp; non-geo bounds is more straight-forward; otherwise 88,88 would actually be practically north,
+    final SpatialContextFactory spatialContextFactory = new SpatialContextFactory();
+    spatialContextFactory.geo = false;
+    spatialContextFactory.worldBounds = new RectangleImpl(-90, 90, -90, 90, null);
+    ctx = spatialContextFactory.newSpatialContext();
+    final int LEVEL = 4;
+    grid = new QuadPrefixTree(ctx, LEVEL);
+    strategy = new RecursivePrefixTreeStrategy(grid, getTestClass().getSimpleName());
+    Circle circle = ctx.makeCircle(0, 0, 89);
+    adoc("0", ctx.makePoint(88, 88));//top-right, inside bbox of circle but not the circle
+    adoc("1", ctx.makePoint(0, 0));//clearly inside; dead center in fact
+    commit();
+    final HeatmapFacetCounter.Heatmap heatmap = HeatmapFacetCounter.calcFacets(
+        (PrefixTreeStrategy) strategy, indexSearcher.getTopReaderContext(), null,
+        circle, LEVEL, 1000);
+    //assert that only one point is found, not 2
+    boolean foundOne = false;
+    for (int count : heatmap.counts) {
+      switch (count) {
+        case 0: break;
+        case 1:
+          assertFalse(foundOne);//this is the first
+          foundOne = true;
+          break;
+        default:
+          fail("counts should be 0 or 1: " + count);
+      }
+    }
+    assertTrue(foundOne);
+  }
+
+  /** Recursively facet & validate at higher resolutions until we've seen enough. We assume there are
+   * some non-zero cells. */
+  private void validateHeatmapResultLoop(Rectangle inputRange, int facetLevel, int cellCountRecursThreshold)
+      throws IOException {
+    if (facetLevel > grid.getMaxLevels()) {
+      return;
+    }
+    final int maxCells = 10_000;
+    final HeatmapFacetCounter.Heatmap heatmap = HeatmapFacetCounter.calcFacets(
+        (PrefixTreeStrategy) strategy, indexSearcher.getTopReaderContext(), null, inputRange, facetLevel, maxCells);
+    int preNonZero = cellValidatedNonZero;
+    validateHeatmapResult(inputRange, facetLevel, heatmap);
+    assert cellValidatedNonZero - preNonZero > 0;//we validated more non-zero cells
+    if (heatmap.counts.length < cellCountRecursThreshold) {
+      validateHeatmapResultLoop(inputRange, facetLevel + 1, cellCountRecursThreshold);
+    }
+  }
+
+  @Test
+  @Repeat(iterations = 20)
+  public void testRandom() throws IOException {
+    // Tests using random index shapes & query shapes. This has found all sorts of edge case bugs (e.g. dateline,
+    // cell border, overflow(?)).
+
+    final int numIndexedShapes = 1 + atMost(9);
+    List<Shape> indexedShapes = new ArrayList<>(numIndexedShapes);
+    for (int i = 0; i < numIndexedShapes; i++) {
+      indexedShapes.add(randomIndexedShape());
+    }
+
+    //Main index loop:
+    for (int i = 0; i < indexedShapes.size(); i++) {
+      Shape shape = indexedShapes.get(i);
+      adoc("" + i, shape);
+
+      if (random().nextInt(10) == 0)
+        commit();//intermediate commit, produces extra segments
+    }
+    //delete some documents randomly
+    for (int id = 0; id < indexedShapes.size(); id++) {
+      if (random().nextInt(10) == 0) {
+        deleteDoc("" + id);
+        indexedShapes.set(id, null);
+      }
+    }
+
+    commit();
+
+    // once without dateline wrap
+    final Rectangle rect = randomRectangle();
+    queryHeatmapRecursive(usually() ? ctx.getWorldBounds() : rect, 1);
+    // and once with dateline wrap
+    if (rect.getWidth() > 0) {
+      double shift = random().nextDouble() % rect.getWidth();
+      queryHeatmapRecursive(ctx.makeRectangle(
+              DistanceUtils.normLonDEG(rect.getMinX() - shift),
+              DistanceUtils.normLonDEG(rect.getMaxX() - shift),
+              rect.getMinY(), rect.getMaxY()),
+          1);
+    }
+  }
+
+  /** Build heatmap, validate results, then descend recursively to another facet level. */
+  private boolean queryHeatmapRecursive(Rectangle inputRange, int facetLevel) throws IOException {
+    if (!inputRange.hasArea()) {
+      // Don't test line inputs. It's not that we don't support it but it is more challenging to test if per-chance it
+      // coincides with a grid line due due to edge overlap issue for some grid implementations (geo & quad).
+      return false;
+    }
+    Bits filter = null; //FYI testing filtering of underlying PrefixTreeFacetCounter is done in another test
+    //Calculate facets
+    final int maxCells = 10_000;
+    final HeatmapFacetCounter.Heatmap heatmap = HeatmapFacetCounter.calcFacets(
+        (PrefixTreeStrategy) strategy, indexSearcher.getTopReaderContext(), filter, inputRange, facetLevel, maxCells);
+
+    validateHeatmapResult(inputRange, facetLevel, heatmap);
+
+    boolean foundNonZeroCount = false;
+    for (int count : heatmap.counts) {
+      if (count > 0) {
+        foundNonZeroCount = true;
+        break;
+      }
+    }
+
+    //Test again recursively to higher facetLevel (more detailed cells)
+    if (foundNonZeroCount && cellsValidated <= 500 && facetLevel != grid.getMaxLevels() && inputRange.hasArea()) {
+      for (int i = 0; i < 5; i++) {//try multiple times until we find non-zero counts
+        if (queryHeatmapRecursive(randomRectangle(inputRange), facetLevel + 1)) {
+          break;//we found data here so we needn't try again
+        }
+      }
+    }
+    return foundNonZeroCount;
+  }
+
+  private void validateHeatmapResult(Rectangle inputRange, int facetLevel, HeatmapFacetCounter.Heatmap heatmap)
+      throws IOException {
+    final Rectangle heatRect = heatmap.region;
+    assertTrue(heatRect.relate(inputRange) == SpatialRelation.CONTAINS || heatRect.equals(inputRange));
+    final double cellWidth = heatRect.getWidth() / heatmap.columns;
+    final double cellHeight = heatRect.getHeight() / heatmap.rows;
+    for (int c = 0; c < heatmap.columns; c++) {
+      for (int r = 0; r < heatmap.rows; r++) {
+        final int facetCount = heatmap.getCount(c, r);
+        double x = DistanceUtils.normLonDEG(heatRect.getMinX() + c * cellWidth + cellWidth / 2);
+        double y = DistanceUtils.normLatDEG(heatRect.getMinY() + r * cellHeight + cellHeight / 2);
+        Point pt =  ctx.makePoint(x, y);
+        assertEquals(countMatchingDocsAtLevel(pt, facetLevel), facetCount);
+      }
+    }
+  }
+
+  private int countMatchingDocsAtLevel(Point pt, int facetLevel) throws IOException {
+    // we use IntersectsPrefixTreeFilter directly so that we can specify the level to go to exactly.
+    RecursivePrefixTreeStrategy strategy = (RecursivePrefixTreeStrategy) this.strategy;
+    Query filter = new IntersectsPrefixTreeQuery(
+        pt, strategy.getFieldName(), grid, facetLevel, grid.getMaxLevels());
+    final TotalHitCountCollector collector = new TotalHitCountCollector();
+    indexSearcher.search(filter, collector);
+    cellsValidated++;
+    if (collector.getTotalHits() > 0) {
+      cellValidatedNonZero++;
+    }
+    return collector.getTotalHits();
+  }
+
+  private Shape randomIndexedShape() {
+    if (((PrefixTreeStrategy) strategy).isPointsOnly() || random().nextBoolean()) {
+      return randomPoint();
+    } else {
+      return randomRectangle();
+    }
+  }
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/50a2f754/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/JtsPolygonTest.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/JtsPolygonTest.java b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/JtsPolygonTest.java
new file mode 100644
index 0000000..09fb3a9
--- /dev/null
+++ b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/JtsPolygonTest.java
@@ -0,0 +1,117 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.spatial.prefix;
+
+import com.spatial4j.core.context.SpatialContextFactory;
+import com.spatial4j.core.shape.Point;
+import com.spatial4j.core.shape.Shape;
+import org.apache.lucene.document.Document;
+import org.apache.lucene.document.Field;
+import org.apache.lucene.document.Field.Store;
+import org.apache.lucene.document.TextField;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.ScoreDoc;
+import org.apache.lucene.search.TopDocs;
+import org.apache.lucene.spatial.StrategyTestCase;
+import org.apache.lucene.spatial.prefix.tree.GeohashPrefixTree;
+import org.apache.lucene.spatial.prefix.tree.QuadPrefixTree;
+import org.apache.lucene.spatial.prefix.tree.SpatialPrefixTree;
+import org.apache.lucene.spatial.query.SpatialArgs;
+import org.apache.lucene.spatial.query.SpatialOperation;
+import org.junit.Test;
+
+import java.text.ParseException;
+import java.util.HashMap;
+
+public class JtsPolygonTest extends StrategyTestCase {
+
+  private static final double LUCENE_4464_distErrPct = SpatialArgs.DEFAULT_DISTERRPCT;//DEFAULT 2.5%
+
+  public JtsPolygonTest() {
+    try {
+      HashMap<String, String> args = new HashMap<>();
+      args.put("spatialContextFactory",
+          "com.spatial4j.core.context.jts.JtsSpatialContextFactory");
+      ctx = SpatialContextFactory.makeSpatialContext(args, getClass().getClassLoader());
+    } catch (NoClassDefFoundError e) {
+      assumeTrue("This test requires JTS jar: "+e, false);
+    }
+
+    GeohashPrefixTree grid = new GeohashPrefixTree(ctx, 11);//< 1 meter == 11 maxLevels
+    this.strategy = new RecursivePrefixTreeStrategy(grid, getClass().getSimpleName());
+    ((RecursivePrefixTreeStrategy)this.strategy).setDistErrPct(LUCENE_4464_distErrPct);//1% radius (small!)
+  }
+
+  @Test
+  /** LUCENE-4464 */
+  public void testCloseButNoMatch() throws Exception {
+    getAddAndVerifyIndexedDocuments("LUCENE-4464.txt");
+    SpatialArgs args = q(
+        "POLYGON((-93.18100824442227 45.25676372469945," +
+            "-93.23182001200654 45.21421290799412," +
+            "-93.16315546122038 45.23742639412364," +
+            "-93.18100824442227 45.25676372469945))",
+        LUCENE_4464_distErrPct);
+    SearchResults got = executeQuery(strategy.makeQuery(args), 100);
+    assertEquals(1, got.numFound);
+    assertEquals("poly2", got.results.get(0).document.get("id"));
+    //did not find poly 1 !
+  }
+
+  private SpatialArgs q(String shapeStr, double distErrPct) throws ParseException {
+    Shape shape = ctx.readShapeFromWkt(shapeStr);
+    SpatialArgs args = new SpatialArgs(SpatialOperation.Intersects, shape);
+    args.setDistErrPct(distErrPct);
+    return args;
+  }
+
+  /**
+   * A PrefixTree pruning optimization gone bad.
+   * See <a href="https://issues.apache.org/jira/browse/LUCENE-4770">LUCENE-4770</a>.
+   */
+  @Test
+  public void testBadPrefixTreePrune() throws Exception {
+
+    Shape area = ctx.readShapeFromWkt("POLYGON((-122.83 48.57, -122.77 48.56, -122.79 48.53, -122.83 48.57))");
+
+    SpatialPrefixTree trie = new QuadPrefixTree(ctx, 12);
+    TermQueryPrefixTreeStrategy strategy = new TermQueryPrefixTreeStrategy(trie, "geo");
+    Document doc = new Document();
+    doc.add(new TextField("id", "1", Store.YES));
+
+    Field[] fields = strategy.createIndexableFields(area, 0.025);
+    for (Field field : fields) {
+      doc.add(field);
+    }
+    addDocument(doc);
+
+    Point upperleft = ctx.makePoint(-122.88, 48.54);
+    Point lowerright = ctx.makePoint(-122.82, 48.62);
+
+    Query query = strategy.makeQuery(new SpatialArgs(SpatialOperation.Intersects, ctx.makeRectangle(upperleft, lowerright)));
+    commit();
+
+    TopDocs search = indexSearcher.search(query, 10);
+    ScoreDoc[] scoreDocs = search.scoreDocs;
+    for (ScoreDoc scoreDoc : scoreDocs) {
+      System.out.println(indexSearcher.doc(scoreDoc.doc));
+    }
+
+    assertEquals(1, search.totalHits);
+  }
+
+}

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/50a2f754/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/NumberRangeFacetsTest.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/NumberRangeFacetsTest.java b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/NumberRangeFacetsTest.java
new file mode 100644
index 0000000..11e1d18
--- /dev/null
+++ b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/NumberRangeFacetsTest.java
@@ -0,0 +1,275 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.spatial.prefix;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Calendar;
+import java.util.Collections;
+import java.util.List;
+
+import com.carrotsearch.randomizedtesting.annotations.Repeat;
+import com.spatial4j.core.shape.Shape;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.Term;
+import org.apache.lucene.queries.TermsQuery;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.SimpleCollector;
+import org.apache.lucene.spatial.StrategyTestCase;
+import org.apache.lucene.spatial.prefix.NumberRangePrefixTreeStrategy.Facets;
+import org.apache.lucene.spatial.prefix.tree.Cell;
+import org.apache.lucene.spatial.prefix.tree.CellIterator;
+import org.apache.lucene.spatial.prefix.tree.DateRangePrefixTree;
+import org.apache.lucene.spatial.prefix.tree.NumberRangePrefixTree;
+import org.apache.lucene.spatial.prefix.tree.NumberRangePrefixTree.UnitNRShape;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+import org.junit.Before;
+import org.junit.Test;
+
+import static com.carrotsearch.randomizedtesting.RandomizedTest.randomInt;
+import static com.carrotsearch.randomizedtesting.RandomizedTest.randomIntBetween;
+
+public class NumberRangeFacetsTest extends StrategyTestCase {
+
+  DateRangePrefixTree tree;
+
+  int randomCalWindowField;
+  long randomCalWindowMs;
+
+  @Before
+  public void setUp() throws Exception {
+    super.setUp();
+    tree = DateRangePrefixTree.INSTANCE;
+    strategy = new NumberRangePrefixTreeStrategy(tree, "dateRange");
+    Calendar tmpCal = tree.newCal();
+    randomCalWindowField = randomIntBetween(1, Calendar.ZONE_OFFSET - 1);//we're not allowed to add zone offset
+    tmpCal.add(randomCalWindowField, 2_000);
+    randomCalWindowMs = Math.max(2000L, tmpCal.getTimeInMillis());
+  }
+
+  @Repeat(iterations = 20)
+  @Test
+  public void test() throws IOException {
+    //generate test data
+    List<Shape> indexedShapes = new ArrayList<>();
+    final int numIndexedShapes = random().nextInt(15);
+    for (int i = 0; i < numIndexedShapes; i++) {
+      indexedShapes.add(randomShape());
+    }
+
+    //Main index loop:
+    for (int i = 0; i < indexedShapes.size(); i++) {
+      Shape shape = indexedShapes.get(i);
+      adoc(""+i, shape);
+
+      if (random().nextInt(10) == 0)
+        commit();//intermediate commit, produces extra segments
+    }
+
+    //delete some documents randomly
+    for (int id = 0; id < indexedShapes.size(); id++) {
+      if (random().nextInt(10) == 0) {
+        deleteDoc(""+id);
+        indexedShapes.set(id, null);
+      }
+    }
+
+    commit();
+
+    //Main query loop:
+    for (int queryIdx = 0; queryIdx < 10; queryIdx++) {
+      preQueryHavoc();
+
+      // We need to have a facet range window to do the facets between (a start time & end time). We randomly
+      // pick a date, decide the level we want to facet on, and then pick a right end time that is up to 2 thousand
+      // values later.
+      int calFieldFacet = randomCalWindowField - 1;
+      if (calFieldFacet > 1 && rarely()) {
+        calFieldFacet--;
+      }
+      final Calendar leftCal = randomCalendar();
+      leftCal.add(calFieldFacet, -1 * randomInt(1000));
+      Calendar rightCal = (Calendar) leftCal.clone();
+      rightCal.add(calFieldFacet, randomInt(2000));
+      // Pick facet detail level based on cal field.
+      int detailLevel = tree.getTreeLevelForCalendarField(calFieldFacet);
+      if (detailLevel < 0) {//no exact match
+        detailLevel = -1 * detailLevel;
+      }
+
+      //Randomly pick a filter/acceptDocs
+      Bits topAcceptDocs = null;
+      List<Integer> acceptFieldIds = new ArrayList<>();
+      if (usually()) {
+        //get all possible IDs into a list, random shuffle it, then randomly choose how many of the first we use to
+        // replace the list.
+        for (int i = 0; i < indexedShapes.size(); i++) {
+          if (indexedShapes.get(i) == null) { // we deleted this one
+            continue;
+          }
+          acceptFieldIds.add(i);
+        }
+        Collections.shuffle(acceptFieldIds, random());
+        acceptFieldIds = acceptFieldIds.subList(0, randomInt(acceptFieldIds.size()));
+        if (!acceptFieldIds.isEmpty()) {
+          List<Term> terms = new ArrayList<>();
+          for (Integer acceptDocId : acceptFieldIds) {
+            terms.add(new Term("id", acceptDocId.toString()));
+          }
+
+          topAcceptDocs = searchForDocBits(new TermsQuery(terms));
+        }
+      }
+
+      //Lets do it!
+      NumberRangePrefixTree.NRShape facetRange = tree.toRangeShape(tree.toShape(leftCal), tree.toShape(rightCal));
+      Facets facets = ((NumberRangePrefixTreeStrategy) strategy)
+          .calcFacets(indexSearcher.getTopReaderContext(), topAcceptDocs, facetRange, detailLevel);
+
+      //System.out.println("Q: " + queryIdx + " " + facets);
+
+      //Verify results. We do it by looping over indexed shapes and reducing the facet counts.
+      Shape facetShapeRounded = facetRange.roundToLevel(detailLevel);
+      for (int indexedShapeId = 0; indexedShapeId < indexedShapes.size(); indexedShapeId++) {
+        if (topAcceptDocs != null && !acceptFieldIds.contains(indexedShapeId)) {
+          continue;// this doc was filtered out via acceptDocs
+        }
+        Shape indexedShape = indexedShapes.get(indexedShapeId);
+        if (indexedShape == null) {//was deleted
+          continue;
+        }
+        Shape indexedShapeRounded = ((NumberRangePrefixTree.NRShape) indexedShape).roundToLevel(detailLevel);
+        if (!indexedShapeRounded.relate(facetShapeRounded).intersects()) { // no intersection at all
+          continue;
+        }
+        // walk the cells
+        final CellIterator cellIterator = tree.getTreeCellIterator(indexedShape, detailLevel);
+        while (cellIterator.hasNext()) {
+          Cell cell = cellIterator.next();
+          if (!cell.getShape().relate(facetShapeRounded).intersects()) {
+            cellIterator.remove();//no intersection; prune
+            continue;
+          }
+          assert cell.getLevel() <= detailLevel;
+
+          if (cell.getLevel() == detailLevel) {
+            //count it
+            UnitNRShape shape = (UnitNRShape) cell.getShape();
+            final UnitNRShape parentShape = shape.getShapeAtLevel(detailLevel - 1);//get parent
+            final Facets.FacetParentVal facetParentVal = facets.parents.get(parentShape);
+            assertNotNull(facetParentVal);
+            int index = shape.getValAtLevel(shape.getLevel());
+            assertNotNull(facetParentVal.childCounts);
+            assert facetParentVal.childCounts[index] > 0;
+            facetParentVal.childCounts[index]--;
+
+          } else if (cell.isLeaf()) {
+            //count it, and remove/prune.
+            if (cell.getLevel() < detailLevel - 1) {
+              assert facets.topLeaves > 0;
+              facets.topLeaves--;
+            } else {
+              UnitNRShape shape = (UnitNRShape) cell.getShape();
+              final UnitNRShape parentShape = shape.getShapeAtLevel(detailLevel - 1);//get parent
+              final Facets.FacetParentVal facetParentVal = facets.parents.get(parentShape);
+              assertNotNull(facetParentVal);
+              assert facetParentVal.parentLeaves > 0;
+              facetParentVal.parentLeaves--;
+            }
+
+            cellIterator.remove();
+          }
+        }
+      }
+      // At this point; all counts should be down to zero.
+      assertTrue(facets.topLeaves == 0);
+      for (Facets.FacetParentVal facetParentVal : facets.parents.values()) {
+        assertTrue(facetParentVal.parentLeaves == 0);
+        if (facetParentVal.childCounts != null) {
+          for (int childCount : facetParentVal.childCounts) {
+            assertTrue(childCount == 0);
+          }
+        }
+      }
+
+    }
+  }
+
+  private Bits searchForDocBits(Query query) throws IOException {
+    FixedBitSet bitSet = new FixedBitSet(indexSearcher.getIndexReader().maxDoc());
+    indexSearcher.search(query,
+        new SimpleCollector() {
+          int leafDocBase;
+          @Override
+          public void collect(int doc) throws IOException {
+            bitSet.set(leafDocBase + doc);
+          }
+
+          @Override
+          protected void doSetNextReader(LeafReaderContext context) throws IOException {
+            leafDocBase = context.docBase;
+          }
+
+          @Override
+          public boolean needsScores() {
+            return false;
+          }
+        });
+    return bitSet;
+  }
+
+  private void preQueryHavoc() {
+    if (strategy instanceof RecursivePrefixTreeStrategy) {
+      RecursivePrefixTreeStrategy rpts = (RecursivePrefixTreeStrategy) strategy;
+      int scanLevel = randomInt(rpts.getGrid().getMaxLevels());
+      rpts.setPrefixGridScanLevel(scanLevel);
+    }
+  }
+
+  protected Shape randomShape() {
+    Calendar cal1 = randomCalendar();
+    UnitNRShape s1 = tree.toShape(cal1);
+    if (rarely()) {
+      return s1;
+    }
+    try {
+      Calendar cal2 = randomCalendar();
+      UnitNRShape s2 = tree.toShape(cal2);
+      if (cal1.compareTo(cal2) < 0) {
+        return tree.toRangeShape(s1, s2);
+      } else {
+        return tree.toRangeShape(s2, s1);
+      }
+    } catch (IllegalArgumentException e) {
+      assert e.getMessage().startsWith("Differing precision");
+      return s1;
+    }
+  }
+
+  private Calendar randomCalendar() {
+    Calendar cal = tree.newCal();
+    cal.setTimeInMillis(random().nextLong() % randomCalWindowMs);
+    try {
+      tree.clearFieldsAfter(cal, random().nextInt(Calendar.FIELD_COUNT+1)-1);
+    } catch (AssertionError e) {
+      if (!e.getMessage().equals("Calendar underflow"))
+        throw e;
+    }
+    return cal;
+  }
+}

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/50a2f754/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/RandomSpatialOpFuzzyPrefixTree50Test.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/RandomSpatialOpFuzzyPrefixTree50Test.java b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/RandomSpatialOpFuzzyPrefixTree50Test.java
new file mode 100644
index 0000000..e932fe9
--- /dev/null
+++ b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/RandomSpatialOpFuzzyPrefixTree50Test.java
@@ -0,0 +1,31 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.spatial.prefix;
+
+/** Test RandomSpatialOpFuzzyPrefixTreeTest using the PrefixTree index format found in 5.0 and prior. */
+public class RandomSpatialOpFuzzyPrefixTree50Test extends RandomSpatialOpFuzzyPrefixTreeTest {
+
+  protected RecursivePrefixTreeStrategy newRPT() {
+    return new RecursivePrefixTreeStrategy(this.grid, getClass().getSimpleName()) {
+      @Override
+      protected CellToBytesRefIterator newCellToBytesRefIterator() {
+        return new CellToBytesRefIterator50();
+      }
+    };
+  }
+
+}

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/50a2f754/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/RandomSpatialOpFuzzyPrefixTreeTest.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/RandomSpatialOpFuzzyPrefixTreeTest.java b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/RandomSpatialOpFuzzyPrefixTreeTest.java
new file mode 100644
index 0000000..8db131c
--- /dev/null
+++ b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/RandomSpatialOpFuzzyPrefixTreeTest.java
@@ -0,0 +1,533 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.spatial.prefix;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.LinkedHashMap;
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import com.carrotsearch.randomizedtesting.annotations.Repeat;
+import com.spatial4j.core.context.SpatialContext;
+import com.spatial4j.core.context.SpatialContextFactory;
+import com.spatial4j.core.shape.Point;
+import com.spatial4j.core.shape.Rectangle;
+import com.spatial4j.core.shape.Shape;
+import com.spatial4j.core.shape.ShapeCollection;
+import com.spatial4j.core.shape.SpatialRelation;
+import com.spatial4j.core.shape.impl.RectangleImpl;
+import org.apache.lucene.document.Document;
+import org.apache.lucene.document.Field;
+import org.apache.lucene.document.StoredField;
+import org.apache.lucene.document.StringField;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.spatial.StrategyTestCase;
+import org.apache.lucene.spatial.prefix.tree.Cell;
+import org.apache.lucene.spatial.prefix.tree.CellIterator;
+import org.apache.lucene.spatial.prefix.tree.GeohashPrefixTree;
+import org.apache.lucene.spatial.prefix.tree.PackedQuadPrefixTree;
+import org.apache.lucene.spatial.prefix.tree.QuadPrefixTree;
+import org.apache.lucene.spatial.prefix.tree.SpatialPrefixTree;
+import org.apache.lucene.spatial.query.SpatialArgs;
+import org.apache.lucene.spatial.query.SpatialOperation;
+import org.junit.Test;
+
+import static com.carrotsearch.randomizedtesting.RandomizedTest.randomBoolean;
+import static com.carrotsearch.randomizedtesting.RandomizedTest.randomInt;
+import static com.carrotsearch.randomizedtesting.RandomizedTest.randomIntBetween;
+import static com.spatial4j.core.shape.SpatialRelation.CONTAINS;
+import static com.spatial4j.core.shape.SpatialRelation.DISJOINT;
+import static com.spatial4j.core.shape.SpatialRelation.INTERSECTS;
+import static com.spatial4j.core.shape.SpatialRelation.WITHIN;
+
+/** Randomized PrefixTree test that considers the fuzziness of the
+ * results introduced by grid approximation. */
+public class RandomSpatialOpFuzzyPrefixTreeTest extends StrategyTestCase {
+
+  static final int ITERATIONS = 10;
+
+  protected SpatialPrefixTree grid;
+  private SpatialContext ctx2D;
+
+  public void setupGrid(int maxLevels) throws IOException {
+    if (randomBoolean())
+      setupQuadGrid(maxLevels, randomBoolean());
+    else
+      setupGeohashGrid(maxLevels);
+    setupCtx2D(ctx);
+
+    // set prune independently on strategy & grid randomly; should work
+    ((RecursivePrefixTreeStrategy)strategy).setPruneLeafyBranches(randomBoolean());
+    if (this.grid instanceof PackedQuadPrefixTree) {
+      ((PackedQuadPrefixTree) this.grid).setPruneLeafyBranches(randomBoolean());
+    }
+
+    if (maxLevels == -1 && rarely()) {
+      ((PrefixTreeStrategy) strategy).setPointsOnly(true);
+    }
+
+    log.info("Strategy: " + strategy.toString());
+  }
+
+  private void setupCtx2D(SpatialContext ctx) {
+    if (!ctx.isGeo())
+      ctx2D = ctx;
+    //A non-geo version of ctx.
+    SpatialContextFactory ctxFactory = new SpatialContextFactory();
+    ctxFactory.geo = false;
+    ctxFactory.worldBounds = ctx.getWorldBounds();
+    ctx2D = ctxFactory.newSpatialContext();
+  }
+
+  private void setupQuadGrid(int maxLevels, boolean packedQuadPrefixTree) {
+    //non-geospatial makes this test a little easier (in gridSnap), and using boundary values 2^X raises
+    // the prospect of edge conditions we want to test, plus makes for simpler numbers (no decimals).
+    SpatialContextFactory factory = new SpatialContextFactory();
+    factory.geo = false;
+    factory.worldBounds = new RectangleImpl(0, 256, -128, 128, null);
+    this.ctx = factory.newSpatialContext();
+    //A fairly shallow grid, and default 2.5% distErrPct
+    if (maxLevels == -1)
+      maxLevels = randomIntBetween(1, 8);//max 64k cells (4^8), also 256*256
+    if (packedQuadPrefixTree) {
+      this.grid = new PackedQuadPrefixTree(ctx, maxLevels);
+    } else {
+      this.grid = new QuadPrefixTree(ctx, maxLevels);
+    }
+    this.strategy = newRPT();
+  }
+
+  public void setupGeohashGrid(int maxLevels) {
+    this.ctx = SpatialContext.GEO;
+    //A fairly shallow grid, and default 2.5% distErrPct
+    if (maxLevels == -1)
+      maxLevels = randomIntBetween(1, 3);//max 16k cells (32^3)
+    this.grid = new GeohashPrefixTree(ctx, maxLevels);
+    this.strategy = newRPT();
+  }
+
+  protected RecursivePrefixTreeStrategy newRPT() {
+    return new RecursivePrefixTreeStrategy(this.grid, getClass().getSimpleName());
+  }
+
+  @Test
+  @Repeat(iterations = ITERATIONS)
+  public void testIntersects() throws IOException {
+    setupGrid(-1);
+    doTest(SpatialOperation.Intersects);
+  }
+
+  @Test
+  @Repeat(iterations = ITERATIONS)
+  public void testWithin() throws IOException {
+    setupGrid(-1);
+    doTest(SpatialOperation.IsWithin);
+  }
+
+  @Test
+  @Repeat(iterations = ITERATIONS)
+  public void testContains() throws IOException {
+    setupGrid(-1);
+    doTest(SpatialOperation.Contains);
+  }
+
+  /** See LUCENE-5062, {@link ContainsPrefixTreeQuery#multiOverlappingIndexedShapes}. */
+  @Test
+  public void testContainsPairOverlap() throws IOException {
+    setupQuadGrid(3, randomBoolean());
+    adoc("0", new ShapePair(ctx.makeRectangle(0, 33, -128, 128), ctx.makeRectangle(33, 128, -128, 128), true));
+    commit();
+    Query query = strategy.makeQuery(new SpatialArgs(SpatialOperation.Contains,
+        ctx.makeRectangle(0, 128, -16, 128)));
+    SearchResults searchResults = executeQuery(query, 1);
+    assertEquals(1, searchResults.numFound);
+  }
+
+  @Test
+  public void testWithinDisjointParts() throws IOException {
+    setupQuadGrid(7, randomBoolean());
+    //one shape comprised of two parts, quite separated apart
+    adoc("0", new ShapePair(ctx.makeRectangle(0, 10, -120, -100), ctx.makeRectangle(220, 240, 110, 125), false));
+    commit();
+    //query surrounds only the second part of the indexed shape
+    Query query = strategy.makeQuery(new SpatialArgs(SpatialOperation.IsWithin,
+        ctx.makeRectangle(210, 245, 105, 128)));
+    SearchResults searchResults = executeQuery(query, 1);
+    //we shouldn't find it because it's not completely within
+    assertTrue(searchResults.numFound == 0);
+  }
+
+  @Test /** LUCENE-4916 */
+  public void testWithinLeafApproxRule() throws IOException {
+    setupQuadGrid(2, randomBoolean());//4x4 grid
+    //indexed shape will simplify to entire right half (2 top cells)
+    adoc("0", ctx.makeRectangle(192, 204, -128, 128));
+    commit();
+
+    ((RecursivePrefixTreeStrategy) strategy).setPrefixGridScanLevel(randomInt(2));
+
+    //query does NOT contain it; both indexed cells are leaves to the query, and
+    // when expanded to the full grid cells, the top one's top row is disjoint
+    // from the query and thus not a match.
+    assertTrue(executeQuery(strategy.makeQuery(
+        new SpatialArgs(SpatialOperation.IsWithin, ctx.makeRectangle(38, 192, -72, 56))
+    ), 1).numFound==0);//no-match
+
+    //this time the rect is a little bigger and is considered a match. It's
+    // an acceptable false-positive because of the grid approximation.
+    assertTrue(executeQuery(strategy.makeQuery(
+        new SpatialArgs(SpatialOperation.IsWithin, ctx.makeRectangle(38, 192, -72, 80))
+    ), 1).numFound==1);//match
+  }
+
+  @Test
+  public void testShapePair() {
+    ctx = SpatialContext.GEO;
+    setupCtx2D(ctx);
+
+    Shape leftShape = new ShapePair(ctx.makeRectangle(-74, -56, -8, 1), ctx.makeRectangle(-180, 134, -90, 90), true);
+    Shape queryShape = ctx.makeRectangle(-180, 180, -90, 90);
+    assertEquals(SpatialRelation.WITHIN, leftShape.relate(queryShape));
+  }
+
+  //Override so we can index parts of a pair separately, resulting in the detailLevel
+  // being independent for each shape vs the whole thing
+  @Override
+  protected Document newDoc(String id, Shape shape) {
+    Document doc = new Document();
+    doc.add(new StringField("id", id, Field.Store.YES));
+    if (shape != null) {
+      Collection<Shape> shapes;
+      if (shape instanceof ShapePair) {
+        shapes = new ArrayList<>(2);
+        shapes.add(((ShapePair)shape).shape1);
+        shapes.add(((ShapePair)shape).shape2);
+      } else {
+        shapes = Collections.singleton(shape);
+      }
+      for (Shape shapei : shapes) {
+        for (Field f : strategy.createIndexableFields(shapei)) {
+          doc.add(f);
+        }
+      }
+      if (storeShape)//just for diagnostics
+        doc.add(new StoredField(strategy.getFieldName(), shape.toString()));
+    }
+    return doc;
+  }
+
+  @SuppressWarnings("fallthrough")
+  private void doTest(final SpatialOperation operation) throws IOException {
+    //first show that when there's no data, a query will result in no results
+    {
+      Query query = strategy.makeQuery(new SpatialArgs(operation, randomRectangle()));
+      SearchResults searchResults = executeQuery(query, 1);
+      assertEquals(0, searchResults.numFound);
+    }
+
+    final boolean biasContains = (operation == SpatialOperation.Contains);
+
+    //Main index loop:
+    Map<String, Shape> indexedShapes = new LinkedHashMap<>();
+    Map<String, Shape> indexedShapesGS = new LinkedHashMap<>();//grid snapped
+    final int numIndexedShapes = randomIntBetween(1, 6);
+    boolean indexedAtLeastOneShapePair = false;
+    final boolean pointsOnly = ((PrefixTreeStrategy) strategy).isPointsOnly();
+    for (int i = 0; i < numIndexedShapes; i++) {
+      String id = "" + i;
+      Shape indexedShape;
+      int R = random().nextInt(12);
+      if (R == 0) {//1 in 12
+        indexedShape = null;
+      } else if (R == 1 || pointsOnly) {//1 in 12
+        indexedShape = randomPoint();//just one point
+      } else if (R <= 4) {//3 in 12
+        //comprised of more than one shape
+        indexedShape = randomShapePairRect(biasContains);
+        indexedAtLeastOneShapePair = true;
+      } else {
+        indexedShape = randomRectangle();//just one rect
+      }
+
+      indexedShapes.put(id, indexedShape);
+      indexedShapesGS.put(id, gridSnap(indexedShape));
+
+      adoc(id, indexedShape);
+
+      if (random().nextInt(10) == 0)
+        commit();//intermediate commit, produces extra segments
+
+    }
+    //delete some documents randomly
+    Iterator<String> idIter = indexedShapes.keySet().iterator();
+    while (idIter.hasNext()) {
+      String id = idIter.next();
+      if (random().nextInt(10) == 0) {
+        deleteDoc(id);
+        idIter.remove();
+        indexedShapesGS.remove(id);
+      }
+    }
+
+    commit();
+
+    //Main query loop:
+    final int numQueryShapes = atLeast(20);
+    for (int i = 0; i < numQueryShapes; i++) {
+      int scanLevel = randomInt(grid.getMaxLevels());
+      ((RecursivePrefixTreeStrategy) strategy).setPrefixGridScanLevel(scanLevel);
+
+      final Shape queryShape;
+      switch (randomInt(10)) {
+        case 0: queryShape = randomPoint(); break;
+// LUCENE-5549
+//TODO debug: -Dtests.method=testWithin -Dtests.multiplier=3 -Dtests.seed=5F5294CE2E075A3E:AAD2F0F79288CA64
+//        case 1:case 2:case 3:
+//          if (!indexedAtLeastOneShapePair) { // avoids ShapePair.relate(ShapePair), which isn't reliable
+//            queryShape = randomShapePairRect(!biasContains);//invert biasContains for query side
+//            break;
+//          }
+
+        case 4:
+          //choose an existing indexed shape
+          if (!indexedShapes.isEmpty()) {
+            Shape tmp = indexedShapes.values().iterator().next();
+            if (tmp instanceof Point || tmp instanceof Rectangle) {//avoids null and shapePair
+              queryShape = tmp;
+              break;
+            }
+          }//else fall-through
+
+        default: queryShape = randomRectangle();
+      }
+      final Shape queryShapeGS = gridSnap(queryShape);
+
+      final boolean opIsDisjoint = operation == SpatialOperation.IsDisjointTo;
+
+      //Generate truth via brute force:
+      // We ensure true-positive matches (if the predicate on the raw shapes match
+      //  then the search should find those same matches).
+      // approximations, false-positive matches
+      Set<String> expectedIds = new LinkedHashSet<>();//true-positives
+      Set<String> secondaryIds = new LinkedHashSet<>();//false-positives (unless disjoint)
+      for (Map.Entry<String, Shape> entry : indexedShapes.entrySet()) {
+        String id = entry.getKey();
+        Shape indexedShapeCompare = entry.getValue();
+        if (indexedShapeCompare == null)
+          continue;
+        Shape queryShapeCompare = queryShape;
+
+        if (operation.evaluate(indexedShapeCompare, queryShapeCompare)) {
+          expectedIds.add(id);
+          if (opIsDisjoint) {
+            //if no longer intersect after buffering them, for disjoint, remember this
+            indexedShapeCompare = indexedShapesGS.get(id);
+            queryShapeCompare = queryShapeGS;
+            if (!operation.evaluate(indexedShapeCompare, queryShapeCompare))
+              secondaryIds.add(id);
+          }
+        } else if (!opIsDisjoint) {
+          //buffer either the indexed or query shape (via gridSnap) and try again
+          if (operation == SpatialOperation.Intersects) {
+            indexedShapeCompare = indexedShapesGS.get(id);
+            queryShapeCompare = queryShapeGS;
+            //TODO Unfortunately, grid-snapping both can result in intersections that otherwise
+            // wouldn't happen when the grids are adjacent. Not a big deal but our test is just a
+            // bit more lenient.
+          } else if (operation == SpatialOperation.Contains) {
+            indexedShapeCompare = indexedShapesGS.get(id);
+          } else if (operation == SpatialOperation.IsWithin) {
+            queryShapeCompare = queryShapeGS;
+          }
+          if (operation.evaluate(indexedShapeCompare, queryShapeCompare))
+            secondaryIds.add(id);
+        }
+      }
+
+      //Search and verify results
+      SpatialArgs args = new SpatialArgs(operation, queryShape);
+      if (queryShape instanceof ShapePair)
+        args.setDistErrPct(0.0);//a hack; we want to be more detailed than gridSnap(queryShape)
+      Query query = strategy.makeQuery(args);
+      SearchResults got = executeQuery(query, 100);
+      Set<String> remainingExpectedIds = new LinkedHashSet<>(expectedIds);
+      for (SearchResult result : got.results) {
+        String id = result.getId();
+        boolean removed = remainingExpectedIds.remove(id);
+        if (!removed && (!opIsDisjoint && !secondaryIds.contains(id))) {
+          fail("Shouldn't match", id, indexedShapes, indexedShapesGS, queryShape);
+        }
+      }
+      if (opIsDisjoint)
+        remainingExpectedIds.removeAll(secondaryIds);
+      if (!remainingExpectedIds.isEmpty()) {
+        String id = remainingExpectedIds.iterator().next();
+        fail("Should have matched", id, indexedShapes, indexedShapesGS, queryShape);
+      }
+    }
+  }
+
+  private Shape randomShapePairRect(boolean biasContains) {
+    Rectangle shape1 = randomRectangle();
+    Rectangle shape2 = randomRectangle();
+    return new ShapePair(shape1, shape2, biasContains);
+  }
+
+  private void fail(String label, String id, Map<String, Shape> indexedShapes, Map<String, Shape> indexedShapesGS, Shape queryShape) {
+    System.err.println("Ig:" + indexedShapesGS.get(id) + " Qg:" + gridSnap(queryShape));
+    fail(label + " I#" + id + ":" + indexedShapes.get(id) + " Q:" + queryShape);
+  }
+
+//  private Rectangle inset(Rectangle r) {
+//    //typically inset by 1 (whole numbers are easy to read)
+//    double d = Math.min(1.0, grid.getDistanceForLevel(grid.getMaxLevels()) / 4);
+//    return ctx.makeRectangle(r.getMinX() + d, r.getMaxX() - d, r.getMinY() + d, r.getMaxY() - d);
+//  }
+
+  protected Shape gridSnap(Shape snapMe) {
+    if (snapMe == null)
+      return null;
+    if (snapMe instanceof ShapePair) {
+      ShapePair me = (ShapePair) snapMe;
+      return new ShapePair(gridSnap(me.shape1), gridSnap(me.shape2), me.biasContainsThenWithin);
+    }
+    if (snapMe instanceof Point) {
+      snapMe = snapMe.getBoundingBox();
+    }
+    //The next 4 lines mimic PrefixTreeStrategy.createIndexableFields()
+    double distErrPct = ((PrefixTreeStrategy) strategy).getDistErrPct();
+    double distErr = SpatialArgs.calcDistanceFromErrPct(snapMe, distErrPct, ctx);
+    int detailLevel = grid.getLevelForDistance(distErr);
+    CellIterator cells = grid.getTreeCellIterator(snapMe, detailLevel);
+
+    //calc bounding box of cells.
+    List<Shape> cellShapes = new ArrayList<>(1024);
+    while (cells.hasNext()) {
+      Cell cell = cells.next();
+      if (!cell.isLeaf())
+        continue;
+      cellShapes.add(cell.getShape());
+    }
+    return new ShapeCollection<>(cellShapes, ctx).getBoundingBox();
+  }
+
+  /**
+   * An aggregate of 2 shapes. Unfortunately we can't simply use a ShapeCollection because:
+   * (a) ambiguity between CONTAINS and WITHIN for equal shapes, and
+   * (b) adjacent pairs could as a whole contain the input shape.
+   * The tests here are sensitive to these matters, although in practice ShapeCollection
+   * is fine.
+   */
+  private class ShapePair extends ShapeCollection<Shape> {
+
+    final Shape shape1, shape2;
+    final Shape shape1_2D, shape2_2D;//not geo (bit of a hack)
+    final boolean biasContainsThenWithin;
+
+    public ShapePair(Shape shape1, Shape shape2, boolean containsThenWithin) {
+      super(Arrays.asList(shape1, shape2), RandomSpatialOpFuzzyPrefixTreeTest.this.ctx);
+      this.shape1 = shape1;
+      this.shape2 = shape2;
+      this.shape1_2D = toNonGeo(shape1);
+      this.shape2_2D = toNonGeo(shape2);
+      biasContainsThenWithin = containsThenWithin;
+    }
+
+    private Shape toNonGeo(Shape shape) {
+      if (!ctx.isGeo())
+        return shape;//already non-geo
+      if (shape instanceof Rectangle) {
+        Rectangle rect = (Rectangle) shape;
+        if (rect.getCrossesDateLine()) {
+          return new ShapePair(
+              ctx2D.makeRectangle(rect.getMinX(), 180, rect.getMinY(), rect.getMaxY()),
+              ctx2D.makeRectangle(-180, rect.getMaxX(), rect.getMinY(), rect.getMaxY()),
+              biasContainsThenWithin);
+        } else {
+          return ctx2D.makeRectangle(rect.getMinX(), rect.getMaxX(), rect.getMinY(), rect.getMaxY());
+        }
+      }
+      //no need to do others; this addresses the -180/+180 ambiguity corner test problem
+      return shape;
+    }
+
+    @Override
+    public SpatialRelation relate(Shape other) {
+      SpatialRelation r = relateApprox(other);
+      if (r == DISJOINT)
+        return r;
+      if (r == CONTAINS)
+        return r;
+      if (r == WITHIN && !biasContainsThenWithin)
+        return r;
+
+      //See if the correct answer is actually Contains, when the indexed shapes are adjacent,
+      // creating a larger shape that contains the input shape.
+      boolean pairTouches = shape1.relate(shape2).intersects();
+      if (!pairTouches)
+        return r;
+      //test all 4 corners
+      // Note: awkwardly, we use a non-geo context for this because in geo, -180 & +180 are the same place, which means
+      //  that "other" might wrap the world horizontally and yet all its corners could be in shape1 (or shape2) even
+      //  though shape1 is only adjacent to the dateline. I couldn't think of a better way to handle this.
+      Rectangle oRect = (Rectangle)other;
+      if (cornerContainsNonGeo(oRect.getMinX(), oRect.getMinY())
+          && cornerContainsNonGeo(oRect.getMinX(), oRect.getMaxY())
+          && cornerContainsNonGeo(oRect.getMaxX(), oRect.getMinY())
+          && cornerContainsNonGeo(oRect.getMaxX(), oRect.getMaxY()) )
+        return CONTAINS;
+      return r;
+    }
+
+    private boolean cornerContainsNonGeo(double x, double y) {
+      Shape pt = ctx2D.makePoint(x, y);
+      return shape1_2D.relate(pt).intersects() || shape2_2D.relate(pt).intersects();
+    }
+
+    private SpatialRelation relateApprox(Shape other) {
+      if (biasContainsThenWithin) {
+        if (shape1.relate(other) == CONTAINS || shape1.equals(other)
+            || shape2.relate(other) == CONTAINS || shape2.equals(other)) return CONTAINS;
+
+        if (shape1.relate(other) == WITHIN && shape2.relate(other) == WITHIN) return WITHIN;
+
+      } else {
+        if ((shape1.relate(other) == WITHIN || shape1.equals(other))
+            && (shape2.relate(other) == WITHIN || shape2.equals(other))) return WITHIN;
+
+        if (shape1.relate(other) == CONTAINS || shape2.relate(other) == CONTAINS) return CONTAINS;
+      }
+
+      if (shape1.relate(other).intersects() || shape2.relate(other).intersects())
+        return INTERSECTS;//might actually be 'CONTAINS' if the pair are adjacent but we handle that later
+      return DISJOINT;
+    }
+
+    @Override
+    public String toString() {
+      return "ShapePair(" + shape1 + " , " + shape2 + ")";
+    }
+  }
+
+}

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/50a2f754/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/RandomSpatialOpStrategyTestCase.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/RandomSpatialOpStrategyTestCase.java b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/RandomSpatialOpStrategyTestCase.java
new file mode 100644
index 0000000..87f1071
--- /dev/null
+++ b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/RandomSpatialOpStrategyTestCase.java
@@ -0,0 +1,141 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.spatial.prefix;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Set;
+
+import com.spatial4j.core.shape.Shape;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.spatial.StrategyTestCase;
+import org.apache.lucene.spatial.query.SpatialArgs;
+import org.apache.lucene.spatial.query.SpatialOperation;
+
+import static com.carrotsearch.randomizedtesting.RandomizedTest.randomInt;
+import static com.carrotsearch.randomizedtesting.RandomizedTest.randomIntBetween;
+
+/** Base test harness, ideally for SpatialStrategy impls that have exact results
+ * (not grid approximated), hence "not fuzzy".
+ */
+public abstract class RandomSpatialOpStrategyTestCase extends StrategyTestCase {
+
+  //Note: this is partially redundant with StrategyTestCase.runTestQuery & testOperation
+
+  protected void testOperationRandomShapes(final SpatialOperation operation) throws IOException {
+
+    final int numIndexedShapes = randomIntBetween(1, 6);
+    List<Shape> indexedShapes = new ArrayList<>(numIndexedShapes);
+    for (int i = 0; i < numIndexedShapes; i++) {
+      indexedShapes.add(randomIndexedShape());
+    }
+
+    final int numQueryShapes = atLeast(20);
+    List<Shape> queryShapes = new ArrayList<>(numQueryShapes);
+    for (int i = 0; i < numQueryShapes; i++) {
+      queryShapes.add(randomQueryShape());
+    }
+
+    testOperation(operation, indexedShapes, queryShapes, true/*havoc*/);
+  }
+
+  protected void testOperation(final SpatialOperation operation,
+                               List<Shape> indexedShapes, List<Shape> queryShapes, boolean havoc) throws IOException {
+    //first show that when there's no data, a query will result in no results
+    {
+      Query query = strategy.makeQuery(new SpatialArgs(operation, randomQueryShape()));
+      SearchResults searchResults = executeQuery(query, 1);
+      assertEquals(0, searchResults.numFound);
+    }
+
+    //Main index loop:
+    for (int i = 0; i < indexedShapes.size(); i++) {
+      Shape shape = indexedShapes.get(i);
+      adoc(""+i, shape);
+
+      if (havoc && random().nextInt(10) == 0)
+        commit();//intermediate commit, produces extra segments
+    }
+    if (havoc) {
+      //delete some documents randomly
+      for (int id = 0; id < indexedShapes.size(); id++) {
+        if (random().nextInt(10) == 0) {
+          deleteDoc(""+id);
+          indexedShapes.set(id, null);
+        }
+      }
+    }
+
+    commit();
+
+    //Main query loop:
+    for (int queryIdx = 0; queryIdx < queryShapes.size(); queryIdx++) {
+      final Shape queryShape = queryShapes.get(queryIdx);
+
+      if (havoc)
+        preQueryHavoc();
+
+      //Generate truth via brute force:
+      // We ensure true-positive matches (if the predicate on the raw shapes match
+      //  then the search should find those same matches).
+      Set<String> expectedIds = new LinkedHashSet<>();//true-positives
+      for (int id = 0; id < indexedShapes.size(); id++) {
+        Shape indexedShape = indexedShapes.get(id);
+        if (indexedShape == null)
+          continue;
+        if (operation.evaluate(indexedShape, queryShape)) {
+          expectedIds.add(""+id);
+        }
+      }
+
+      //Search and verify results
+      SpatialArgs args = new SpatialArgs(operation, queryShape);
+      Query query = strategy.makeQuery(args);
+      SearchResults got = executeQuery(query, 100);
+      Set<String> remainingExpectedIds = new LinkedHashSet<>(expectedIds);
+      for (SearchResult result : got.results) {
+        String id = result.getId();
+        if (!remainingExpectedIds.remove(id)) {
+          fail("qIdx:" + queryIdx + " Shouldn't match", id, indexedShapes, queryShape, operation);
+        }
+      }
+      if (!remainingExpectedIds.isEmpty()) {
+        String id = remainingExpectedIds.iterator().next();
+        fail("qIdx:" + queryIdx + " Should have matched", id, indexedShapes, queryShape, operation);
+      }
+    }
+  }
+
+  private void fail(String label, String id, List<Shape> indexedShapes, Shape queryShape, SpatialOperation operation) {
+    fail("[" + operation + "] " + label
+        + " I#" + id + ":" + indexedShapes.get(Integer.parseInt(id)) + " Q:" + queryShape);
+  }
+
+  protected void preQueryHavoc() {
+    if (strategy instanceof RecursivePrefixTreeStrategy) {
+      RecursivePrefixTreeStrategy rpts = (RecursivePrefixTreeStrategy) strategy;
+      int scanLevel = randomInt(rpts.getGrid().getMaxLevels());
+      rpts.setPrefixGridScanLevel(scanLevel);
+    }
+  }
+
+  protected abstract Shape randomIndexedShape();
+
+  protected abstract Shape randomQueryShape();
+}

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/50a2f754/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/TestRecursivePrefixTreeStrategy.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/TestRecursivePrefixTreeStrategy.java b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/TestRecursivePrefixTreeStrategy.java
new file mode 100644
index 0000000..a53d52d
--- /dev/null
+++ b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/TestRecursivePrefixTreeStrategy.java
@@ -0,0 +1,122 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.spatial.prefix;
+
+import com.spatial4j.core.context.SpatialContext;
+import com.spatial4j.core.distance.DistanceUtils;
+import com.spatial4j.core.shape.Point;
+import com.spatial4j.core.shape.Shape;
+import org.apache.lucene.spatial.SpatialMatchConcern;
+import org.apache.lucene.spatial.StrategyTestCase;
+import org.apache.lucene.spatial.prefix.tree.GeohashPrefixTree;
+import org.apache.lucene.spatial.query.SpatialArgs;
+import org.apache.lucene.spatial.query.SpatialOperation;
+import org.junit.Test;
+
+import java.io.IOException;
+import java.util.HashSet;
+import java.util.Set;
+
+public class TestRecursivePrefixTreeStrategy extends StrategyTestCase {
+
+  private int maxLength;
+
+  //Tests should call this first.
+  private void init(int maxLength) {
+    this.maxLength = maxLength;
+    this.ctx = SpatialContext.GEO;
+    GeohashPrefixTree grid = new GeohashPrefixTree(ctx, maxLength);
+    this.strategy = new RecursivePrefixTreeStrategy(grid, getClass().getSimpleName());
+  }
+
+  @Test
+  public void testFilterWithVariableScanLevel() throws IOException {
+    init(GeohashPrefixTree.getMaxLevelsPossible());
+    getAddAndVerifyIndexedDocuments(DATA_WORLD_CITIES_POINTS);
+
+    //execute queries for each prefix grid scan level
+    for(int i = 0; i <= maxLength; i++) {
+      ((RecursivePrefixTreeStrategy)strategy).setPrefixGridScanLevel(i);
+      executeQueries(SpatialMatchConcern.FILTER, QTEST_Cities_Intersects_BBox);
+    }
+  }
+
+  @Test
+  public void testOneMeterPrecision() {
+    init(GeohashPrefixTree.getMaxLevelsPossible());
+    GeohashPrefixTree grid = (GeohashPrefixTree) ((RecursivePrefixTreeStrategy) strategy).getGrid();
+    //DWS: I know this to be true.  11 is needed for one meter
+    double degrees = DistanceUtils.dist2Degrees(0.001, DistanceUtils.EARTH_MEAN_RADIUS_KM);
+    assertEquals(11, grid.getLevelForDistance(degrees));
+  }
+
+  @Test
+  public void testPrecision() throws IOException{
+    init(GeohashPrefixTree.getMaxLevelsPossible());
+
+    Point iPt = ctx.makePoint(2.8028712999999925, 48.3708044);//lon, lat
+    addDocument(newDoc("iPt", iPt));
+    commit();
+
+    Point qPt = ctx.makePoint(2.4632387000000335, 48.6003516);
+
+    final double KM2DEG = DistanceUtils.dist2Degrees(1, DistanceUtils.EARTH_MEAN_RADIUS_KM);
+    final double DEG2KM = 1 / KM2DEG;
+
+    final double DIST = 35.75;//35.7499...
+    assertEquals(DIST, ctx.getDistCalc().distance(iPt, qPt) * DEG2KM, 0.001);
+
+    //distErrPct will affect the query shape precision. The indexed precision
+    // was set to nearly zilch via init(GeohashPrefixTree.getMaxLevelsPossible());
+    final double distErrPct = 0.025; //the suggested default, by the way
+    final double distMult = 1+distErrPct;
+
+    assertTrue(35.74*distMult >= DIST);
+    checkHits(q(qPt, 35.74 * KM2DEG, distErrPct), 1, null);
+
+    assertTrue(30*distMult < DIST);
+    checkHits(q(qPt, 30 * KM2DEG, distErrPct), 0, null);
+
+    assertTrue(33*distMult < DIST);
+    checkHits(q(qPt, 33 * KM2DEG, distErrPct), 0, null);
+
+    assertTrue(34*distMult < DIST);
+    checkHits(q(qPt, 34 * KM2DEG, distErrPct), 0, null);
+  }
+
+  private SpatialArgs q(Point pt, double distDEG, double distErrPct) {
+    Shape shape = ctx.makeCircle(pt, distDEG);
+    SpatialArgs args = new SpatialArgs(SpatialOperation.Intersects,shape);
+    args.setDistErrPct(distErrPct);
+    return args;
+  }
+
+  private void checkHits(SpatialArgs args, int assertNumFound, int[] assertIds) {
+    SearchResults got = executeQuery(strategy.makeQuery(args), 100);
+    assertEquals("" + args, assertNumFound, got.numFound);
+    if (assertIds != null) {
+      Set<Integer> gotIds = new HashSet<>();
+      for (SearchResult result : got.results) {
+        gotIds.add(Integer.valueOf(result.document.get("id")));
+      }
+      for (int assertId : assertIds) {
+        assertTrue("has "+assertId,gotIds.contains(assertId));
+      }
+    }
+  }
+
+}

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/50a2f754/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/TestTermQueryPrefixGridStrategy.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/TestTermQueryPrefixGridStrategy.java b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/TestTermQueryPrefixGridStrategy.java
new file mode 100644
index 0000000..1a912c0
--- /dev/null
+++ b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/TestTermQueryPrefixGridStrategy.java
@@ -0,0 +1,63 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.spatial.prefix;
+
+import com.spatial4j.core.context.SpatialContext;
+import com.spatial4j.core.shape.Shape;
+import org.apache.lucene.document.Document;
+import org.apache.lucene.document.Field;
+import org.apache.lucene.document.StoredField;
+import org.apache.lucene.document.StringField;
+import org.apache.lucene.spatial.SpatialTestCase;
+import org.apache.lucene.spatial.prefix.tree.QuadPrefixTree;
+import org.apache.lucene.spatial.query.SpatialArgsParser;
+import org.junit.Test;
+
+import java.io.IOException;
+import java.util.Arrays;
+
+
+public class TestTermQueryPrefixGridStrategy extends SpatialTestCase {
+
+  @Test
+  public void testNGramPrefixGridLosAngeles() throws IOException {
+    SpatialContext ctx = SpatialContext.GEO;
+    TermQueryPrefixTreeStrategy prefixGridStrategy = new TermQueryPrefixTreeStrategy(new QuadPrefixTree(ctx), "geo");
+
+    Shape point = ctx.makePoint(-118.243680, 34.052230);
+
+    Document losAngeles = new Document();
+    losAngeles.add(new StringField("name", "Los Angeles", Field.Store.YES));
+    for (Field field : prefixGridStrategy.createIndexableFields(point)) {
+      losAngeles.add(field);
+    }
+    losAngeles.add(new StoredField(prefixGridStrategy.getFieldName(), point.toString()));//just for diagnostics
+
+    addDocumentsAndCommit(Arrays.asList(losAngeles));
+
+    // This won't work with simple spatial context...
+    SpatialArgsParser spatialArgsParser = new SpatialArgsParser();
+    // TODO... use a non polygon query
+//    SpatialArgs spatialArgs = spatialArgsParser.parse(
+//        "Intersects(POLYGON((-127.00390625 39.8125,-112.765625 39.98828125,-111.53515625 31.375,-125.94921875 30.14453125,-127.00390625 39.8125)))",
+//        new SimpleSpatialContext());
+
+//    Query query = prefixGridStrategy.makeQuery(spatialArgs, fieldInfo);
+//    SearchResults searchResults = executeQuery(query, 1);
+//    assertEquals(1, searchResults.numFound);
+  }
+}

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/50a2f754/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/tree/DateRangePrefixTreeTest.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/tree/DateRangePrefixTreeTest.java b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/tree/DateRangePrefixTreeTest.java
new file mode 100644
index 0000000..74a989e
--- /dev/null
+++ b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/tree/DateRangePrefixTreeTest.java
@@ -0,0 +1,175 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.spatial.prefix.tree;
+
+import java.text.ParseException;
+import java.util.Arrays;
+import java.util.Calendar;
+import java.util.GregorianCalendar;
+
+import com.spatial4j.core.shape.Shape;
+import com.spatial4j.core.shape.SpatialRelation;
+import org.apache.lucene.spatial.prefix.tree.NumberRangePrefixTree.UnitNRShape;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LuceneTestCase;
+
+public class DateRangePrefixTreeTest extends LuceneTestCase {
+
+  private DateRangePrefixTree tree = DateRangePrefixTree.INSTANCE;
+
+  public void testRoundTrip() throws Exception {
+    Calendar cal = tree.newCal();
+
+    assertEquals("*", tree.toString(cal));
+
+    //test no underflow
+    assertTrue(tree.toShape(new int[]{0}, 1).toString().startsWith("-"));
+
+    //Some arbitrary date
+    cal.set(2014, Calendar.MAY, 9);
+    roundTrip(cal);
+    assertEquals("2014-05-09",tree.toString(cal));
+
+    //Earliest date
+    cal.setTimeInMillis(Long.MIN_VALUE);
+    roundTrip(cal);
+
+    //Farthest date
+    cal.setTimeInMillis(Long.MAX_VALUE);
+    roundTrip(cal);
+
+    //1BC is "0000".
+    cal.clear();
+    cal.set(Calendar.ERA, GregorianCalendar.BC);
+    cal.set(Calendar.YEAR, 1);
+    roundTrip(cal);
+    assertEquals("0000", tree.toString(cal));
+    //adding a "+" parses to the same; and a trailing 'Z' is fine too
+    assertEquals(cal, tree.parseCalendar("+0000Z"));
+
+    //2BC is "-0001"
+    cal.clear();
+    cal.set(Calendar.ERA, GregorianCalendar.BC);
+    cal.set(Calendar.YEAR, 2);
+    roundTrip(cal);
+    assertEquals("-0001", tree.toString(cal));
+
+    //1AD is "0001"
+    cal.clear();
+    cal.set(Calendar.YEAR, 1);
+    roundTrip(cal);
+    assertEquals("0001", tree.toString(cal));
+
+    //test random
+    cal.setTimeInMillis(random().nextLong());
+    roundTrip(cal);
+  }
+
+  //copies from DateRangePrefixTree
+  private static final int[] CAL_FIELDS = {
+      Calendar.YEAR, Calendar.MONTH, Calendar.DAY_OF_MONTH,
+      Calendar.HOUR_OF_DAY, Calendar.MINUTE, Calendar.SECOND, Calendar.MILLISECOND};
+
+  private void roundTrip(Calendar calOrig) throws ParseException {
+    Calendar cal = (Calendar) calOrig.clone();
+    String lastString = null;
+    while (true) {
+      String calString = tree.toString(cal);
+      assert lastString == null || calString.length() < lastString.length();
+      //test parseCalendar
+      assertEquals(cal, tree.parseCalendar(calString));
+
+      //to Shape and back to Cal
+      UnitNRShape shape = tree.toShape(cal);
+      Calendar cal2 = tree.toCalendar(shape);
+      assertEquals(calString, tree.toString(cal2));
+
+      if (!calString.equals("*")) {//not world cell
+        //to Term and back to Cell
+        Cell cell = (Cell) shape;
+        BytesRef term = cell.getTokenBytesNoLeaf(null);
+        Cell cell2 = tree.readCell(BytesRef.deepCopyOf(term), null);
+        assertEquals(calString, cell, cell2);
+        Calendar cal3 = tree.toCalendar((UnitNRShape) cell2.getShape());
+        assertEquals(calString, tree.toString(cal3));
+
+        // setLeaf comparison
+        cell2.setLeaf();
+        BytesRef termLeaf = cell2.getTokenBytesWithLeaf(null);
+        assertTrue(term.compareTo(termLeaf) < 0);
+        assertEquals(termLeaf.length, term.length + 1);
+        assertEquals(0, termLeaf.bytes[termLeaf.offset + termLeaf.length - 1]);
+        assertTrue(cell.isPrefixOf(cell2));
+      }
+
+      //end of loop; decide if should loop again with lower precision
+      final int calPrecField = tree.getCalPrecisionField(cal);
+      if (calPrecField == -1)
+        break;
+      int fieldIdx = Arrays.binarySearch(CAL_FIELDS, calPrecField);
+      assert fieldIdx >= 0;
+      int prevPrecField = (fieldIdx == 0 ? -1 : CAL_FIELDS[--fieldIdx]);
+      try {
+        tree.clearFieldsAfter(cal, prevPrecField);
+      } catch (AssertionError e) {
+        if (e.getMessage().equals("Calendar underflow"))
+          return;
+        throw e;
+      }
+      lastString = calString;
+    }
+  }
+
+  public void testShapeRelations() throws ParseException {
+    //note: left range is 264000 at the thousand year level whereas right value is exact year
+    assertEquals(SpatialRelation.WITHIN,
+        tree.parseShape("[-264000 TO -264000-11-20]").relate(tree.parseShape("-264000")));
+
+    Shape shapeA = tree.parseShape("[3122-01-23 TO 3122-11-27]");
+    Shape shapeB = tree.parseShape("[3122-08 TO 3122-11]");
+    assertEquals(SpatialRelation.INTERSECTS, shapeA.relate(shapeB));
+
+    shapeA = tree.parseShape("3122");
+    shapeB = tree.parseShape("[* TO 3122-10-31]");
+    assertEquals(SpatialRelation.INTERSECTS, shapeA.relate(shapeB));
+
+    shapeA = tree.parseShape("[3122-05-28 TO 3122-06-29]");
+    shapeB = tree.parseShape("[3122 TO 3122-04]");
+    assertEquals(SpatialRelation.DISJOINT, shapeA.relate(shapeB));
+  }
+
+  public void testShapeRangeOptimizer() throws ParseException {
+    assertEquals("[2014-08 TO 2014-09]", tree.parseShape("[2014-08-01 TO 2014-09-30]").toString());
+
+    assertEquals("2014", tree.parseShape("[2014-01-01 TO 2014-12-31]").toString());
+
+    assertEquals("2014",    tree.parseShape("[2014-01 TO 2014]").toString());
+    assertEquals("2014-01", tree.parseShape("[2014 TO 2014-01]").toString());
+    assertEquals("2014-12", tree.parseShape("[2014-12 TO 2014]").toString());
+
+    assertEquals("[2014 TO 2014-04-06]", tree.parseShape("[2014-01 TO 2014-04-06]").toString());
+
+    assertEquals("*", tree.parseShape("[* TO *]").toString());
+
+    assertEquals("2014-08-01", tree.parseShape("[2014-08-01 TO 2014-08-01]").toString());
+
+    assertEquals("[2014 TO 2014-09-15]", tree.parseShape("[2014 TO 2014-09-15]").toString());
+
+    assertEquals("[* TO 2014-09-15]", tree.parseShape("[* TO 2014-09-15]").toString());
+  }
+
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/50a2f754/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTreeTest.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTreeTest.java b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTreeTest.java
new file mode 100644
index 0000000..403b8d1
--- /dev/null
+++ b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTreeTest.java
@@ -0,0 +1,114 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.spatial.prefix.tree;
+
+import com.spatial4j.core.context.SpatialContext;
+import com.spatial4j.core.shape.Point;
+import com.spatial4j.core.shape.Rectangle;
+import com.spatial4j.core.shape.Shape;
+import org.apache.lucene.document.Document;
+import org.apache.lucene.document.Field;
+import org.apache.lucene.document.Field.Store;
+import org.apache.lucene.document.TextField;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.ScoreDoc;
+import org.apache.lucene.search.TopDocs;
+import org.apache.lucene.spatial.SpatialTestCase;
+import org.apache.lucene.spatial.prefix.TermQueryPrefixTreeStrategy;
+import org.apache.lucene.spatial.query.SpatialArgs;
+import org.apache.lucene.spatial.query.SpatialOperation;
+import org.junit.Before;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class SpatialPrefixTreeTest extends SpatialTestCase {
+
+  //TODO plug in others and test them
+  private SpatialContext ctx;
+  private SpatialPrefixTree trie;
+
+  @Override
+  @Before
+  public void setUp() throws Exception {
+    super.setUp();
+    ctx = SpatialContext.GEO;
+  }
+
+  @Test
+  public void testCellTraverse() {
+    trie = new GeohashPrefixTree(ctx,4);
+
+    Cell prevC = null;
+    Cell c = trie.getWorldCell();
+    assertEquals(0, c.getLevel());
+    assertEquals(ctx.getWorldBounds(), c.getShape());
+    while (c.getLevel() < trie.getMaxLevels()) {
+      prevC = c;
+      List<Cell> subCells = new ArrayList<>();
+      CellIterator subCellsIter = c.getNextLevelCells(null);
+      while (subCellsIter.hasNext()) {
+        subCells.add(subCellsIter.next());
+      }
+      c = subCells.get(random().nextInt(subCells.size()-1));
+
+      assertEquals(prevC.getLevel()+1,c.getLevel());
+      Rectangle prevNShape = (Rectangle) prevC.getShape();
+      Shape s = c.getShape();
+      Rectangle sbox = s.getBoundingBox();
+      assertTrue(prevNShape.getWidth() > sbox.getWidth());
+      assertTrue(prevNShape.getHeight() > sbox.getHeight());
+    }
+  }
+  /**
+   * A PrefixTree pruning optimization gone bad, applicable when optimize=true.
+   * See <a href="https://issues.apache.org/jira/browse/LUCENE-4770">LUCENE-4770</a>.
+   */
+  @Test
+  public void testBadPrefixTreePrune() throws Exception {
+
+    trie = new QuadPrefixTree(ctx, 12);
+    TermQueryPrefixTreeStrategy strategy = new TermQueryPrefixTreeStrategy(trie, "geo");
+    Document doc = new Document();
+    doc.add(new TextField("id", "1", Store.YES));
+
+    Shape area = ctx.makeRectangle(-122.82, -122.78, 48.54, 48.56);
+
+    Field[] fields = strategy.createIndexableFields(area, 0.025);
+    for (Field field : fields) {
+      doc.add(field);
+    }
+    addDocument(doc);
+
+    Point upperleft = ctx.makePoint(-122.88, 48.54);
+    Point lowerright = ctx.makePoint(-122.82, 48.62);
+
+    Query query = strategy.makeQuery(new SpatialArgs(SpatialOperation.Intersects, ctx.makeRectangle(upperleft, lowerright)));
+
+    commit();
+
+    TopDocs search = indexSearcher.search(query, 10);
+    ScoreDoc[] scoreDocs = search.scoreDocs;
+    for (ScoreDoc scoreDoc : scoreDocs) {
+      System.out.println(indexSearcher.doc(scoreDoc.doc));
+    }
+
+    assertEquals(1, search.totalHits);
+  }
+
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/50a2f754/lucene/spatial-extras/src/test/org/apache/lucene/spatial/query/SpatialArgsParserTest.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/test/org/apache/lucene/spatial/query/SpatialArgsParserTest.java b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/query/SpatialArgsParserTest.java
new file mode 100644
index 0000000..b7bd50d
--- /dev/null
+++ b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/query/SpatialArgsParserTest.java
@@ -0,0 +1,81 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.spatial.query;
+
+import com.spatial4j.core.context.SpatialContext;
+import com.spatial4j.core.shape.Rectangle;
+import org.apache.lucene.util.LuceneTestCase;
+import org.junit.Test;
+
+import java.text.ParseException;
+
+//Tests SpatialOperation somewhat too
+public class SpatialArgsParserTest extends LuceneTestCase {
+
+  private SpatialContext ctx = SpatialContext.GEO;
+
+  //The args parser is only dependent on the ctx for IO so I don't care to test
+  // with other implementations.
+
+  @Test
+  public void testArgsParser() throws Exception {
+    SpatialArgsParser parser = new SpatialArgsParser();
+
+    String arg = SpatialOperation.IsWithin + "(Envelope(-10, 10, 20, -20))";
+    SpatialArgs out = parser.parse(arg, ctx);
+    assertEquals(SpatialOperation.IsWithin, out.getOperation());
+    Rectangle bounds = (Rectangle) out.getShape();
+    assertEquals(-10.0, bounds.getMinX(), 0D);
+    assertEquals(10.0, bounds.getMaxX(), 0D);
+
+    // Disjoint should not be scored
+    arg = SpatialOperation.IsDisjointTo + " (Envelope(-10,-20,20,10))";
+    out = parser.parse(arg, ctx);
+    assertEquals(SpatialOperation.IsDisjointTo, out.getOperation());
+
+    try {
+      parser.parse(SpatialOperation.IsDisjointTo + "[ ]", ctx);
+      fail("spatial operations need args");
+    }
+    catch (Exception ex) {//expected
+    }
+
+    try {
+      parser.parse("XXXX(Envelope(-10, 10, 20, -20))", ctx);
+      fail("unknown operation!");
+    }
+    catch (Exception ex) {//expected
+    }
+
+    assertAlias(SpatialOperation.IsWithin, "CoveredBy");
+    assertAlias(SpatialOperation.IsWithin, "COVEREDBY");
+    assertAlias(SpatialOperation.IsWithin, "coveredBy");
+    assertAlias(SpatialOperation.IsWithin, "Within");
+    assertAlias(SpatialOperation.IsEqualTo, "Equals");
+    assertAlias(SpatialOperation.IsDisjointTo, "disjoint");
+    assertAlias(SpatialOperation.Contains, "Covers");
+  }
+
+  private void assertAlias(SpatialOperation op, final String name) throws ParseException {
+    String arg;
+    SpatialArgs out;
+    arg = name + "(Point(0 0))";
+    out = new SpatialArgsParser().parse(arg, ctx);
+    assertEquals(op, out.getOperation());
+  }
+
+}


Mime
View raw message