You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by ho...@apache.org on 2016/03/01 18:07:03 UTC
[20/50] [abbrv] lucene-solr git commit: LUCENE-7015: Refactor spatial
module to spatial-extras
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/89db4950/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/89db4950/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/89db4950/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/89db4950/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/89db4950/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/89db4950/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/89db4950/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/89db4950/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/89db4950/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/89db4950/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/89db4950/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/89db4950/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..93b95f3
--- /dev/null
+++ b/lucene/spatial-extras/src/test/org/apache/lucene/spatial/query/SpatialArgsParserTest.java
@@ -0,0 +1,77 @@
+/*
+ * 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());
+
+ // spatial operations need args
+ expectThrows(Exception.class, () -> {
+ parser.parse(SpatialOperation.IsDisjointTo + "[ ]", ctx);
+ });
+
+ // unknown operation
+ expectThrows(Exception.class, () -> {
+ parser.parse("XXXX(Envelope(-10, 10, 20, -20))", ctx);
+ });
+
+ 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());
+ }
+
+}