You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by nk...@apache.org on 2016/06/20 15:39:53 UTC
lucene-solr:master: LUCENE-7343: Cleanup GeoPoint by sharing relation
logic and removing stale code.
Repository: lucene-solr
Updated Branches:
refs/heads/master 97b6c5b8f -> fb3480b80
LUCENE-7343: Cleanup GeoPoint by sharing relation logic and removing stale code.
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/fb3480b8
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/fb3480b8
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/fb3480b8
Branch: refs/heads/master
Commit: fb3480b807149ef2777e3e12eeaf925a5622efe2
Parents: 97b6c5b
Author: Nicholas Knize <nk...@gmail.com>
Authored: Mon Jun 20 10:38:28 2016 -0500
Committer: Nicholas Knize <nk...@gmail.com>
Committed: Mon Jun 20 10:38:28 2016 -0500
----------------------------------------------------------------------
.../java/org/apache/lucene/geo/GeoUtils.java | 43 +++-
.../document/LatLonPointDistanceQuery.java | 35 +--
.../geopoint/search/GeoPointDistanceQuery.java | 15 +-
.../search/GeoPointDistanceQueryImpl.java | 63 ++----
.../search/GeoPointInBBoxQueryImpl.java | 32 +--
.../search/GeoPointInPolygonQueryImpl.java | 14 +-
.../geopoint/search/GeoPointMultiTermQuery.java | 49 ++---
.../geopoint/search/GeoPointTermsEnum.java | 212 ++++++-------------
8 files changed, 165 insertions(+), 298 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/fb3480b8/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java b/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java
index c11dfe1..723cbaf 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java
@@ -1,8 +1,3 @@
-package org.apache.lucene.geo;
-
-import static org.apache.lucene.util.SloppyMath.TO_RADIANS;
-import static org.apache.lucene.util.SloppyMath.cos;
-
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
@@ -19,6 +14,11 @@ import static org.apache.lucene.util.SloppyMath.cos;
* See the License for the specific language governing permissions and
* limitations under the License.
*/
+package org.apache.lucene.geo;
+
+import static org.apache.lucene.util.SloppyMath.TO_RADIANS;
+import static org.apache.lucene.util.SloppyMath.cos;
+import static org.apache.lucene.util.SloppyMath.haversinMeters;
/**
* Basic reusable geo-spatial utility methods
@@ -91,4 +91,37 @@ public final class GeoUtils {
public static double sloppySin(double a) {
return cos(a - PIO2);
}
+
+ /**
+ * binary search to find the exact sortKey needed to match the specified radius
+ * any sort key lte this is a query match.
+ */
+ public static double distanceQuerySortKey(double radius) {
+ // effectively infinite
+ if (radius >= haversinMeters(Double.MAX_VALUE)) {
+ return haversinMeters(Double.MAX_VALUE);
+ }
+
+ // this is a search through non-negative long space only
+ long lo = 0;
+ long hi = Double.doubleToRawLongBits(Double.MAX_VALUE);
+ while (lo <= hi) {
+ long mid = (lo + hi) >>> 1;
+ double sortKey = Double.longBitsToDouble(mid);
+ double midRadius = haversinMeters(sortKey);
+ if (midRadius == radius) {
+ return sortKey;
+ } else if (midRadius > radius) {
+ hi = mid - 1;
+ } else {
+ lo = mid + 1;
+ }
+ }
+
+ // not found: this is because a user can supply an arbitrary radius, one that we will never
+ // calculate exactly via our haversin method.
+ double ceil = Double.longBitsToDouble(lo);
+ assert haversinMeters(ceil) > radius;
+ return ceil;
+ }
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/fb3480b8/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java
index 29fac79..d479713 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java
@@ -96,7 +96,7 @@ final class LatLonPointDistanceQuery extends Query {
}
// compute exact sort key: avoid any asin() computations
- final double sortKey = sortKey(radiusMeters);
+ final double sortKey = GeoUtils.distanceQuerySortKey(radiusMeters);
final double axisLat = Rectangle.axisLat(latitude, radiusMeters);
@@ -215,39 +215,6 @@ final class LatLonPointDistanceQuery extends Query {
};
}
- /**
- * binary search to find the exact sortKey needed to match the specified radius
- * any sort key <= this is a query match.
- */
- static double sortKey(double radius) {
- // effectively infinite
- if (radius >= SloppyMath.haversinMeters(Double.MAX_VALUE)) {
- return SloppyMath.haversinMeters(Double.MAX_VALUE);
- }
-
- // this is a search through non-negative long space only
- long lo = 0;
- long hi = Double.doubleToRawLongBits(Double.MAX_VALUE);
- while (lo <= hi) {
- long mid = (lo + hi) >>> 1;
- double sortKey = Double.longBitsToDouble(mid);
- double midRadius = SloppyMath.haversinMeters(sortKey);
- if (midRadius == radius) {
- return sortKey;
- } else if (midRadius > radius) {
- hi = mid - 1;
- } else {
- lo = mid + 1;
- }
- }
-
- // not found: this is because a user can supply an arbitrary radius, one that we will never
- // calculate exactly via our haversin method.
- double ceil = Double.longBitsToDouble(lo);
- assert SloppyMath.haversinMeters(ceil) > radius;
- return ceil;
- }
-
public String getField() {
return field;
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/fb3480b8/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQuery.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQuery.java b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQuery.java
index 3875ebf..743c116 100644
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQuery.java
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQuery.java
@@ -45,6 +45,8 @@ public class GeoPointDistanceQuery extends GeoPointInBBoxQuery {
protected final double centerLon;
/** distance (in meters) from lat, lon center location */
protected final double radiusMeters;
+ /** partial haversin computation */
+ protected final double sortKey;
// we must check these before passing to superclass or circleToBBox, or users can get a strange exception!
private static double checkRadius(double radiusMeters) {
@@ -53,17 +55,7 @@ public class GeoPointDistanceQuery extends GeoPointInBBoxQuery {
}
return radiusMeters;
}
-
- private static double checkLatitude(double centerLat) {
- GeoUtils.checkLatitude(centerLat);
- return centerLat;
- }
-
- private static double checkLongitude(double centerLon) {
- GeoUtils.checkLongitude(centerLon);
- return centerLon;
- }
-
+
/**
* Constructs a Query for all {@link org.apache.lucene.spatial.geopoint.document.GeoPointField} types within a
* distance (in meters) from a given point
@@ -79,6 +71,7 @@ public class GeoPointDistanceQuery extends GeoPointInBBoxQuery {
this.centerLat = centerLat;
this.centerLon = centerLon;
this.radiusMeters = radiusMeters;
+ this.sortKey = GeoUtils.distanceQuerySortKey(radiusMeters);
}
@Override
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/fb3480b8/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQueryImpl.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQueryImpl.java b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQueryImpl.java
index 83e87c5..ea85240 100644
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQueryImpl.java
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointDistanceQueryImpl.java
@@ -17,6 +17,7 @@
package org.apache.lucene.spatial.geopoint.search;
import org.apache.lucene.geo.Rectangle;
+import org.apache.lucene.index.PointValues;
import org.apache.lucene.search.MultiTermQuery;
import org.apache.lucene.util.SloppyMath;
@@ -28,9 +29,6 @@ final class GeoPointDistanceQueryImpl extends GeoPointInBBoxQueryImpl {
private final GeoPointDistanceQuery distanceQuery;
private final double centerLon;
- // optimization, maximum partial haversin needed to be a candidate
- private final double maxPartialDistance;
-
// optimization, used for detecting axis cross
final double axisLat;
@@ -39,15 +37,6 @@ final class GeoPointDistanceQueryImpl extends GeoPointInBBoxQueryImpl {
super(field, bbox.minLat, bbox.maxLat, bbox.minLon, bbox.maxLon);
distanceQuery = q;
centerLon = centerLonUnwrapped;
-
- // unless our box is crazy, we can use this bound
- // to reject edge cases faster in postFilter()
- if (bbox.maxLon - centerLon < 90 && centerLon - bbox.minLon < 90) {
- maxPartialDistance = Math.max(SloppyMath.haversinSortKey(distanceQuery.centerLat, centerLon, distanceQuery.centerLat, bbox.maxLon),
- SloppyMath.haversinSortKey(distanceQuery.centerLat, centerLon, bbox.maxLat, centerLon));
- } else {
- maxPartialDistance = Double.POSITIVE_INFINITY;
- }
axisLat = Rectangle.axisLat(distanceQuery.centerLat, distanceQuery.radiusMeters);
}
@@ -67,40 +56,31 @@ final class GeoPointDistanceQueryImpl extends GeoPointInBBoxQueryImpl {
}
@Override
- protected boolean cellCrosses(final double minLat, final double maxLat, final double minLon, final double maxLon) {
+ protected PointValues.Relation relate(final double minLat, final double maxLat, final double minLon, final double maxLon) {
// bounding box check
- if (maxLat < GeoPointDistanceQueryImpl.this.minLat ||
- maxLon < GeoPointDistanceQueryImpl.this.minLon ||
- minLat > GeoPointDistanceQueryImpl.this.maxLat ||
- minLon > GeoPointDistanceQueryImpl.this.maxLon) {
- return false;
- } else if ((centerLon < minLon || centerLon > maxLon) && (axisLat+ Rectangle.AXISLAT_ERROR < minLat || axisLat- Rectangle.AXISLAT_ERROR > maxLat)) {
- if (SloppyMath.haversinMeters(distanceQuery.centerLat, centerLon, minLat, minLon) > distanceQuery.radiusMeters &&
- SloppyMath.haversinMeters(distanceQuery.centerLat, centerLon, minLat, maxLon) > distanceQuery.radiusMeters &&
- SloppyMath.haversinMeters(distanceQuery.centerLat, centerLon, maxLat, minLon) > distanceQuery.radiusMeters &&
- SloppyMath.haversinMeters(distanceQuery.centerLat, centerLon, maxLat, maxLon) > distanceQuery.radiusMeters) {
- return false;
+ if (cellIntersectsMBR(minLat, maxLat, minLon, maxLon) == false) {
+ return PointValues.Relation.CELL_OUTSIDE_QUERY;
+ }
+ if ((centerLon < minLon || centerLon > maxLon) && (axisLat + Rectangle.AXISLAT_ERROR < minLat
+ || axisLat- Rectangle.AXISLAT_ERROR > maxLat)) {
+ if (SloppyMath.haversinSortKey(distanceQuery.centerLat, centerLon, minLat, minLon) > distanceQuery.sortKey &&
+ SloppyMath.haversinSortKey(distanceQuery.centerLat, centerLon, minLat, maxLon) > distanceQuery.sortKey &&
+ SloppyMath.haversinSortKey(distanceQuery.centerLat, centerLon, maxLat, minLon) > distanceQuery.sortKey &&
+ SloppyMath.haversinSortKey(distanceQuery.centerLat, centerLon, maxLat, maxLon) > distanceQuery.sortKey) {
+ return PointValues.Relation.CELL_OUTSIDE_QUERY;
}
}
- return true;
- }
- @Override
- protected boolean cellWithin(final double minLat, final double maxLat, final double minLon, final double maxLon) {
if (maxLon - centerLon < 90 && centerLon - minLon < 90 &&
- SloppyMath.haversinMeters(distanceQuery.centerLat, centerLon, minLat, minLon) <= distanceQuery.radiusMeters &&
- SloppyMath.haversinMeters(distanceQuery.centerLat, centerLon, minLat, maxLon) <= distanceQuery.radiusMeters &&
- SloppyMath.haversinMeters(distanceQuery.centerLat, centerLon, maxLat, minLon) <= distanceQuery.radiusMeters &&
- SloppyMath.haversinMeters(distanceQuery.centerLat, centerLon, maxLat, maxLon) <= distanceQuery.radiusMeters) {
+ SloppyMath.haversinSortKey(distanceQuery.centerLat, centerLon, minLat, minLon) <= distanceQuery.sortKey &&
+ SloppyMath.haversinSortKey(distanceQuery.centerLat, centerLon, minLat, maxLon) <= distanceQuery.sortKey &&
+ SloppyMath.haversinSortKey(distanceQuery.centerLat, centerLon, maxLat, minLon) <= distanceQuery.sortKey &&
+ SloppyMath.haversinSortKey(distanceQuery.centerLat, centerLon, maxLat, maxLon) <= distanceQuery.sortKey) {
// we are fully enclosed, collect everything within this subtree
- return true;
+ return PointValues.Relation.CELL_INSIDE_QUERY;
}
- return false;
- }
- @Override
- protected boolean cellIntersectsShape(final double minLat, final double maxLat, final double minLon, final double maxLon) {
- return cellCrosses(minLat, maxLat, minLon, maxLon);
+ return PointValues.Relation.CELL_CROSSES_QUERY;
}
/**
@@ -118,12 +98,11 @@ final class GeoPointDistanceQueryImpl extends GeoPointInBBoxQueryImpl {
// first check the partial distance, if its more than that, it can't be <= radiusMeters
double h1 = SloppyMath.haversinSortKey(distanceQuery.centerLat, centerLon, lat, lon);
- if (h1 > maxPartialDistance) {
- return false;
+ if (h1 <= distanceQuery.sortKey) {
+ return true;
}
- // fully confirm with part 2:
- return SloppyMath.haversinMeters(h1) <= distanceQuery.radiusMeters;
+ return false;
}
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/fb3480b8/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInBBoxQueryImpl.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInBBoxQueryImpl.java b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInBBoxQueryImpl.java
index fcae635..ee1f8da 100644
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInBBoxQueryImpl.java
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInBBoxQueryImpl.java
@@ -16,6 +16,7 @@
*/
package org.apache.lucene.spatial.geopoint.search;
+import org.apache.lucene.index.PointValues.Relation;
import org.apache.lucene.search.MultiTermQuery;
import org.apache.lucene.util.SloppyMath;
import org.apache.lucene.spatial.geopoint.document.GeoPointField;
@@ -71,28 +72,17 @@ class GeoPointInBBoxQueryImpl extends GeoPointMultiTermQuery {
super(query);
}
- /**
- * Determine whether the quad-cell crosses the shape
- */
@Override
- protected boolean cellCrosses(final double minLat, final double maxLat, final double minLon, final double maxLon) {
- return GeoRelationUtils.rectCrosses(minLat, maxLat, minLon, maxLon, GeoPointInBBoxQueryImpl.this.minLat,
- GeoPointInBBoxQueryImpl.this.maxLat, GeoPointInBBoxQueryImpl.this.minLon, GeoPointInBBoxQueryImpl.this.maxLon);
- }
-
- /**
- * Determine whether quad-cell is within the shape
- */
- @Override
- protected boolean cellWithin(final double minLat, final double maxLat, final double minLon, final double maxLon) {
- return GeoRelationUtils.rectWithin(minLat, maxLat, minLon, maxLon, GeoPointInBBoxQueryImpl.this.minLat,
- GeoPointInBBoxQueryImpl.this.maxLat,
- GeoPointInBBoxQueryImpl.this.minLon, GeoPointInBBoxQueryImpl.this.maxLon);
- }
-
- @Override
- protected boolean cellIntersectsShape(final double minLat, final double maxLat, final double minLon, final double maxLon) {
- return cellIntersectsMBR(minLat, maxLat, minLon, maxLon);
+ protected Relation relate(final double minLat, final double maxLat, final double minLon, final double maxLon) {
+ if (GeoRelationUtils.rectCrosses(minLat, maxLat, minLon, maxLon, GeoPointInBBoxQueryImpl.this.minLat,
+ GeoPointInBBoxQueryImpl.this.maxLat, GeoPointInBBoxQueryImpl.this.minLon, GeoPointInBBoxQueryImpl.this.maxLon)) {
+ return Relation.CELL_CROSSES_QUERY;
+ } else if (GeoRelationUtils.rectWithin(minLat, maxLat, minLon, maxLon, GeoPointInBBoxQueryImpl.this.minLat,
+ GeoPointInBBoxQueryImpl.this.maxLat,
+ GeoPointInBBoxQueryImpl.this.minLon, GeoPointInBBoxQueryImpl.this.maxLon)) {
+ return Relation.CELL_INSIDE_QUERY;
+ }
+ return Relation.CELL_OUTSIDE_QUERY;
}
@Override
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/fb3480b8/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInPolygonQueryImpl.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInPolygonQueryImpl.java b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInPolygonQueryImpl.java
index c931b58..425b40e 100644
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInPolygonQueryImpl.java
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointInPolygonQueryImpl.java
@@ -57,18 +57,8 @@ final class GeoPointInPolygonQueryImpl extends GeoPointInBBoxQueryImpl {
}
@Override
- protected boolean cellCrosses(final double minLat, final double maxLat, final double minLon, final double maxLon) {
- return polygons.relate(minLat, maxLat, minLon, maxLon) == Relation.CELL_CROSSES_QUERY;
- }
-
- @Override
- protected boolean cellWithin(final double minLat, final double maxLat, final double minLon, final double maxLon) {
- return polygons.relate(minLat, maxLat, minLon, maxLon) == Relation.CELL_INSIDE_QUERY;
- }
-
- @Override
- protected boolean cellIntersectsShape(final double minLat, final double maxLat, final double minLon, final double maxLon) {
- return polygons.relate(minLat, maxLat, minLon, maxLon) != Relation.CELL_OUTSIDE_QUERY;
+ protected Relation relate(final double minLat, final double maxLat, final double minLon, final double maxLon) {
+ return polygons.relate(minLat, maxLat, minLon, maxLon);
}
/**
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/fb3480b8/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointMultiTermQuery.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointMultiTermQuery.java b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointMultiTermQuery.java
index 4037237..5117206 100644
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointMultiTermQuery.java
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointMultiTermQuery.java
@@ -1,5 +1,3 @@
-package org.apache.lucene.spatial.geopoint.search;
-
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
@@ -16,10 +14,12 @@ package org.apache.lucene.spatial.geopoint.search;
* See the License for the specific language governing permissions and
* limitations under the License.
*/
+package org.apache.lucene.spatial.geopoint.search;
import java.io.IOException;
import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.index.PointValues.Relation;
import org.apache.lucene.index.Terms;
import org.apache.lucene.index.TermsEnum;
import org.apache.lucene.search.MultiTermQuery;
@@ -27,7 +27,7 @@ import org.apache.lucene.search.Query;
import org.apache.lucene.util.AttributeSource;
import org.apache.lucene.spatial.geopoint.document.GeoPointField;
import org.apache.lucene.spatial.util.GeoRelationUtils;
-import org.apache.lucene.geo.GeoUtils;
+import org.apache.lucene.util.BitUtil;
import org.apache.lucene.util.SloppyMath;
/**
@@ -39,9 +39,14 @@ import org.apache.lucene.util.SloppyMath;
abstract class GeoPointMultiTermQuery extends MultiTermQuery {
// simple bounding box optimization - no objects used to avoid dependencies
protected final double minLon;
+ protected final long minEncoded;
+ protected final int minX;
protected final double minLat;
+ protected final int minY;
protected final double maxLon;
+ protected final int maxX;
protected final double maxLat;
+ protected final int maxY;
protected final short maxShift;
protected final CellComparator cellComparator;
@@ -53,10 +58,13 @@ abstract class GeoPointMultiTermQuery extends MultiTermQuery {
public GeoPointMultiTermQuery(String field, final double minLat, final double maxLat, final double minLon, final double maxLon) {
super(field);
- GeoUtils.checkLatitude(minLat);
- GeoUtils.checkLatitude(maxLat);
- GeoUtils.checkLongitude(minLon);
- GeoUtils.checkLongitude(maxLon);
+ this.minEncoded = GeoPointField.encodeLatLon(minLat, minLon);
+ final long maxEncoded = GeoPointField.encodeLatLon(maxLat, maxLon);
+
+ this.minX = (int)BitUtil.deinterleave(minEncoded);
+ this.maxX = (int)BitUtil.deinterleave(maxEncoded);
+ this.minY = (int)BitUtil.deinterleave(minEncoded >>> 1);
+ this.maxY = (int)BitUtil.deinterleave(maxEncoded >>> 1);
this.minLat = minLat;
this.maxLat = maxLat;
@@ -125,28 +133,15 @@ abstract class GeoPointMultiTermQuery extends MultiTermQuery {
geoPointQuery.minLon, geoPointQuery.maxLon);
}
- /**
- * Return whether quad-cell contains the bounding box of this shape
- */
- protected boolean cellContains(final double minLat, final double maxLat, final double minLon, final double maxLon) {
- return GeoRelationUtils.rectWithin(geoPointQuery.minLat, geoPointQuery.maxLat, geoPointQuery.minLon,
- geoPointQuery.maxLon, minLat, maxLat, minLon, maxLon);
+ /** uses encoded values to check whether quad cell intersects the shape bounding box */
+ protected boolean cellIntersectsMBR(final long min, final long max) {
+ return !(Integer.compareUnsigned((int)BitUtil.deinterleave(max), geoPointQuery.minX) < 0
+ || Integer.compareUnsigned((int)BitUtil.deinterleave(min), geoPointQuery.maxX) > 0
+ || Integer.compareUnsigned((int)BitUtil.deinterleave(max >>> 1), geoPointQuery.minY) < 0
+ || Integer.compareUnsigned((int)BitUtil.deinterleave(min >>> 1), geoPointQuery.maxY) > 0);
}
- /**
- * Determine whether the quad-cell crosses the shape
- */
- abstract protected boolean cellCrosses(final double minLat, final double maxLat, final double minLon, final double maxLon);
-
- /**
- * Determine whether quad-cell is within the shape
- */
- abstract protected boolean cellWithin(final double minLat, final double maxLat, final double minLon, final double maxLon);
-
- /**
- * Default shape is a rectangle, so this returns the same as {@code cellIntersectsMBR}
- */
- abstract protected boolean cellIntersectsShape(final double minLat, final double maxLat, final double minLon, final double maxLon);
+ abstract protected Relation relate(final double minLat, final double maxLat, final double minLon, final double maxLon);
abstract protected boolean postFilter(final double lat, final double lon);
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/fb3480b8/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointTermsEnum.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointTermsEnum.java b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointTermsEnum.java
index 1a3ed4b..533597d 100644
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointTermsEnum.java
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointTermsEnum.java
@@ -1,5 +1,3 @@
-package org.apache.lucene.spatial.geopoint.search;
-
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
@@ -16,13 +14,17 @@ package org.apache.lucene.spatial.geopoint.search;
* See the License for the specific language governing permissions and
* limitations under the License.
*/
+package org.apache.lucene.spatial.geopoint.search;
import org.apache.lucene.index.FilteredTermsEnum;
+import org.apache.lucene.index.PointValues.Relation;
import org.apache.lucene.index.TermsEnum;
import org.apache.lucene.util.BytesRef;
import org.apache.lucene.util.BytesRefBuilder;
import org.apache.lucene.spatial.geopoint.document.GeoPointField;
+import static org.apache.lucene.spatial.geopoint.document.GeoPointField.decodeLatitude;
+import static org.apache.lucene.spatial.geopoint.document.GeoPointField.decodeLongitude;
import static org.apache.lucene.spatial.geopoint.document.GeoPointField.geoCodedToPrefixCoded;
import static org.apache.lucene.spatial.geopoint.document.GeoPointField.prefixCodedToGeoCoded;
import static org.apache.lucene.spatial.geopoint.document.GeoPointField.getPrefixCodedShift;
@@ -37,21 +39,14 @@ import static org.apache.lucene.spatial.geopoint.document.GeoPointField.getPrefi
*/
final class GeoPointTermsEnum extends FilteredTermsEnum {
private final short maxShift;
- private final BytesRefBuilder currentCellBRB = new BytesRefBuilder();
- private final BytesRefBuilder nextSubRangeBRB = new BytesRefBuilder();
private final GeoPointMultiTermQuery.CellComparator relationImpl;
+ private final BytesRefBuilder currentCellBRB;
+ private final Range range;
private short shift; // shift mask
- private long currStart; // range start as encoded long
- private long currEnd; // range end as encoded long
-
- private final Range currentRange = new Range(-1, shift, true);;
- private final Range nextRange = new Range(-1, shift, true);
- private BytesRef currentCell;
-
+ private long start; // range start as encoded long
+ private long end; // range end as encoded long
private boolean hasNext = false;
- private boolean withinOnly = false;
- private long lastWithin;
public GeoPointTermsEnum(final TermsEnum tenum, final GeoPointMultiTermQuery query) {
super(tenum);
@@ -60,143 +55,83 @@ final class GeoPointTermsEnum extends FilteredTermsEnum {
// start shift at maxShift value (from computeMaxShift)
this.shift = maxShift;
final long mask = (1L << shift) - 1;
- this.currStart = GeoPointField.encodeLatLon(query.minLat, query.minLon) & ~mask;
- this.currEnd = currStart | mask;
- }
-
- private boolean within(final double minLat, final double maxLat, final double minLon, final double maxLon) {
- return relationImpl.cellWithin(minLat, maxLat, minLon, maxLon);
- }
-
- private boolean boundary(final double minLat, final double maxLat, final double minLon, final double maxLon) {
- return shift == maxShift && relationImpl.cellIntersectsShape(minLat, maxLat, minLon, maxLon);
+ this.start = query.minEncoded & ~mask;
+ this.end = start | mask;
+ this.currentCellBRB = new BytesRefBuilder();
+ this.range = new Range(-1, shift, true);
}
- private boolean nextWithin() {
- if (withinOnly == false) {
- return false;
- }
- currStart += (1L << shift);
- setNextRange(false);
- currentRange.set(nextRange);
- hasNext = true;
-
- withinOnly = lastWithin != currStart;
- if (withinOnly == false) advanceVariables();
- return true;
- }
-
- private void nextRelation() {
- double minLon = GeoPointField.decodeLongitude(currStart);
- double minLat = GeoPointField.decodeLatitude(currStart);
- double maxLon;
- double maxLat;
- boolean isWithin;
+ private boolean nextRelation() {
+ Relation relation;
do {
- maxLon = GeoPointField.decodeLongitude(currEnd);
- maxLat = GeoPointField.decodeLatitude(currEnd);
-
- isWithin = false;
// within or a boundary
- if (boundary(minLat, maxLat, minLon, maxLon) == true) {
- isWithin = within(minLat, maxLat, minLon, maxLon);
- final int m;
- if (isWithin == false || (m = shift % GeoPointField.PRECISION_STEP) == 0) {
- setNextRange(isWithin == false);
+ if ((shift % GeoPointField.PRECISION_STEP) == 0 &&
+ (relation = relationImpl.relate(decodeLatitude(start), decodeLatitude(end),
+ decodeLongitude(start), decodeLongitude(end))) != Relation.CELL_OUTSIDE_QUERY) {
+ // if at max depth or cell completely within
+ if (shift == maxShift || relation == Relation.CELL_INSIDE_QUERY) {
+ setRange(relation == Relation.CELL_CROSSES_QUERY);
advanceVariables();
- break;
- } else if (shift < 54) {
- withinOnly = true;
- shift = (short)(shift - m);
- lastWithin = currEnd & ~((1L << shift) - 1);
- setNextRange(false);
- break;
+ return true;
}
}
// within cell but not at a depth factor of PRECISION_STEP
- if (isWithin == true || (relationImpl.cellIntersectsMBR(minLat, maxLat, minLon, maxLon) == true && shift != maxShift)) {
- // descend: currStart need not change since shift handles end of range
- currEnd = currStart | (1L<<--shift) - 1;
+ if (shift != maxShift && relationImpl.cellIntersectsMBR(start, end) == true) {
+ // descend: start need not change since shift handles end of range
+ end = start | (1L<<--shift) - 1;
} else {
advanceVariables();
- minLon = GeoPointField.decodeLongitude(currStart);
- minLat = GeoPointField.decodeLatitude(currStart);
}
- } while(shift < 63);
+ } while(shift < 62);
+ return false;
}
- private void setNextRange(final boolean boundary) {
- nextRange.start = currStart;
- nextRange.shift = shift;
- nextRange.boundary = boundary;
+ private void setRange(final boolean boundary) {
+ range.start = start;
+ range.shift = shift;
+ range.boundary = boundary;
+ hasNext = true;
}
private void advanceVariables() {
/** set next variables */
long shiftMask = 1L << shift;
// pop-up if shift bit is set
- while ( (currStart & shiftMask) == shiftMask) {
+ while ((start & shiftMask) != 0) {
shiftMask = 1L << ++shift;
}
final long shiftMOne = shiftMask - 1;
- currStart = currStart & ~shiftMOne | shiftMask;
- currEnd = currStart | shiftMOne;
+ start = start & ~shiftMOne | shiftMask;
+ end = start | shiftMOne;
}
- protected final BytesRef peek() {
- nextRange.fillBytesRef(nextSubRangeBRB);
- return nextSubRangeBRB.get();
- }
-
- protected void seek(long term, short res) {
- if (term < currStart && res < maxShift) {
+ private void seek(long term, short res) {
+ if (term < start && res < maxShift) {
throw new IllegalArgumentException("trying to seek backwards");
- } else if (term == currStart) {
+ } else if (term == start && res == shift) {
return;
}
shift = res;
- currStart = term;
- currEnd = currStart | ((1L<<shift)-1);
- withinOnly = false;
- }
-
- protected void nextRange() {
- hasNext = false;
- currentRange.fillBytesRef(currentCellBRB);
- currentCell = currentCellBRB.get();
+ start = term;
+ end = start | ((1L<<shift)-1);
}
- protected final boolean hasNext() {
- if (hasNext == true || nextWithin()) {
- return true;
+ private final boolean hasNext() {
+ if (hasNext == false) {
+ return nextRelation();
}
- nextRelation();
- if (currentRange.compareTo(nextRange) != 0) {
- currentRange.set(nextRange);
- return (hasNext = true);
- }
- return false;
+ return true;
}
@Override
protected final BytesRef nextSeekTerm(BytesRef term) {
- while (hasNext()) {
- nextRange();
- if (term == null) {
- return currentCell;
- }
-
- final int comparison = term.compareTo(currentCell);
- if (comparison > 0) {
- seek(prefixCodedToGeoCoded(term), (short)(64 - getPrefixCodedShift(term)));
- continue;
- }
- return currentCell;
+ if (hasNext() == false) {
+ return null;
}
-
- // no more sub-range enums available
- return null;
+ geoCodedToPrefixCoded(range.start, range.shift, currentCellBRB);
+ hasNext = false;
+ return currentCellBRB.get();
}
/**
@@ -209,40 +144,40 @@ final class GeoPointTermsEnum extends FilteredTermsEnum {
*/
@Override
protected AcceptStatus accept(BytesRef term) {
- // range < term or range is null
- while (currentCell == null || term.compareTo(currentCell) > 0) {
+ final long encodedTerm = prefixCodedToGeoCoded(term);
+ final short termShift = (short)(64-getPrefixCodedShift(term));
+ // range < term
+ while (range.compare(encodedTerm, termShift) < 0) {
// no more ranges, be gone
if (hasNext() == false) {
return AcceptStatus.END;
}
// peek next range, if the range > term then seek
- final int peekCompare = term.compareTo(peek());
- if (peekCompare < 0) {
+ final int peekCompare = range.compare(encodedTerm, termShift);
+ if (peekCompare > 0) {
return AcceptStatus.NO_AND_SEEK;
- } else if (peekCompare > 0) {
- seek(prefixCodedToGeoCoded(term), (short)(64 - getPrefixCodedShift(term)));
+ } else if (peekCompare < 0) {
+ seek(encodedTerm, termShift);
}
- nextRange();
+ hasNext = false;
}
return AcceptStatus.YES;
}
- /**
- * Returns true if the current range term is a boundary of the query shape
- */
- public boolean boundaryTerm() {
- if (currentCell == null) {
+ /** Returns true if the current range term is a boundary of the query shape */
+ protected boolean boundaryTerm() {
+ if (range.start == -1) {
throw new IllegalStateException("GeoPointTermsEnum empty or not initialized");
}
- return currentRange.boundary;
+ return range.boundary;
}
protected boolean postFilter(final double lat, final double lon) {
return relationImpl.postFilter(lat, lon);
}
- protected final class Range implements Comparable<Range> {
+ protected final class Range {
private short shift;
private long start;
private boolean boundary;
@@ -250,30 +185,15 @@ final class GeoPointTermsEnum extends FilteredTermsEnum {
public Range(final long start, final short shift, final boolean boundary) {
this.boundary = boundary;
this.start = start;
- this.shift = shift; }
-
- /**
- * Encode as a BytesRef using a reusable object. This allows us to lazily create the BytesRef (which is
- * quite expensive), only when we need it.
- */
- protected void fillBytesRef(BytesRefBuilder result) {
- assert result != null;
- geoCodedToPrefixCoded(start, shift, result);
+ this.shift = shift;
}
- @Override
- public int compareTo(Range other) {
- final int result = Short.compare(this.shift, other.shift);
+ private int compare(long encoded, short shift) {
+ final int result = Long.compare(this.start, encoded);
if (result == 0) {
- return Long.compare(this.start, other.start);
+ return Short.compare(shift, this.shift);
}
return result;
}
-
- protected void set(Range other) {
- this.start = other.start;
- this.shift = other.shift;
- this.boundary = other.boundary;
- }
}
}