lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From dsmi...@apache.org
Subject svn commit: r1588398 - 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...
Date Fri, 18 Apr 2014 02:07:05 GMT
Author: dsmiley
Date: Fri Apr 18 02:07:04 2014
New Revision: 1588398

URL: http://svn.apache.org/r1588398
Log:
LUCENE-5565: reverting spatial API change; leave in trunk for now

Removed:
    lucene/dev/branches/branch_4x/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   (contents, props changed)
    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=1588398&r1=1588397&r2=1588398&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/CHANGES.txt (original)
+++ lucene/dev/branches/branch_4x/lucene/CHANGES.txt Fri Apr 18 02:07:04 2014
@@ -166,8 +166,6 @@ API Changes
 
 * LUCENE-5543: Remove/deprecate Directory.fileExists (Mike McCandless)
 
-* LUCENE-5565: Refactor SpatialPrefixTree/Cell to not use Strings. (David Smiley)
-
 * LUCENE-5573: Move docvalues constants and helper methods to o.a.l.index.DocValues.
   (Dawid Weiss, Robert Muir)
 

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=1588398&r1=1588397&r2=1588398&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 18 02:07:04 2014
@@ -25,6 +25,7 @@ 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;
@@ -116,7 +117,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, without leaf
+    private BytesRef curVNodeTerm = new BytesRef();//curVNode.cell's term.
     private Cell scanCell;
 
     private BytesRef thisTerm;//the result of termsEnum.term()
@@ -170,7 +171,8 @@ public abstract class AbstractVisitingPr
         }
 
         //Seek to curVNode's cell (or skip if termsEnum has moved beyond)
-        curVNode.cell.getTokenBytesNoLeaf(curVNodeTerm);
+        curVNodeTerm.bytes = curVNode.cell.getTokenBytes();
+        curVNodeTerm.length = curVNodeTerm.bytes.length;
         int compare = termsEnum.getComparator().compare(thisTerm, curVNodeTerm);
         if (compare > 0) {
           // leap frog (termsEnum is beyond where we would otherwise seek)
@@ -213,7 +215,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 curVNode.cell.isWithin(curVNodeTerm, thisTerm);
+        assert StringHelper.startsWith(thisTerm, curVNodeTerm);//TODO refactor to use method
on curVNode.cell
         scanCell = grid.getCell(thisTerm.bytes, thisTerm.offset, thisTerm.length, scanCell);
         if (scanCell.getLevel() == cell.getLevel() && scanCell.isLeaf()) {
           visitLeaf(scanCell);
@@ -263,7 +265,7 @@ public abstract class AbstractVisitingPr
      */
     protected void scan(int scanDetailLevel) throws IOException {
       for (;
-           thisTerm != null && curVNode.cell.isWithin(curVNodeTerm, thisTerm);
+           thisTerm != null && StringHelper.startsWith(thisTerm, curVNodeTerm);//TODO
refactor to use method on curVNode.cell
            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=1588398&r1=1588397&r2=1588398&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 18 02:07:04 2014
@@ -83,7 +83,7 @@ public class ContainsPrefixTreeFilter ex
       super(context, acceptDocs);
     }
 
-    BytesRef termBytes = new BytesRef();//no leaf
+    BytesRef termBytes = new BytesRef();
     Cell nextCell;//see getLeafDocs
 
     /** This is the primary algorithm; recursive.  Returns null if finds none. */
@@ -130,15 +130,16 @@ public class ContainsPrefixTreeFilter ex
     }
 
     private boolean seekExact(Cell cell) throws IOException {
-      assert cell.getTokenBytesNoLeaf(null).compareTo(termBytes) > 0;
-      cell.getTokenBytesNoLeaf(termBytes);
+      assert new BytesRef(cell.getTokenBytes()).compareTo(termBytes) > 0;
+      termBytes.bytes = cell.getTokenBytes();
+      termBytes.length = termBytes.bytes.length;
       if (termsEnum == null)
         return false;
       return termsEnum.seekExact(termBytes);
     }
 
     private SmallDocSet getDocs(Cell cell, Bits acceptContains) throws IOException {
-      assert cell.getTokenBytesNoLeaf(null).equals(termBytes);
+      assert new BytesRef(cell.getTokenBytes()).equals(termBytes);
 
       return collectDocs(acceptContains);
     }
@@ -146,7 +147,7 @@ public class ContainsPrefixTreeFilter ex
     private Cell lastLeaf = null;//just for assertion
 
     private SmallDocSet getLeafDocs(Cell leafCell, Bits acceptContains) throws IOException
{
-      assert leafCell.getTokenBytesNoLeaf(null).equals(termBytes);
+      assert new BytesRef(leafCell.getTokenBytes()).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=1588398&r1=1588397&r2=1588398&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 18 02:07:04 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.getShape().getCenter();
+      return scanCell.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=1588398&r1=1588397&r2=1588398&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 18 02:07:04 2014
@@ -19,6 +19,8 @@ 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;
@@ -30,6 +32,7 @@ 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;
@@ -123,12 +126,13 @@ 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().setCells(cells.iterator()), FIELD_TYPE);
+        new CellTokenStream(cells.iterator()), FIELD_TYPE);
     return new Field[]{field};
   }
 
@@ -143,6 +147,41 @@ 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=1588398&r1=1588397&r2=1588398&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 18 02:07:04 2014
@@ -61,7 +61,7 @@ public class TermQueryPrefixTreeStrategy
     BytesRef[] terms = new BytesRef[cells.size()];
     int i = 0;
     for (Cell cell : cells) {
-      terms[i++] = cell.getTokenBytesNoLeaf(null);
+      terms[i++] = new BytesRef(cell.getTokenString());//TODO use cell.getTokenBytes()
     }
     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=1588398&r1=1588397&r2=1588398&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 18 02:07:04 2014
@@ -20,8 +20,6 @@ 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;
@@ -29,45 +27,74 @@ import java.util.Collections;
 import java.util.List;
 
 /**
- * Represents a grid cell. These are not necessarily thread-safe, although calling {@link
#getShape()} will
- * sufficiently prepare it to be so, if needed.
+ * Represents a grid cell. These are not necessarily thread-safe, although new
+ * Cell("") (world cell) must be.
  *
  * @lucene.experimental
  */
-public abstract class Cell {
+public abstract class Cell implements Comparable<Cell> {
+  public static final byte LEAF_BYTE = '+';//NOTE: must sort before letters & numbers
 
-  private static final byte LEAF_BYTE = '+';//NOTE: must sort before letters & numbers
-
-  //Arguably we could simply use a BytesRef, using an extra Object.
+  /*
+  Holds a byte[] and/or String representation of the cell. Both are lazy constructed from
the other.
+  Neither contains the trailing leaf byte.
+   */
   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. Doesn't participate in shape equality.
+   * and the given shape filter.
    */
   protected SpatialRelation shapeRel;
 
-  /** Warning: Refers to the same bytes (no copy). If {@link #setLeaf()} is subsequently
called then it
-   * may modify bytes. */
+  /**
+   * 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
+  }
+
   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();
   }
 
-  protected abstract SpatialPrefixTree getGrid();
+  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;
+    }
+  }
 
   public SpatialRelation getShapeRel() {
     return shapeRel;
@@ -78,68 +105,47 @@ public abstract class Cell {
    * further cells with this prefix for the shape (always true at maxLevels).
    */
   public boolean isLeaf() {
-    return (b_len > 0 && bytes[b_off + b_len - 1] == LEAF_BYTE);
+    return leaf;
   }
 
-  /** 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. */
+  /** Note: not supported at level 0. */
   public void setLeaf() {
     assert getLevel() != 0;
-    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;
-    }
+    leaf = true;
   }
 
   /**
-   * 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
+   * Note: doesn't contain a trailing leaf byte.
    */
-  public BytesRef getTokenBytes(BytesRef result) {
-    if (result == null)
-      result = new BytesRef();
-    result.bytes = bytes;
-    result.offset = b_off;
-    result.length = b_len;
-    return result;
+  public String getTokenString() {
+    if (token == null) {
+      token = new String(bytes, b_off, b_len, SpatialPrefixTree.UTF8);
+    }
+    return token;
   }
 
   /**
-   * 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
+   * Note: doesn't contain a trailing leaf byte.
    */
-  public BytesRef getTokenBytesNoLeaf(BytesRef result) {
-    result = getTokenBytes(result);
-    if (isLeaf())
-      result.length--;
-    return result;
+  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;
   }
 
-  /** 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 isLeaf() ? b_len - 1 : b_len;
+    return token != null ? token.length() : b_len;
   }
 
-  /** 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));
-  }
+  //TODO add getParent() and update some algorithms to use this?
+  //public Cell getParent();
 
   /**
    * Like {@link #getSubCells()} but with the results filtered by a shape. If
@@ -190,6 +196,8 @@ public abstract class Cell {
    */
   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.
@@ -203,45 +211,30 @@ public abstract class Cell {
    */
   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) {
-    //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;
-    }
+    return !(obj == null || !(obj instanceof Cell)) && getTokenString().equals(((Cell)
obj).getTokenString());
   }
 
   @Override
   public int hashCode() {
-    return getTokenBytesNoLeaf(null).hashCode();
+    return getTokenString().hashCode();
   }
 
   @Override
   public String toString() {
-    //this method isn't "normally" called; just in asserts/tests
-    return getTokenBytes(null).utf8ToString();
+    return getTokenString() + (isLeaf() ? (char) LEAF_BYTE : "");
   }
 
-  /**
-   * 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=1588398&r1=1588397&r2=1588398&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 18 02:07:04 2014
@@ -84,29 +84,18 @@ public class GeohashPrefixTree extends S
   }
 
   @Override
-  public Cell getCell(byte[] bytes, int offset, int len) {
-    return new GhCell(bytes, offset, len);
+  public Cell getCell(String token) {
+    return new GhCell(token);
   }
 
-  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;
+  @Override
+  public Cell getCell(byte[] bytes, int offset, int len) {
+    return new GhCell(bytes, offset, len);
   }
 
   class GhCell extends Cell {
-
-    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(String token) {
+      super(token);
     }
 
     GhCell(byte[] bytes, int off, int len) {
@@ -114,12 +103,8 @@ 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;
     }
 
@@ -140,26 +125,26 @@ public class GeohashPrefixTree extends S
 
     @Override
     public Cell getSubCell(Point p) {
-      return getGrid().getCell(p, getLevel() + 1);//not performant!
+      return GeohashPrefixTree.this.getCell(p, getLevel() + 1);//not performant!
     }
 
+    private Shape shape;//cache
+
     @Override
     public Shape getShape() {
       if (shape == null) {
-        shape = GeohashUtils.decodeBoundary(getGeohash(), getGrid().getSpatialContext());
+        shape = GeohashUtils.decodeBoundary(getGeohash(), ctx);
       }
       return shape;
     }
 
     @Override
     public Point getCenter() {
-      return GeohashUtils.decode(getGeohash(), getGrid().getSpatialContext());
+      return GeohashUtils.decode(getGeohash(), ctx);
     }
 
     private String getGeohash() {
-      if (geohash == null)
-        geohash = getTokenBytesNoLeaf(null).utf8ToString();
-      return geohash;
+      return getTokenString();
     }
 
   }//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=1588398&r1=1588397&r2=1588398&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 18 02:07:04 2014
@@ -22,7 +22,6 @@ 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;
@@ -143,11 +142,16 @@ 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 BytesRef(maxLevels+1), ctx.makePoint(p.getX(),p.getY()),
level);
+    build(xmid, ymid, 0, cells, new StringBuilder(), 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);
   }
@@ -157,10 +161,10 @@ public class QuadPrefixTree extends Spat
       double y,
       int level,
       List<Cell> matches,
-      BytesRef str,
+      StringBuilder str,
       Shape shape,
       int maxLevel) {
-    assert str.length == level;
+    assert str.length() == level;
     double w = levelW[level] / 2;
     double h = levelH[level] / 2;
 
@@ -183,50 +187,50 @@ public class QuadPrefixTree extends Spat
       double cy,
       int level,
       List<Cell> matches,
-      BytesRef str,
+      StringBuilder str,
       Shape shape,
       int maxLevel) {
-    assert str.length == level;
-    assert str.offset == 0;
+    assert str.length() == level;
     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.bytes[str.length++] = (byte)c;//append
+      str.append(c);
       //str.append(SpatialPrefixGrid.COVER);
-      matches.add(new QuadCell(BytesRef.deepCopyOf(str), v.transpose()));
+      matches.add(new QuadCell(str.toString(),v.transpose()));
     } else if (SpatialRelation.DISJOINT == v) {
       // nothing
     } else { // SpatialRelation.WITHIN, SpatialRelation.INTERSECTS
-      str.bytes[str.length++] = (byte)c;//append
+      str.append(c);
 
       int nextLevel = level+1;
       if (nextLevel >= maxLevel) {
         //str.append(SpatialPrefixGrid.INTERSECTS);
-        matches.add(new QuadCell(BytesRef.deepCopyOf(str), v.transpose()));
+        matches.add(new QuadCell(str.toString(),v.transpose()));
       } else {
         build(cx, cy, nextLevel, matches, str, shape, maxLevel);
       }
     }
-    str.length = strlen;
+    str.setLength(strlen);
   }
 
-  class QuadCell extends Cell{
+  class QuadCell extends Cell {
 
-    QuadCell(byte[] bytes, int off, int len) {
-      super(bytes, off, len);
+    public QuadCell(String token) {
+      super(token);
     }
 
-    QuadCell(BytesRef str, SpatialRelation shapeRel) {
-      this(str.bytes, str.offset, str.length);
+    public QuadCell(String token, SpatialRelation shapeRel) {
+      super(token);
       this.shapeRel = shapeRel;
     }
 
-    @Override
-    protected SpatialPrefixTree getGrid() { return QuadPrefixTree.this; }
+    QuadCell(byte[] bytes, int off, int len) {
+      super(bytes, off, len);
+    }
 
     @Override
     public void reset(byte[] bytes, int off, int len) {
@@ -236,26 +240,14 @@ 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(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));
+      cells.add(new QuadCell(getTokenString()+"A"));
+      cells.add(new QuadCell(getTokenString()+"B"));
+      cells.add(new QuadCell(getTokenString()+"C"));
+      cells.add(new QuadCell(getTokenString()+"D"));
       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;
@@ -276,30 +268,27 @@ public class QuadPrefixTree extends Spat
     }
 
     private Rectangle makeShape() {
-      BytesRef token = getTokenBytesNoLeaf(null);
+      String token = getTokenString();
       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);
+      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);
         }
       }
-      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=1588398&r1=1588397&r2=1588398&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 18 02:07:04 2014
@@ -21,12 +21,10 @@ 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;
@@ -105,14 +103,14 @@ public abstract class SpatialPrefixTree 
   private transient Cell worldCell;//cached
 
   /**
-   * 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.
+   * 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?
    */
-  public Cell getWorldCell() {//another possible name: getTopCell
+  public Cell getWorldCell() {
     if (worldCell == null) {
-      worldCell = getCell(BytesRef.EMPTY_BYTES, 0, 0);
-      worldCell.getShape();//lazy load; make thread-safe
+      worldCell = getCell("");
     }
     return worldCell;
   }
@@ -121,6 +119,8 @@ 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,23 +215,40 @@ 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);
-    assert !cell.isLeaf();
-    if (!inclParents || detailLevel == 1) {
+    if (!inclParents) {
       return Collections.singletonList(cell);
     }
 
-    //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();
+    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()
     }
-    return Arrays.asList(cells);
+    cells.add(cell);
+    return 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=1588398&r1=1588397&r2=1588398&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 18 02:07:04 2014
@@ -35,9 +35,6 @@ 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
@@ -59,10 +56,9 @@ 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;
-      List<Cell> subCells = new ArrayList<>(c.getSubCells());
-      c = subCells.get(random().nextInt(subCells.size()-1));
+      c = c.getSubCells().iterator().next();//TODO random which one?
       
       assertEquals(prevC.getLevel()+1,c.getLevel());
       Rectangle prevNShape = (Rectangle) prevC.getShape();



Mime
View raw message