Package org.apache.lucene.spatial.prefix.tree

Class NumberRangePrefixTree

java.lang.Object

org.apache.lucene.spatial.prefix.tree.SpatialPrefixTree

org.apache.lucene.spatial.prefix.tree.NumberRangePrefixTree

Direct Known Subclasses:

DateRangePrefixTree

public abstract class NumberRangePrefixTree
extends SpatialPrefixTree

A SpatialPrefixTree for single-dimensional numbers and number ranges of fixed precision values (not floating point). Despite its name, the indexed values (and queries) need not actually be ranges, they can be unit instance/values.

Why might you use this instead of Lucene's built-in integer/long support? Here are some reasons with features based on code in this class, or are possible based on this class but require a subclass to fully realize it.

• Index ranges, not just unit instances. This is especially useful when the requirement calls for a multi-valued range.
• Instead of a fixed "precisionStep", this prefixTree can have a customizable number of child values for any prefix (up to 32768). This allows exact alignment of the prefix-tree with typical/expected values, which results in better performance. For example in a Date implementation, every month can get its own dedicated prefix, every day, etc., even though months vary in duration.
• Arbitrary precision, like BigDecimal.
• Standard Lucene integer/long indexing always indexes the full precision of those data types but this one is customizable.

Unlike "normal" spatial components in this module, this special-purpose one only works with Shapes created by the methods on this class, not from any SpatialContext.

See Also:

• NumberRangePrefixTreeStrategy
• LUCENE-5648

WARNING: This API is experimental and might change in incompatible ways in the next release.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected class	NumberRangePrefixTree.NRCell	Most of the PrefixTree implementation is in this one class, which is both the Cell, the CellIterator, and the Shape to reduce object allocation.
static interface	NumberRangePrefixTree.NRShape	Base interface for Shapes this prefix tree supports.
class	NumberRangePrefixTree.SpanUnitsNRShape	A range Shape; based on a pair of NumberRangePrefixTree.UnitNRShape.
static interface	NumberRangePrefixTree.UnitNRShape	A unit value Shape implemented as a stack of numbers, one for each level in the prefix tree.

Field Summary

Fields

Modifier and Type	Field	Description
protected final int[]	levelByTermLen
protected final int[]	maxSubCellsByLevel
protected final int	maxTermLen
protected final int[]	termLenByLevel

Fields inherited from class org.apache.lucene.spatial.prefix.tree.SpatialPrefixTree

ctx, maxLevels

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	NumberRangePrefixTree(int[] maxSubCellsByLevel)

Method Summary

Modifier and Type	Method	Description
protected static int	comparePrefix(NumberRangePrefixTree.UnitNRShape a, NumberRangePrefixTree.UnitNRShape b)	Compares a to b, returning less than 0, 0, or greater than 0, if a is less than, equal to, or greater than b, respectively, up to their common prefix (i.e.
double	getDistanceForLevel(int level)	Given a cell having the specified level, returns the distance from opposite corners.
int	getLevelForDistance(double dist)	Returns the level of the largest grid in which its longest side is less than or equal to the provided distance (in degrees).
int	getNumSubCells(NumberRangePrefixTree.UnitNRShape lv)	Returns the number of sub-cells beneath the given UnitNRShape.
Cell	getWorldCell()	Returns the level 0 cell which encompasses all spatial data.
protected NumberRangePrefixTree.NRCell[]	newCellStack(int levels)
NumberRangePrefixTree.NRShape	parseShape(String str)	Detects a range pattern and parses it, otherwise it's parsed as one shape via parseUnitShape(String).
protected abstract NumberRangePrefixTree.UnitNRShape	parseUnitShape(String str)	Parse a String to a UnitNRShape.
Cell	readCell(BytesRef term, Cell scratch)	This creates a new Cell (or re-using scratch if provided), initialized to the state as read by the bytes.
abstract Object	toObject(NumberRangePrefixTree.UnitNRShape shape)	Converts a UnitNRShape shape to the corresponding type supported by this class, such as a Calendar/BigDecimal.
NumberRangePrefixTree.NRShape	toRangeShape(NumberRangePrefixTree.UnitNRShape startUnit, NumberRangePrefixTree.UnitNRShape endUnit)	Returns a shape that represents the continuous range between start and end.
protected NumberRangePrefixTree.UnitNRShape	toShape(int[] valStack, int len)
String	toString()
protected abstract String	toString(NumberRangePrefixTree.UnitNRShape lv)	A string representation of the UnitNRShape that is parse-able by parseUnitShape(String).
protected static String	toStringUnitRaw(NumberRangePrefixTree.UnitNRShape lv)
abstract NumberRangePrefixTree.UnitNRShape	toUnitShape(Object value)	Converts the value to a unit shape.

Methods inherited from class org.apache.lucene.spatial.prefix.tree.SpatialPrefixTree

getMaxLevels, getSpatialContext, getTreeCellIterator

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Details

maxSubCellsByLevel

protected final int[] maxSubCellsByLevel

termLenByLevel

protected final int[] termLenByLevel

levelByTermLen

protected final int[] levelByTermLen

maxTermLen

protected final int maxTermLen

Constructor Details

NumberRangePrefixTree

protected NumberRangePrefixTree(int[] maxSubCellsByLevel)

Method Details

toUnitShape

public abstract NumberRangePrefixTree.UnitNRShape toUnitShape(Object value)

Converts the value to a unit shape. Doesn't parse strings; see parseShape(String) for that. This is the reverse of toObject(org.apache.lucene.spatial.prefix.tree.NumberRangePrefixTree.UnitNRShape).

toRangeShape

public NumberRangePrefixTree.NRShape toRangeShape(NumberRangePrefixTree.UnitNRShape startUnit,
 NumberRangePrefixTree.UnitNRShape endUnit)

Returns a shape that represents the continuous range between start and end. It will be normalized, and so sometimes a NumberRangePrefixTree.UnitNRShape will be returned, other times a NumberRangePrefixTree.SpanUnitsNRShape will be.

Throws:

IllegalArgumentException - if the arguments are in the wrong order, or if either contains the other (yet they aren't equal).

toObject

public abstract Object toObject(NumberRangePrefixTree.UnitNRShape shape)

Converts a UnitNRShape shape to the corresponding type supported by this class, such as a Calendar/BigDecimal. This is the reverse of toUnitShape(Object).

toString

protected abstract String toString(NumberRangePrefixTree.UnitNRShape lv)

A string representation of the UnitNRShape that is parse-able by parseUnitShape(String).

toStringUnitRaw

protected static String toStringUnitRaw(NumberRangePrefixTree.UnitNRShape lv)

parseShape

public NumberRangePrefixTree.NRShape parseShape(String str)
                                         throws ParseException

Detects a range pattern and parses it, otherwise it's parsed as one shape via parseUnitShape(String). The range pattern looks like this BNF:

   '[' + parseShapeLV + ' TO ' + parseShapeLV + ']'
 

It's the same thing as the toString() of the range shape, notwithstanding range optimization.

Parameters:

str - not null or empty

Returns:

not null

Throws:

ParseException - If there is a problem

parseUnitShape

protected abstract NumberRangePrefixTree.UnitNRShape parseUnitShape(String str)
                                                             throws ParseException

Parse a String to a UnitNRShape. "*" should be the full-range (level 0 shape).

Throws:

ParseException

comparePrefix

protected static int comparePrefix(NumberRangePrefixTree.UnitNRShape a,
 NumberRangePrefixTree.UnitNRShape b)

Compares a to b, returning less than 0, 0, or greater than 0, if a is less than, equal to, or greater than b, respectively, up to their common prefix (i.e. only min(a.levels,b.levels) are compared).

NOTE: This API is for internal purposes only and might change in incompatible ways in the next release.

toString

public String toString()

Overrides:

toString in class SpatialPrefixTree

getLevelForDistance

public int getLevelForDistance(double dist)

Description copied from class: SpatialPrefixTree

Returns the level of the largest grid in which its longest side is less than or equal to the provided distance (in degrees). Consequently dist acts as an error epsilon declaring the amount of detail needed in the grid, such that you can get a grid with just the right amount of precision.

Specified by:

getLevelForDistance in class SpatialPrefixTree

Parameters:

dist - >= 0

Returns:

level [1 to maxLevels]

getDistanceForLevel

public double getDistanceForLevel(int level)

Description copied from class: SpatialPrefixTree

Given a cell having the specified level, returns the distance from opposite corners. Since this might vary depending on where the cell is, this method may over-estimate.

Specified by:

getDistanceForLevel in class SpatialPrefixTree

Parameters:

level - [1 to maxLevels]

Returns:

> 0

toShape

protected NumberRangePrefixTree.UnitNRShape toShape(int[] valStack,
 int len)

getWorldCell

public Cell getWorldCell()

Description copied from class: SpatialPrefixTree

Returns the level 0 cell which encompasses all spatial data. Equivalent to SpatialPrefixTree.readCell(BytesRef,Cell) with no bytes.

Specified by:

getWorldCell in class SpatialPrefixTree

newCellStack

protected NumberRangePrefixTree.NRCell[] newCellStack(int levels)

readCell

public Cell readCell(BytesRef term,
 Cell scratch)

Description copied from class: SpatialPrefixTree

This creates a new Cell (or re-using scratch if provided), initialized to the state as read by the bytes. Warning: An implementation may refer to the same byte array (no copy). If Cell.setLeaf() is subsequently called, it would then modify these bytes.

Specified by:

readCell in class SpatialPrefixTree

getNumSubCells

public int getNumSubCells(NumberRangePrefixTree.UnitNRShape lv)

Returns the number of sub-cells beneath the given UnitNRShape.