You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by ds...@apache.org on 2014/04/04 18:29:20 UTC
svn commit: r1584795 - in /lucene/dev/branches/branch_4x: ./ lucene/
lucene/spatial/ lucene/spatial/src/java/org/apache/lucene/spatial/prefix/
lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/
lucene/spatial/src/test/org/apache/lucene/spat...
Author: dsmiley
Date: Fri Apr 4 16:29:20 2014
New Revision: 1584795
URL: http://svn.apache.org/r1584795
Log:
LUCENE-5565: Refactor SpatialPrefixTree/Cell to not use Strings. Other misc API changes to these classes too.
Added:
lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/CellTokenStream.java
- copied unchanged from r1584793, lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/CellTokenStream.java
Modified:
lucene/dev/branches/branch_4x/ (props changed)
lucene/dev/branches/branch_4x/lucene/ (props changed)
lucene/dev/branches/branch_4x/lucene/CHANGES.txt
lucene/dev/branches/branch_4x/lucene/spatial/ (props changed)
lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/AbstractVisitingPrefixTreeFilter.java
lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/ContainsPrefixTreeFilter.java
lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/PointPrefixTreeFieldCacheProvider.java
lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/PrefixTreeStrategy.java
lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/TermQueryPrefixTreeStrategy.java
lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/Cell.java
lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/GeohashPrefixTree.java
lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/QuadPrefixTree.java
lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTree.java
lucene/dev/branches/branch_4x/lucene/spatial/src/test/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTreeTest.java
Modified: lucene/dev/branches/branch_4x/lucene/CHANGES.txt
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/CHANGES.txt?rev=1584795&r1=1584794&r2=1584795&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/CHANGES.txt (original)
+++ lucene/dev/branches/branch_4x/lucene/CHANGES.txt Fri Apr 4 16:29:20 2014
@@ -130,6 +130,8 @@ API Changes
* LUCENE-5543: Remove/deprecate Directory.fileExists (Mike McCandless)
+* LUCENE-5565: Refactor SpatialPrefixTree/Cell to not use Strings. (David Smiley)
+
Optimizations
* LUCENE-5468: HunspellStemFilter uses 10 to 100x less RAM. It also loads
Modified: lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/AbstractVisitingPrefixTreeFilter.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/AbstractVisitingPrefixTreeFilter.java?rev=1584795&r1=1584794&r2=1584795&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/AbstractVisitingPrefixTreeFilter.java (original)
+++ lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/AbstractVisitingPrefixTreeFilter.java Fri Apr 4 16:29:20 2014
@@ -25,7 +25,6 @@ import org.apache.lucene.spatial.prefix.
import org.apache.lucene.spatial.prefix.tree.SpatialPrefixTree;
import org.apache.lucene.util.Bits;
import org.apache.lucene.util.BytesRef;
-import org.apache.lucene.util.StringHelper;
import java.io.IOException;
import java.util.Iterator;
@@ -117,7 +116,7 @@ public abstract class AbstractVisitingPr
protected final boolean hasIndexedLeaves;//if false then we can skip looking for them
private VNode curVNode;//current pointer, derived from query shape
- private BytesRef curVNodeTerm = new BytesRef();//curVNode.cell's term.
+ private BytesRef curVNodeTerm = new BytesRef();//curVNode.cell's term, without leaf
private Cell scanCell;
private BytesRef thisTerm;//the result of termsEnum.term()
@@ -171,8 +170,7 @@ public abstract class AbstractVisitingPr
}
//Seek to curVNode's cell (or skip if termsEnum has moved beyond)
- curVNodeTerm.bytes = curVNode.cell.getTokenBytes();
- curVNodeTerm.length = curVNodeTerm.bytes.length;
+ curVNode.cell.getTokenBytesNoLeaf(curVNodeTerm);
int compare = termsEnum.getComparator().compare(thisTerm, curVNodeTerm);
if (compare > 0) {
// leap frog (termsEnum is beyond where we would otherwise seek)
@@ -215,7 +213,7 @@ public abstract class AbstractVisitingPr
if (hasIndexedLeaves && cell.getLevel() != 0) {
//If the next indexed term just adds a leaf marker ('+') to cell,
// then add all of those docs
- assert StringHelper.startsWith(thisTerm, curVNodeTerm);//TODO refactor to use method on curVNode.cell
+ assert curVNode.cell.isWithin(curVNodeTerm, thisTerm);
scanCell = grid.getCell(thisTerm.bytes, thisTerm.offset, thisTerm.length, scanCell);
if (scanCell.getLevel() == cell.getLevel() && scanCell.isLeaf()) {
visitLeaf(scanCell);
@@ -265,7 +263,7 @@ public abstract class AbstractVisitingPr
*/
protected void scan(int scanDetailLevel) throws IOException {
for (;
- thisTerm != null && StringHelper.startsWith(thisTerm, curVNodeTerm);//TODO refactor to use method on curVNode.cell
+ thisTerm != null && curVNode.cell.isWithin(curVNodeTerm, thisTerm);
thisTerm = termsEnum.next()) {
scanCell = grid.getCell(thisTerm.bytes, thisTerm.offset, thisTerm.length, scanCell);
Modified: lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/ContainsPrefixTreeFilter.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/ContainsPrefixTreeFilter.java?rev=1584795&r1=1584794&r2=1584795&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/ContainsPrefixTreeFilter.java (original)
+++ lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/ContainsPrefixTreeFilter.java Fri Apr 4 16:29:20 2014
@@ -83,7 +83,7 @@ public class ContainsPrefixTreeFilter ex
super(context, acceptDocs);
}
- BytesRef termBytes = new BytesRef();
+ BytesRef termBytes = new BytesRef();//no leaf
Cell nextCell;//see getLeafDocs
/** This is the primary algorithm; recursive. Returns null if finds none. */
@@ -130,16 +130,15 @@ public class ContainsPrefixTreeFilter ex
}
private boolean seekExact(Cell cell) throws IOException {
- assert new BytesRef(cell.getTokenBytes()).compareTo(termBytes) > 0;
- termBytes.bytes = cell.getTokenBytes();
- termBytes.length = termBytes.bytes.length;
+ assert cell.getTokenBytesNoLeaf(null).compareTo(termBytes) > 0;
+ cell.getTokenBytesNoLeaf(termBytes);
if (termsEnum == null)
return false;
return termsEnum.seekExact(termBytes);
}
private SmallDocSet getDocs(Cell cell, Bits acceptContains) throws IOException {
- assert new BytesRef(cell.getTokenBytes()).equals(termBytes);
+ assert cell.getTokenBytesNoLeaf(null).equals(termBytes);
return collectDocs(acceptContains);
}
@@ -147,7 +146,7 @@ public class ContainsPrefixTreeFilter ex
private Cell lastLeaf = null;//just for assertion
private SmallDocSet getLeafDocs(Cell leafCell, Bits acceptContains) throws IOException {
- assert new BytesRef(leafCell.getTokenBytes()).equals(termBytes);
+ assert leafCell.getTokenBytesNoLeaf(null).equals(termBytes);
assert ! leafCell.equals(lastLeaf);//don't call for same leaf again
lastLeaf = leafCell;
Modified: lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/PointPrefixTreeFieldCacheProvider.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/PointPrefixTreeFieldCacheProvider.java?rev=1584795&r1=1584794&r2=1584795&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/PointPrefixTreeFieldCacheProvider.java (original)
+++ lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/PointPrefixTreeFieldCacheProvider.java Fri Apr 4 16:29:20 2014
@@ -46,7 +46,7 @@ public class PointPrefixTreeFieldCachePr
protected Point readShape(BytesRef term) {
scanCell = grid.getCell(term.bytes, term.offset, term.length, scanCell);
if (scanCell.getLevel() == grid.getMaxLevels() && !scanCell.isLeaf())
- return scanCell.getCenter();
+ return scanCell.getShape().getCenter();
return null;
}
}
Modified: lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/PrefixTreeStrategy.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/PrefixTreeStrategy.java?rev=1584795&r1=1584794&r2=1584795&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/PrefixTreeStrategy.java (original)
+++ lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/PrefixTreeStrategy.java Fri Apr 4 16:29:20 2014
@@ -19,8 +19,6 @@ package org.apache.lucene.spatial.prefix
import com.spatial4j.core.shape.Point;
import com.spatial4j.core.shape.Shape;
-import org.apache.lucene.analysis.TokenStream;
-import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
import org.apache.lucene.document.Field;
import org.apache.lucene.document.FieldType;
import org.apache.lucene.index.FieldInfo;
@@ -32,7 +30,6 @@ import org.apache.lucene.spatial.prefix.
import org.apache.lucene.spatial.query.SpatialArgs;
import org.apache.lucene.spatial.util.ShapeFieldCacheDistanceValueSource;
-import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
@@ -126,13 +123,12 @@ public abstract class PrefixTreeStrategy
public Field[] createIndexableFields(Shape shape, double distErr) {
int detailLevel = grid.getLevelForDistance(distErr);
+ // note: maybe CellTokenStream should do this line, but it doesn't matter and it would create extra
+ // coupling
List<Cell> cells = grid.getCells(shape, detailLevel, true, simplifyIndexedCells);//intermediates cells
- //TODO is CellTokenStream supposed to be re-used somehow? see Uwe's comments:
- // http://code.google.com/p/lucene-spatial-playground/issues/detail?id=4
-
Field field = new Field(getFieldName(),
- new CellTokenStream(cells.iterator()), FIELD_TYPE);
+ new CellTokenStream().setCells(cells.iterator()), FIELD_TYPE);
return new Field[]{field};
}
@@ -147,41 +143,6 @@ public abstract class PrefixTreeStrategy
FIELD_TYPE.freeze();
}
- /** Outputs the tokenString of a cell, and if its a leaf, outputs it again with the leaf byte. */
- final static class CellTokenStream extends TokenStream {
-
- private final CharTermAttribute termAtt = addAttribute(CharTermAttribute.class);
-
- private Iterator<Cell> iter = null;
-
- public CellTokenStream(Iterator<Cell> tokens) {
- this.iter = tokens;
- }
-
- CharSequence nextTokenStringNeedingLeaf = null;
-
- @Override
- public boolean incrementToken() {
- clearAttributes();
- if (nextTokenStringNeedingLeaf != null) {
- termAtt.append(nextTokenStringNeedingLeaf);
- termAtt.append((char) Cell.LEAF_BYTE);
- nextTokenStringNeedingLeaf = null;
- return true;
- }
- if (iter.hasNext()) {
- Cell cell = iter.next();
- CharSequence token = cell.getTokenString();
- termAtt.append(token);
- if (cell.isLeaf())
- nextTokenStringNeedingLeaf = token;
- return true;
- }
- return false;
- }
-
- }
-
@Override
public ValueSource makeDistanceValueSource(Point queryPoint, double multiplier) {
PointPrefixTreeFieldCacheProvider p = provider.get( getFieldName() );
Modified: lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/TermQueryPrefixTreeStrategy.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/TermQueryPrefixTreeStrategy.java?rev=1584795&r1=1584794&r2=1584795&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/TermQueryPrefixTreeStrategy.java (original)
+++ lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/TermQueryPrefixTreeStrategy.java Fri Apr 4 16:29:20 2014
@@ -61,7 +61,7 @@ public class TermQueryPrefixTreeStrategy
BytesRef[] terms = new BytesRef[cells.size()];
int i = 0;
for (Cell cell : cells) {
- terms[i++] = new BytesRef(cell.getTokenString());//TODO use cell.getTokenBytes()
+ terms[i++] = cell.getTokenBytesNoLeaf(null);
}
return new TermsFilter(getFieldName(), terms);
}
Modified: lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/Cell.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/Cell.java?rev=1584795&r1=1584794&r2=1584795&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/Cell.java (original)
+++ lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/Cell.java Fri Apr 4 16:29:20 2014
@@ -20,6 +20,8 @@ package org.apache.lucene.spatial.prefix
import com.spatial4j.core.shape.Point;
import com.spatial4j.core.shape.Shape;
import com.spatial4j.core.shape.SpatialRelation;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.StringHelper;
import java.util.ArrayList;
import java.util.Collection;
@@ -27,74 +29,45 @@ import java.util.Collections;
import java.util.List;
/**
- * Represents a grid cell. These are not necessarily thread-safe, although new
- * Cell("") (world cell) must be.
+ * Represents a grid cell. These are not necessarily thread-safe, although calling {@link #getShape()} will
+ * sufficiently prepare it to be so, if needed.
*
* @lucene.experimental
*/
-public abstract class Cell implements Comparable<Cell> {
- public static final byte LEAF_BYTE = '+';//NOTE: must sort before letters & numbers
+public abstract class Cell {
- /*
- Holds a byte[] and/or String representation of the cell. Both are lazy constructed from the other.
- Neither contains the trailing leaf byte.
- */
+ private static final byte LEAF_BYTE = '+';//NOTE: must sort before letters & numbers
+
+ //Arguably we could simply use a BytesRef, using an extra Object.
private byte[] bytes;
private int b_off;
private int b_len;
- private String token;//this is the only part of equality
-
/**
* When set via getSubCells(filter), it is the relationship between this cell
- * and the given shape filter.
+ * and the given shape filter. Doesn't participate in shape equality.
*/
protected SpatialRelation shapeRel;
- /**
- * Always false for points. Otherwise, indicate no further sub-cells are going
- * to be provided because shapeRel is WITHIN or maxLevels or a detailLevel is
- * hit.
- */
- protected boolean leaf;
-
- protected Cell(String token) {
- this.token = token;
- if (token.length() > 0 && token.charAt(token.length() - 1) == (char) LEAF_BYTE) {
- this.token = token.substring(0, token.length() - 1);
- setLeaf();
- }
-
- if (getLevel() == 0)
- getShape();//ensure any lazy instantiation completes to make this threadsafe
- }
-
+ /** Warning: Refers to the same bytes (no copy). If {@link #setLeaf()} is subsequently called then it
+ * may modify bytes. */
protected Cell(byte[] bytes, int off, int len) {
this.bytes = bytes;
this.b_off = off;
this.b_len = len;
- b_fixLeaf();
}
+ /** Warning: Refers to the same bytes (no copy). If {@link #setLeaf()} is subsequently called then it
+ * may modify bytes. */
public void reset(byte[] bytes, int off, int len) {
assert getLevel() != 0;
- token = null;
shapeRel = null;
this.bytes = bytes;
this.b_off = off;
this.b_len = len;
- b_fixLeaf();
}
- private void b_fixLeaf() {
- //note that non-point shapes always have the maxLevels cell set with setLeaf
- if (bytes[b_off + b_len - 1] == LEAF_BYTE) {
- b_len--;
- setLeaf();
- } else {
- leaf = false;
- }
- }
+ protected abstract SpatialPrefixTree getGrid();
public SpatialRelation getShapeRel() {
return shapeRel;
@@ -105,47 +78,68 @@ public abstract class Cell implements Co
* further cells with this prefix for the shape (always true at maxLevels).
*/
public boolean isLeaf() {
- return leaf;
+ return (b_len > 0 && bytes[b_off + b_len - 1] == LEAF_BYTE);
}
- /** Note: not supported at level 0. */
+ /** Modifies the bytes to reflect that this is a leaf. Warning: never invoke from a cell
+ * initialized to reference the same bytes from termsEnum, which should be treated as immutable.
+ * Note: not supported at level 0. */
public void setLeaf() {
assert getLevel() != 0;
- leaf = true;
+ if (isLeaf())
+ return;
+ //if isn't big enough, we have to copy
+ if (bytes.length < b_off + b_len) {
+ //hopefully this copying doesn't happen too much (DWS: I checked and it doesn't seem to happen)
+ byte[] copy = new byte[b_len + 1];
+ System.arraycopy(bytes, b_off, copy, 0, b_len);
+ copy[b_len++] = LEAF_BYTE;
+ bytes = copy;
+ b_off = 0;
+ } else {
+ bytes[b_off + b_len++] = LEAF_BYTE;
+ }
}
/**
- * Note: doesn't contain a trailing leaf byte.
+ * Returns the bytes for this cell.
+ * The result param is used to save object allocation, though it's bytes aren't used.
+ * @param result where the result goes, or null to create new
*/
- public String getTokenString() {
- if (token == null) {
- token = new String(bytes, b_off, b_len, SpatialPrefixTree.UTF8);
- }
- return token;
+ public BytesRef getTokenBytes(BytesRef result) {
+ if (result == null)
+ result = new BytesRef();
+ result.bytes = bytes;
+ result.offset = b_off;
+ result.length = b_len;
+ return result;
}
/**
- * Note: doesn't contain a trailing leaf byte.
+ * Returns the bytes for this cell, without leaf set. The bytes should sort before any
+ * cells that have the leaf set for the spatial location.
+ * The result param is used to save object allocation, though it's bytes aren't used.
+ * @param result where the result goes, or null to create new
*/
- public byte[] getTokenBytes() {
- if (bytes != null) {
- if (b_off != 0 || b_len != bytes.length) {
- throw new IllegalStateException("Not supported if byte[] needs to be recreated.");
- }
- } else {
- bytes = token.getBytes(SpatialPrefixTree.UTF8);
- b_off = 0;
- b_len = bytes.length;
- }
- return bytes;
+ public BytesRef getTokenBytesNoLeaf(BytesRef result) {
+ result = getTokenBytes(result);
+ if (isLeaf())
+ result.length--;
+ return result;
}
+ /** Level 0 is the world (and has no parent), from then on a higher level means a smaller
+ * cell than the level before it.
+ */
public int getLevel() {
- return token != null ? token.length() : b_len;
+ return isLeaf() ? b_len - 1 : b_len;
}
- //TODO add getParent() and update some algorithms to use this?
- //public Cell getParent();
+ /** Gets the parent cell that contains this one. Don't call on the world cell. */
+ public Cell getParent() {
+ assert getLevel() > 0;
+ return getGrid().getCell(bytes, b_off, b_len - (isLeaf() ? 2 : 1));
+ }
/**
* Like {@link #getSubCells()} but with the results filtered by a shape. If
@@ -196,8 +190,6 @@ public abstract class Cell implements Co
*/
public abstract Cell getSubCell(Point p);
- //TODO Cell getSubCell(byte b)
-
/**
* Gets the cells at the next grid cell level that cover this cell.
* Precondition: Never called when getLevel() == maxLevel.
@@ -211,30 +203,45 @@ public abstract class Cell implements Co
*/
public abstract int getSubCellsSize();
+ /** Gets the shape for this cell; typically a Rectangle. This method also serves to trigger any lazy
+ * loading needed to make the cell instance thread-safe.
+ */
public abstract Shape getShape();
+ /** TODO remove once no longer used. */
public Point getCenter() {
return getShape().getCenter();
}
@Override
- public int compareTo(Cell o) {
- return getTokenString().compareTo(o.getTokenString());
- }
-
- @Override
public boolean equals(Object obj) {
- return !(obj == null || !(obj instanceof Cell)) && getTokenString().equals(((Cell) obj).getTokenString());
+ //this method isn't "normally" called; just in asserts/tests
+ if (obj instanceof Cell) {
+ Cell cell = (Cell) obj;
+ return getTokenBytes(null).equals(cell.getTokenBytes(null));
+ } else {
+ return false;
+ }
}
@Override
public int hashCode() {
- return getTokenString().hashCode();
+ return getTokenBytesNoLeaf(null).hashCode();
}
@Override
public String toString() {
- return getTokenString() + (isLeaf() ? (char) LEAF_BYTE : "");
+ //this method isn't "normally" called; just in asserts/tests
+ return getTokenBytes(null).utf8ToString();
}
+ /**
+ * Returns if the target term is within/underneath this cell; not necessarily a direct descendant.
+ * @param bytesNoLeaf must be getTokenBytesNoLeaf
+ * @param term the term
+ */
+ public boolean isWithin(BytesRef bytesNoLeaf, BytesRef term) {
+ assert bytesNoLeaf.equals(getTokenBytesNoLeaf(null));
+ return StringHelper.startsWith(term, bytesNoLeaf);
+ }
}
Modified: lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/GeohashPrefixTree.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/GeohashPrefixTree.java?rev=1584795&r1=1584794&r2=1584795&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/GeohashPrefixTree.java (original)
+++ lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/GeohashPrefixTree.java Fri Apr 4 16:29:20 2014
@@ -84,18 +84,29 @@ public class GeohashPrefixTree extends S
}
@Override
- public Cell getCell(String token) {
- return new GhCell(token);
- }
-
- @Override
public Cell getCell(byte[] bytes, int offset, int len) {
return new GhCell(bytes, offset, len);
}
+ private static byte[] stringToBytesPlus1(String token) {
+ //copy ASCII token to byte array with one extra spot for eventual LEAF_BYTE if needed
+ byte[] bytes = new byte[token.length() + 1];
+ for (int i = 0; i < token.length(); i++) {
+ bytes[i] = (byte) token.charAt(i);
+ }
+ return bytes;
+ }
+
class GhCell extends Cell {
- GhCell(String token) {
- super(token);
+
+ private Shape shape;//cache
+ private String geohash;//cache; never has leaf byte, simply a geohash
+
+ GhCell(String geohash) {
+ super(stringToBytesPlus1(geohash), 0, geohash.length());
+ this.geohash = geohash;
+ if (isLeaf())
+ this.geohash = geohash.substring(0, geohash.length() - 1);
}
GhCell(byte[] bytes, int off, int len) {
@@ -103,8 +114,12 @@ public class GeohashPrefixTree extends S
}
@Override
+ protected SpatialPrefixTree getGrid() { return GeohashPrefixTree.this; }
+
+ @Override
public void reset(byte[] bytes, int off, int len) {
super.reset(bytes, off, len);
+ geohash = null;
shape = null;
}
@@ -125,26 +140,26 @@ public class GeohashPrefixTree extends S
@Override
public Cell getSubCell(Point p) {
- return GeohashPrefixTree.this.getCell(p, getLevel() + 1);//not performant!
+ return getGrid().getCell(p, getLevel() + 1);//not performant!
}
- private Shape shape;//cache
-
@Override
public Shape getShape() {
if (shape == null) {
- shape = GeohashUtils.decodeBoundary(getGeohash(), ctx);
+ shape = GeohashUtils.decodeBoundary(getGeohash(), getGrid().getSpatialContext());
}
return shape;
}
@Override
public Point getCenter() {
- return GeohashUtils.decode(getGeohash(), ctx);
+ return GeohashUtils.decode(getGeohash(), getGrid().getSpatialContext());
}
private String getGeohash() {
- return getTokenString();
+ if (geohash == null)
+ geohash = getTokenBytesNoLeaf(null).utf8ToString();
+ return geohash;
}
}//class GhCell
Modified: lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/QuadPrefixTree.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/QuadPrefixTree.java?rev=1584795&r1=1584794&r2=1584795&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/QuadPrefixTree.java (original)
+++ lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/QuadPrefixTree.java Fri Apr 4 16:29:20 2014
@@ -22,6 +22,7 @@ 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;
import java.io.PrintStream;
import java.text.NumberFormat;
@@ -142,16 +143,11 @@ public class QuadPrefixTree extends Spat
@Override
public Cell getCell(Point p, int level) {
List<Cell> cells = new ArrayList<>(1);
- build(xmid, ymid, 0, cells, new StringBuilder(), ctx.makePoint(p.getX(),p.getY()), level);
+ 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
}
@Override
- public Cell getCell(String token) {
- return new QuadCell(token);
- }
-
- @Override
public Cell getCell(byte[] bytes, int offset, int len) {
return new QuadCell(bytes, offset, len);
}
@@ -161,10 +157,10 @@ public class QuadPrefixTree extends Spat
double y,
int level,
List<Cell> matches,
- StringBuilder str,
+ BytesRef str,
Shape shape,
int maxLevel) {
- assert str.length() == level;
+ assert str.length == level;
double w = levelW[level] / 2;
double h = levelH[level] / 2;
@@ -187,50 +183,50 @@ public class QuadPrefixTree extends Spat
double cy,
int level,
List<Cell> matches,
- StringBuilder str,
+ BytesRef str,
Shape shape,
int maxLevel) {
- assert str.length() == level;
+ assert str.length == level;
+ assert str.offset == 0;
double w = levelW[level] / 2;
double h = levelH[level] / 2;
- int strlen = str.length();
+ 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.append(c);
+ str.bytes[str.length++] = (byte)c;//append
//str.append(SpatialPrefixGrid.COVER);
- matches.add(new QuadCell(str.toString(),v.transpose()));
+ matches.add(new QuadCell(BytesRef.deepCopyOf(str), v.transpose()));
} else if (SpatialRelation.DISJOINT == v) {
// nothing
} else { // SpatialRelation.WITHIN, SpatialRelation.INTERSECTS
- str.append(c);
+ str.bytes[str.length++] = (byte)c;//append
int nextLevel = level+1;
if (nextLevel >= maxLevel) {
//str.append(SpatialPrefixGrid.INTERSECTS);
- matches.add(new QuadCell(str.toString(),v.transpose()));
+ matches.add(new QuadCell(BytesRef.deepCopyOf(str), v.transpose()));
} else {
build(cx, cy, nextLevel, matches, str, shape, maxLevel);
}
}
- str.setLength(strlen);
+ str.length = strlen;
}
- class QuadCell extends Cell {
+ class QuadCell extends Cell{
- public QuadCell(String token) {
- super(token);
+ QuadCell(byte[] bytes, int off, int len) {
+ super(bytes, off, len);
}
- public QuadCell(String token, SpatialRelation shapeRel) {
- super(token);
+ QuadCell(BytesRef str, SpatialRelation shapeRel) {
+ this(str.bytes, str.offset, str.length);
this.shapeRel = shapeRel;
}
- QuadCell(byte[] bytes, int off, int len) {
- super(bytes, off, len);
- }
+ @Override
+ protected SpatialPrefixTree getGrid() { return QuadPrefixTree.this; }
@Override
public void reset(byte[] bytes, int off, int len) {
@@ -240,14 +236,26 @@ public class QuadPrefixTree extends Spat
@Override
public Collection<Cell> getSubCells() {
+ BytesRef source = getTokenBytesNoLeaf(null);
+ BytesRef target = new BytesRef();
+
List<Cell> cells = new ArrayList<>(4);
- cells.add(new QuadCell(getTokenString()+"A"));
- cells.add(new QuadCell(getTokenString()+"B"));
- cells.add(new QuadCell(getTokenString()+"C"));
- cells.add(new QuadCell(getTokenString()+"D"));
+ cells.add(new QuadCell(concat(source, (byte)'A', target), null));
+ cells.add(new QuadCell(concat(source, (byte)'B', target), null));
+ cells.add(new QuadCell(concat(source, (byte)'C', target), null));
+ cells.add(new QuadCell(concat(source, (byte)'D', target), null));
return cells;
}
+ private BytesRef concat(BytesRef source, byte b, BytesRef target) {
+ assert target.offset == 0;
+ target.bytes = new byte[source.length + 2];//+2 for new char + potential leaf
+ target.length = 0;
+ target.copyBytes(source);
+ target.bytes[target.length++] = b;
+ return target;
+ }
+
@Override
public int getSubCellsSize() {
return 4;
@@ -268,27 +276,30 @@ public class QuadPrefixTree extends Spat
}
private Rectangle makeShape() {
- String token = getTokenString();
+ BytesRef token = getTokenBytesNoLeaf(null);
double xmin = QuadPrefixTree.this.xmin;
double ymin = QuadPrefixTree.this.ymin;
- for (int i = 0; i < token.length(); i++) {
- char c = token.charAt(i);
- if ('A' == c || 'a' == c) {
- ymin += levelH[i];
- } else if ('B' == c || 'b' == c) {
- xmin += levelW[i];
- ymin += levelH[i];
- } else if ('C' == c || 'c' == c) {
- // nothing really
- }
- else if('D' == c || 'd' == c) {
- xmin += levelW[i];
- } else {
- throw new RuntimeException("unexpected char: " + c);
+ 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();
+ int len = token.length;
double width, height;
if (len > 0) {
width = levelW[len-1];
Modified: lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTree.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTree.java?rev=1584795&r1=1584794&r2=1584795&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTree.java (original)
+++ lucene/dev/branches/branch_4x/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTree.java Fri Apr 4 16:29:20 2014
@@ -21,10 +21,12 @@ import com.spatial4j.core.context.Spatia
import com.spatial4j.core.shape.Point;
import com.spatial4j.core.shape.Rectangle;
import com.spatial4j.core.shape.Shape;
+import org.apache.lucene.util.BytesRef;
import java.nio.charset.Charset;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
+import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
@@ -103,14 +105,14 @@ public abstract class SpatialPrefixTree
private transient Cell worldCell;//cached
/**
- * Returns the level 0 cell which encompasses all spatial data. Equivalent to {@link #getCell(String)} with "".
- * This cell is threadsafe, just like a spatial prefix grid is, although cells aren't
- * generally threadsafe.
- * TODO rename to getTopCell or is this fine?
+ * Returns the level 0 cell which encompasses all spatial data. Equivalent to {@link #getCell(byte[], int, int)} with
+ * no bytes. This cell is thread-safe, just like a spatial prefix grid is, although cells aren't
+ * generally thread-safe.
*/
- public Cell getWorldCell() {
+ public Cell getWorldCell() {//another possible name: getTopCell
if (worldCell == null) {
- worldCell = getCell("");
+ worldCell = getCell(BytesRef.EMPTY_BYTES, 0, 0);
+ worldCell.getShape();//lazy load; make thread-safe
}
return worldCell;
}
@@ -119,8 +121,6 @@ public abstract class SpatialPrefixTree
* The cell for the specified token. The empty string should be equal to {@link #getWorldCell()}.
* Precondition: Never called when token length > maxLevel.
*/
- public abstract Cell getCell(String token);
-
public abstract Cell getCell(byte[] bytes, int offset, int len);
public final Cell getCell(byte[] bytes, int offset, int len, Cell target) {
@@ -215,40 +215,23 @@ public abstract class SpatialPrefixTree
* A Point-optimized implementation of
* {@link #getCells(com.spatial4j.core.shape.Shape, int, boolean, boolean)}. That
* method in facts calls this for points.
- * <p/>
- * This implementation depends on {@link #getCell(String)} being fast, as its
- * called repeatedly when incPlarents is true.
*/
public List<Cell> getCells(Point p, int detailLevel, boolean inclParents) {
Cell cell = getCell(p, detailLevel);
- if (!inclParents) {
+ assert !cell.isLeaf();
+ if (!inclParents || detailLevel == 1) {
return Collections.singletonList(cell);
}
- String endToken = cell.getTokenString();
- assert endToken.length() == detailLevel;
- List<Cell> cells = new ArrayList<>(detailLevel);
- for (int i = 1; i < detailLevel; i++) {
- cells.add(getCell(endToken.substring(0, i)));//TODO refactor: add a cell.getParent()
+ //fill in reverse order to be sorted
+ Cell[] cells = new Cell[detailLevel];
+ for (int i = detailLevel-1; true; i--) {
+ cells[i] = cell;
+ if (i == 0)
+ break;
+ cell = cell.getParent();
}
- cells.add(cell);
- return cells;
+ return Arrays.asList(cells);
}
- /**
- * Will add the trailing leaf byte for leaves. This isn't particularly efficient.
- * @deprecated TODO remove; not used and not interesting, don't need collection in & out
- */
- public static List<String> cellsToTokenStrings(Collection<Cell> cells) {
- List<String> tokens = new ArrayList<>((cells.size()));
- for (Cell cell : cells) {
- final String token = cell.getTokenString();
- if (cell.isLeaf()) {
- tokens.add(token + (char) Cell.LEAF_BYTE);
- } else {
- tokens.add(token);
- }
- }
- return tokens;
- }
}
Modified: lucene/dev/branches/branch_4x/lucene/spatial/src/test/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTreeTest.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/spatial/src/test/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTreeTest.java?rev=1584795&r1=1584794&r2=1584795&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/spatial/src/test/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTreeTest.java (original)
+++ lucene/dev/branches/branch_4x/lucene/spatial/src/test/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTreeTest.java Fri Apr 4 16:29:20 2014
@@ -35,6 +35,9 @@ import org.apache.lucene.spatial.query.S
import org.junit.Before;
import org.junit.Test;
+import java.util.ArrayList;
+import java.util.List;
+
public class SpatialPrefixTreeTest extends SpatialTestCase {
//TODO plug in others and test them
@@ -56,9 +59,10 @@ public class SpatialPrefixTreeTest exten
Cell c = trie.getWorldCell();
assertEquals(0, c.getLevel());
assertEquals(ctx.getWorldBounds(), c.getShape());
- while(c.getLevel() < trie.getMaxLevels()) {
+ while (c.getLevel() < trie.getMaxLevels()) {
prevC = c;
- c = c.getSubCells().iterator().next();//TODO random which one?
+ List<Cell> subCells = new ArrayList<>(c.getSubCells());
+ c = subCells.get(random().nextInt(subCells.size()-1));
assertEquals(prevC.getLevel()+1,c.getLevel());
Rectangle prevNShape = (Rectangle) prevC.getShape();