org.apache.lucene.spatial.prefix.tree

Class PackedQuadPrefixTree

java.lang.Object

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

org.apache.lucene.spatial.prefix.tree.QuadPrefixTree

org.apache.lucene.spatial.prefix.tree.PackedQuadPrefixTree

public class PackedQuadPrefixTree
extends QuadPrefixTree

Uses a compact binary representation of 8 bytes to encode a spatial quad trie. The binary representation is as follows:

 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDL

 Where C = Cell bits (2 per quad)
       D = Depth bits (5 with max of 29 levels)
       L = isLeaf bit
 

It includes a built-in "pruneLeafyBranches" setting (true by default) similar to RecursivePrefixTreeStrategy.setPruneLeafyBranches(boolean) although this one only prunes at the target detail level (where it has the most effect). Usually you should disable RPT's prune, since it is very memory in-efficient.

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

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	PackedQuadPrefixTree.Factory Factory for creating PackedQuadPrefixTree instances with useful defaults.
protected class	PackedQuadPrefixTree.PackedQuadCell See binary representation in the javadocs of PackedQuadPrefixTree.
protected class	PackedQuadPrefixTree.PrefixTreeIterator This is a streamlined version of TreeCellIterator, with built-in support to prune at detailLevel (but not recursively upwards).

Nested classes/interfaces inherited from class org.apache.lucene.spatial.prefix.tree.QuadPrefixTree

QuadPrefixTree.QuadCell

Field Summary

Fields

Modifier and Type	Field and Description
protected boolean	leafyPrune
static int	MAX_LEVELS_POSSIBLE
protected static byte[]	QUAD

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

DEFAULT_MAX_LEVELS, gridH, gridW, robust, xmax, xmid, xmin, ymax, ymid, ymin

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

ctx, maxLevels

Constructor Summary

Constructors

Constructor and Description
PackedQuadPrefixTree(org.locationtech.spatial4j.context.SpatialContext ctx, int maxLevels)

Method Summary

Modifier and Type	Method and Description
protected void	buildNotRobustly(double x, double y, int level, List<Cell> matches, long term, org.locationtech.spatial4j.shape.Shape shape, int maxLevel)
protected void	checkBattenbergNotRobustly(byte quad, double cx, double cy, int level, List<Cell> matches, long term, org.locationtech.spatial4j.shape.Shape shape, int maxLevel)
Cell	getCell(org.locationtech.spatial4j.shape.Point p, int level) Returns the cell containing point p at the specified level.
double	getDistanceForLevel(int level) Given a cell having the specified level, returns the distance from opposite corners.
CellIterator	getTreeCellIterator(org.locationtech.spatial4j.shape.Shape shape, int detailLevel) Gets the intersecting cells for the specified shape, without exceeding detail level.
Cell	getWorldCell() Returns the level 0 cell which encompasses all spatial data.
boolean	isPruneLeafyBranches()
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.
void	setPruneLeafyBranches(boolean pruneLeafyBranches) Like RecursivePrefixTreeStrategy.setPruneLeafyBranches(boolean) but more memory efficient and only applies to the detailLevel, where it has the most effect.
String	toString()

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

battenberg, checkBattenbergNotRobustly, getLevelForDistance, printInfo

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

getMaxLevels, getSpatialContext

Methods inherited from class java.lang.Object

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

Field Detail

MAX_LEVELS_POSSIBLE

public static final int MAX_LEVELS_POSSIBLE

See Also:

Constant Field Values

QUAD

protected static final byte[] QUAD

leafyPrune

protected boolean leafyPrune

Constructor Detail

PackedQuadPrefixTree

public PackedQuadPrefixTree(org.locationtech.spatial4j.context.SpatialContext ctx,
                            int maxLevels)

Method Detail

toString

public String toString()

Overrides:

toString in class SpatialPrefixTree

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.

Overrides:

getWorldCell in class QuadPrefixTree

getCell

public Cell getCell(org.locationtech.spatial4j.shape.Point p,
                    int level)

Returns the cell containing point p at the specified level.

Overrides:

getCell in class QuadPrefixTree

buildNotRobustly

protected void buildNotRobustly(double x,
                                double y,
                                int level,
                                List<Cell> matches,
                                long term,
                                org.locationtech.spatial4j.shape.Shape shape,
                                int maxLevel)

checkBattenbergNotRobustly

protected void checkBattenbergNotRobustly(byte quad,
                                          double cx,
                                          double cy,
                                          int level,
                                          List<Cell> matches,
                                          long term,
                                          org.locationtech.spatial4j.shape.Shape shape,
                                          int maxLevel)

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.

getTreeCellIterator

public CellIterator getTreeCellIterator(org.locationtech.spatial4j.shape.Shape shape,
                                        int detailLevel)

Description copied from class: SpatialPrefixTree

Gets the intersecting cells for the specified shape, without exceeding detail level. If a cell is within the query shape then it's marked as a leaf and none of its children are added. For cells at detailLevel, they are marked as leaves too, unless it's a point.

IMPORTANT: Cells returned from the iterator can be re-used for cells at the same level. So you can't simply iterate to subsequent cells and still refer to the former cell nor the bytes returned from the former cell, unless you know the former cell is a parent.

Parameters:

shape - the shape; possibly null but the caller should liberally call remove() if so.

detailLevel - the maximum detail level to get cells for

Returns:

the matching cells

isPruneLeafyBranches

public boolean isPruneLeafyBranches()

setPruneLeafyBranches

public void setPruneLeafyBranches(boolean pruneLeafyBranches)

Like RecursivePrefixTreeStrategy.setPruneLeafyBranches(boolean) but more memory efficient and only applies to the detailLevel, where it has the most effect.

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