You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by ry...@apache.org on 2012/03/01 08:35:04 UTC
svn commit: r1295444 - in
/lucene/dev/branches/lucene3795_lsp_spatial_module: modules/spatial/lib/
modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/
modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/
modules/spat...
Author: ryan
Date: Thu Mar 1 07:35:03 2012
New Revision: 1295444
URL: http://svn.apache.org/viewvc?rev=1295444&view=rev
Log:
LUCENE-3795: moving prefix/tree stuff into strategy
Added:
lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/
lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/GeohashPrefixTree.java
lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/Node.java
lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/QuadPrefixTree.java
lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/SpatialPrefixTree.java
lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/SpatialPrefixTreeFactory.java
lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/package-info.java
lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/test/org/apache/lucene/spatial/strategy/prefix/tree/
lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/test/org/apache/lucene/spatial/strategy/prefix/tree/SpatialPrefixTreeTest.java
Modified:
lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/lib/spatial4j-0.1.jar
lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/PointPrefixTreeFieldCacheProvider.java
lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/PrefixTreeStrategy.java
lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/RecursivePrefixTreeFilter.java
lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/RecursivePrefixTreeStrategy.java
lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/TermQueryPrefixTreeStrategy.java
lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/test/org/apache/lucene/spatial/strategy/prefix/BaseRecursivePrefixTreeStrategyTestCase.java
lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/test/org/apache/lucene/spatial/strategy/prefix/TestTermQueryPrefixGridStrategy.java
lucene/dev/branches/lucene3795_lsp_spatial_module/solr/core/src/java/org/apache/solr/schema/GeoHashField.java
lucene/dev/branches/lucene3795_lsp_spatial_module/solr/core/src/java/org/apache/solr/search/function/distance/GeohashFunction.java
lucene/dev/branches/lucene3795_lsp_spatial_module/solr/core/src/java/org/apache/solr/search/function/distance/GeohashHaversineFunction.java
lucene/dev/branches/lucene3795_lsp_spatial_module/solr/core/src/test/org/apache/solr/search/function/distance/DistanceFunctionTest.java
lucene/dev/branches/lucene3795_lsp_spatial_module/solr/lib/spatial4j-0.1.jar
Modified: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/lib/spatial4j-0.1.jar
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/lib/spatial4j-0.1.jar?rev=1295444&r1=1295443&r2=1295444&view=diff
==============================================================================
Binary files - no diff available.
Modified: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/PointPrefixTreeFieldCacheProvider.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/PointPrefixTreeFieldCacheProvider.java?rev=1295444&r1=1295443&r2=1295444&view=diff
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/PointPrefixTreeFieldCacheProvider.java (original)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/PointPrefixTreeFieldCacheProvider.java Thu Mar 1 07:35:03 2012
@@ -17,9 +17,10 @@
package org.apache.lucene.spatial.strategy.prefix;
-import com.spatial4j.core.prefix.Node;
-import com.spatial4j.core.prefix.SpatialPrefixTree;
import com.spatial4j.core.shape.Point;
+
+import org.apache.lucene.spatial.strategy.prefix.tree.Node;
+import org.apache.lucene.spatial.strategy.prefix.tree.SpatialPrefixTree;
import org.apache.lucene.spatial.strategy.util.ShapeFieldCacheProvider;
import org.apache.lucene.util.BytesRef;
Modified: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/PrefixTreeStrategy.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/PrefixTreeStrategy.java?rev=1295444&r1=1295443&r2=1295444&view=diff
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/PrefixTreeStrategy.java (original)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/PrefixTreeStrategy.java Thu Mar 1 07:35:03 2012
@@ -25,13 +25,13 @@ import org.apache.lucene.document.Stored
import org.apache.lucene.index.IndexableField;
import org.apache.lucene.queries.function.ValueSource;
import com.spatial4j.core.distance.DistanceCalculator;
-import com.spatial4j.core.prefix.Node;
-import com.spatial4j.core.prefix.SpatialPrefixTree;
import com.spatial4j.core.query.SpatialArgs;
import com.spatial4j.core.shape.Point;
import com.spatial4j.core.shape.Shape;
import org.apache.lucene.spatial.strategy.SimpleSpatialFieldInfo;
import org.apache.lucene.spatial.strategy.SpatialStrategy;
+import org.apache.lucene.spatial.strategy.prefix.tree.Node;
+import org.apache.lucene.spatial.strategy.prefix.tree.SpatialPrefixTree;
import org.apache.lucene.spatial.strategy.util.CachedDistanceValueSource;
import java.io.IOException;
Modified: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/RecursivePrefixTreeFilter.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/RecursivePrefixTreeFilter.java?rev=1295444&r1=1295443&r2=1295444&view=diff
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/RecursivePrefixTreeFilter.java (original)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/RecursivePrefixTreeFilter.java Thu Mar 1 07:35:03 2012
@@ -21,9 +21,10 @@ import org.apache.lucene.index.*;
import org.apache.lucene.search.DocIdSet;
import org.apache.lucene.search.DocIdSetIterator;
import org.apache.lucene.search.Filter;
+import org.apache.lucene.spatial.strategy.prefix.tree.Node;
+import org.apache.lucene.spatial.strategy.prefix.tree.SpatialPrefixTree;
+
import com.spatial4j.core.shape.SpatialRelation;
-import com.spatial4j.core.prefix.Node;
-import com.spatial4j.core.prefix.SpatialPrefixTree;
import com.spatial4j.core.shape.Shape;
import org.apache.lucene.util.Bits;
import org.apache.lucene.util.BytesRef;
Modified: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/RecursivePrefixTreeStrategy.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/RecursivePrefixTreeStrategy.java?rev=1295444&r1=1295443&r2=1295444&view=diff
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/RecursivePrefixTreeStrategy.java (original)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/RecursivePrefixTreeStrategy.java Thu Mar 1 07:35:03 2012
@@ -23,11 +23,11 @@ import org.apache.lucene.search.Query;
import org.apache.lucene.queries.function.ValueSource;
import org.apache.lucene.queries.function.FunctionQuery;
import com.spatial4j.core.exception.UnsupportedSpatialOperation;
-import com.spatial4j.core.prefix.SpatialPrefixTree;
import com.spatial4j.core.query.SpatialArgs;
import com.spatial4j.core.query.SpatialOperation;
import com.spatial4j.core.shape.Shape;
import org.apache.lucene.spatial.strategy.SimpleSpatialFieldInfo;
+import org.apache.lucene.spatial.strategy.prefix.tree.SpatialPrefixTree;
public class RecursivePrefixTreeStrategy extends PrefixTreeStrategy {
Modified: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/TermQueryPrefixTreeStrategy.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/TermQueryPrefixTreeStrategy.java?rev=1295444&r1=1295443&r2=1295444&view=diff
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/TermQueryPrefixTreeStrategy.java (original)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/TermQueryPrefixTreeStrategy.java Thu Mar 1 07:35:03 2012
@@ -20,12 +20,12 @@ package org.apache.lucene.spatial.strate
import org.apache.lucene.index.Term;
import org.apache.lucene.search.*;
import com.spatial4j.core.exception.UnsupportedSpatialOperation;
-import com.spatial4j.core.prefix.Node;
-import com.spatial4j.core.prefix.SpatialPrefixTree;
import com.spatial4j.core.query.SpatialArgs;
import com.spatial4j.core.query.SpatialOperation;
import com.spatial4j.core.shape.Shape;
import org.apache.lucene.spatial.strategy.SimpleSpatialFieldInfo;
+import org.apache.lucene.spatial.strategy.prefix.tree.Node;
+import org.apache.lucene.spatial.strategy.prefix.tree.SpatialPrefixTree;
import java.util.List;
Added: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/GeohashPrefixTree.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/GeohashPrefixTree.java?rev=1295444&view=auto
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/GeohashPrefixTree.java (added)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/GeohashPrefixTree.java Thu Mar 1 07:35:03 2012
@@ -0,0 +1,149 @@
+/*
+ * 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.strategy.prefix.tree;
+
+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.util.GeohashUtils;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+
+
+/**
+ * A SpatialPrefixGrid based on Geohashes. Uses {@link GeohashUtils} to do all the geohash work.
+ */
+public class GeohashPrefixTree extends SpatialPrefixTree {
+
+ public static class Factory extends SpatialPrefixTreeFactory {
+
+ @Override
+ protected int getLevelForDistance(double degrees) {
+ GeohashPrefixTree grid = new GeohashPrefixTree(ctx, GeohashPrefixTree.getMaxLevelsPossible());
+ return grid.getLevelForDistance(degrees) + 1;//returns 1 greater
+ }
+
+ @Override
+ protected SpatialPrefixTree newSPT() {
+ return new GeohashPrefixTree(ctx,
+ maxLevels != null ? maxLevels : GeohashPrefixTree.getMaxLevelsPossible());
+ }
+ }
+
+ public GeohashPrefixTree(SpatialContext ctx, int maxLevels) {
+ super(ctx, maxLevels);
+ Rectangle bounds = ctx.getWorldBounds();
+ if (bounds.getMinX() != -180)
+ throw new IllegalArgumentException("Geohash only supports lat-lon world bounds. Got "+bounds);
+ int MAXP = getMaxLevelsPossible();
+ if (maxLevels <= 0 || maxLevels > MAXP)
+ throw new IllegalArgumentException("maxLen must be [1-"+MAXP+"] but got "+ maxLevels);
+ }
+
+ /** Any more than this and there's no point (double lat & lon are the same). */
+ public static int getMaxLevelsPossible() {
+ return GeohashUtils.MAX_PRECISION;
+ }
+
+ @Override
+ public int getLevelForDistance(double dist) {
+ final int level = GeohashUtils.lookupHashLenForWidthHeight(dist, dist);
+ return Math.max(Math.min(level, maxLevels), 1);
+ }
+
+ @Override
+ public Node getNode(Point p, int level) {
+ return new GhCell(GeohashUtils.encodeLatLon(p.getY(), p.getX(), level));//args are lat,lon (y,x)
+ }
+
+ @Override
+ public Node getNode(String token) {
+ return new GhCell(token);
+ }
+
+ @Override
+ public Node getNode(byte[] bytes, int offset, int len) {
+ return new GhCell(bytes, offset, len);
+ }
+
+ @Override
+ public List<Node> getNodes(Shape shape, int detailLevel, boolean inclParents) {
+ return shape instanceof Point ? super.getNodesAltPoint((Point) shape, detailLevel, inclParents) :
+ super.getNodes(shape, detailLevel, inclParents);
+ }
+
+ class GhCell extends Node {
+ GhCell(String token) {
+ super(GeohashPrefixTree.this, token);
+ }
+
+ GhCell(byte[] bytes, int off, int len) {
+ super(GeohashPrefixTree.this, bytes, off, len);
+ }
+
+ @Override
+ public void reset(byte[] bytes, int off, int len) {
+ super.reset(bytes, off, len);
+ shape = null;
+ }
+
+ @Override
+ public Collection<Node> getSubCells() {
+ String[] hashes = GeohashUtils.getSubGeohashes(getGeohash());//sorted
+ List<Node> cells = new ArrayList<Node>(hashes.length);
+ for (String hash : hashes) {
+ cells.add(new GhCell(hash));
+ }
+ return cells;
+ }
+
+ @Override
+ public int getSubCellsSize() {
+ return 32;//8x4
+ }
+
+ @Override
+ public Node getSubCell(Point p) {
+ return GeohashPrefixTree.this.getNode(p,getLevel()+1);//not performant!
+ }
+
+ private Shape shape;//cache
+
+ @Override
+ public Shape getShape() {
+ if (shape == null) {
+ shape = GeohashUtils.decodeBoundary(getGeohash(), ctx);
+ }
+ return shape;
+ }
+
+ @Override
+ public Point getCenter() {
+ return GeohashUtils.decode(getGeohash(), ctx);
+ }
+
+ private String getGeohash() {
+ return getTokenString();
+ }
+
+ }//class GhCell
+
+}
Added: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/Node.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/Node.java?rev=1295444&view=auto
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/Node.java (added)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/Node.java Thu Mar 1 07:35:03 2012
@@ -0,0 +1,212 @@
+/*
+ * 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.strategy.prefix.tree;
+
+import com.spatial4j.core.shape.SpatialRelation;
+import com.spatial4j.core.shape.Point;
+import com.spatial4j.core.shape.Shape;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.List;
+
+/**
+ * Represents a grid cell. These are not necessarily threadsafe, although new Cell("") (world cell) must be.
+ */
+public abstract class Node implements Comparable<Node> {
+ public static final byte LEAF_BYTE = '+';//NOTE: must sort before letters & numbers
+
+ /*
+ 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
+
+ protected SpatialRelation shapeRel;//set in getSubCells(filter), and via setLeaf().
+ private SpatialPrefixTree spatialPrefixTree;
+
+ protected Node(SpatialPrefixTree spatialPrefixTree, String token) {
+ this.spatialPrefixTree = spatialPrefixTree;
+ 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 Node(SpatialPrefixTree spatialPrefixTree, byte[] bytes, int off, int len) {
+ this.spatialPrefixTree = spatialPrefixTree;
+ this.bytes = bytes;
+ this.b_off = off;
+ this.b_len = len;
+ b_fixLeaf();
+ }
+
+ 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() {
+ if (bytes[b_off + b_len - 1] == LEAF_BYTE) {
+ b_len--;
+ setLeaf();
+ } else if (getLevel() == spatialPrefixTree.getMaxLevels()) {
+ setLeaf();
+ }
+ }
+
+ public SpatialRelation getShapeRel() {
+ return shapeRel;
+ }
+
+ public boolean isLeaf() {
+ return shapeRel == SpatialRelation.WITHIN;
+ }
+
+ public void setLeaf() {
+ assert getLevel() != 0;
+ shapeRel = SpatialRelation.WITHIN;
+ }
+
+ /**
+ * Note: doesn't contain a trailing leaf byte.
+ */
+ public String getTokenString() {
+ if (token == null) {
+ token = new String(bytes, b_off, b_len, SpatialPrefixTree.UTF8);
+ }
+ return token;
+ }
+
+ /**
+ * Note: doesn't contain a trailing leaf byte.
+ */
+ 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 int getLevel() {
+ return token != null ? token.length() : b_len;
+ }
+
+ //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 that shape is a {@link com.spatial4j.core.shape.Point} then it
+ * must call {@link #getSubCell(com.spatial4j.core.shape.Point)};
+ * Precondition: Never called when getLevel() == maxLevel.
+ *
+ * @param shapeFilter an optional filter for the returned cells.
+ * @return A set of cells (no dups), sorted. Not Modifiable.
+ */
+ public Collection<Node> getSubCells(Shape shapeFilter) {
+ //Note: Higher-performing subclasses might override to consider the shape filter to generate fewer cells.
+ if (shapeFilter instanceof Point) {
+ return Collections.singleton(getSubCell((Point) shapeFilter));
+ }
+ Collection<Node> cells = getSubCells();
+
+ if (shapeFilter == null) {
+ return cells;
+ }
+ List<Node> copy = new ArrayList<Node>(cells.size());//copy since cells contractually isn't modifiable
+ for (Node cell : cells) {
+ SpatialRelation rel = cell.getShape().relate(shapeFilter, spatialPrefixTree.ctx);
+ if (rel == SpatialRelation.DISJOINT)
+ continue;
+ cell.shapeRel = rel;
+ copy.add(cell);
+ }
+ cells = copy;
+ return cells;
+ }
+
+ /**
+ * Performant implementations are expected to implement this efficiently by considering the current
+ * cell's boundary.
+ * Precondition: Never called when getLevel() == maxLevel.
+ * Precondition: this.getShape().relate(p) != DISJOINT.
+ */
+ public abstract Node 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.
+ *
+ * @return A set of cells (no dups), sorted. Not Modifiable.
+ */
+ protected abstract Collection<Node> getSubCells();
+
+ /**
+ * {@link #getSubCells()}.size() -- usually a constant. Should be >=2
+ */
+ public abstract int getSubCellsSize();
+
+ public abstract Shape getShape();
+
+ public Point getCenter() {
+ return getShape().getCenter();
+ }
+
+ @Override
+ public int compareTo(Node o) {
+ return getTokenString().compareTo(o.getTokenString());
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ return !(obj == null || !(obj instanceof Node)) && getTokenString().equals(((Node) obj).getTokenString());
+ }
+
+ @Override
+ public int hashCode() {
+ return getTokenString().hashCode();
+ }
+
+ @Override
+ public String toString() {
+ return getTokenString() + (isLeaf() ? (char) LEAF_BYTE : "");
+ }
+
+}
Added: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/QuadPrefixTree.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/QuadPrefixTree.java?rev=1295444&view=auto
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/QuadPrefixTree.java (added)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/QuadPrefixTree.java Thu Mar 1 07:35:03 2012
@@ -0,0 +1,299 @@
+/*
+ * 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.strategy.prefix.tree;
+
+import com.spatial4j.core.shape.SpatialRelation;
+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.simple.PointImpl;
+
+import java.text.NumberFormat;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+
+
+public class QuadPrefixTree extends SpatialPrefixTree {
+
+ public static class Factory extends SpatialPrefixTreeFactory {
+
+ @Override
+ protected int getLevelForDistance(double degrees) {
+ QuadPrefixTree grid = new QuadPrefixTree(ctx, MAX_LEVELS_POSSIBLE);
+ return grid.getLevelForDistance(degrees) + 1;//returns 1 greater
+ }
+
+ @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;
+ private final double xmin;
+ private final double xmax;
+ private final double ymin;
+ private final double ymax;
+ private final double xmid;
+ private final double ymid;
+
+ private 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);
+ }
+
+ public void printInfo() {
+ NumberFormat nf = NumberFormat.getNumberInstance();
+ nf.setMaximumFractionDigits(5);
+ nf.setMinimumFractionDigits(5);
+ nf.setMinimumIntegerDigits(3);
+
+ for (int i = 0; i < maxLevels; i++) {
+ System.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) {
+ for (int i = 1; i < maxLevels; i++) {
+ //note: level[i] is actually a lookup for level i+1
+ if(dist > levelW[i] || dist > levelH[i]) {
+ return i;
+ }
+ }
+ return maxLevels;
+ }
+
+ @Override
+ public Node getNode(Point p, int level) {
+ List<Node> cells = new ArrayList<Node>(1);
+ build(xmid, ymid, 0, cells, new StringBuilder(), new PointImpl(p.getX(),p.getY()), level);
+ return cells.get(0);//note cells could be longer if p on edge
+ }
+
+ @Override
+ public Node getNode(String token) {
+ return new QuadCell(token);
+ }
+
+ @Override
+ public Node getNode(byte[] bytes, int offset, int len) {
+ return new QuadCell(bytes, offset, len);
+ }
+
+ @Override //for performance
+ public List<Node> getNodes(Shape shape, int detailLevel, boolean inclParents) {
+ if (shape instanceof Point)
+ return super.getNodesAltPoint((Point) shape, detailLevel, inclParents);
+ else
+ return super.getNodes(shape, detailLevel, inclParents);
+ }
+
+ private void build(
+ double x,
+ double y,
+ int level,
+ List<Node> matches,
+ StringBuilder 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
+ }
+
+ private void checkBattenberg(
+ char c,
+ double cx,
+ double cy,
+ int level,
+ List<Node> matches,
+ StringBuilder str,
+ Shape shape,
+ int maxLevel) {
+ assert str.length() == level;
+ double w = levelW[level] / 2;
+ double h = levelH[level] / 2;
+
+ int strlen = str.length();
+ Rectangle rectangle = ctx.makeRect(cx - w, cx + w, cy - h, cy + h);
+ SpatialRelation v = shape.relate(rectangle, ctx);
+ if (SpatialRelation.CONTAINS == v) {
+ str.append(c);
+ //str.append(SpatialPrefixGrid.COVER);
+ matches.add(new QuadCell(str.toString(),v.transpose()));
+ } else if (SpatialRelation.DISJOINT == v) {
+ // nothing
+ } else { // SpatialRelation.WITHIN, SpatialRelation.INTERSECTS
+ str.append(c);
+
+ int nextLevel = level+1;
+ if (nextLevel >= maxLevel) {
+ //str.append(SpatialPrefixGrid.INTERSECTS);
+ matches.add(new QuadCell(str.toString(),v.transpose()));
+ } else {
+ build(cx, cy, nextLevel, matches, str, shape, maxLevel);
+ }
+ }
+ str.setLength(strlen);
+ }
+
+ class QuadCell extends Node {
+
+ public QuadCell(String token) {
+ super(QuadPrefixTree.this, token);
+ }
+
+ public QuadCell(String token, SpatialRelation shapeRel) {
+ super(QuadPrefixTree.this, token);
+ this.shapeRel = shapeRel;
+ }
+
+ QuadCell(byte[] bytes, int off, int len) {
+ super(QuadPrefixTree.this, bytes, off, len);
+ }
+
+ @Override
+ public void reset(byte[] bytes, int off, int len) {
+ super.reset(bytes, off, len);
+ shape = null;
+ }
+
+ @Override
+ public Collection<Node> getSubCells() {
+ List<Node> cells = new ArrayList<Node>(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"));
+ return cells;
+ }
+
+ @Override
+ public int getSubCellsSize() {
+ return 4;
+ }
+
+ @Override
+ public Node getSubCell(Point p) {
+ return QuadPrefixTree.this.getNode(p,getLevel()+1);//not performant!
+ }
+
+ private Shape shape;//cache
+
+ @Override
+ public Shape getShape() {
+ if (shape == null)
+ shape = makeShape();
+ return shape;
+ }
+
+ private Rectangle makeShape() {
+ String token = getTokenString();
+ 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);
+ }
+ }
+ 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.makeRect(xmin, xmin + width, ymin, ymin + height);
+ }
+ }//QuadCell
+}
Added: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/SpatialPrefixTree.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/SpatialPrefixTree.java?rev=1295444&view=auto
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/SpatialPrefixTree.java (added)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/SpatialPrefixTree.java Thu Mar 1 07:35:03 2012
@@ -0,0 +1,246 @@
+/*
+ * 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.strategy.prefix.tree;
+
+import com.spatial4j.core.context.SpatialContext;
+import com.spatial4j.core.shape.Point;
+import com.spatial4j.core.shape.Shape;
+
+import java.nio.charset.Charset;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.List;
+
+/**
+ * A Spatial Prefix Tree, or Trie, which decomposes shapes into prefixed strings at variable lengths corresponding to
+ * variable precision. Each string corresponds to a spatial region.
+ *
+ * Implementations of this class should be thread-safe and immutable once initialized.
+ */
+public abstract class SpatialPrefixTree {
+
+ protected static final Charset UTF8 = Charset.forName("UTF-8");
+
+ 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 + ")";
+ }
+
+ /**
+ * See {@link com.spatial4j.core.query.SpatialArgs#getDistPrecision()}.
+ * A grid level looked up via {@link #getLevelForDistance(double)} is returned.
+ *
+ * @param shape
+ * @param precision 0-0.5
+ * @return 1-maxLevels
+ */
+ public int getMaxLevelForPrecision(Shape shape, double precision) {
+ if (precision < 0 || precision > 0.5) {
+ throw new IllegalArgumentException("Precision " + precision + " must be between [0-0.5]");
+ }
+ if (precision == 0 || shape instanceof Point) {
+ return maxLevels;
+ }
+ double bboxArea = shape.getBoundingBox().getArea();
+ if (bboxArea == 0) {
+ return maxLevels;
+ }
+ double avgSideLenFromCenter = Math.sqrt(bboxArea) / 2;
+ return getLevelForDistance(avgSideLenFromCenter * precision);
+ }
+
+ /**
+ * Returns the level of the smallest grid size with a side length that is greater or equal to the provided
+ * distance.
+ *
+ * @param dist >= 0
+ * @return level [1-maxLevels]
+ */
+ public abstract int getLevelForDistance(double dist);
+
+ //TODO double getDistanceForLevel(int level)
+
+ private transient Node worldNode;//cached
+
+ /**
+ * Returns the level 0 cell which encompasses all spatial data. Equivalent to {@link #getNode(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 Node getWorldNode() {
+ if (worldNode == null) {
+ worldNode = getNode("");
+ }
+ return worldNode;
+ }
+
+ /**
+ * The cell for the specified token. The empty string should be equal to {@link #getWorldNode()}.
+ * Precondition: Never called when token length > maxLevel.
+ */
+ public abstract Node getNode(String token);
+
+ public abstract Node getNode(byte[] bytes, int offset, int len);
+
+ public final Node getNode(byte[] bytes, int offset, int len, Node target) {
+ if (target == null) {
+ return getNode(bytes, offset, len);
+ }
+
+ target.reset(bytes, offset, len);
+ return target;
+ }
+
+ protected Node getNode(Point p, int level) {
+ return getNodes(p, level, false).get(0);
+ }
+
+ /**
+ * Gets the intersecting & including cells for the specified shape, without exceeding detail level.
+ * The result is a set of cells (no dups), sorted. Unmodifiable.
+ * <p/>
+ * This implementation checks if shape is a Point and if so uses an implementation that
+ * recursively calls {@link Node#getSubCell(com.spatial4j.core.shape.Point)}. Cell subclasses
+ * ideally implement that method with a quick implementation, otherwise, subclasses should
+ * override this method to invoke {@link #getNodesAltPoint(com.spatial4j.core.shape.Point, int, boolean)}.
+ * TODO consider another approach returning an iterator -- won't build up all cells in memory.
+ */
+ public List<Node> getNodes(Shape shape, int detailLevel, boolean inclParents) {
+ if (detailLevel > maxLevels) {
+ throw new IllegalArgumentException("detailLevel > maxLevels");
+ }
+
+ List<Node> cells;
+ if (shape instanceof Point) {
+ //optimized point algorithm
+ final int initialCapacity = inclParents ? 1 + detailLevel : 1;
+ cells = new ArrayList<Node>(initialCapacity);
+ recursiveGetNodes(getWorldNode(), (Point) shape, detailLevel, true, cells);
+ assert cells.size() == initialCapacity;
+ } else {
+ cells = new ArrayList<Node>(inclParents ? 1024 : 512);
+ recursiveGetNodes(getWorldNode(), shape, detailLevel, inclParents, cells);
+ }
+ if (inclParents) {
+ Node c = cells.remove(0);//remove getWorldNode()
+ assert c.getLevel() == 0;
+ }
+ return cells;
+ }
+
+ private void recursiveGetNodes(Node node, Shape shape, int detailLevel, boolean inclParents,
+ Collection<Node> result) {
+ if (node.isLeaf()) {//cell is within shape
+ result.add(node);
+ return;
+ }
+ final Collection<Node> subCells = node.getSubCells(shape);
+ if (node.getLevel() == detailLevel - 1) {
+ if (subCells.size() < node.getSubCellsSize()) {
+ if (inclParents)
+ result.add(node);
+ for (Node subCell : subCells) {
+ subCell.setLeaf();
+ }
+ result.addAll(subCells);
+ } else {//a bottom level (i.e. detail level) optimization where all boxes intersect, so use parent cell.
+ node.setLeaf();
+ result.add(node);
+ }
+ } else {
+ if (inclParents) {
+ result.add(node);
+ }
+ for (Node subCell : subCells) {
+ recursiveGetNodes(subCell, shape, detailLevel, inclParents, result);//tail call
+ }
+ }
+ }
+
+ private void recursiveGetNodes(Node node, Point point, int detailLevel, boolean inclParents,
+ Collection<Node> result) {
+ if (inclParents) {
+ result.add(node);
+ }
+ final Node pCell = node.getSubCell(point);
+ if (node.getLevel() == detailLevel - 1) {
+ pCell.setLeaf();
+ result.add(pCell);
+ } else {
+ recursiveGetNodes(pCell, point, detailLevel, inclParents, result);//tail call
+ }
+ }
+
+ /**
+ * Subclasses might override {@link #getNodes(com.spatial4j.core.shape.Shape, int, boolean)}
+ * and check if the argument is a shape and if so, delegate
+ * to this implementation, which calls {@link #getNode(com.spatial4j.core.shape.Point, int)} and
+ * then calls {@link #getNode(String)} repeatedly if inclParents is true.
+ */
+ protected final List<Node> getNodesAltPoint(Point p, int detailLevel, boolean inclParents) {
+ Node cell = getNode(p, detailLevel);
+ if (!inclParents) {
+ return Collections.singletonList(cell);
+ }
+
+ String endToken = cell.getTokenString();
+ assert endToken.length() == detailLevel;
+ List<Node> cells = new ArrayList<Node>(detailLevel);
+ for (int i = 1; i < detailLevel; i++) {
+ cells.add(getNode(endToken.substring(0, i)));
+ }
+ cells.add(cell);
+ return cells;
+ }
+
+ /**
+ * Will add the trailing leaf byte for leaves. This isn't particularly efficient.
+ */
+ public static List<String> nodesToTokenStrings(Collection<Node> nodes) {
+ List<String> tokens = new ArrayList<String>((nodes.size()));
+ for (Node node : nodes) {
+ final String token = node.getTokenString();
+ if (node.isLeaf()) {
+ tokens.add(token + (char) Node.LEAF_BYTE);
+ } else {
+ tokens.add(token);
+ }
+ }
+ return tokens;
+ }
+}
Added: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/SpatialPrefixTreeFactory.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/SpatialPrefixTreeFactory.java?rev=1295444&view=auto
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/SpatialPrefixTreeFactory.java (added)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/SpatialPrefixTreeFactory.java Thu Mar 1 07:35:03 2012
@@ -0,0 +1,93 @@
+/*
+ * 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.strategy.prefix.tree;
+
+import com.spatial4j.core.context.SpatialContext;
+import com.spatial4j.core.distance.DistanceUnits;
+import com.spatial4j.core.distance.DistanceUtils;
+
+import java.util.Map;
+
+/**
+ * @author dsmiley
+ */
+public abstract class SpatialPrefixTreeFactory {
+
+ private static final double DEFAULT_GEO_MAX_DETAIL_KM = 0.001;//1m
+
+ 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 its 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("prefixTree");
+ 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 {
+ 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("maxLevels");
+ if (mlStr != null) {
+ maxLevels = Integer.valueOf(mlStr);
+ return;
+ }
+
+ double degrees;
+ String maxDetailDistStr = args.get("maxDetailDist");
+ if (maxDetailDistStr == null) {
+ if (!ctx.isGeo()) {
+ return;//let default to max
+ }
+ degrees = DistanceUtils.dist2Degrees(DEFAULT_GEO_MAX_DETAIL_KM, DistanceUnits.KILOMETERS.earthRadius());
+ } else {
+ degrees = DistanceUtils.dist2Degrees(Double.parseDouble(maxDetailDistStr), ctx.getUnits().earthRadius());
+ }
+ maxLevels = getLevelForDistance(degrees) + 1;//returns 1 greater
+ }
+
+ /** Calls {@link SpatialPrefixTree#getLevelForDistance(double)}. */
+ protected abstract int getLevelForDistance(double degrees);
+
+ protected abstract SpatialPrefixTree newSPT();
+
+}
Added: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/package-info.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/package-info.java?rev=1295444&view=auto
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/package-info.java (added)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/java/org/apache/lucene/spatial/strategy/prefix/tree/package-info.java Thu Mar 1 07:35:03 2012
@@ -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.
+ */
+
+/**
+ * The Spatial Prefix package supports spatial indexing by index-time tokens
+ * where adding characters to a string gives greater resolution.
+ *
+ * Potential Implementations include:
+ * * http://en.wikipedia.org/wiki/Quadtree
+ * * http://en.wikipedia.org/wiki/Geohash
+ * * http://healpix.jpl.nasa.gov/
+ */
+package org.apache.lucene.spatial.strategy.prefix.tree;
+
Modified: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/test/org/apache/lucene/spatial/strategy/prefix/BaseRecursivePrefixTreeStrategyTestCase.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/test/org/apache/lucene/spatial/strategy/prefix/BaseRecursivePrefixTreeStrategyTestCase.java?rev=1295444&r1=1295443&r2=1295444&view=diff
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/test/org/apache/lucene/spatial/strategy/prefix/BaseRecursivePrefixTreeStrategyTestCase.java (original)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/test/org/apache/lucene/spatial/strategy/prefix/BaseRecursivePrefixTreeStrategyTestCase.java Thu Mar 1 07:35:03 2012
@@ -18,8 +18,8 @@
package org.apache.lucene.spatial.strategy.prefix;
import com.spatial4j.core.context.SpatialContext;
-import com.spatial4j.core.prefix.geohash.GeohashPrefixTree;
import org.apache.lucene.spatial.strategy.SimpleSpatialFieldInfo;
+import org.apache.lucene.spatial.strategy.prefix.tree.GeohashPrefixTree;
import org.apache.lucene.spatial.SpatialMatchConcern;
import org.apache.lucene.spatial.StrategyTestCase;
import org.junit.Test;
Modified: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/test/org/apache/lucene/spatial/strategy/prefix/TestTermQueryPrefixGridStrategy.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/test/org/apache/lucene/spatial/strategy/prefix/TestTermQueryPrefixGridStrategy.java?rev=1295444&r1=1295443&r2=1295444&view=diff
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/test/org/apache/lucene/spatial/strategy/prefix/TestTermQueryPrefixGridStrategy.java (original)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/test/org/apache/lucene/spatial/strategy/prefix/TestTermQueryPrefixGridStrategy.java Thu Mar 1 07:35:03 2012
@@ -22,11 +22,11 @@ import org.apache.lucene.document.Field;
import org.apache.lucene.document.StringField;
import com.spatial4j.core.context.SpatialContext;
import com.spatial4j.core.context.simple.SimpleSpatialContext;
-import com.spatial4j.core.prefix.quad.QuadPrefixTree;
import com.spatial4j.core.query.SpatialArgsParser;
import com.spatial4j.core.shape.Shape;
import com.spatial4j.core.shape.simple.PointImpl;
import org.apache.lucene.spatial.strategy.SimpleSpatialFieldInfo;
+import org.apache.lucene.spatial.strategy.prefix.tree.QuadPrefixTree;
import org.apache.lucene.spatial.SpatialTestCase;
import org.junit.Test;
Added: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/test/org/apache/lucene/spatial/strategy/prefix/tree/SpatialPrefixTreeTest.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/test/org/apache/lucene/spatial/strategy/prefix/tree/SpatialPrefixTreeTest.java?rev=1295444&view=auto
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/test/org/apache/lucene/spatial/strategy/prefix/tree/SpatialPrefixTreeTest.java (added)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial/src/test/org/apache/lucene/spatial/strategy/prefix/tree/SpatialPrefixTreeTest.java Thu Mar 1 07:35:03 2012
@@ -0,0 +1,64 @@
+/*
+ * 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.strategy.prefix.tree;
+
+import com.spatial4j.core.context.simple.SimpleSpatialContext;
+import com.spatial4j.core.shape.Rectangle;
+import com.spatial4j.core.shape.Shape;
+
+import org.apache.lucene.spatial.strategy.prefix.tree.GeohashPrefixTree;
+import org.apache.lucene.spatial.strategy.prefix.tree.Node;
+import org.apache.lucene.spatial.strategy.prefix.tree.SpatialPrefixTree;
+import org.junit.Before;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+
+public class SpatialPrefixTreeTest {
+
+ //TODO plug in others and test them
+ private SimpleSpatialContext ctx;
+ private SpatialPrefixTree trie;
+
+ @Before
+ public void setUp() throws Exception {
+ ctx = SimpleSpatialContext.GEO_KM;
+ trie = new GeohashPrefixTree(ctx,4);
+ }
+
+ @Test
+ public void testNodeTraverse() {
+ Node prevN = null;
+ Node n = trie.getWorldNode();
+ assertEquals(0,n.getLevel());
+ assertEquals(ctx.getWorldBounds(),n.getShape());
+ while(n.getLevel() < trie.getMaxLevels()) {
+ prevN = n;
+ n = n.getSubCells().iterator().next();//TODO random which one?
+
+ assertEquals(prevN.getLevel()+1,n.getLevel());
+ Rectangle prevNShape = (Rectangle) prevN.getShape();
+ Shape s = n.getShape();
+ Rectangle sbox = s.getBoundingBox();
+ assertTrue(prevNShape.getWidth() > sbox.getWidth());
+ assertTrue(prevNShape.getHeight() > sbox.getHeight());
+ }
+ }
+}
Modified: lucene/dev/branches/lucene3795_lsp_spatial_module/solr/core/src/java/org/apache/solr/schema/GeoHashField.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/solr/core/src/java/org/apache/solr/schema/GeoHashField.java?rev=1295444&r1=1295443&r2=1295444&view=diff
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/solr/core/src/java/org/apache/solr/schema/GeoHashField.java (original)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/solr/core/src/java/org/apache/solr/schema/GeoHashField.java Thu Mar 1 07:35:03 2012
@@ -26,7 +26,7 @@ import com.spatial4j.core.context.ParseU
import com.spatial4j.core.context.SpatialContext;
import com.spatial4j.core.context.simple.SimpleSpatialContext;
import com.spatial4j.core.exception.InvalidShapeException;
-import com.spatial4j.core.prefix.geohash.GeohashUtils;
+import com.spatial4j.core.util.GeohashUtils;
import com.spatial4j.core.shape.Point;
import org.apache.solr.common.SolrException;
import org.apache.solr.response.TextResponseWriter;
Modified: lucene/dev/branches/lucene3795_lsp_spatial_module/solr/core/src/java/org/apache/solr/search/function/distance/GeohashFunction.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/solr/core/src/java/org/apache/solr/search/function/distance/GeohashFunction.java?rev=1295444&r1=1295443&r2=1295444&view=diff
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/solr/core/src/java/org/apache/solr/search/function/distance/GeohashFunction.java (original)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/solr/core/src/java/org/apache/solr/search/function/distance/GeohashFunction.java Thu Mar 1 07:35:03 2012
@@ -19,7 +19,7 @@ package org.apache.solr.search.function.
import org.apache.lucene.index.AtomicReaderContext;
import org.apache.lucene.queries.function.FunctionValues;
import org.apache.lucene.queries.function.ValueSource;
-import com.spatial4j.core.prefix.geohash.GeohashUtils;
+import com.spatial4j.core.util.GeohashUtils;
import java.util.Map;
import java.io.IOException;
Modified: lucene/dev/branches/lucene3795_lsp_spatial_module/solr/core/src/java/org/apache/solr/search/function/distance/GeohashHaversineFunction.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/solr/core/src/java/org/apache/solr/search/function/distance/GeohashHaversineFunction.java?rev=1295444&r1=1295443&r2=1295444&view=diff
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/solr/core/src/java/org/apache/solr/search/function/distance/GeohashHaversineFunction.java (original)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/solr/core/src/java/org/apache/solr/search/function/distance/GeohashHaversineFunction.java Thu Mar 1 07:35:03 2012
@@ -27,7 +27,7 @@ import com.spatial4j.core.context.simple
import com.spatial4j.core.distance.DistanceCalculator;
import com.spatial4j.core.distance.DistanceUnits;
import com.spatial4j.core.distance.GeodesicSphereDistCalc;
-import com.spatial4j.core.prefix.geohash.GeohashUtils;
+import com.spatial4j.core.util.GeohashUtils;
import com.spatial4j.core.shape.Point;
import java.util.Map;
Modified: lucene/dev/branches/lucene3795_lsp_spatial_module/solr/core/src/test/org/apache/solr/search/function/distance/DistanceFunctionTest.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/solr/core/src/test/org/apache/solr/search/function/distance/DistanceFunctionTest.java?rev=1295444&r1=1295443&r2=1295444&view=diff
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/solr/core/src/test/org/apache/solr/search/function/distance/DistanceFunctionTest.java (original)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/solr/core/src/test/org/apache/solr/search/function/distance/DistanceFunctionTest.java Thu Mar 1 07:35:03 2012
@@ -17,7 +17,7 @@ package org.apache.solr.search.function.
*/
import com.spatial4j.core.distance.DistanceUtils;
-import com.spatial4j.core.prefix.geohash.GeohashUtils;
+import com.spatial4j.core.util.GeohashUtils;
import org.apache.solr.SolrTestCaseJ4;
import org.apache.solr.common.SolrException;
import org.junit.BeforeClass;
Modified: lucene/dev/branches/lucene3795_lsp_spatial_module/solr/lib/spatial4j-0.1.jar
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/solr/lib/spatial4j-0.1.jar?rev=1295444&r1=1295443&r2=1295444&view=diff
==============================================================================
Binary files - no diff available.