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 19:54:48 UTC
lucene-solr:branch_6x: LUCENE-7343: Cleanup GeoPoint by sharing
relation logic and removing stale code.
Repository: lucene-solr
Updated Branches:
refs/heads/branch_6x aaddefe80 -> fc68bd90e
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/fc68bd90
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/fc68bd90
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/fc68bd90
Branch: refs/heads/branch_6x
Commit: fc68bd90e6fa3f8ed364f522f997fe6efd50a8b7
Parents: aaddefe
Author: Nicholas Knize <nk...@gmail.com>
Authored: Mon Jun 20 14:54:27 2016 -0500
Committer: Nicholas Knize <nk...@gmail.com>
Committed: Mon Jun 20 14:54:27 2016 -0500
----------------------------------------------------------------------
.../java/org/apache/lucene/geo/GeoUtils.java | 34 ++++
.../document/LatLonPointDistanceQuery.java | 35 +---
.../geopoint/search/GeoPointDistanceQuery.java | 3 +
.../search/GeoPointDistanceQueryImpl.java | 52 ++++--
.../search/GeoPointInBBoxQueryImpl.java | 14 ++
.../search/GeoPointInPolygonQueryImpl.java | 5 +
.../geopoint/search/GeoPointMultiTermQuery.java | 29 ++-
.../search/GeoPointNumericTermsEnum.java | 54 +++---
.../search/GeoPointPrefixTermsEnum.java | 182 ++++++-------------
.../geopoint/search/GeoPointTermsEnum.java | 60 ++----
10 files changed, 214 insertions(+), 254 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/fc68bd90/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..dbdadfd 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java
@@ -2,6 +2,7 @@ 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;
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
@@ -91,4 +92,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/fc68bd90/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/fc68bd90/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 a6cf35c..b546929 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
@@ -46,6 +46,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) {
@@ -89,6 +91,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/fc68bd90/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 a360fdb..871979c 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.Relation;
import org.apache.lucene.search.MultiTermQuery;
import org.apache.lucene.spatial.geopoint.document.GeoPointField.TermEncoding;
import org.apache.lucene.util.SloppyMath;
@@ -28,27 +29,15 @@ import org.apache.lucene.util.SloppyMath;
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;
-
+
GeoPointDistanceQueryImpl(final String field, final TermEncoding termEncoding, final GeoPointDistanceQuery q,
final double centerLonUnwrapped, final Rectangle bbox) {
super(field, termEncoding, 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);
}
@@ -104,6 +93,35 @@ final class GeoPointDistanceQueryImpl extends GeoPointInBBoxQueryImpl {
return cellCrosses(minLat, maxLat, minLon, maxLon);
}
+ @Override
+ protected Relation relate(final double minLat, final double maxLat, final double minLon, final double maxLon) {
+ // bounding check
+ if (cellIntersectsMBR(minLat, maxLat, minLon, maxLon) == false) {
+ return 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 Relation.CELL_OUTSIDE_QUERY;
+ }
+ }
+
+ if (maxLon - centerLon < 90 && centerLon - minLon < 90 &&
+ 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 Relation.CELL_INSIDE_QUERY;
+ }
+
+ return Relation.CELL_CROSSES_QUERY;
+ }
+
+
/**
* The two-phase query approach. The parent {@link GeoPointTermsEnum} class matches
* encoded terms that fall within the minimum bounding box of the point-radius circle. Those documents that pass
@@ -119,12 +137,12 @@ 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/fc68bd90/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 c19e6d2..3133de6 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;
@@ -97,6 +98,19 @@ class GeoPointInBBoxQueryImpl extends GeoPointMultiTermQuery {
}
@Override
+ 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
protected boolean postFilter(final double lat, final double lon) {
return GeoRelationUtils.pointInRectPrecise(lat, lon, minLat, maxLat, minLon, maxLon);
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/fc68bd90/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 047bf27..006b150 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
@@ -72,6 +72,11 @@ final class GeoPointInPolygonQueryImpl extends GeoPointInBBoxQueryImpl {
return polygons.relate(minLat, maxLat, minLon, maxLon) != Relation.CELL_OUTSIDE_QUERY;
}
+ @Override
+ protected Relation relate(final double minLat, final double maxLat, final double minLon, final double maxLon) {
+ return polygons.relate(minLat, maxLat, minLon, maxLon);
+ }
+
/**
* The two-phase query approach. The parent
* {@link org.apache.lucene.spatial.geopoint.search.GeoPointTermsEnum#accept} method is called to match
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/fc68bd90/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 20026a1..0d4a274 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
@@ -20,6 +20,7 @@ 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;
@@ -28,7 +29,7 @@ import org.apache.lucene.util.AttributeSource;
import org.apache.lucene.spatial.geopoint.document.GeoPointField;
import org.apache.lucene.spatial.geopoint.document.GeoPointField.TermEncoding;
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;
/**
@@ -40,9 +41,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 TermEncoding termEncoding;
@@ -55,10 +61,13 @@ abstract class GeoPointMultiTermQuery extends MultiTermQuery {
public GeoPointMultiTermQuery(String field, final TermEncoding termEncoding, 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;
@@ -128,6 +137,14 @@ abstract class GeoPointMultiTermQuery extends MultiTermQuery {
geoPointQuery.minLon, geoPointQuery.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);
+ }
+
/**
* Return whether quad-cell contains the bounding box of this shape
*/
@@ -151,6 +168,8 @@ abstract class GeoPointMultiTermQuery extends MultiTermQuery {
*/
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/fc68bd90/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointNumericTermsEnum.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointNumericTermsEnum.java b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointNumericTermsEnum.java
index 06dfec7..82c8a29 100644
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointNumericTermsEnum.java
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointNumericTermsEnum.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,6 +14,7 @@ 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.util.Collections;
import java.util.LinkedList;
@@ -41,6 +40,7 @@ import static org.apache.lucene.spatial.geopoint.document.GeoPointField.BITS;
@Deprecated
final class GeoPointNumericTermsEnum extends GeoPointTermsEnum {
private final List<Range> rangeBounds = new LinkedList<>();
+ private final BytesRefBuilder nextSubRangeBRB = new BytesRefBuilder();
// detail level should be a factor of PRECISION_STEP limiting the depth of recursion (and number of ranges)
private final short DETAIL_LEVEL;
@@ -102,16 +102,16 @@ final class GeoPointNumericTermsEnum extends GeoPointTermsEnum {
}
}
- @Override
protected final BytesRef peek() {
- rangeBounds.get(0).fillBytesRef(this.nextSubRangeBRB);
+ Range range = rangeBounds.get(0);
+ LegacyNumericUtils.longToPrefixCoded(range.start, range.shift, this.nextSubRangeBRB);
return nextSubRangeBRB.get();
}
- @Override
protected void nextRange() {
currentRange = rangeBounds.remove(0);
- super.nextRange();
+ LegacyNumericUtils.longToPrefixCoded(currentRange.start, currentRange.shift, currentCellBRB);
+ currentCell = currentCellBRB.get();
}
@Override
@@ -136,27 +136,33 @@ final class GeoPointNumericTermsEnum extends GeoPointTermsEnum {
return null;
}
- @Override
- protected final boolean hasNext() {
- return rangeBounds.isEmpty() == false;
- }
-
/**
- * Internal class to represent a range along the space filling curve
+ * The two-phase query approach. {@link #nextSeekTerm} is called to obtain the next term that matches a numeric
+ * range of the bounding box. Those terms that pass the initial range filter are then compared against the
+ * decoded min/max latitude and longitude values of the bounding box only if the range is not a "boundary" range
+ * (e.g., a range that straddles the boundary of the bbox).
+ * @param term term for candidate document
+ * @return match status
*/
- protected final class Range extends BaseRange {
- Range(final long lower, final short shift, boolean boundary) {
- super(lower, shift, boundary);
+ @Override
+ protected AcceptStatus accept(BytesRef term) {
+ // validate value is in range
+ while (currentCell == null || term.compareTo(currentCell) > 0) {
+ if (hasNext() == false) {
+ return AcceptStatus.END;
+ }
+ // peek next sub-range, only seek if the current term is smaller than next lower bound
+ if (term.compareTo(peek()) < 0) {
+ return AcceptStatus.NO_AND_SEEK;
+ }
+ nextRange();
}
- /**
- * 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.
- */
- @Override
- protected void fillBytesRef(BytesRefBuilder result) {
- assert result != null;
- LegacyNumericUtils.longToPrefixCoded(start, shift, result);
- }
+ return AcceptStatus.YES;
+ }
+
+ @Override
+ protected final boolean hasNext() {
+ return rangeBounds.isEmpty() == false;
}
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/fc68bd90/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointPrefixTermsEnum.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointPrefixTermsEnum.java b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointPrefixTermsEnum.java
index c8975f2..2979b71 100644
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointPrefixTermsEnum.java
+++ b/lucene/spatial/src/java/org/apache/lucene/spatial/geopoint/search/GeoPointPrefixTermsEnum.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,12 +14,15 @@ 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.PointValues;
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,199 +38,126 @@ import static org.apache.lucene.spatial.geopoint.document.GeoPointField.getPrefi
* @lucene.experimental
*/
final class GeoPointPrefixTermsEnum extends GeoPointTermsEnum {
- private final long start;
-
private short shift;
// current range as long
- private long currStart;
- private long currEnd;
-
- private final Range nextRange = new Range(-1, shift, true);
+ private long start;
+ private long end;
private boolean hasNext = false;
- private boolean withinOnly = false;
- private long lastWithin;
-
public GeoPointPrefixTermsEnum(final TermsEnum tenum, final GeoPointMultiTermQuery query) {
super(tenum, query);
- this.start = GeoPointField.encodeLatLon(query.minLat, query.minLon);
this.currentRange = new Range(-1, shift, true);
// start shift at maxShift value (from computeMaxShift)
this.shift = maxShift;
final long mask = (1L << shift) - 1;
- this.currStart = start & ~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;
}
- 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() {
+ PointValues.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))) != PointValues.Relation.CELL_OUTSIDE_QUERY) {
+ // if at max depth or cell completely within
+ if (shift == maxShift || relation == PointValues.Relation.CELL_INSIDE_QUERY) {
+ setRange(relation == PointValues.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) {
+ currentRange.start = start;
+ currentRange.shift = shift;
+ currentRange.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) == shiftMask) {
shiftMask = 1L << ++shift;
}
final long shiftMOne = shiftMask - 1;
- currStart = currStart & ~shiftMOne | shiftMask;
- currEnd = currStart | shiftMOne;
- }
-
- @Override
- protected final BytesRef peek() {
- nextRange.fillBytesRef(nextSubRangeBRB);
- return super.peek();
+ start = start & ~shiftMOne | shiftMask;
+ end = start | shiftMOne;
}
protected void seek(long term, short res) {
- if (term < currStart && res < maxShift) {
+ if (term < start && res < maxShift) {
throw new IllegalArgumentException("trying to seek backwards");
- } else if (term == currStart) {
+ } else if (term == start) {
return;
}
shift = res;
- currStart = term;
- currEnd = currStart | ((1L<<shift)-1);
- withinOnly = false;
- }
-
- @Override
- protected void nextRange() {
- hasNext = false;
- super.nextRange();
+ start = term;
+ end = start | ((1L<<shift)-1);
}
@Override
protected final boolean hasNext() {
- if (hasNext == true || nextWithin()) {
- return true;
+ 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(currentRange.start, currentRange.shift, currentCellBRB);
+ hasNext = false;
+ return currentCellBRB.get();
}
@Override
protected AcceptStatus accept(BytesRef term) {
+ final long encodedTerm = prefixCodedToGeoCoded(term);
+ final short termShift = (short)(64-getPrefixCodedShift(term));
// range < term or range is null
- while (currentCell == null || term.compareTo(currentCell) > 0) {
+ while (currentRange.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 = currentRange.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;
}
- protected final class Range extends BaseRange {
- public Range(final long start, final short res, final boolean boundary) {
- super(start, res, boundary);
- }
-
- @Override
- protected void fillBytesRef(BytesRefBuilder result) {
- assert result != null;
- geoCodedToPrefixCoded(start, shift, result);
+ @Override
+ public boolean boundaryTerm() {
+ if (currentRange.start == -1) {
+ throw new IllegalStateException("GeoPointTermsEnum empty or not initialized");
}
+ return currentRange.boundary;
}
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/fc68bd90/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 d82b340..2b5e3cc 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
@@ -32,10 +32,9 @@ import org.apache.lucene.spatial.geopoint.search.GeoPointMultiTermQuery.CellComp
abstract class GeoPointTermsEnum extends FilteredTermsEnum {
protected final short maxShift;
- protected BaseRange currentRange;
+ protected Range currentRange;
protected BytesRef currentCell;
protected final BytesRefBuilder currentCellBRB = new BytesRefBuilder();
- protected final BytesRefBuilder nextSubRangeBRB = new BytesRefBuilder();
protected final CellComparator relationImpl;
@@ -61,43 +60,8 @@ abstract class GeoPointTermsEnum extends FilteredTermsEnum {
return currentRange.boundary;
}
- protected BytesRef peek() {
- return nextSubRangeBRB.get();
- }
-
abstract protected boolean hasNext();
- protected void nextRange() {
- currentRange.fillBytesRef(currentCellBRB);
- currentCell = currentCellBRB.get();
- }
-
- /**
- * The two-phase query approach. {@link #nextSeekTerm} is called to obtain the next term that matches a numeric
- * range of the bounding box. Those terms that pass the initial range filter are then compared against the
- * decoded min/max latitude and longitude values of the bounding box only if the range is not a "boundary" range
- * (e.g., a range that straddles the boundary of the bbox).
- * @param term term for candidate document
- * @return match status
- */
- @Override
- protected AcceptStatus accept(BytesRef term) {
- // validate value is in range
- while (currentCell == null || term.compareTo(currentCell) > 0) {
- if (hasNext() == false) {
- return AcceptStatus.END;
- }
- // peek next sub-range, only seek if the current term is smaller than next lower bound
- if (term.compareTo(peek()) < 0) {
- return AcceptStatus.NO_AND_SEEK;
- }
- // step forward to next range without seeking, as next range is less or equal current term
- nextRange();
- }
-
- return AcceptStatus.YES;
- }
-
protected boolean postFilter(final double lat, final double lon) {
return relationImpl.postFilter(lat, lon);
}
@@ -105,25 +69,19 @@ abstract class GeoPointTermsEnum extends FilteredTermsEnum {
/**
* Internal class to represent a range along the space filling curve
*/
- abstract class BaseRange implements Comparable<BaseRange> {
+ class Range implements Comparable<Range> {
protected short shift;
protected long start;
protected boolean boundary;
- BaseRange(final long lower, final short shift, boolean boundary) {
+ Range(final long lower, final short shift, boolean boundary) {
this.boundary = boundary;
this.start = lower;
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.
- */
- abstract protected void fillBytesRef(BytesRefBuilder result);
-
@Override
- public int compareTo(BaseRange other) {
+ public int compareTo(Range other) {
final int result = Short.compare(this.shift, other.shift);
if (result == 0) {
return Long.compare(this.start, other.start);
@@ -131,10 +89,18 @@ abstract class GeoPointTermsEnum extends FilteredTermsEnum {
return result;
}
- protected void set(BaseRange other) {
+ protected void set(Range other) {
this.start = other.start;
this.shift = other.shift;
this.boundary = other.boundary;
}
+
+ protected int compare(long encoded, short shift) {
+ final int result = Long.compare(this.start, encoded);
+ if (result == 0) {
+ return Short.compare(shift, this.shift);
+ }
+ return result;
+ }
}
}