lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From hoss...@apache.org
Subject [29/50] [abbrv] lucene-solr git commit: LUCENE-7015: Refactor spatial module to spatial-extras
Date Tue, 01 Mar 2016 17:07:12 GMT
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


Mime
View raw message