You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by nk...@apache.org on 2016/02/05 18:03:12 UTC
[68/87] [abbrv] lucene-solr git commit: LUCENE-6997: refactors
lucene-spatial module to a new lucene-spatial-extras module,
and refactors sandbox GeoPointField and queries to lucene-spatial module
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/50a2f754/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/WithinPrefixTreeQuery.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/WithinPrefixTreeQuery.java b/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/WithinPrefixTreeQuery.java
deleted file mode 100644
index c534a5b..0000000
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/WithinPrefixTreeQuery.java
+++ /dev/null
@@ -1,233 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.lucene.spatial.prefix;
-
-import java.io.IOException;
-
-import com.spatial4j.core.context.SpatialContext;
-import com.spatial4j.core.distance.DistanceUtils;
-import com.spatial4j.core.shape.Circle;
-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.index.LeafReaderContext;
-import org.apache.lucene.search.DocIdSet;
-import org.apache.lucene.spatial.prefix.tree.Cell;
-import org.apache.lucene.spatial.prefix.tree.CellIterator;
-import org.apache.lucene.spatial.prefix.tree.SpatialPrefixTree;
-import org.apache.lucene.util.BitDocIdSet;
-import org.apache.lucene.util.Bits;
-import org.apache.lucene.util.FixedBitSet;
-
-/**
- * Finds docs where its indexed shape is {@link org.apache.lucene.spatial.query.SpatialOperation#IsWithin
- * WITHIN} the query shape. It works by looking at cells outside of the query
- * shape to ensure documents there are excluded. By default, it will
- * examine all cells, and it's fairly slow. If you know that the indexed shapes
- * are never comprised of multiple disjoint parts (which also means it is not multi-valued),
- * then you can pass {@code SpatialPrefixTree.getDistanceForLevel(maxLevels)} as
- * the {@code queryBuffer} constructor parameter to minimally look this distance
- * beyond the query shape's edge. Even if the indexed shapes are sometimes
- * comprised of multiple disjoint parts, you might want to use this option with
- * a large buffer as a faster approximation with minimal false-positives.
- *
- * @lucene.experimental
- */
-public class WithinPrefixTreeQuery extends AbstractVisitingPrefixTreeQuery {
- //TODO LUCENE-4869: implement faster algorithm based on filtering out false-positives of a
- // minimal query buffer by looking in a DocValues cache holding a representative
- // point of each disjoint component of a document's shape(s).
-
- //TODO Could the recursion in allCellsIntersectQuery() be eliminated when non-fuzzy or other
- // circumstances?
-
- private final Shape bufferedQueryShape;//if null then the whole world
-
- /**
- * See {@link AbstractVisitingPrefixTreeQuery#AbstractVisitingPrefixTreeQuery(com.spatial4j.core.shape.Shape, String, org.apache.lucene.spatial.prefix.tree.SpatialPrefixTree, int, int)}.
- * {@code queryBuffer} is the (minimum) distance beyond the query shape edge
- * where non-matching documents are looked for so they can be excluded. If
- * -1 is used then the whole world is examined (a good default for correctness).
- */
- public WithinPrefixTreeQuery(Shape queryShape, String fieldName, SpatialPrefixTree grid,
- int detailLevel, int prefixGridScanLevel,
- double queryBuffer) {
- super(queryShape, fieldName, grid, detailLevel, prefixGridScanLevel);
- this.bufferedQueryShape = queryBuffer == -1 ? null : bufferShape(queryShape, queryBuffer);
- }
-
- @Override
- public boolean equals(Object o) {
- if (!super.equals(o)) return false;//checks getClass == o.getClass & instanceof
-
- WithinPrefixTreeQuery that = (WithinPrefixTreeQuery) o;
-
- if (bufferedQueryShape != null ? !bufferedQueryShape.equals(that.bufferedQueryShape) : that.bufferedQueryShape != null)
- return false;
-
- return true;
- }
-
- @Override
- public int hashCode() {
- int result = super.hashCode();
- result = 31 * result + (bufferedQueryShape != null ? bufferedQueryShape.hashCode() : 0);
- return result;
- }
-
- @Override
- public String toString(String field) {
- return getClass().getSimpleName() + "(" +
- "fieldName=" + fieldName + "," +
- "queryShape=" + queryShape + "," +
- "detailLevel=" + detailLevel + "," +
- "prefixGridScanLevel=" + prefixGridScanLevel +
- ")";
- }
-
- /** Returns a new shape that is larger than shape by at distErr.
- */
- //TODO move this generic code elsewhere? Spatial4j?
- protected Shape bufferShape(Shape shape, double distErr) {
- if (distErr <= 0)
- throw new IllegalArgumentException("distErr must be > 0");
- SpatialContext ctx = grid.getSpatialContext();
- if (shape instanceof Point) {
- return ctx.makeCircle((Point)shape, distErr);
- } else if (shape instanceof Circle) {
- Circle circle = (Circle) shape;
- double newDist = circle.getRadius() + distErr;
- if (ctx.isGeo() && newDist > 180)
- newDist = 180;
- return ctx.makeCircle(circle.getCenter(), newDist);
- } else {
- Rectangle bbox = shape.getBoundingBox();
- double newMinX = bbox.getMinX() - distErr;
- double newMaxX = bbox.getMaxX() + distErr;
- double newMinY = bbox.getMinY() - distErr;
- double newMaxY = bbox.getMaxY() + distErr;
- if (ctx.isGeo()) {
- if (newMinY < -90)
- newMinY = -90;
- if (newMaxY > 90)
- newMaxY = 90;
- if (newMinY == -90 || newMaxY == 90 || bbox.getWidth() + 2*distErr > 360) {
- newMinX = -180;
- newMaxX = 180;
- } else {
- newMinX = DistanceUtils.normLonDEG(newMinX);
- newMaxX = DistanceUtils.normLonDEG(newMaxX);
- }
- } else {
- //restrict to world bounds
- newMinX = Math.max(newMinX, ctx.getWorldBounds().getMinX());
- newMaxX = Math.min(newMaxX, ctx.getWorldBounds().getMaxX());
- newMinY = Math.max(newMinY, ctx.getWorldBounds().getMinY());
- newMaxY = Math.min(newMaxY, ctx.getWorldBounds().getMaxY());
- }
- return ctx.makeRectangle(newMinX, newMaxX, newMinY, newMaxY);
- }
- }
-
-
- @Override
- protected DocIdSet getDocIdSet(LeafReaderContext context) throws IOException {
- return new VisitorTemplate(context) {
- private FixedBitSet inside;
- private FixedBitSet outside;
-
- @Override
- protected void start() {
- inside = new FixedBitSet(maxDoc);
- outside = new FixedBitSet(maxDoc);
- }
-
- @Override
- protected DocIdSet finish() {
- inside.andNot(outside);
- return new BitDocIdSet(inside);
- }
-
- @Override
- protected CellIterator findSubCellsToVisit(Cell cell) {
- //use buffered query shape instead of orig. Works with null too.
- return cell.getNextLevelCells(bufferedQueryShape);
- }
-
- @Override
- protected boolean visitPrefix(Cell cell) throws IOException {
- //cell.relate is based on the bufferedQueryShape; we need to examine what
- // the relation is against the queryShape
- SpatialRelation visitRelation = cell.getShape().relate(queryShape);
- if (cell.getLevel() == detailLevel) {
- collectDocs(visitRelation.intersects() ? inside : outside);
- return false;
- } else if (visitRelation == SpatialRelation.WITHIN) {
- collectDocs(inside);
- return false;
- } else if (visitRelation == SpatialRelation.DISJOINT) {
- collectDocs(outside);
- return false;
- }
- return true;
- }
-
- @Override
- protected void visitLeaf(Cell cell) throws IOException {
- if (allCellsIntersectQuery(cell))
- collectDocs(inside);
- else
- collectDocs(outside);
- }
-
- /** Returns true if the provided cell, and all its sub-cells down to
- * detailLevel all intersect the queryShape.
- */
- private boolean allCellsIntersectQuery(Cell cell) {
- SpatialRelation relate = cell.getShape().relate(queryShape);
- if (cell.getLevel() == detailLevel)
- return relate.intersects();
- if (relate == SpatialRelation.WITHIN)
- return true;
- if (relate == SpatialRelation.DISJOINT)
- return false;
- // Note: Generating all these cells just to determine intersection is not ideal.
- // The real solution is LUCENE-4869.
- CellIterator subCells = cell.getNextLevelCells(null);
- while (subCells.hasNext()) {
- Cell subCell = subCells.next();
- if (!allCellsIntersectQuery(subCell))//recursion
- return false;
- }
- return true;
- }
-
- @Override
- protected void visitScanned(Cell cell) throws IOException {
- visitLeaf(cell);//collects as we want, even if not a leaf
-// if (cell.isLeaf()) {
-// visitLeaf(cell);
-// } else {
-// visitPrefix(cell);
-// }
- }
-
- }.getDocIdSet();
- }
-
-}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/50a2f754/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/Cell.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/Cell.java b/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/Cell.java
deleted file mode 100644
index fe3846d..0000000
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/Cell.java
+++ /dev/null
@@ -1,109 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.lucene.spatial.prefix.tree;
-
-import com.spatial4j.core.shape.Shape;
-import com.spatial4j.core.shape.SpatialRelation;
-import org.apache.lucene.util.BytesRef;
-
-/**
- * Represents a grid cell. Cell instances are generally very transient and may be re-used
- * internally. To get an instance, you could start with {@link SpatialPrefixTree#getWorldCell()}.
- * And from there you could either traverse down the tree with {@link #getNextLevelCells(com.spatial4j.core.shape.Shape)},
- * or you could read an indexed term via {@link SpatialPrefixTree#readCell(org.apache.lucene.util.BytesRef,Cell)}.
- * When a cell is read from a term, it is comprised of just the base bytes plus optionally a leaf flag.
- *
- * @lucene.experimental
- */
-public interface Cell {
-
-// If we bring this back; perhaps do so as a method that un-shares its internal state: void unshare();
-// /** Resets the state of this cell such that it is identical to {@code source}. This can be used for
-// * cloning a cell to have a safe copy, and it also might be used to position this cell
-// * before calling {@link #readCell(org.apache.lucene.util.BytesRef)} in a loop if you know the first term
-// * is going to be close to some other cell, thereby saving some computations. */
-// void copyFrom(Cell source);
-
- /** Gets the relationship this cell has with the shape from which it was filtered from, assuming it came from a
- * {@link CellIterator}. Arguably it belongs there but it's very convenient here. */
- SpatialRelation getShapeRel();
-
- /** See {@link #getShapeRel()}.
- * @lucene.internal */
- void setShapeRel(SpatialRelation rel);
-
- /**
- * Some cells are flagged as leaves, which are indexed as such. A leaf cell is either within some
- * shape or it both intersects and the cell is at an accuracy threshold such that no smaller cells
- * for the shape will be represented.
- */
- boolean isLeaf();
-
- /** Set this cell to be a leaf. Warning: never call on a cell
- * initialized to reference the same bytes from termsEnum, which should be treated as immutable.
- * Note: not supported at level 0.
- * @lucene.internal */
- void setLeaf();
-
- /**
- * Returns the bytes for this cell, with a leaf byte <em>if this is a leaf cell</em>.
- * The result param is used to save object allocation, though its bytes aren't used.
- * @param result where the result goes, or null to create new
- */
- BytesRef getTokenBytesWithLeaf(BytesRef result);
-
- /**
- * Returns the bytes for this cell, without a leaf set. The bytes should sort before
- * {@link #getTokenBytesWithLeaf(org.apache.lucene.util.BytesRef)}.
- * The result param is used to save object allocation, though its bytes aren't used.
- * @param result where the result goes, or null to create new
- */
- BytesRef getTokenBytesNoLeaf(BytesRef result);
-
- /** Level 0 is the world (and has no parent), from then on a higher level means a smaller
- * cell than the level before it.
- */
- int getLevel();
-
- /**
- * Gets the cells at the next grid cell level underneath this one, optionally filtered by
- * {@code shapeFilter}. The returned cells should have {@link #getShapeRel()} set to
- * their relation with {@code shapeFilter}. In addition, for non-points {@link #isLeaf()}
- * must be true when that relation is WITHIN.
- * <p>
- * IMPORTANT: Cells returned from this iterator can be shared, as well as the bytes.
- * <p>
- * 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.
- */
- CellIterator getNextLevelCells(Shape shapeFilter);
-
- /** Gets the shape for this cell; typically a Rectangle. */
- Shape getShape();
-
- /**
- * Returns if the target term is within/underneath this cell; not necessarily a direct
- * descendant.
- * @param c the term
- */
- boolean isPrefixOf(Cell c);
-
- /** Equivalent to {@code this.getTokenBytesNoLeaf(null).compareTo(fromCell.getTokenBytesNoLeaf(null))}. */
- int compareToNoLeaf(Cell fromCell);
-}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/50a2f754/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/CellIterator.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/CellIterator.java b/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/CellIterator.java
deleted file mode 100644
index 1cef37a..0000000
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/CellIterator.java
+++ /dev/null
@@ -1,76 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.lucene.spatial.prefix.tree;
-
-import java.util.Iterator;
-import java.util.NoSuchElementException;
-
-/**
- * An Iterator of SpatialPrefixTree Cells. The order is always sorted without duplicates.
- *
- * @lucene.experimental
- */
-public abstract class CellIterator implements Iterator<Cell> {
-
- //note: nextCell or thisCell can be non-null but neither at the same time. That's
- // because they might return the same instance when re-used!
-
- protected Cell nextCell;//to be returned by next(), and null'ed after
- protected Cell thisCell;//see next() & thisCell(). Should be cleared in hasNext().
-
- /** Returns the cell last returned from {@link #next()}. It's cleared by hasNext(). */
- public Cell thisCell() {
- assert thisCell != null : "Only call thisCell() after next(), not hasNext()";
- return thisCell;
- }
-
- // Arguably this belongs here and not on Cell
- //public SpatialRelation getShapeRel()
-
- /**
- * Gets the next cell that is >= {@code fromCell}, compared using non-leaf bytes. If it returns null then
- * the iterator is exhausted.
- */
- public Cell nextFrom(Cell fromCell) {
- while (true) {
- if (!hasNext())
- return null;
- Cell c = next();//will update thisCell
- if (c.compareToNoLeaf(fromCell) >= 0) {
- return c;
- }
- }
- }
-
- /** This prevents sub-cells (those underneath the current cell) from being iterated to,
- * if applicable, otherwise a NO-OP. */
- @Override
- public void remove() {
- assert thisCell != null;
- }
-
- @Override
- public Cell next() {
- if (nextCell == null) {
- if (!hasNext())
- throw new NoSuchElementException();
- }
- thisCell = nextCell;
- nextCell = null;
- return thisCell;
- }
-}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/50a2f754/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/DateRangePrefixTree.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/DateRangePrefixTree.java b/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/DateRangePrefixTree.java
deleted file mode 100644
index 13281f3..0000000
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/DateRangePrefixTree.java
+++ /dev/null
@@ -1,444 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.lucene.spatial.prefix.tree;
-
-import java.text.ParseException;
-import java.text.SimpleDateFormat;
-import java.util.Calendar;
-import java.util.Date;
-import java.util.GregorianCalendar;
-import java.util.Locale;
-import java.util.TimeZone;
-
-import com.spatial4j.core.shape.Shape;
-
-/**
- * A PrefixTree for date ranges in which the levels of the tree occur at natural periods of time (e.g. years,
- * months, ...). You pass in {@link Calendar} objects with the desired fields set and the unspecified
- * fields unset, which conveys the precision. The implementation makes some optimization assumptions about a
- * {@link java.util.GregorianCalendar}; others could probably be supported easily.
- * <p>
- * Warning: If you construct a Calendar and then get something from the object like a field (e.g. year) or
- * milliseconds, then every field is fully set by side-effect. So after setting the fields, pass it to this
- * API first.
- * @lucene.experimental
- */
-public class DateRangePrefixTree extends NumberRangePrefixTree {
-
- /*
- WARNING java.util.Calendar is tricky to work with:
- * If you "get" any field value, every field becomes "set". This can introduce a Heisenbug effect,
- when in a debugger in some cases. Fortunately, Calendar.toString() doesn't apply.
- * Beware Calendar underflow of the underlying long. If you create a Calendar from LONG.MIN_VALUE, and clear
- a field, it will underflow and appear close to LONG.MAX_VALUE (BC to AD).
-
- There are no doubt other reasons but those two were hard fought lessons here.
-
- TODO Improvements:
- * Make max precision configurable (i.e. to SECOND).
- * Make min & max year span configurable. Use that to remove pointless top levels of the SPT.
- If year span is > 10k, then add 1k year level. If year span is > 10k of 1k levels, add 1M level.
- * NumberRangePrefixTree: override getTreeCellIterator for optimized case where the shape isn't a date span; use
- FilterCellIterator of the cell stack.
-
- */
-
- private static final TimeZone UTC = TimeZone.getTimeZone("UTC");
- private static Calendar CAL_TMP;//template
- static {
- CAL_TMP = Calendar.getInstance(UTC, Locale.ROOT);
- CAL_TMP.clear();
- }
-
- private static final Calendar MINCAL = (Calendar) CAL_TMP.clone();
- private static final Calendar MAXCAL = (Calendar) CAL_TMP.clone();
- static {
- MINCAL.setTimeInMillis(Long.MIN_VALUE);
- MAXCAL.setTimeInMillis(Long.MAX_VALUE);
- }
- //BC years are decreasing, remember. Yet ActualMaximum is the numerically high value, ActualMinimum is 1.
- private static final int BC_FIRSTYEAR = MINCAL.getActualMaximum(Calendar.YEAR);
- private static final int BC_LASTYEAR = MINCAL.getActualMinimum(Calendar.YEAR);//1
- private static final int BC_YEARS = BC_FIRSTYEAR - BC_LASTYEAR + 1;
- private static final int AD_FIRSTYEAR = MAXCAL.getActualMinimum(Calendar.YEAR);//1
- private static final int AD_LASTYEAR = MAXCAL.getActualMaximum(Calendar.YEAR);
- private static final int AD_YEAR_BASE = (((BC_YEARS-1) / 1000_000)+1) * 1000_000;
- static { assert BC_LASTYEAR == 1 && AD_FIRSTYEAR == 1; }
-
- //how many million years are there?
- private static final int NUM_MYEARS = (AD_YEAR_BASE + AD_LASTYEAR) / 1000_000;
-
- private static int calFieldLen(int field) {
- return CAL_TMP.getMaximum(field) - CAL_TMP.getMinimum(field) + 1;
- }
-
- private static final int[] FIELD_BY_LEVEL = {
- -1/*unused*/, -1, -1, Calendar.YEAR, Calendar.MONTH, Calendar.DAY_OF_MONTH,
- Calendar.HOUR_OF_DAY, Calendar.MINUTE, Calendar.SECOND, Calendar.MILLISECOND};
- private static final int yearLevel = 3;
-
- public static final DateRangePrefixTree INSTANCE = new DateRangePrefixTree();
-
- private final UnitNRShape minLV, maxLV;
- private final UnitNRShape gregorianChangeDateLV;
-
- protected DateRangePrefixTree() {
- super(new int[]{//sublevels by level
- NUM_MYEARS,
- 1000,//1 thousand thousand-years in a million years
- 1000,//1 thousand years in a thousand-year
- calFieldLen(Calendar.MONTH),
- calFieldLen(Calendar.DAY_OF_MONTH),
- calFieldLen(Calendar.HOUR_OF_DAY),
- calFieldLen(Calendar.MINUTE),
- calFieldLen(Calendar.SECOND),
- calFieldLen(Calendar.MILLISECOND),
- });
- maxLV = toShape((Calendar)MAXCAL.clone());
- minLV = toShape((Calendar)MINCAL.clone());
- if (MAXCAL instanceof GregorianCalendar) {
- //TODO this should be a configurable param by passing a Calendar serving as a template.
- GregorianCalendar gCal = (GregorianCalendar)MAXCAL;
- gregorianChangeDateLV = toUnitShape(gCal.getGregorianChange());
- } else {
- gregorianChangeDateLV = null;
- }
- }
-
- @Override
- public int getNumSubCells(UnitNRShape lv) {
- int cmp = comparePrefix(lv, maxLV);
- assert cmp <= 0;
- if (cmp == 0)//edge case (literally!)
- return maxLV.getValAtLevel(lv.getLevel()+1);
-
- // if using GregorianCalendar and we're after the "Gregorian change date" then we'll compute
- // the sub-cells ourselves more efficiently without the need to construct a Calendar.
- cmp = gregorianChangeDateLV != null ? comparePrefix(lv, gregorianChangeDateLV) : -1;
- //TODO consider also doing fast-path if field is <= hours even if before greg change date
- if (cmp >= 0) {
- int result = fastSubCells(lv);
- assert result == slowSubCells(lv) : "fast/slow numSubCells inconsistency";
- return result;
- } else {
- return slowSubCells(lv);
- }
- }
-
- private int fastSubCells(UnitNRShape lv) {
- if (lv.getLevel() == yearLevel+1) {//month
- switch (lv.getValAtLevel(lv.getLevel())) {
- case Calendar.SEPTEMBER:
- case Calendar.APRIL:
- case Calendar.JUNE:
- case Calendar.NOVEMBER:
- return 30;
- case Calendar.FEBRUARY:
- //get the year (negative numbers for BC)
- int yearAdj = lv.getValAtLevel(1) * 1_000_000;
- yearAdj += lv.getValAtLevel(2) * 1000;
- yearAdj += lv.getValAtLevel(3);
- int year = yearAdj - AD_YEAR_BASE;
- if (year % 4 == 0 && !(year % 100 == 0 && year % 400 != 0) )//leap year
- return 29;
- else
- return 28;
- default:
- return 31;
- }
- } else {//typical:
- return super.getNumSubCells(lv);
- }
- }
-
- private int slowSubCells(UnitNRShape lv) {
- int field = FIELD_BY_LEVEL[lv.getLevel()+1];
- //short-circuit optimization (GregorianCalendar assumptions)
- if (field == -1 || field == Calendar.YEAR || field >= Calendar.HOUR_OF_DAY)//TODO make configurable
- return super.getNumSubCells(lv);
- Calendar cal = toCalendar(lv);//somewhat heavyweight op; ideally should be stored on UnitNRShape somehow
- return cal.getActualMaximum(field) - cal.getActualMinimum(field) + 1;
- }
-
- /** Calendar utility method:
- * Returns a new {@link Calendar} in UTC TimeZone, ROOT Locale, with all fields cleared. */
- public Calendar newCal() {
- return (Calendar) CAL_TMP.clone();
- }
-
- /** Calendar utility method:
- * Returns the spatial prefix tree level for the corresponding {@link java.util.Calendar} field, such as
- * {@link java.util.Calendar#YEAR}. If there's no match, the next greatest level is returned as a negative value.
- */
- public int getTreeLevelForCalendarField(int calField) {
- for (int i = yearLevel; i < FIELD_BY_LEVEL.length; i++) {
- if (FIELD_BY_LEVEL[i] == calField) {
- return i;
- } else if (FIELD_BY_LEVEL[i] > calField) {
- return -1 * i;
- }
- }
- throw new IllegalArgumentException("Bad calendar field?: " + calField);
- }
-
- /** Calendar utility method:
- * Gets the Calendar field code of the last field that is set prior to an unset field. It only
- * examines fields relevant to the prefix tree. If no fields are set, it returns -1. */
- public int getCalPrecisionField(Calendar cal) {
- int lastField = -1;
- for (int level = yearLevel; level < FIELD_BY_LEVEL.length; level++) {
- int field = FIELD_BY_LEVEL[level];
- if (!cal.isSet(field))
- break;
- lastField = field;
- }
- return lastField;
- }
-
- /** Calendar utility method:
- * Calls {@link Calendar#clear(int)} for every field after {@code field}. Beware of Calendar underflow. */
- public void clearFieldsAfter(Calendar cal, int field) {
- if (field == -1) {
- cal.clear();
- return;
- }
- int assertEra = -1;
- assert (assertEra = (((Calendar)cal.clone()).get(Calendar.ERA))) >= 0;//a trick to only get this if assert enabled
- for (int f = field+1; f < Calendar.FIELD_COUNT; f++) {
- cal.clear(f);
- }
- assert ((Calendar)cal.clone()).get(Calendar.ERA) == assertEra : "Calendar underflow";
- }
-
- /** Converts {@code value} from a {@link Calendar} or {@link Date} to a {@link Shape}. Other arguments
- * result in a {@link java.lang.IllegalArgumentException}.
- */
- @Override
- public UnitNRShape toUnitShape(Object value) {
- if (value instanceof Calendar) {
- return toShape((Calendar) value);
- } else if (value instanceof Date) {
- Calendar cal = newCal();
- cal.setTime((Date)value);
- return toShape(cal);
- }
- throw new IllegalArgumentException("Expecting Calendar or Date but got: "+value.getClass());
- }
-
- /** Converts the Calendar into a Shape.
- * The isSet() state of the Calendar is re-instated when done. */
- public UnitNRShape toShape(Calendar cal) {
- // Convert a Calendar into a stack of cell numbers
- final int calPrecField = getCalPrecisionField(cal);//must call first; getters set all fields
- try {
- int[] valStack = new int[maxLevels];//starts at level 1, not 0
- int len = 0;
- if (calPrecField >= Calendar.YEAR) {//year or better precision
- int year = cal.get(Calendar.YEAR);
- int yearAdj = cal.get(Calendar.ERA) == 0 ? AD_YEAR_BASE - (year - 1) : AD_YEAR_BASE + year;
-
- valStack[len++] = yearAdj / 1000_000;
- yearAdj -= valStack[len-1] * 1000_000;
- valStack[len++] = yearAdj / 1000;
- yearAdj -= valStack[len-1] * 1000;
- valStack[len++] = yearAdj;
- for (int level = yearLevel+1; level < FIELD_BY_LEVEL.length; level++) {
- int field = FIELD_BY_LEVEL[level];
- if (field > calPrecField)
- break;
- valStack[len++] = cal.get(field) - cal.getActualMinimum(field);
- }
- }
-
- return toShape(valStack, len);
- } finally {
- clearFieldsAfter(cal, calPrecField);//restore precision state modified by get()
- }
- }
-
- /** Calls {@link #toCalendar(org.apache.lucene.spatial.prefix.tree.NumberRangePrefixTree.UnitNRShape)}. */
- @Override
- public Object toObject(UnitNRShape shape) {
- return toCalendar(shape);
- }
-
- /** Converts the {@link org.apache.lucene.spatial.prefix.tree.NumberRangePrefixTree.UnitNRShape} shape to a
- * corresponding Calendar that is cleared below its level. */
- public Calendar toCalendar(UnitNRShape lv) {
- if (lv.getLevel() == 0)
- return newCal();
- if (comparePrefix(lv, minLV) <= 0) {//shouldn't typically happen; sometimes in a debugger
- return (Calendar) MINCAL.clone();//full precision; truncation would cause underflow
- }
- assert comparePrefix(lv, maxLV) <= 0;
- Calendar cal = newCal();
-
- int yearAdj = lv.getValAtLevel(1) * 1_000_000;
- if (lv.getLevel() > 1) {
- yearAdj += lv.getValAtLevel(2) * 1000;
- if (lv.getLevel() > 2) {
- yearAdj += lv.getValAtLevel(3);
- }
- }
- if (yearAdj > AD_YEAR_BASE) {
- cal.set(Calendar.ERA, 1);
- cal.set(Calendar.YEAR, yearAdj - AD_YEAR_BASE);//setting the year resets the era
- } else {
- cal.set(Calendar.ERA, 0);//we assert this "sticks" at the end
- cal.set(Calendar.YEAR, (AD_YEAR_BASE - yearAdj) + 1);
- }
- for (int level = yearLevel+1; level <= lv.getLevel(); level++) {
- int field = FIELD_BY_LEVEL[level];
- cal.set(field, lv.getValAtLevel(level) + cal.getActualMinimum(field));
- }
- assert yearAdj > AD_YEAR_BASE || ((Calendar)cal.clone()).get(Calendar.ERA) == 0 : "ERA / YEAR underflow";
- return cal;
- }
-
- @Override
- protected String toString(UnitNRShape lv) {
- return toString(toCalendar(lv));
- }
-
- /** Calendar utility method:
- * Formats the calendar to ISO-8601 format, to include proper BC handling (1BC is "0000", 2BC is "-0001", etc.);
- * and WITHOUT a trailing 'Z'.
- * A fully cleared calendar will yield the string "*".
- * The isSet() state of the Calendar is re-instated when done. */
- @SuppressWarnings("fallthrough")
- public String toString(Calendar cal) {
- final int calPrecField = getCalPrecisionField(cal);//must call first; getters set all fields
- if (calPrecField == -1)
- return "*";
- try {
- //TODO not fully optimized; but it's at least not used in 'search'.
- //TODO maybe borrow code from Solr DateUtil (put in Lucene util somewhere), and have it reference this back?
- String pattern = "yyyy-MM-dd'T'HH:mm:ss.SSS";
- int ptnLen = 0;
- switch (calPrecField) {//switch fall-through is deliberate
- case Calendar.MILLISECOND: ptnLen += 4;
- case Calendar.SECOND: ptnLen += 3;
- case Calendar.MINUTE: ptnLen += 3;
- case Calendar.HOUR_OF_DAY: ptnLen += 5;
- case Calendar.DAY_OF_MONTH: ptnLen += 3;
- case Calendar.MONTH: ptnLen += 3;
- case Calendar.YEAR: ptnLen += 4;
- break;
- default: throw new IllegalStateException(""+calPrecField);
- }
- pattern = pattern.substring(0, ptnLen);
- SimpleDateFormat format = new SimpleDateFormat(pattern, Locale.ROOT);
- format.setTimeZone(cal.getTimeZone());
- if (cal.get(Calendar.ERA) == 0) {//BC
- //SDF doesn't do this properly according to ISO-8601
- // Example: 1BC == "0000" (actually 0 AD), 2BC == "-0001", 3BC == "-0002", ...
- final int yearOrig = cal.get(Calendar.YEAR);
- cal.set(Calendar.YEAR, yearOrig-1);
- String str;
- try {
- str = format.format(cal.getTime());
- } finally {
- //reset to what it was
- cal.set(Calendar.ERA, 0);//necessary!
- cal.set(Calendar.YEAR, yearOrig);
- }
- if (yearOrig > 1)
- return "-" + str;
- else
- return "0000" + str.substring(4);
- }
- return format.format(cal.getTime());
- } finally {
- clearFieldsAfter(cal, calPrecField);//restore precision state modified by get()
- }
- }
-
- @Override
- protected UnitNRShape parseUnitShape(String str) throws ParseException {
- return toShape(parseCalendar(str));
- }
-
- /** Calendar utility method:
- * The reverse of {@link #toString(java.util.Calendar)}. It will only set the fields found, leaving
- * the remainder in an un-set state. A leading '-' or '+' is optional (positive assumed), and a
- * trailing 'Z' is also optional.
- * @param str not null and not empty
- * @return not null
- */
- public Calendar parseCalendar(String str) throws ParseException {
- // example: +2014-10-23T21:22:33.159Z
- if (str == null || str.isEmpty())
- throw new IllegalArgumentException("str is null or blank");
- Calendar cal = newCal();
- if (str.equals("*"))
- return cal;
- int offset = 0;//a pointer
- try {
- //year & era:
- int lastOffset = str.charAt(str.length()-1) == 'Z' ? str.length() - 1 : str.length();
- int hyphenIdx = str.indexOf('-', 1);//look past possible leading hyphen
- if (hyphenIdx < 0)
- hyphenIdx = lastOffset;
- int year = Integer.parseInt(str.substring(offset, hyphenIdx));
- cal.set(Calendar.ERA, year <= 0 ? 0 : 1);
- cal.set(Calendar.YEAR, year <= 0 ? -1*year + 1 : year);
- offset = hyphenIdx + 1;
- if (lastOffset < offset)
- return cal;
-
- //NOTE: We aren't validating separator chars, and we unintentionally accept leading +/-.
- // The str.substring()'s hopefully get optimized to be stack-allocated.
-
- //month:
- cal.set(Calendar.MONTH, Integer.parseInt(str.substring(offset, offset+2)) - 1);//starts at 0
- offset += 3;
- if (lastOffset < offset)
- return cal;
- //day:
- cal.set(Calendar.DAY_OF_MONTH, Integer.parseInt(str.substring(offset, offset+2)));
- offset += 3;
- if (lastOffset < offset)
- return cal;
- //hour:
- cal.set(Calendar.HOUR_OF_DAY, Integer.parseInt(str.substring(offset, offset+2)));
- offset += 3;
- if (lastOffset < offset)
- return cal;
- //minute:
- cal.set(Calendar.MINUTE, Integer.parseInt(str.substring(offset, offset+2)));
- offset += 3;
- if (lastOffset < offset)
- return cal;
- //second:
- cal.set(Calendar.SECOND, Integer.parseInt(str.substring(offset, offset+2)));
- offset += 3;
- if (lastOffset < offset)
- return cal;
- //ms:
- cal.set(Calendar.MILLISECOND, Integer.parseInt(str.substring(offset, offset+3)));
- offset += 3;//last one, move to next char
- if (lastOffset == offset)
- return cal;
- } catch (Exception e) {
- ParseException pe = new ParseException("Improperly formatted date: "+str, offset);
- pe.initCause(e);
- throw pe;
- }
- throw new ParseException("Improperly formatted date: "+str, offset);
- }
-
-}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/50a2f754/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/FilterCellIterator.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/FilterCellIterator.java b/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/FilterCellIterator.java
deleted file mode 100644
index e4f50e0..0000000
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/FilterCellIterator.java
+++ /dev/null
@@ -1,61 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.lucene.spatial.prefix.tree;
-
-import com.spatial4j.core.shape.Shape;
-import com.spatial4j.core.shape.SpatialRelation;
-
-import java.util.Iterator;
-
-/**
- * A filtering iterator of Cells. Those not matching the provided shape (disjoint) are
- * skipped. If {@code shapeFilter} is null then all cells are returned.
- *
- * @lucene.internal
- */
-class FilterCellIterator extends CellIterator {
- final Iterator<Cell> baseIter;
- final Shape shapeFilter;
-
- FilterCellIterator(Iterator<Cell> baseIter, Shape shapeFilter) {
- this.baseIter = baseIter;
- this.shapeFilter = shapeFilter;
- }
-
- @Override
- public boolean hasNext() {
- thisCell = null;
- if (nextCell != null)//calling hasNext twice in a row
- return true;
- while (baseIter.hasNext()) {
- nextCell = baseIter.next();
- if (shapeFilter == null) {
- return true;
- } else {
- SpatialRelation rel = nextCell.getShape().relate(shapeFilter);
- if (rel.intersects()) {
- nextCell.setShapeRel(rel);
- if (rel == SpatialRelation.WITHIN)
- nextCell.setLeaf();
- return true;
- }
- }
- }
- return false;
- }
-
-}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/50a2f754/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/GeohashPrefixTree.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/GeohashPrefixTree.java b/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/GeohashPrefixTree.java
deleted file mode 100644
index fa4e987..0000000
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/GeohashPrefixTree.java
+++ /dev/null
@@ -1,162 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.lucene.spatial.prefix.tree;
-
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.List;
-
-import com.spatial4j.core.context.SpatialContext;
-import com.spatial4j.core.io.GeohashUtils;
-import com.spatial4j.core.shape.Point;
-import com.spatial4j.core.shape.Rectangle;
-import com.spatial4j.core.shape.Shape;
-import org.apache.lucene.util.BytesRef;
-
-/**
- * A {@link SpatialPrefixTree} based on
- * <a href="http://en.wikipedia.org/wiki/Geohash">Geohashes</a>.
- * Uses {@link GeohashUtils} to do all the geohash work.
- *
- * @lucene.experimental
- */
-public class GeohashPrefixTree extends LegacyPrefixTree {
-
- /**
- * Factory for creating {@link GeohashPrefixTree} instances with useful defaults
- */
- public static class Factory extends SpatialPrefixTreeFactory {
-
- @Override
- protected int getLevelForDistance(double degrees) {
- GeohashPrefixTree grid = new GeohashPrefixTree(ctx, GeohashPrefixTree.getMaxLevelsPossible());
- return grid.getLevelForDistance(degrees);
- }
-
- @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("maxLevels must be [1-"+MAXP+"] but got "+ maxLevels);
- }
-
- /** Any more than this and there's no point (double lat and lon are the same). */
- public static int getMaxLevelsPossible() {
- return GeohashUtils.MAX_PRECISION;
- }
-
- @Override
- public Cell getWorldCell() {
- return new GhCell(BytesRef.EMPTY_BYTES, 0, 0);
- }
-
- @Override
- public int getLevelForDistance(double dist) {
- if (dist == 0)
- return maxLevels;//short circuit
- final int level = GeohashUtils.lookupHashLenForWidthHeight(dist, dist);
- return Math.max(Math.min(level, maxLevels), 1);
- }
-
- @Override
- protected Cell getCell(Point p, int level) {
- return new GhCell(GeohashUtils.encodeLatLon(p.getY(), p.getX(), level));//args are lat,lon (y,x)
- }
-
- 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;
- }
-
- private class GhCell extends LegacyCell {
-
- 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() && getLevel() < getMaxLevels())//we don't have a leaf byte at max levels (an opt)
- this.geohash = geohash.substring(0, geohash.length() - 1);
- }
-
- GhCell(byte[] bytes, int off, int len) {
- super(bytes, off, len);
- }
-
- @Override
- protected GeohashPrefixTree getGrid() { return GeohashPrefixTree.this; }
-
- @Override
- protected int getMaxLevels() { return maxLevels; }
-
- @Override
- protected void readCell(BytesRef bytesRef) {
- super.readCell(bytesRef);
- geohash = null;
- }
-
- @Override
- public Collection<Cell> getSubCells() {
- String[] hashes = GeohashUtils.getSubGeohashes(getGeohash());//sorted
- List<Cell> cells = new ArrayList<>(hashes.length);
- for (String hash : hashes) {
- cells.add(new GhCell(hash));
- }
- return cells;
- }
-
- @Override
- public int getSubCellsSize() {
- return 32;//8x4
- }
-
- @Override
- protected GhCell getSubCell(Point p) {
- return (GhCell) getGrid().getCell(p, getLevel() + 1);//not performant!
- }
-
- @Override
- public Shape getShape() {
- if (shape == null) {
- shape = GeohashUtils.decodeBoundary(getGeohash(), getGrid().getSpatialContext());
- }
- return shape;
- }
-
- private String getGeohash() {
- if (geohash == null)
- geohash = getTokenBytesNoLeaf(null).utf8ToString();
- return geohash;
- }
-
- }//class GhCell
-
-}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/50a2f754/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/LegacyCell.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/LegacyCell.java b/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/LegacyCell.java
deleted file mode 100644
index 27c56a7..0000000
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/LegacyCell.java
+++ /dev/null
@@ -1,242 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.lucene.spatial.prefix.tree;
-
-import java.util.Collection;
-
-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;
-
-/** The base for the original two SPT's: Geohash and Quad. Don't subclass this for new SPTs.
- * @lucene.internal */
-//public for RPT pruneLeafyBranches code
-public abstract class LegacyCell implements Cell {
-
- // Important: A LegacyCell doesn't share state for getNextLevelCells(), and
- // LegacySpatialPrefixTree assumes this in its simplify tree logic.
-
- private static final byte LEAF_BYTE = '+';//NOTE: must sort before letters & numbers
-
- //Arguably we could simply use a BytesRef, using an extra Object.
- protected byte[] bytes;//generally bigger to potentially hold a leaf
- protected int b_off;
- protected int b_len;//doesn't reflect leaf; same as getLevel()
-
- protected boolean isLeaf;
-
- /**
- * When set via getSubCells(filter), it is the relationship between this cell
- * and the given shape filter. Doesn't participate in shape equality.
- */
- protected SpatialRelation shapeRel;
-
- protected Shape shape;//cached
-
- /** Warning: Refers to the same bytes (no copy). If {@link #setLeaf()} is subsequently called then it
- * may modify bytes. */
- protected LegacyCell(byte[] bytes, int off, int len) {
- this.bytes = bytes;
- this.b_off = off;
- this.b_len = len;
- readLeafAdjust();
- }
-
- protected void readCell(BytesRef bytes) {
- shapeRel = null;
- shape = null;
- this.bytes = bytes.bytes;
- this.b_off = bytes.offset;
- this.b_len = (short) bytes.length;
- readLeafAdjust();
- }
-
- protected void readLeafAdjust() {
- isLeaf = (b_len > 0 && bytes[b_off + b_len - 1] == LEAF_BYTE);
- if (isLeaf)
- b_len--;
- if (getLevel() == getMaxLevels())
- isLeaf = true;
- }
-
- protected abstract SpatialPrefixTree getGrid();
-
- protected abstract int getMaxLevels();
-
- @Override
- public SpatialRelation getShapeRel() {
- return shapeRel;
- }
-
- @Override
- public void setShapeRel(SpatialRelation rel) {
- this.shapeRel = rel;
- }
-
- @Override
- public boolean isLeaf() {
- return isLeaf;
- }
-
- @Override
- public void setLeaf() {
- isLeaf = true;
- }
-
- @Override
- public BytesRef getTokenBytesWithLeaf(BytesRef result) {
- result = getTokenBytesNoLeaf(result);
- if (!isLeaf || getLevel() == getMaxLevels())
- return result;
- if (result.bytes.length < result.offset + result.length + 1) {
- assert false : "Not supposed to happen; performance bug";
- byte[] copy = new byte[result.length + 1];
- System.arraycopy(result.bytes, result.offset, copy, 0, result.length - 1);
- result.bytes = copy;
- result.offset = 0;
- }
- result.bytes[result.offset + result.length++] = LEAF_BYTE;
- return result;
- }
-
- @Override
- public BytesRef getTokenBytesNoLeaf(BytesRef result) {
- if (result == null)
- return new BytesRef(bytes, b_off, b_len);
- result.bytes = bytes;
- result.offset = b_off;
- result.length = b_len;
- return result;
- }
-
- @Override
- public int getLevel() {
- return b_len;
- }
-
- @Override
- public CellIterator getNextLevelCells(Shape shapeFilter) {
- assert getLevel() < getGrid().getMaxLevels();
- if (shapeFilter instanceof Point) {
- LegacyCell cell = getSubCell((Point) shapeFilter);
- cell.shapeRel = SpatialRelation.CONTAINS;
- return new SingletonCellIterator(cell);
- } else {
- return new FilterCellIterator(getSubCells().iterator(), shapeFilter);
- }
- }
-
- /**
- * Performant implementations are expected to implement this efficiently by
- * considering the current cell's boundary.
- * <p>
- * Precondition: Never called when getLevel() == maxLevel.
- * Precondition: this.getShape().relate(p) != DISJOINT.
- */
- protected abstract LegacyCell getSubCell(Point p);
-
- /**
- * Gets the cells at the next grid cell level that covers this cell.
- * Precondition: Never called when getLevel() == maxLevel.
- *
- * @return A set of cells (no dups), sorted, modifiable, not empty, not null.
- */
- protected abstract Collection<Cell> getSubCells();
-
- /**
- * {@link #getSubCells()}.size() -- usually a constant. Should be >=2
- */
- public abstract int getSubCellsSize();
-
- @Override
- public boolean isPrefixOf(Cell c) {
- //Note: this only works when each level uses a whole number of bytes.
- LegacyCell cell = (LegacyCell)c;
- boolean result = sliceEquals(cell.bytes, cell.b_off, cell.b_len, bytes, b_off, b_len);
- assert result == StringHelper.startsWith(c.getTokenBytesNoLeaf(null), getTokenBytesNoLeaf(null));
- return result;
- }
-
- /** Copied from {@link org.apache.lucene.util.StringHelper#startsWith(BytesRef, BytesRef)}
- * which calls this. This is to avoid creating a BytesRef. */
- private static boolean sliceEquals(byte[] sliceToTest_bytes, int sliceToTest_offset, int sliceToTest_length,
- byte[] other_bytes, int other_offset, int other_length) {
- if (sliceToTest_length < other_length) {
- return false;
- }
- int i = sliceToTest_offset;
- int j = other_offset;
- final int k = other_offset + other_length;
-
- while (j < k) {
- if (sliceToTest_bytes[i++] != other_bytes[j++]) {
- return false;
- }
- }
-
- return true;
- }
-
- @Override
- public int compareToNoLeaf(Cell fromCell) {
- LegacyCell b = (LegacyCell) fromCell;
- return compare(bytes, b_off, b_len, b.bytes, b.b_off, b.b_len);
- }
-
- /** Copied from {@link BytesRef#compareTo(BytesRef)}.
- * This is to avoid creating a BytesRef. */
- protected static int compare(byte[] aBytes, int aUpto, int a_length, byte[] bBytes, int bUpto, int b_length) {
- final int aStop = aUpto + Math.min(a_length, b_length);
- while(aUpto < aStop) {
- int aByte = aBytes[aUpto++] & 0xff;
- int bByte = bBytes[bUpto++] & 0xff;
-
- int diff = aByte - bByte;
- if (diff != 0) {
- return diff;
- }
- }
-
- // One is a prefix of the other, or, they are equal:
- return a_length - b_length;
- }
-
- @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 getTokenBytesWithLeaf(null).equals(cell.getTokenBytesWithLeaf(null));
- } else {
- return false;
- }
- }
-
- @Override
- public int hashCode() {
- return getTokenBytesWithLeaf(null).hashCode();
- }
-
- @Override
- public String toString() {
- //this method isn't "normally" called; just in asserts/tests
- return getTokenBytesWithLeaf(null).utf8ToString();
- }
-
-}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/50a2f754/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/LegacyPrefixTree.java
----------------------------------------------------------------------
diff --git a/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/LegacyPrefixTree.java b/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/LegacyPrefixTree.java
deleted file mode 100644
index 672c2fe..0000000
--- a/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/LegacyPrefixTree.java
+++ /dev/null
@@ -1,84 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.lucene.spatial.prefix.tree;
-
-import java.util.Arrays;
-
-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 org.apache.lucene.util.BytesRef;
-
-/** The base for the original two SPT's: Geohash and Quad. Don't subclass this for new SPTs.
- * @lucene.internal */
-abstract class LegacyPrefixTree extends SpatialPrefixTree {
- public LegacyPrefixTree(SpatialContext ctx, int maxLevels) {
- super(ctx, maxLevels);
- }
-
- public double getDistanceForLevel(int level) {
- if (level < 1 || level > getMaxLevels())
- throw new IllegalArgumentException("Level must be in 1 to maxLevels range");
- //TODO cache for each level
- Cell cell = getCell(ctx.getWorldBounds().getCenter(), level);
- Rectangle bbox = cell.getShape().getBoundingBox();
- double width = bbox.getWidth();
- double height = bbox.getHeight();
- //Use standard cartesian hypotenuse. For geospatial, this answer is larger
- // than the correct one but it's okay to over-estimate.
- return Math.sqrt(width * width + height * height);
- }
-
- /**
- * Returns the cell containing point {@code p} at the specified {@code level}.
- */
- protected abstract Cell getCell(Point p, int level);
-
- @Override
- public Cell readCell(BytesRef term, Cell scratch) {
- LegacyCell cell = (LegacyCell) scratch;
- if (cell == null)
- cell = (LegacyCell) getWorldCell();
- cell.readCell(term);
- return cell;
- }
-
- @Override
- public CellIterator getTreeCellIterator(Shape shape, int detailLevel) {
- if (!(shape instanceof Point))
- return super.getTreeCellIterator(shape, detailLevel);
-
- //This specialization is here because the legacy implementations don't have a fast implementation of
- // cell.getSubCells(point). It's fastest here to encode the full bytes for detailLevel, and create
- // subcells from the bytesRef in a loop. This avoids an O(N^2) encode, and we have O(N) instead.
-
- Cell cell = getCell((Point) shape, detailLevel);
- assert cell instanceof LegacyCell;
- BytesRef fullBytes = cell.getTokenBytesNoLeaf(null);
- //fill in reverse order to be sorted
- Cell[] cells = new Cell[detailLevel];
- for (int i = 1; i < detailLevel; i++) {
- fullBytes.length = i;
- Cell parentCell = readCell(fullBytes, null);
- cells[i-1] = parentCell;
- }
- cells[detailLevel-1] = cell;
- return new FilterCellIterator(Arrays.asList(cells).iterator(), null);//null filter
- }
-
-}