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/02/29 23:20:11 UTC
[25/29] 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/java/org/apache/lucene/spatial/prefix/tree/PackedQuadPrefixTree.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/PackedQuadPrefixTree.java b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/PackedQuadPrefixTree.java
new file mode 100644
index 0000000..6fe2bff
--- /dev/null
+++ b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/PackedQuadPrefixTree.java
@@ -0,0 +1,459 @@
+/*
+ * 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.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+import java.util.NoSuchElementException;
+
+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 com.spatial4j.core.shape.SpatialRelation;
+import com.spatial4j.core.shape.impl.RectangleImpl;
+import org.apache.lucene.util.BytesRef;
+
+/**
+ * Uses a compact binary representation of 8 bytes to encode a spatial quad trie.
+ *
+ * The binary representation is as follows:
+ * <pre>
+ * CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDL
+ *
+ * Where C = Cell bits (2 per quad)
+ * D = Depth bits (5 with max of 29 levels)
+ * L = isLeaf bit
+ * </pre>
+ *
+ * It includes a built-in "pruneLeafyBranches" setting (true by default) similar to
+ * {@link org.apache.lucene.spatial.prefix.RecursivePrefixTreeStrategy#setPruneLeafyBranches(boolean)} although
+ * this one only prunes at the target detail level (where it has the most effect). Usually you should disable RPT's
+ * prune, since it is very memory in-efficient.
+ *
+ * @lucene.experimental
+ */
+public class PackedQuadPrefixTree extends QuadPrefixTree {
+ public static final int MAX_LEVELS_POSSIBLE = 29;
+ protected static final byte[] QUAD = new byte[] {0x00, 0x01, 0x02, 0x03};
+
+ protected boolean leafyPrune = true;
+
+ /**
+ * Factory for creating {@link PackedQuadPrefixTree} instances with useful defaults.
+ */
+ public static class Factory extends QuadPrefixTree.Factory {
+ @Override
+ protected SpatialPrefixTree newSPT() {
+ return new PackedQuadPrefixTree(ctx, maxLevels != null ? maxLevels : MAX_LEVELS_POSSIBLE);
+ }
+ }
+
+ public PackedQuadPrefixTree(SpatialContext ctx, int maxLevels) {
+ super(ctx, maxLevels);
+ if (maxLevels > MAX_LEVELS_POSSIBLE) {
+ throw new IllegalArgumentException("maxLevels of " + maxLevels + " exceeds limit of " + MAX_LEVELS_POSSIBLE);
+ }
+ }
+
+ @Override
+ public String toString() {
+ return getClass().getSimpleName() + "(maxLevels:" + maxLevels + ",ctx:" + ctx + ",prune:" + leafyPrune + ")";
+ }
+
+ @Override
+ public Cell getWorldCell() {
+ return new PackedQuadCell(0x0L);
+ }
+
+ @Override
+ public Cell getCell(Point p, int level) {
+ List<Cell> cells = new ArrayList<>(1);
+ build(xmid, ymid, 0, cells, 0x0L, ctx.makePoint(p.getX(), p.getY()), level);
+ return cells.get(0);//note cells could be longer if p on edge
+ }
+
+ protected void build(double x, double y, int level, List<Cell> matches, long term, Shape shape, int maxLevel) {
+ double w = levelW[level] / 2;
+ double h = levelH[level] / 2;
+
+ // Z-Order
+ // http://en.wikipedia.org/wiki/Z-order_%28curve%29
+ checkBattenberg(QUAD[0], x - w, y + h, level, matches, term, shape, maxLevel);
+ checkBattenberg(QUAD[1], x + w, y + h, level, matches, term, shape, maxLevel);
+ checkBattenberg(QUAD[2], x - w, y - h, level, matches, term, shape, maxLevel);
+ checkBattenberg(QUAD[3], x + w, y - h, level, matches, term, shape, maxLevel);
+ }
+
+ protected void checkBattenberg(byte quad, double cx, double cy, int level, List<Cell> matches,
+ long term, Shape shape, int maxLevel) {
+ // short-circuit if we find a match for the point (no need to continue recursion)
+ if (shape instanceof Point && !matches.isEmpty())
+ return;
+ double w = levelW[level] / 2;
+ double h = levelH[level] / 2;
+
+ SpatialRelation v = shape.relate(ctx.makeRectangle(cx - w, cx + w, cy - h, cy + h));
+
+ if (SpatialRelation.DISJOINT == v) {
+ return;
+ }
+
+ // set bits for next level
+ term |= (((long)(quad))<<(64-(++level<<1)));
+ // increment level
+ term = ((term>>>1)+1)<<1;
+
+ if (SpatialRelation.CONTAINS == v || (level >= maxLevel)) {
+ matches.add(new PackedQuadCell(term, v.transpose()));
+ } else {// SpatialRelation.WITHIN, SpatialRelation.INTERSECTS
+ build(cx, cy, level, matches, term, shape, maxLevel);
+ }
+ }
+
+ @Override
+ public Cell readCell(BytesRef term, Cell scratch) {
+ PackedQuadCell cell = (PackedQuadCell) scratch;
+ if (cell == null)
+ cell = (PackedQuadCell) getWorldCell();
+ cell.readCell(term);
+ return cell;
+ }
+
+ @Override
+ public CellIterator getTreeCellIterator(Shape shape, int detailLevel) {
+ if (detailLevel > maxLevels) {
+ throw new IllegalArgumentException("detailLevel:" + detailLevel +" exceed max: " + maxLevels);
+ }
+ return new PrefixTreeIterator(shape, (short) detailLevel);
+ }
+
+ public boolean isPruneLeafyBranches() {
+ return leafyPrune;
+ }
+
+ /** Like {@link org.apache.lucene.spatial.prefix.RecursivePrefixTreeStrategy#setPruneLeafyBranches(boolean)}
+ * but more memory efficient and only applies to the detailLevel, where it has the most effect. */
+ public void setPruneLeafyBranches( boolean pruneLeafyBranches ) {
+ this.leafyPrune = pruneLeafyBranches;
+ }
+
+ /** See binary representation in the javadocs of {@link PackedQuadPrefixTree}. */
+ protected class PackedQuadCell extends QuadCell {
+ private long term;
+
+ PackedQuadCell(long term) {
+ super(null, 0, 0);
+ this.term = term;
+ this.b_off = 0;
+ this.bytes = longToByteArray(this.term);
+ this.b_len = 8;
+ readLeafAdjust();
+ }
+
+ PackedQuadCell(long term, SpatialRelation shapeRel) {
+ this(term);
+ this.shapeRel = shapeRel;
+ }
+
+ @Override
+ protected void readCell(BytesRef bytes) {
+ shapeRel = null;
+ shape = null;
+ this.bytes = bytes.bytes;
+ this.b_off = bytes.offset;
+ this.b_len = (short) bytes.length;
+ this.term = longFromByteArray(this.bytes, bytes.offset);
+ readLeafAdjust();
+ }
+
+ private final int getShiftForLevel(final int level) {
+ return 64 - (level<<1);
+ }
+
+ public boolean isEnd(final int level, final int shift) {
+ return (term != 0x0L && ((((0x1L<<(level<<1))-1)-(term>>>shift)) == 0x0L));
+ }
+
+ /**
+ * Get the next cell in the tree without using recursion. descend parameter requests traversal to the child nodes,
+ * setting this to false will step to the next sibling.
+ * Note: This complies with lexicographical ordering, once you've moved to the next sibling there is no backtracking.
+ */
+ public PackedQuadCell nextCell(boolean descend) {
+ final int level = getLevel();
+ final int shift = getShiftForLevel(level);
+ // base case: can't go further
+ if ( (!descend && isEnd(level, shift)) || isEnd(maxLevels, getShiftForLevel(maxLevels))) {
+ return null;
+ }
+ long newTerm;
+ final boolean isLeaf = (term&0x1L)==0x1L;
+ // if descend requested && we're not at the maxLevel
+ if ((descend && !isLeaf && (level != maxLevels)) || level == 0) {
+ // simple case: increment level bits (next level)
+ newTerm = ((term>>>1)+0x1L)<<1;
+ } else { // we're not descending or we can't descend
+ newTerm = term + (0x1L<<shift);
+ // we're at the last sibling...force descend
+ if (((term>>>shift)&0x3L) == 0x3L) {
+ // adjust level for number popping up
+ newTerm = ((newTerm>>>1) - (Long.numberOfTrailingZeros(newTerm>>>shift)>>>1))<<1;
+ }
+ }
+ return new PackedQuadCell(newTerm);
+ }
+
+ @Override
+ protected void readLeafAdjust() {
+ isLeaf = ((0x1L)&term) == 0x1L;
+ if (getLevel() == getMaxLevels()) {
+ isLeaf = true;
+ }
+ }
+
+ @Override
+ public BytesRef getTokenBytesWithLeaf(BytesRef result) {
+ if (isLeaf) {
+ term |= 0x1L;
+ }
+ return getTokenBytesNoLeaf(result);
+ }
+
+ @Override
+ public BytesRef getTokenBytesNoLeaf(BytesRef result) {
+ if (result == null)
+ return new BytesRef(bytes, b_off, b_len);
+ result.bytes = longToByteArray(this.term);
+ result.offset = 0;
+ result.length = result.bytes.length;
+ return result;
+ }
+
+ @Override
+ public int compareToNoLeaf(Cell fromCell) {
+ PackedQuadCell b = (PackedQuadCell) fromCell;
+ final long thisTerm = (((0x1L)&term) == 0x1L) ? term-1 : term;
+ final long fromTerm = (((0x1L)&b.term) == 0x1L) ? b.term-1 : b.term;
+ final int result = Long.compareUnsigned(thisTerm, fromTerm);
+ assert Math.signum(result)
+ == Math.signum(compare(longToByteArray(thisTerm), 0, 8, longToByteArray(fromTerm), 0, 8)); // TODO remove
+ return result;
+ }
+
+ @Override
+ public int getLevel() {
+ int l = (int)((term >>> 1)&0x1FL);
+ return l;
+ }
+
+ @Override
+ protected Collection<Cell> getSubCells() {
+ List<Cell> cells = new ArrayList<>(4);
+ PackedQuadCell pqc = (new PackedQuadCell(((term&0x1)==0x1) ? this.term-1 : this.term))
+ .nextCell(true);
+ cells.add(pqc);
+ cells.add((pqc = pqc.nextCell(false)));
+ cells.add((pqc = pqc.nextCell(false)));
+ cells.add(pqc.nextCell(false));
+ return cells;
+ }
+
+ @Override
+ protected QuadCell getSubCell(Point p) {
+ return (PackedQuadCell) PackedQuadPrefixTree.this.getCell(p, getLevel() + 1);//not performant!
+ }
+
+ @Override
+ public boolean isPrefixOf(Cell c) {
+ PackedQuadCell cell = (PackedQuadCell)c;
+ return (this.term == 0x0L) || isInternalPrefix(cell);
+ }
+
+ protected boolean isInternalPrefix(PackedQuadCell c) {
+ final int shift = 64 - (getLevel()<<1);
+ return ((term>>>shift)-(c.term>>>shift)) == 0x0L;
+ }
+
+ protected long concat(byte postfix) {
+ // extra leaf bit
+ return this.term | (((long)(postfix))<<((getMaxLevels()-getLevel()<<1)+6));
+ }
+
+ /**
+ * Constructs a bounding box shape out of the encoded cell
+ */
+ @Override
+ protected Rectangle makeShape() {
+ double xmin = PackedQuadPrefixTree.this.xmin;
+ double ymin = PackedQuadPrefixTree.this.ymin;
+ int level = getLevel();
+
+ byte b;
+ for (short l=0, i=1; l<level; ++l, ++i) {
+ b = (byte) ((term>>>(64-(i<<1))) & 0x3L);
+
+ switch (b) {
+ case 0x00:
+ ymin += levelH[l];
+ break;
+ case 0x01:
+ xmin += levelW[l];
+ ymin += levelH[l];
+ break;
+ case 0x02:
+ break;//nothing really
+ case 0x03:
+ xmin += levelW[l];
+ break;
+ default:
+ throw new RuntimeException("unexpected quadrant");
+ }
+ }
+
+ double width, height;
+ if (level > 0) {
+ width = levelW[level - 1];
+ height = levelH[level - 1];
+ } else {
+ width = gridW;
+ height = gridH;
+ }
+ return new RectangleImpl(xmin, xmin + width, ymin, ymin + height, ctx);
+ }
+
+ private long fromBytes(byte b1, byte b2, byte b3, byte b4, byte b5, byte b6, byte b7, byte b8) {
+ return ((long)b1 & 255L) << 56 | ((long)b2 & 255L) << 48 | ((long)b3 & 255L) << 40
+ | ((long)b4 & 255L) << 32 | ((long)b5 & 255L) << 24 | ((long)b6 & 255L) << 16
+ | ((long)b7 & 255L) << 8 | (long)b8 & 255L;
+ }
+
+ private byte[] longToByteArray(long value) {
+ byte[] result = new byte[8];
+ for(int i = 7; i >= 0; --i) {
+ result[i] = (byte)((int)(value & 255L));
+ value >>= 8;
+ }
+ return result;
+ }
+
+ private long longFromByteArray(byte[] bytes, int ofs) {
+ assert bytes.length >= 8;
+ return fromBytes(bytes[0+ofs], bytes[1+ofs], bytes[2+ofs], bytes[3+ofs],
+ bytes[4+ofs], bytes[5+ofs], bytes[6+ofs], bytes[7+ofs]);
+ }
+
+ /**
+ * Used for debugging, this will print the bits of the cell
+ */
+ @Override
+ public String toString() {
+ StringBuilder s = new StringBuilder(64);
+ final int numberOfLeadingZeros = Long.numberOfLeadingZeros(term);
+ for (int i = 0; i < numberOfLeadingZeros; i++) {
+ s.append('0');
+ }
+ if (term != 0)
+ s.append(Long.toBinaryString(term));
+ return s.toString();
+ }
+ } // PackedQuadCell
+
+ /** This is a streamlined version of TreeCellIterator, with built-in support to prune at detailLevel
+ * (but not recursively upwards). */
+ protected class PrefixTreeIterator extends CellIterator {
+ private Shape shape;
+ private PackedQuadCell thisCell;
+ private PackedQuadCell nextCell;
+
+ private short level;
+ private final short detailLevel;
+ private CellIterator pruneIter;
+
+ PrefixTreeIterator(Shape shape, short detailLevel) {
+ this.shape = shape;
+ this.thisCell = ((PackedQuadCell)(getWorldCell())).nextCell(true);
+ this.detailLevel = detailLevel;
+ this.nextCell = null;
+ }
+
+ @Override
+ public boolean hasNext() {
+ if (nextCell != null) {
+ return true;
+ }
+ SpatialRelation rel;
+ // loop until we're at the end of the quad tree or we hit a relation
+ while (thisCell != null) {
+ rel = thisCell.getShape().relate(shape);
+ if (rel == SpatialRelation.DISJOINT) {
+ thisCell = thisCell.nextCell(false);
+ } else { // within || intersects || contains
+ thisCell.setShapeRel(rel);
+ nextCell = thisCell;
+ if (rel == SpatialRelation.WITHIN) {
+ thisCell.setLeaf();
+ thisCell = thisCell.nextCell(false);
+ } else { // intersects || contains
+ level = (short) (thisCell.getLevel());
+ if (level == detailLevel || pruned(rel)) {
+ thisCell.setLeaf();
+ if (shape instanceof Point) {
+ thisCell.setShapeRel(SpatialRelation.WITHIN);
+ thisCell = null;
+ } else {
+ thisCell = thisCell.nextCell(false);
+ }
+ break;
+ }
+ thisCell = thisCell.nextCell(true);
+ }
+ break;
+ }
+ }
+ return nextCell != null;
+ }
+
+ private boolean pruned(SpatialRelation rel) {
+ int leaves;
+ if (rel == SpatialRelation.INTERSECTS && leafyPrune && level == detailLevel - 1) {
+ for (leaves=0, pruneIter=thisCell.getNextLevelCells(shape); pruneIter.hasNext(); pruneIter.next(), ++leaves);
+ return leaves == 4;
+ }
+ return false;
+ }
+
+ @Override
+ public Cell next() {
+ if (nextCell == null) {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+ }
+ // overriding since this implementation sets thisCell in hasNext
+ Cell temp = nextCell;
+ nextCell = null;
+ return temp;
+ }
+
+ @Override
+ public void remove() {
+ //no-op
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/89db4950/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/QuadPrefixTree.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/QuadPrefixTree.java b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/QuadPrefixTree.java
new file mode 100644
index 0000000..48dac87
--- /dev/null
+++ b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/QuadPrefixTree.java
@@ -0,0 +1,308 @@
+/*
+ * 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.io.PrintStream;
+import java.text.NumberFormat;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.List;
+import java.util.Locale;
+
+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 com.spatial4j.core.shape.SpatialRelation;
+import org.apache.lucene.util.BytesRef;
+
+/**
+ * A {@link SpatialPrefixTree} which uses a
+ * <a href="http://en.wikipedia.org/wiki/Quadtree">quad tree</a> in which an
+ * indexed term will be generated for each cell, 'A', 'B', 'C', 'D'.
+ *
+ * @lucene.experimental
+ */
+public class QuadPrefixTree extends LegacyPrefixTree {
+
+ /**
+ * Factory for creating {@link QuadPrefixTree} instances with useful defaults
+ */
+ public static class Factory extends SpatialPrefixTreeFactory {
+
+ @Override
+ protected int getLevelForDistance(double degrees) {
+ QuadPrefixTree grid = new QuadPrefixTree(ctx, MAX_LEVELS_POSSIBLE);
+ return grid.getLevelForDistance(degrees);
+ }
+
+ @Override
+ protected SpatialPrefixTree newSPT() {
+ return new QuadPrefixTree(ctx,
+ maxLevels != null ? maxLevels : MAX_LEVELS_POSSIBLE);
+ }
+ }
+
+ public static final int MAX_LEVELS_POSSIBLE = 50;//not really sure how big this should be
+
+ public static final int DEFAULT_MAX_LEVELS = 12;
+ protected final double xmin;
+ protected final double xmax;
+ protected final double ymin;
+ protected final double ymax;
+ protected final double xmid;
+ protected final double ymid;
+
+ protected final double gridW;
+ public final double gridH;
+
+ final double[] levelW;
+ final double[] levelH;
+ final int[] levelS; // side
+ final int[] levelN; // number
+
+ public QuadPrefixTree(
+ SpatialContext ctx, Rectangle bounds, int maxLevels) {
+ super(ctx, maxLevels);
+ this.xmin = bounds.getMinX();
+ this.xmax = bounds.getMaxX();
+ this.ymin = bounds.getMinY();
+ this.ymax = bounds.getMaxY();
+
+ levelW = new double[maxLevels];
+ levelH = new double[maxLevels];
+ levelS = new int[maxLevels];
+ levelN = new int[maxLevels];
+
+ gridW = xmax - xmin;
+ gridH = ymax - ymin;
+ this.xmid = xmin + gridW/2.0;
+ this.ymid = ymin + gridH/2.0;
+ levelW[0] = gridW/2.0;
+ levelH[0] = gridH/2.0;
+ levelS[0] = 2;
+ levelN[0] = 4;
+
+ for (int i = 1; i < levelW.length; i++) {
+ levelW[i] = levelW[i - 1] / 2.0;
+ levelH[i] = levelH[i - 1] / 2.0;
+ levelS[i] = levelS[i - 1] * 2;
+ levelN[i] = levelN[i - 1] * 4;
+ }
+ }
+
+ public QuadPrefixTree(SpatialContext ctx) {
+ this(ctx, DEFAULT_MAX_LEVELS);
+ }
+
+ public QuadPrefixTree(
+ SpatialContext ctx, int maxLevels) {
+ this(ctx, ctx.getWorldBounds(), maxLevels);
+ }
+
+ @Override
+ public Cell getWorldCell() {
+ return new QuadCell(BytesRef.EMPTY_BYTES, 0, 0);
+ }
+
+ public void printInfo(PrintStream out) {
+ NumberFormat nf = NumberFormat.getNumberInstance(Locale.ROOT);
+ nf.setMaximumFractionDigits(5);
+ nf.setMinimumFractionDigits(5);
+ nf.setMinimumIntegerDigits(3);
+
+ for (int i = 0; i < maxLevels; i++) {
+ out.println(i + "]\t" + nf.format(levelW[i]) + "\t" + nf.format(levelH[i]) + "\t" +
+ levelS[i] + "\t" + (levelS[i] * levelS[i]));
+ }
+ }
+
+ @Override
+ public int getLevelForDistance(double dist) {
+ if (dist == 0)//short circuit
+ return maxLevels;
+ for (int i = 0; i < maxLevels-1; i++) {
+ //note: level[i] is actually a lookup for level i+1
+ if(dist > levelW[i] && dist > levelH[i]) {
+ return i+1;
+ }
+ }
+ return maxLevels;
+ }
+
+ @Override
+ public Cell getCell(Point p, int level) {
+ List<Cell> cells = new ArrayList<>(1);
+ build(xmid, ymid, 0, cells, new BytesRef(maxLevels+1), ctx.makePoint(p.getX(),p.getY()), level);
+ return cells.get(0);//note cells could be longer if p on edge
+ }
+
+ private void build(
+ double x,
+ double y,
+ int level,
+ List<Cell> matches,
+ BytesRef str,
+ Shape shape,
+ int maxLevel) {
+ assert str.length == level;
+ double w = levelW[level] / 2;
+ double h = levelH[level] / 2;
+
+ // Z-Order
+ // http://en.wikipedia.org/wiki/Z-order_%28curve%29
+ checkBattenberg('A', x - w, y + h, level, matches, str, shape, maxLevel);
+ checkBattenberg('B', x + w, y + h, level, matches, str, shape, maxLevel);
+ checkBattenberg('C', x - w, y - h, level, matches, str, shape, maxLevel);
+ checkBattenberg('D', x + w, y - h, level, matches, str, shape, maxLevel);
+
+ // possibly consider hilbert curve
+ // http://en.wikipedia.org/wiki/Hilbert_curve
+ // http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves
+ // if we actually use the range property in the query, this could be useful
+ }
+
+ protected void checkBattenberg(
+ char c,
+ double cx,
+ double cy,
+ int level,
+ List<Cell> matches,
+ BytesRef str,
+ Shape shape,
+ int maxLevel) {
+ assert str.length == level;
+ assert str.offset == 0;
+ double w = levelW[level] / 2;
+ double h = levelH[level] / 2;
+
+ int strlen = str.length;
+ Rectangle rectangle = ctx.makeRectangle(cx - w, cx + w, cy - h, cy + h);
+ SpatialRelation v = shape.relate(rectangle);
+ if (SpatialRelation.CONTAINS == v) {
+ str.bytes[str.length++] = (byte)c;//append
+ //str.append(SpatialPrefixGrid.COVER);
+ matches.add(new QuadCell(BytesRef.deepCopyOf(str), v.transpose()));
+ } else if (SpatialRelation.DISJOINT == v) {
+ // nothing
+ } else { // SpatialRelation.WITHIN, SpatialRelation.INTERSECTS
+ str.bytes[str.length++] = (byte)c;//append
+
+ int nextLevel = level+1;
+ if (nextLevel >= maxLevel) {
+ //str.append(SpatialPrefixGrid.INTERSECTS);
+ matches.add(new QuadCell(BytesRef.deepCopyOf(str), v.transpose()));
+ } else {
+ build(cx, cy, nextLevel, matches, str, shape, maxLevel);
+ }
+ }
+ str.length = strlen;
+ }
+
+ protected class QuadCell extends LegacyCell {
+
+ QuadCell(byte[] bytes, int off, int len) {
+ super(bytes, off, len);
+ }
+
+ QuadCell(BytesRef str, SpatialRelation shapeRel) {
+ this(str.bytes, str.offset, str.length);
+ this.shapeRel = shapeRel;
+ }
+
+ @Override
+ protected QuadPrefixTree getGrid() { return QuadPrefixTree.this; }
+
+ @Override
+ protected int getMaxLevels() { return maxLevels; }
+
+ @Override
+ protected Collection<Cell> getSubCells() {
+ BytesRef source = getTokenBytesNoLeaf(null);
+
+ List<Cell> cells = new ArrayList<>(4);
+ cells.add(new QuadCell(concat(source, (byte)'A'), null));
+ cells.add(new QuadCell(concat(source, (byte)'B'), null));
+ cells.add(new QuadCell(concat(source, (byte)'C'), null));
+ cells.add(new QuadCell(concat(source, (byte)'D'), null));
+ return cells;
+ }
+
+ protected BytesRef concat(BytesRef source, byte b) {
+ //+2 for new char + potential leaf
+ final byte[] buffer = Arrays.copyOfRange(source.bytes, source.offset, source.offset + source.length + 2);
+ BytesRef target = new BytesRef(buffer);
+ target.length = source.length;
+ target.bytes[target.length++] = b;
+ return target;
+ }
+
+ @Override
+ public int getSubCellsSize() {
+ return 4;
+ }
+
+ @Override
+ protected QuadCell getSubCell(Point p) {
+ return (QuadCell) QuadPrefixTree.this.getCell(p, getLevel() + 1);//not performant!
+ }
+
+ @Override
+ public Shape getShape() {
+ if (shape == null)
+ shape = makeShape();
+ return shape;
+ }
+
+ protected Rectangle makeShape() {
+ BytesRef token = getTokenBytesNoLeaf(null);
+ double xmin = QuadPrefixTree.this.xmin;
+ double ymin = QuadPrefixTree.this.ymin;
+
+ for (int i = 0; i < token.length; i++) {
+ byte c = token.bytes[token.offset + i];
+ switch (c) {
+ case 'A':
+ ymin += levelH[i];
+ break;
+ case 'B':
+ xmin += levelW[i];
+ ymin += levelH[i];
+ break;
+ case 'C':
+ break;//nothing really
+ case 'D':
+ xmin += levelW[i];
+ break;
+ default:
+ throw new RuntimeException("unexpected char: " + c);
+ }
+ }
+ int len = token.length;
+ double width, height;
+ if (len > 0) {
+ width = levelW[len-1];
+ height = levelH[len-1];
+ } else {
+ width = gridW;
+ height = gridH;
+ }
+ return ctx.makeRectangle(xmin, xmin + width, ymin, ymin + height);
+ }
+ }//QuadCell
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/89db4950/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/SingletonCellIterator.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/SingletonCellIterator.java b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/SingletonCellIterator.java
new file mode 100644
index 0000000..177b431
--- /dev/null
+++ b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/SingletonCellIterator.java
@@ -0,0 +1,36 @@
+/*
+ * 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;
+
+/**
+ * A singleton (one Cell) instance of CellIterator.
+ *
+ * @lucene.internal
+ */
+class SingletonCellIterator extends CellIterator {
+
+ SingletonCellIterator(Cell cell) {
+ this.nextCell = cell;//preload nextCell
+ }
+
+ @Override
+ public boolean hasNext() {
+ thisCell = null;
+ return nextCell != null;
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/89db4950/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTree.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTree.java b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTree.java
new file mode 100644
index 0000000..8ead954
--- /dev/null
+++ b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTree.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.tree;
+
+import com.spatial4j.core.context.SpatialContext;
+import com.spatial4j.core.shape.Shape;
+import org.apache.lucene.util.BytesRef;
+
+/**
+ * A spatial Prefix Tree, or Trie, which decomposes shapes into prefixed strings
+ * at variable lengths corresponding to variable precision. Each string
+ * corresponds to a rectangular spatial region. This approach is
+ * also referred to "Grids", "Tiles", and "Spatial Tiers".
+ * <p>
+ * Implementations of this class should be thread-safe and immutable once
+ * initialized.
+ *
+ * @lucene.experimental
+ */
+public abstract class SpatialPrefixTree {
+
+ protected final int maxLevels;
+
+ protected final SpatialContext ctx;
+
+ public SpatialPrefixTree(SpatialContext ctx, int maxLevels) {
+ assert maxLevels > 0;
+ this.ctx = ctx;
+ this.maxLevels = maxLevels;
+ }
+
+ public SpatialContext getSpatialContext() {
+ return ctx;
+ }
+
+ public int getMaxLevels() {
+ return maxLevels;
+ }
+
+ @Override
+ public String toString() {
+ return getClass().getSimpleName() + "(maxLevels:" + maxLevels + ",ctx:" + ctx + ")";
+ }
+
+ /**
+ * Returns the level of the largest grid in which its longest side is less
+ * than or equal to the provided distance (in degrees). Consequently {@code
+ * dist} acts as an error epsilon declaring the amount of detail needed in the
+ * grid, such that you can get a grid with just the right amount of
+ * precision.
+ *
+ * @param dist {@code >= 0}
+ * @return level [1 to maxLevels]
+ */
+ public abstract int getLevelForDistance(double dist);
+
+ /**
+ * Given a cell having the specified level, returns the distance from opposite
+ * corners. Since this might vary depending on where the cell is, this method
+ * may over-estimate.
+ *
+ * @param level [1 to maxLevels]
+ * @return {@code > 0}
+ */
+ public abstract double getDistanceForLevel(int level);
+
+ /**
+ * Returns the level 0 cell which encompasses all spatial data. Equivalent to {@link #readCell(BytesRef,Cell)}
+ * with no bytes.
+ */
+ public abstract Cell getWorldCell(); //another possible name: getTopCell
+
+ /**
+ * This creates a new Cell (or re-using {@code scratch} if provided), initialized to the state as read
+ * by the bytes.
+ * Warning: An implementation may refer to the same byte array (no copy). If {@link Cell#setLeaf()} is
+ * subsequently called, it would then modify these bytes.
+ */
+ public abstract Cell readCell(BytesRef term, Cell scratch);
+
+ /**
+ * Gets the intersecting cells for the specified shape, without exceeding
+ * detail level. If a cell is within the query shape then it's marked as a
+ * leaf and none of its children are added. For cells at detailLevel, they are marked as
+ * leaves too, unless it's a point.
+ * <p>
+ * IMPORTANT: Cells returned from the iterator can be re-used for cells at the same level. So you can't simply
+ * iterate to subsequent cells and still refer to the former cell nor the bytes returned from the former cell, unless
+ * you know the former cell is a parent.
+ *
+ * @param shape the shape; possibly null but the caller should liberally call
+ * {@code remove()} if so.
+ * @param detailLevel the maximum detail level to get cells for
+ * @return the matching cells
+ */
+ public CellIterator getTreeCellIterator(Shape shape, int detailLevel) {
+ if (detailLevel > maxLevels) {
+ throw new IllegalArgumentException("detailLevel > maxLevels");
+ }
+ return new TreeCellIterator(shape, detailLevel, getWorldCell());
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/89db4950/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTreeFactory.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTreeFactory.java b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTreeFactory.java
new file mode 100644
index 0000000..b74dc93
--- /dev/null
+++ b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTreeFactory.java
@@ -0,0 +1,99 @@
+/*
+ * 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.util.Map;
+
+import com.spatial4j.core.context.SpatialContext;
+import com.spatial4j.core.distance.DistanceUtils;
+
+/**
+ * Abstract Factory for creating {@link SpatialPrefixTree} instances with useful
+ * defaults and passed on configurations defined in a Map.
+ *
+ * @lucene.experimental
+ */
+public abstract class SpatialPrefixTreeFactory {
+
+ private static final double DEFAULT_GEO_MAX_DETAIL_KM = 0.001;//1m
+ public static final String PREFIX_TREE = "prefixTree";
+ public static final String MAX_LEVELS = "maxLevels";
+ public static final String MAX_DIST_ERR = "maxDistErr";
+
+ protected Map<String, String> args;
+ protected SpatialContext ctx;
+ protected Integer maxLevels;
+
+ /**
+ * The factory is looked up via "prefixTree" in args, expecting "geohash" or "quad".
+ * If it's neither of these, then "geohash" is chosen for a geo context, otherwise "quad" is chosen.
+ */
+ public static SpatialPrefixTree makeSPT(Map<String,String> args, ClassLoader classLoader, SpatialContext ctx) {
+ SpatialPrefixTreeFactory instance;
+ String cname = args.get(PREFIX_TREE);
+ if (cname == null)
+ cname = ctx.isGeo() ? "geohash" : "quad";
+ if ("geohash".equalsIgnoreCase(cname))
+ instance = new GeohashPrefixTree.Factory();
+ else if ("quad".equalsIgnoreCase(cname))
+ instance = new QuadPrefixTree.Factory();
+ else if ("packedQuad".equalsIgnoreCase(cname))
+ instance = new PackedQuadPrefixTree.Factory();
+ else {
+ try {
+ Class<?> c = classLoader.loadClass(cname);
+ instance = (SpatialPrefixTreeFactory) c.newInstance();
+ } catch (Exception e) {
+ throw new RuntimeException(e);
+ }
+ }
+ instance.init(args,ctx);
+ return instance.newSPT();
+ }
+
+ protected void init(Map<String, String> args, SpatialContext ctx) {
+ this.args = args;
+ this.ctx = ctx;
+ initMaxLevels();
+ }
+
+ protected void initMaxLevels() {
+ String mlStr = args.get(MAX_LEVELS);
+ if (mlStr != null) {
+ maxLevels = Integer.valueOf(mlStr);
+ return;
+ }
+
+ double degrees;
+ String maxDetailDistStr = args.get(MAX_DIST_ERR);
+ if (maxDetailDistStr == null) {
+ if (!ctx.isGeo()) {
+ return;//let default to max
+ }
+ degrees = DistanceUtils.dist2Degrees(DEFAULT_GEO_MAX_DETAIL_KM, DistanceUtils.EARTH_MEAN_RADIUS_KM);
+ } else {
+ degrees = Double.parseDouble(maxDetailDistStr);
+ }
+ maxLevels = getLevelForDistance(degrees);
+ }
+
+ /** Calls {@link SpatialPrefixTree#getLevelForDistance(double)}. */
+ protected abstract int getLevelForDistance(double degrees);
+
+ protected abstract SpatialPrefixTree newSPT();
+
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/89db4950/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/TreeCellIterator.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/TreeCellIterator.java b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/TreeCellIterator.java
new file mode 100644
index 0000000..3ec56ac
--- /dev/null
+++ b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/TreeCellIterator.java
@@ -0,0 +1,87 @@
+/*
+ * 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.shape.Point;
+import com.spatial4j.core.shape.Shape;
+
+/**
+ * Navigates a {@link org.apache.lucene.spatial.prefix.tree.SpatialPrefixTree} from a given cell (typically the world
+ * cell) down to a maximum number of configured levels, filtered by a given shape. Intermediate non-leaf cells are
+ * returned. It supports {@link #remove()} for skipping traversal of subcells of the current cell.
+ *
+ * @lucene.internal
+ */
+class TreeCellIterator extends CellIterator {
+ //This class uses a stack approach, which is more efficient than creating linked nodes. And it might more easily
+ // pave the way for re-using Cell & CellIterator at a given level in the future.
+
+ private final Shape shapeFilter;//possibly null
+ private final CellIterator[] iterStack;//starts at level 1
+ private int stackIdx;//-1 when done
+ private boolean descend;
+
+ public TreeCellIterator(Shape shapeFilter, int detailLevel, Cell parentCell) {
+ this.shapeFilter = shapeFilter;
+ assert parentCell.getLevel() == 0;
+ iterStack = new CellIterator[detailLevel];
+ iterStack[0] = parentCell.getNextLevelCells(shapeFilter);
+ stackIdx = 0;//always points to an iter (non-null)
+ //note: not obvious but needed to visit the first cell before trying to descend
+ descend = false;
+ }
+
+ @Override
+ public boolean hasNext() {
+ if (nextCell != null)
+ return true;
+ while (true) {
+ if (stackIdx == -1)//the only condition in which we return false
+ return false;
+ //If we can descend...
+ if (descend && !(stackIdx == iterStack.length - 1 || iterStack[stackIdx].thisCell().isLeaf())) {
+ CellIterator nextIter = iterStack[stackIdx].thisCell().getNextLevelCells(shapeFilter);
+ //push stack
+ iterStack[++stackIdx] = nextIter;
+ }
+ //Get sibling...
+ if (iterStack[stackIdx].hasNext()) {
+ nextCell = iterStack[stackIdx].next();
+ //at detailLevel
+ if (stackIdx == iterStack.length - 1 && !(shapeFilter instanceof Point)) //point check is a kludge
+ nextCell.setLeaf();//because at bottom
+ break;
+ }
+ //Couldn't get next; go up...
+ //pop stack
+ iterStack[stackIdx--] = null;
+ descend = false;//so that we don't re-descend where we just were
+ }
+ assert nextCell != null;
+ descend = true;//reset
+ return true;
+ }
+
+ @Override
+ public void remove() {
+ assert thisCell() != null && nextCell == null;
+ descend = false;
+ }
+
+ //TODO implement a smart nextFrom() that looks at the parent's bytes first
+
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/89db4950/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/package-info.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/package-info.java b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/package-info.java
new file mode 100644
index 0000000..20a4a0e
--- /dev/null
+++ b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/package-info.java
@@ -0,0 +1,30 @@
+/*
+ * 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.
+ */
+
+/**
+ * This package is about SpatialPrefixTree and any supporting classes.
+ * A SpatialPrefixTree supports spatial indexing by index-time tokens
+ * where adding characters to a string gives greater resolution.
+ * <p>
+ * Potential Implementations include:
+ * <ul>
+ * <li>http://en.wikipedia.org/wiki/Quadtree
+ * <li>http://en.wikipedia.org/wiki/Geohash
+ * <li>http://healpix.jpl.nasa.gov/
+ * </ul>
+ */
+package org.apache.lucene.spatial.prefix.tree;
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/89db4950/lucene/spatial-extras/src/java/org/apache/lucene/spatial/query/SpatialArgs.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/java/org/apache/lucene/spatial/query/SpatialArgs.java b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/query/SpatialArgs.java
new file mode 100644
index 0000000..0503072
--- /dev/null
+++ b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/query/SpatialArgs.java
@@ -0,0 +1,148 @@
+/*
+ * 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.Point;
+import com.spatial4j.core.shape.Rectangle;
+import com.spatial4j.core.shape.Shape;
+
+/**
+ * Principally holds the query {@link Shape} and the {@link SpatialOperation}.
+ * It's used as an argument to some methods on {@link org.apache.lucene.spatial.SpatialStrategy}.
+ *
+ * @lucene.experimental
+ */
+public class SpatialArgs {
+
+ public static final double DEFAULT_DISTERRPCT = 0.025d;
+
+ private SpatialOperation operation;
+ private Shape shape;
+ private Double distErrPct;
+ private Double distErr;
+
+ public SpatialArgs(SpatialOperation operation, Shape shape) {
+ if (operation == null || shape == null)
+ throw new NullPointerException("operation and shape are required");
+ this.operation = operation;
+ this.shape = shape;
+ }
+
+ /**
+ * Computes the distance given a shape and the {@code distErrPct}. The
+ * algorithm is the fraction of the distance from the center of the query
+ * shape to its closest bounding box corner.
+ *
+ * @param shape Mandatory.
+ * @param distErrPct 0 to 0.5
+ * @param ctx Mandatory
+ * @return A distance (in degrees).
+ */
+ public static double calcDistanceFromErrPct(Shape shape, double distErrPct, SpatialContext ctx) {
+ if (distErrPct < 0 || distErrPct > 0.5) {
+ throw new IllegalArgumentException("distErrPct " + distErrPct + " must be between [0 to 0.5]");
+ }
+ if (distErrPct == 0 || shape instanceof Point) {
+ return 0;
+ }
+ Rectangle bbox = shape.getBoundingBox();
+ //Compute the distance from the center to a corner. Because the distance
+ // to a bottom corner vs a top corner can vary in a geospatial scenario,
+ // take the closest one (greater precision).
+ Point ctr = bbox.getCenter();
+ double y = (ctr.getY() >= 0 ? bbox.getMaxY() : bbox.getMinY());
+ double diagonalDist = ctx.getDistCalc().distance(ctr, bbox.getMaxX(), y);
+ return diagonalDist * distErrPct;
+ }
+
+ /**
+ * Gets the error distance that specifies how precise the query shape is. This
+ * looks at {@link #getDistErr()}, {@link #getDistErrPct()}, and {@code
+ * defaultDistErrPct}.
+ * @param defaultDistErrPct 0 to 0.5
+ * @return {@code >= 0}
+ */
+ public double resolveDistErr(SpatialContext ctx, double defaultDistErrPct) {
+ if (distErr != null)
+ return distErr;
+ double distErrPct = (this.distErrPct != null ? this.distErrPct : defaultDistErrPct);
+ return calcDistanceFromErrPct(shape, distErrPct, ctx);
+ }
+
+ /** Check if the arguments make sense -- throw an exception if not */
+ public void validate() throws IllegalArgumentException {
+ if (distErr != null && distErrPct != null)
+ throw new IllegalArgumentException("Only distErr or distErrPct can be specified.");
+ }
+
+ @Override
+ public String toString() {
+ return SpatialArgsParser.writeSpatialArgs(this);
+ }
+
+ //------------------------------------------------
+ // Getters & Setters
+ //------------------------------------------------
+
+ public SpatialOperation getOperation() {
+ return operation;
+ }
+
+ public void setOperation(SpatialOperation operation) {
+ this.operation = operation;
+ }
+
+ public Shape getShape() {
+ return shape;
+ }
+
+ public void setShape(Shape shape) {
+ this.shape = shape;
+ }
+
+ /**
+ * A measure of acceptable error of the shape as a fraction. This effectively
+ * inflates the size of the shape but should not shrink it.
+ *
+ * @return 0 to 0.5
+ * @see #calcDistanceFromErrPct(com.spatial4j.core.shape.Shape, double,
+ * com.spatial4j.core.context.SpatialContext)
+ */
+ public Double getDistErrPct() {
+ return distErrPct;
+ }
+
+ public void setDistErrPct(Double distErrPct) {
+ if (distErrPct != null)
+ this.distErrPct = distErrPct;
+ }
+
+ /**
+ * The acceptable error of the shape. This effectively inflates the
+ * size of the shape but should not shrink it.
+ *
+ * @return {@code >= 0}
+ */
+ public Double getDistErr() {
+ return distErr;
+ }
+
+ public void setDistErr(Double distErr) {
+ this.distErr = distErr;
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/89db4950/lucene/spatial-extras/src/java/org/apache/lucene/spatial/query/SpatialArgsParser.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/java/org/apache/lucene/spatial/query/SpatialArgsParser.java b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/query/SpatialArgsParser.java
new file mode 100644
index 0000000..81612ff
--- /dev/null
+++ b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/query/SpatialArgsParser.java
@@ -0,0 +1,146 @@
+/*
+ * 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.exception.InvalidShapeException;
+import com.spatial4j.core.shape.Shape;
+
+import java.text.ParseException;
+import java.util.HashMap;
+import java.util.Locale;
+import java.util.Map;
+import java.util.StringTokenizer;
+
+/**
+ * Parses a string that usually looks like "OPERATION(SHAPE)" into a {@link SpatialArgs}
+ * object. The set of operations supported are defined in {@link SpatialOperation}, such
+ * as "Intersects" being a common one. The shape portion is defined by WKT {@link com.spatial4j.core.io.WktShapeParser},
+ * but it can be overridden/customized via {@link #parseShape(String, com.spatial4j.core.context.SpatialContext)}.
+ * There are some optional name-value pair parameters that follow the closing parenthesis. Example:
+ * <pre>
+ * Intersects(ENVELOPE(-10,-8,22,20)) distErrPct=0.025
+ * </pre>
+ * <p>
+ * In the future it would be good to support something at least semi-standardized like a
+ * variant of <a href="http://docs.geoserver.org/latest/en/user/filter/ecql_reference.html#spatial-predicate">
+ * [E]CQL</a>.
+ *
+ * @lucene.experimental
+ */
+public class SpatialArgsParser {
+
+ public static final String DIST_ERR_PCT = "distErrPct";
+ public static final String DIST_ERR = "distErr";
+
+ /** Writes a close approximation to the parsed input format. */
+ static String writeSpatialArgs(SpatialArgs args) {
+ StringBuilder str = new StringBuilder();
+ str.append(args.getOperation().getName());
+ str.append('(');
+ str.append(args.getShape().toString());
+ if (args.getDistErrPct() != null)
+ str.append(" distErrPct=").append(String.format(Locale.ROOT, "%.2f%%", args.getDistErrPct() * 100d));
+ if (args.getDistErr() != null)
+ str.append(" distErr=").append(args.getDistErr());
+ str.append(')');
+ return str.toString();
+ }
+
+ /**
+ * Parses a string such as "Intersects(ENVELOPE(-10,-8,22,20)) distErrPct=0.025".
+ *
+ * @param v The string to parse. Mandatory.
+ * @param ctx The spatial context. Mandatory.
+ * @return Not null.
+ * @throws IllegalArgumentException if the parameters don't make sense or an add-on parameter is unknown
+ * @throws ParseException If there is a problem parsing the string
+ * @throws InvalidShapeException When the coordinates are invalid for the shape
+ */
+ public SpatialArgs parse(String v, SpatialContext ctx) throws ParseException, InvalidShapeException {
+ int idx = v.indexOf('(');
+ int edx = v.lastIndexOf(')');
+
+ if (idx < 0 || idx > edx) {
+ throw new ParseException("missing parens: " + v, -1);
+ }
+
+ SpatialOperation op = SpatialOperation.get(v.substring(0, idx).trim());
+
+ String body = v.substring(idx + 1, edx).trim();
+ if (body.length() < 1) {
+ throw new ParseException("missing body : " + v, idx + 1);
+ }
+
+ Shape shape = parseShape(body, ctx);
+ SpatialArgs args = newSpatialArgs(op, shape);
+
+ if (v.length() > (edx + 1)) {
+ body = v.substring(edx + 1).trim();
+ if (body.length() > 0) {
+ Map<String, String> aa = parseMap(body);
+ readNameValuePairs(args, aa);
+ if (!aa.isEmpty()) {
+ throw new IllegalArgumentException("unused parameters: " + aa);
+ }
+ }
+ }
+ args.validate();
+ return args;
+ }
+
+ protected SpatialArgs newSpatialArgs(SpatialOperation op, Shape shape) {
+ return new SpatialArgs(op, shape);
+ }
+
+ protected void readNameValuePairs(SpatialArgs args, Map<String, String> nameValPairs) {
+ args.setDistErrPct(readDouble(nameValPairs.remove(DIST_ERR_PCT)));
+ args.setDistErr(readDouble(nameValPairs.remove(DIST_ERR)));
+ }
+
+ protected Shape parseShape(String str, SpatialContext ctx) throws ParseException {
+ //return ctx.readShape(str);//still in Spatial4j 0.4 but will be deleted
+ return ctx.readShapeFromWkt(str);
+ }
+
+ protected static Double readDouble(String v) {
+ return v == null ? null : Double.valueOf(v);
+ }
+
+ protected static boolean readBool(String v, boolean defaultValue) {
+ return v == null ? defaultValue : Boolean.parseBoolean(v);
+ }
+
+ /** Parses "a=b c=d f" (whitespace separated) into name-value pairs. If there
+ * is no '=' as in 'f' above then it's short for f=f. */
+ protected static Map<String, String> parseMap(String body) {
+ Map<String, String> map = new HashMap<>();
+ StringTokenizer st = new StringTokenizer(body, " \n\t");
+ while (st.hasMoreTokens()) {
+ String a = st.nextToken();
+ int idx = a.indexOf('=');
+ if (idx > 0) {
+ String k = a.substring(0, idx);
+ String v = a.substring(idx + 1);
+ map.put(k, v);
+ } else {
+ map.put(a, a);
+ }
+ }
+ return map;
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/89db4950/lucene/spatial-extras/src/java/org/apache/lucene/spatial/query/SpatialOperation.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/java/org/apache/lucene/spatial/query/SpatialOperation.java b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/query/SpatialOperation.java
new file mode 100644
index 0000000..7d750ac
--- /dev/null
+++ b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/query/SpatialOperation.java
@@ -0,0 +1,179 @@
+/*
+ * 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.shape.Rectangle;
+import com.spatial4j.core.shape.Shape;
+import com.spatial4j.core.shape.SpatialRelation;
+
+import java.io.Serializable;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Locale;
+import java.util.Map;
+
+/**
+ * A predicate that compares a stored geometry to a supplied geometry. It's enum-like. For more
+ * explanation of each predicate, consider looking at the source implementation
+ * of {@link #evaluate(com.spatial4j.core.shape.Shape, com.spatial4j.core.shape.Shape)}. It's important
+ * to be aware that Lucene-spatial makes no distinction of shape boundaries, unlike many standardized
+ * definitions. Nor does it make dimensional distinctions (e.g. line vs polygon).
+ * You can lookup a predicate by "Covers" or "Contains", for example, and you will get the
+ * same underlying predicate implementation.
+ *
+ * @see <a href="http://en.wikipedia.org/wiki/DE-9IM">DE-9IM at Wikipedia, based on OGC specs</a>
+ * @see <a href="http://edndoc.esri.com/arcsde/9.1/general_topics/understand_spatial_relations.htm">
+ * ESRIs docs on spatial relations</a>
+ *
+ * @lucene.experimental
+ */
+public abstract class SpatialOperation implements Serializable {
+ //TODO rename to SpatialPredicate. Use enum? LUCENE-5771
+
+ // Private registry
+ private static final Map<String, SpatialOperation> registry = new HashMap<>();//has aliases
+ private static final List<SpatialOperation> list = new ArrayList<>();
+
+ // Geometry Operations
+
+ /** Bounding box of the *indexed* shape, then {@link #Intersects}. */
+ public static final SpatialOperation BBoxIntersects = new SpatialOperation("BBoxIntersects") {
+ @Override
+ public boolean evaluate(Shape indexedShape, Shape queryShape) {
+ return indexedShape.getBoundingBox().relate(queryShape).intersects();
+ }
+ };
+ /** Bounding box of the *indexed* shape, then {@link #IsWithin}. */
+ public static final SpatialOperation BBoxWithin = new SpatialOperation("BBoxWithin") {
+ {
+ register("BBoxCoveredBy");//alias -- the better name
+ }
+ @Override
+ public boolean evaluate(Shape indexedShape, Shape queryShape) {
+ Rectangle bbox = indexedShape.getBoundingBox();
+ return bbox.relate(queryShape) == SpatialRelation.WITHIN || bbox.equals(queryShape);
+ }
+ };
+ /** Meets the "Covers" OGC definition (boundary-neutral). */
+ public static final SpatialOperation Contains = new SpatialOperation("Contains") {
+ {
+ register("Covers");//alias -- the better name
+ }
+ @Override
+ public boolean evaluate(Shape indexedShape, Shape queryShape) {
+ return indexedShape.relate(queryShape) == SpatialRelation.CONTAINS || indexedShape.equals(queryShape);
+ }
+ };
+ /** Meets the "Intersects" OGC definition. */
+ public static final SpatialOperation Intersects = new SpatialOperation("Intersects") {
+ @Override
+ public boolean evaluate(Shape indexedShape, Shape queryShape) {
+ return indexedShape.relate(queryShape).intersects();
+ }
+ };
+ /** Meets the "Equals" OGC definition. */
+ public static final SpatialOperation IsEqualTo = new SpatialOperation("Equals") {
+ {
+ register("IsEqualTo");//alias (deprecated)
+ }
+ @Override
+ public boolean evaluate(Shape indexedShape, Shape queryShape) {
+ return indexedShape.equals(queryShape);
+ }
+ };
+ /** Meets the "Disjoint" OGC definition. */
+ public static final SpatialOperation IsDisjointTo = new SpatialOperation("Disjoint") {
+ {
+ register("IsDisjointTo");//alias (deprecated)
+ }
+ @Override
+ public boolean evaluate(Shape indexedShape, Shape queryShape) {
+ return ! indexedShape.relate(queryShape).intersects();
+ }
+ };
+ /** Meets the "CoveredBy" OGC definition (boundary-neutral). */
+ public static final SpatialOperation IsWithin = new SpatialOperation("Within") {
+ {
+ register("IsWithin");//alias (deprecated)
+ register("CoveredBy");//alias -- the more appropriate name.
+ }
+ @Override
+ public boolean evaluate(Shape indexedShape, Shape queryShape) {
+ return indexedShape.relate(queryShape) == SpatialRelation.WITHIN || indexedShape.equals(queryShape);
+ }
+ };
+ /** Almost meets the "Overlaps" OGC definition, but boundary-neutral (boundary==interior). */
+ public static final SpatialOperation Overlaps = new SpatialOperation("Overlaps") {
+ @Override
+ public boolean evaluate(Shape indexedShape, Shape queryShape) {
+ return indexedShape.relate(queryShape) == SpatialRelation.INTERSECTS;//not Contains or Within or Disjoint
+ }
+ };
+
+ private final String name;
+
+ protected SpatialOperation(String name) {
+ this.name = name;
+ register(name);
+ list.add( this );
+ }
+
+ protected void register(String name) {
+ registry.put(name, this);
+ registry.put(name.toUpperCase(Locale.ROOT), this);
+ }
+
+ public static SpatialOperation get( String v ) {
+ SpatialOperation op = registry.get( v );
+ if( op == null ) {
+ op = registry.get(v.toUpperCase(Locale.ROOT));
+ }
+ if( op == null ) {
+ throw new IllegalArgumentException("Unknown Operation: " + v );
+ }
+ return op;
+ }
+
+ public static List<SpatialOperation> values() {
+ return list;
+ }
+
+ public static boolean is( SpatialOperation op, SpatialOperation ... tst ) {
+ for( SpatialOperation t : tst ) {
+ if( op == t ) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ /**
+ * Returns whether the relationship between indexedShape and queryShape is
+ * satisfied by this operation.
+ */
+ public abstract boolean evaluate(Shape indexedShape, Shape queryShape);
+
+ public String getName() {
+ return name;
+ }
+
+ @Override
+ public String toString() {
+ return name;
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/89db4950/lucene/spatial-extras/src/java/org/apache/lucene/spatial/query/UnsupportedSpatialOperation.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/java/org/apache/lucene/spatial/query/UnsupportedSpatialOperation.java b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/query/UnsupportedSpatialOperation.java
new file mode 100644
index 0000000..d6cb152
--- /dev/null
+++ b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/query/UnsupportedSpatialOperation.java
@@ -0,0 +1,28 @@
+/*
+ * 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;
+
+/**
+ * Exception thrown when the {@link org.apache.lucene.spatial.SpatialStrategy} cannot implement the requested operation.
+ * @lucene.experimental
+ */
+public class UnsupportedSpatialOperation extends UnsupportedOperationException {
+
+ public UnsupportedSpatialOperation(SpatialOperation op) {
+ super(op.getName());
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/89db4950/lucene/spatial-extras/src/java/org/apache/lucene/spatial/query/package-info.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/java/org/apache/lucene/spatial/query/package-info.java b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/query/package-info.java
new file mode 100644
index 0000000..a7946a4
--- /dev/null
+++ b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/query/package-info.java
@@ -0,0 +1,21 @@
+/*
+ * 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.
+ */
+
+/**
+ * Spatial Query options useful for client side requests
+ */
+package org.apache.lucene.spatial.query;
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/89db4950/lucene/spatial-extras/src/java/org/apache/lucene/spatial/serialized/SerializedDVStrategy.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/java/org/apache/lucene/spatial/serialized/SerializedDVStrategy.java b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/serialized/SerializedDVStrategy.java
new file mode 100644
index 0000000..a6c575b
--- /dev/null
+++ b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/serialized/SerializedDVStrategy.java
@@ -0,0 +1,278 @@
+/*
+ * 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.serialized;
+
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.FilterOutputStream;
+import java.io.IOException;
+import java.util.Map;
+
+import com.spatial4j.core.context.SpatialContext;
+import com.spatial4j.core.io.BinaryCodec;
+import com.spatial4j.core.shape.Point;
+import com.spatial4j.core.shape.Shape;
+import org.apache.lucene.document.BinaryDocValuesField;
+import org.apache.lucene.document.Field;
+import org.apache.lucene.index.BinaryDocValues;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.queries.function.FunctionValues;
+import org.apache.lucene.queries.function.ValueSource;
+import org.apache.lucene.search.Explanation;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.RandomAccessWeight;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.spatial.SpatialStrategy;
+import org.apache.lucene.spatial.query.SpatialArgs;
+import org.apache.lucene.spatial.util.DistanceToShapeValueSource;
+import org.apache.lucene.spatial.util.ShapePredicateValueSource;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.BytesRefBuilder;
+
+
+/**
+ * A SpatialStrategy based on serializing a Shape stored into BinaryDocValues.
+ * This is not at all fast; it's designed to be used in conjunction with another index based
+ * SpatialStrategy that is approximated (like {@link org.apache.lucene.spatial.prefix.RecursivePrefixTreeStrategy})
+ * to add precision or eventually make more specific / advanced calculations on the per-document
+ * geometry.
+ * The serialization uses Spatial4j's {@link com.spatial4j.core.io.BinaryCodec}.
+ *
+ * @lucene.experimental
+ */
+public class SerializedDVStrategy extends SpatialStrategy {
+
+ /**
+ * A cache heuristic for the buf size based on the last shape size.
+ */
+ //TODO do we make this non-volatile since it's merely a heuristic?
+ private volatile int indexLastBufSize = 8 * 1024;//8KB default on first run
+
+ /**
+ * Constructs the spatial strategy with its mandatory arguments.
+ */
+ public SerializedDVStrategy(SpatialContext ctx, String fieldName) {
+ super(ctx, fieldName);
+ }
+
+ @Override
+ public Field[] createIndexableFields(Shape shape) {
+ int bufSize = Math.max(128, (int) (this.indexLastBufSize * 1.5));//50% headroom over last
+ ByteArrayOutputStream byteStream = new ByteArrayOutputStream(bufSize);
+ final BytesRef bytesRef = new BytesRef();//receiver of byteStream's bytes
+ try {
+ ctx.getBinaryCodec().writeShape(new DataOutputStream(byteStream), shape);
+ //this is a hack to avoid redundant byte array copying by byteStream.toByteArray()
+ byteStream.writeTo(new FilterOutputStream(null/*not used*/) {
+ @Override
+ public void write(byte[] b, int off, int len) throws IOException {
+ bytesRef.bytes = b;
+ bytesRef.offset = off;
+ bytesRef.length = len;
+ }
+ });
+ } catch (IOException e) {
+ throw new RuntimeException(e);
+ }
+ this.indexLastBufSize = bytesRef.length;//cache heuristic
+ return new Field[]{new BinaryDocValuesField(getFieldName(), bytesRef)};
+ }
+
+ @Override
+ public ValueSource makeDistanceValueSource(Point queryPoint, double multiplier) {
+ //TODO if makeShapeValueSource gets lifted to the top; this could become a generic impl.
+ return new DistanceToShapeValueSource(makeShapeValueSource(), queryPoint, multiplier, ctx);
+ }
+
+ /**
+ * Returns a Query that should be used in a random-access fashion.
+ * Use in another manner will be SLOW.
+ */
+ @Override
+ public Query makeQuery(SpatialArgs args) {
+ ValueSource shapeValueSource = makeShapeValueSource();
+ ShapePredicateValueSource predicateValueSource = new ShapePredicateValueSource(
+ shapeValueSource, args.getOperation(), args.getShape());
+ return new PredicateValueSourceQuery(predicateValueSource);
+ }
+
+ /**
+ * Provides access to each shape per document as a ValueSource in which
+ * {@link org.apache.lucene.queries.function.FunctionValues#objectVal(int)} returns a {@link
+ * Shape}.
+ */ //TODO raise to SpatialStrategy
+ public ValueSource makeShapeValueSource() {
+ return new ShapeDocValueSource(getFieldName(), ctx.getBinaryCodec());
+ }
+
+ /** Warning: don't iterate over the results of this query; it's designed for use in a random-access fashion
+ * by {@link TwoPhaseIterator}.
+ */
+ static class PredicateValueSourceQuery extends Query {
+ private final ValueSource predicateValueSource;//we call boolVal(doc)
+
+ public PredicateValueSourceQuery(ValueSource predicateValueSource) {
+ this.predicateValueSource = predicateValueSource;
+ }
+
+ @Override
+ public Weight createWeight(IndexSearcher searcher, boolean needsScores) throws IOException {
+ return new RandomAccessWeight(this) {
+ @Override
+ protected Bits getMatchingDocs(LeafReaderContext context) throws IOException {
+ final FunctionValues predFuncValues = predicateValueSource.getValues(null, context);
+ return new Bits() {
+ @Override
+ public boolean get(int index) {
+ return predFuncValues.boolVal(index);
+ }
+
+ @Override
+ public int length() {
+ return context.reader().maxDoc();
+ }
+ };
+ }
+ };
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) return true;
+ if (super.equals(o) == false) return false;
+
+ PredicateValueSourceQuery that = (PredicateValueSourceQuery) o;
+
+ if (!predicateValueSource.equals(that.predicateValueSource)) return false;
+
+ return true;
+ }
+
+ @Override
+ public int hashCode() {
+ return super.hashCode() + 31 * predicateValueSource.hashCode();
+ }
+
+ @Override
+ public String toString(String field) {
+ return "PredicateValueSourceQuery(" +
+ predicateValueSource.toString() +
+ ")";
+ }
+ }//PredicateValueSourceQuery
+
+ /**
+ * Implements a ValueSource by deserializing a Shape in from BinaryDocValues using BinaryCodec.
+ * @see #makeShapeValueSource()
+ */
+ static class ShapeDocValueSource extends ValueSource {
+
+ private final String fieldName;
+ private final BinaryCodec binaryCodec;//spatial4j
+
+ private ShapeDocValueSource(String fieldName, BinaryCodec binaryCodec) {
+ this.fieldName = fieldName;
+ this.binaryCodec = binaryCodec;
+ }
+
+ @Override
+ public FunctionValues getValues(Map context, LeafReaderContext readerContext) throws IOException {
+ final BinaryDocValues docValues = readerContext.reader().getBinaryDocValues(fieldName);
+
+ return new FunctionValues() {
+ int bytesRefDoc = -1;
+ BytesRefBuilder bytesRef = new BytesRefBuilder();
+
+ boolean fillBytes(int doc) {
+ if (bytesRefDoc != doc) {
+ bytesRef.copyBytes(docValues.get(doc));
+ bytesRefDoc = doc;
+ }
+ return bytesRef.length() != 0;
+ }
+
+ @Override
+ public boolean exists(int doc) {
+ return fillBytes(doc);
+ }
+
+ @Override
+ public boolean bytesVal(int doc, BytesRefBuilder target) {
+ target.clear();
+ if (fillBytes(doc)) {
+ target.copyBytes(bytesRef);
+ return true;
+ } else {
+ return false;
+ }
+ }
+
+ @Override
+ public Object objectVal(int docId) {
+ if (!fillBytes(docId))
+ return null;
+ DataInputStream dataInput = new DataInputStream(
+ new ByteArrayInputStream(bytesRef.bytes(), 0, bytesRef.length()));
+ try {
+ return binaryCodec.readShape(dataInput);
+ } catch (IOException e) {
+ throw new RuntimeException(e);
+ }
+ }
+
+ @Override
+ public Explanation explain(int doc) {
+ return Explanation.match(Float.NaN, toString(doc));
+ }
+
+ @Override
+ public String toString(int doc) {
+ return description() + "=" + objectVal(doc);//TODO truncate?
+ }
+
+ };
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) return true;
+ if (o == null || getClass() != o.getClass()) return false;
+
+ ShapeDocValueSource that = (ShapeDocValueSource) o;
+
+ if (!fieldName.equals(that.fieldName)) return false;
+
+ return true;
+ }
+
+ @Override
+ public int hashCode() {
+ int result = fieldName.hashCode();
+ return result;
+ }
+
+ @Override
+ public String description() {
+ return "shapeDocVal(" + fieldName + ")";
+ }
+ }//ShapeDocValueSource
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/89db4950/lucene/spatial-extras/src/java/org/apache/lucene/spatial/serialized/package-info.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/java/org/apache/lucene/spatial/serialized/package-info.java b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/serialized/package-info.java
new file mode 100644
index 0000000..8f88a73
--- /dev/null
+++ b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/serialized/package-info.java
@@ -0,0 +1,21 @@
+/*
+ * 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.
+ */
+
+/**
+ * Strategies that serialize the shape (non-indexed).
+ */
+package org.apache.lucene.spatial.serialized;
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/89db4950/lucene/spatial-extras/src/java/org/apache/lucene/spatial/spatial4j/Geo3dShape.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/java/org/apache/lucene/spatial/spatial4j/Geo3dShape.java b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/spatial4j/Geo3dShape.java
new file mode 100644
index 0000000..7a3078a
--- /dev/null
+++ b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/spatial4j/Geo3dShape.java
@@ -0,0 +1,185 @@
+/*
+ * 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.spatial4j;
+
+import com.spatial4j.core.context.SpatialContext;
+import com.spatial4j.core.distance.DistanceUtils;
+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.geo3d.LatLonBounds;
+import org.apache.lucene.geo3d.GeoArea;
+import org.apache.lucene.geo3d.GeoAreaFactory;
+import org.apache.lucene.geo3d.GeoPoint;
+import org.apache.lucene.geo3d.GeoShape;
+import org.apache.lucene.geo3d.PlanetModel;
+
+/**
+ * A Spatial4j Shape wrapping a {@link GeoShape} ("Geo3D") -- a 3D planar geometry based Spatial4j Shape implementation.
+ * Geo3D implements shapes on the surface of a sphere or ellipsoid.
+ *
+ * @lucene.experimental
+ */
+public class Geo3dShape implements Shape {
+ /** The required size of this adjustment depends on the actual planetary model chosen.
+ * This value is big enough to account for WGS84. */
+ protected static final double ROUNDOFF_ADJUSTMENT = 0.05;
+
+ public final SpatialContext ctx;
+ public final GeoShape shape;
+ public final PlanetModel planetModel;
+
+ private volatile Rectangle boundingBox = null; // lazy initialized
+
+ public Geo3dShape(final GeoShape shape, final SpatialContext ctx) {
+ this(PlanetModel.SPHERE, shape, ctx);
+ }
+
+ public Geo3dShape(final PlanetModel planetModel, final GeoShape shape, final SpatialContext ctx) {
+ if (!ctx.isGeo()) {
+ throw new IllegalArgumentException("SpatialContext.isGeo() must be true");
+ }
+ this.ctx = ctx;
+ this.planetModel = planetModel;
+ this.shape = shape;
+ }
+
+ @Override
+ public SpatialContext getContext() {
+ return ctx;
+ }
+
+ @Override
+ public SpatialRelation relate(Shape other) {
+ if (other instanceof Rectangle)
+ return relate((Rectangle)other);
+ else if (other instanceof Point)
+ return relate((Point)other);
+ else
+ throw new RuntimeException("Unimplemented shape relationship determination: " + other.getClass());
+ }
+
+ protected SpatialRelation relate(Rectangle r) {
+ // Construct the right kind of GeoArea first
+ GeoArea geoArea = GeoAreaFactory.makeGeoArea(planetModel,
+ r.getMaxY() * DistanceUtils.DEGREES_TO_RADIANS,
+ r.getMinY() * DistanceUtils.DEGREES_TO_RADIANS,
+ r.getMinX() * DistanceUtils.DEGREES_TO_RADIANS,
+ r.getMaxX() * DistanceUtils.DEGREES_TO_RADIANS);
+ int relationship = geoArea.getRelationship(shape);
+ if (relationship == GeoArea.WITHIN)
+ return SpatialRelation.WITHIN;
+ else if (relationship == GeoArea.CONTAINS)
+ return SpatialRelation.CONTAINS;
+ else if (relationship == GeoArea.OVERLAPS)
+ return SpatialRelation.INTERSECTS;
+ else if (relationship == GeoArea.DISJOINT)
+ return SpatialRelation.DISJOINT;
+ else
+ throw new RuntimeException("Unknown relationship returned: "+relationship);
+ }
+
+ protected SpatialRelation relate(Point p) {
+ // Create a GeoPoint
+ GeoPoint point = new GeoPoint(planetModel, p.getY()* DistanceUtils.DEGREES_TO_RADIANS, p.getX()* DistanceUtils.DEGREES_TO_RADIANS);
+ if (shape.isWithin(point)) {
+ // Point within shape
+ return SpatialRelation.CONTAINS;
+ }
+ return SpatialRelation.DISJOINT;
+ }
+
+
+
+ @Override
+ public Rectangle getBoundingBox() {
+ Rectangle bbox = this.boundingBox;//volatile read once
+ if (bbox == null) {
+ LatLonBounds bounds = new LatLonBounds();
+ shape.getBounds(bounds);
+ double leftLon;
+ double rightLon;
+ if (bounds.checkNoLongitudeBound()) {
+ leftLon = -180.0;
+ rightLon = 180.0;
+ } else {
+ leftLon = bounds.getLeftLongitude().doubleValue() * DistanceUtils.RADIANS_TO_DEGREES;
+ rightLon = bounds.getRightLongitude().doubleValue() * DistanceUtils.RADIANS_TO_DEGREES;
+ }
+ double minLat;
+ if (bounds.checkNoBottomLatitudeBound()) {
+ minLat = -90.0;
+ } else {
+ minLat = bounds.getMinLatitude().doubleValue() * DistanceUtils.RADIANS_TO_DEGREES;
+ }
+ double maxLat;
+ if (bounds.checkNoTopLatitudeBound()) {
+ maxLat = 90.0;
+ } else {
+ maxLat = bounds.getMaxLatitude().doubleValue() * DistanceUtils.RADIANS_TO_DEGREES;
+ }
+ bbox = new RectangleImpl(leftLon, rightLon, minLat, maxLat, ctx).getBuffered(ROUNDOFF_ADJUSTMENT, ctx);
+ this.boundingBox = bbox;
+ }
+ return bbox;
+ }
+
+ @Override
+ public boolean hasArea() {
+ return true;
+ }
+
+ @Override
+ public double getArea(SpatialContext ctx) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public Point getCenter() {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public Shape getBuffered(double distance, SpatialContext ctx) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public boolean isEmpty() {
+ return false;
+ }
+
+ @Override
+ public String toString() {
+ return "Geo3dShape{planetmodel=" + planetModel + ", shape=" + shape + '}';
+ }
+
+ @Override
+ public boolean equals(Object other) {
+ if (!(other instanceof Geo3dShape))
+ return false;
+ Geo3dShape tr = (Geo3dShape)other;
+ return tr.ctx.equals(ctx) && tr.planetModel.equals(planetModel) && tr.shape.equals(shape);
+ }
+
+ @Override
+ public int hashCode() {
+ return planetModel.hashCode() + shape.hashCode();
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/89db4950/lucene/spatial-extras/src/java/org/apache/lucene/spatial/spatial4j/package-info.java
----------------------------------------------------------------------
diff --git a/lucene/spatial-extras/src/java/org/apache/lucene/spatial/spatial4j/package-info.java b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/spatial4j/package-info.java
new file mode 100644
index 0000000..7815318
--- /dev/null
+++ b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/spatial4j/package-info.java
@@ -0,0 +1,19 @@
+/*
+ * 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.
+ */
+
+/** Spatial4j stuff that ideally belongs in Spatial4j (isn't related to Lucene). */
+package org.apache.lucene.spatial.spatial4j;
\ No newline at end of file