org.apache.lucene.spatial.prefix.tree

## Class SpatialPrefixTree

- java.lang.Object
- - org.apache.lucene.spatial.prefix.tree.SpatialPrefixTree

Direct Known Subclasses:
  GeohashPrefixTree, QuadPrefixTree

    public abstract class SpatialPrefixTree
    extends Object

A spatial Prefix Tree, or Trie, which decomposes shapes into prefixed strings at variable lengths corresponding to variable precision. Each string corresponds to a rectangular spatial region. This approach is also referred to "Grids", "Tiles", and "Spatial Tiers".

Implementations of this class should be thread-safe and immutable once initialized.

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

### Field Summary

Fields
`protected com.spatial4j.core.context.SpatialContext` `ctx`
`protected int` `maxLevels`
`protected static Charset` `UTF8`

### Constructor Summary

Constructors
Constructor and Description
`SpatialPrefixTree(com.spatial4j.core.context.SpatialContext ctx, int maxLevels)`

### Method Summary

Methods
`abstract 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` `getMaxLevels()`
`abstract Node` `getNode(byte[] bytes, int offset, int len)`
`Node` `getNode(byte[] bytes, int offset, int len, Node target)`
`protected Node` `getNode(com.spatial4j.core.shape.Point p, int level)`
`abstract Node` `getNode(String token)` The cell for the specified token.
`List<Node>` `getNodes(com.spatial4j.core.shape.Point p, int detailLevel, boolean inclParents)` A Point-optimized implementation of `getNodes(com.spatial4j.core.shape.Shape, int, boolean, boolean)`.
`List<Node>` `getNodes(com.spatial4j.core.shape.Shape shape, int detailLevel, boolean inclParents, boolean simplify)` Gets the intersecting cells for the specified shape, without exceeding detail level.
`com.spatial4j.core.context.SpatialContext` `getSpatialContext()`
`Node` `getWorldNode()` Returns the level 0 cell which encompasses all spatial data.
`static List<String>` `nodesToTokenStrings(Collection<Node> nodes)` Will add the trailing leaf byte for leaves.
`String` `toString()`

### Methods inherited from class java.lang.Object

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

### Field Detail

#### UTF8

    protected static final Charset UTF8

#### maxLevels

    protected final int maxLevels

#### ctx

    protected final com.spatial4j.core.context.SpatialContext ctx

### Constructor Detail

#### SpatialPrefixTree

    public SpatialPrefixTree(com.spatial4j.core.context.SpatialContext ctx,
                     int maxLevels)

### Method Detail

#### getSpatialContext

    public com.spatial4j.core.context.SpatialContext getSpatialContext()

#### getMaxLevels

    public int getMaxLevels()

#### toString

    public String toString()

Overrides:
  `toString` in class `Object`

#### getLevelForDistance

    public abstract 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). 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.

Parameters:
  `dist` - >= 0
Returns:
  level [1 to maxLevels]

#### getWorldNode

    public Node getWorldNode()

Returns the level 0 cell which encompasses all spatial data. Equivalent to `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?

#### getNode

    public abstract Node getNode(String token)

The cell for the specified token. The empty string should be equal to `getWorldNode()`. Precondition: Never called when token length > maxLevel.

#### getNode

    public abstract Node getNode(byte[] bytes,
               int offset,
               int len)

#### getNode

    public final Node getNode(byte[] bytes,
               int offset,
               int len,
               Node target)

#### getNode

    protected Node getNode(com.spatial4j.core.shape.Point p,
               int level)

#### getNodes

    public List<Node> getNodes(com.spatial4j.core.shape.Shape shape,
                      int detailLevel,
                      boolean inclParents,
                      boolean simplify)

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.

This implementation checks if shape is a Point and if so returns `getNodes(com.spatial4j.core.shape.Point, int, boolean)`.

Parameters:
  `shape` - the shape; non-null
  `detailLevel` - the maximum detail level to get cells for
  `inclParents` - if true then all parent cells of leaves are returned too. The top world cell is never returned.
  `simplify` - for non-point shapes, this will simply/aggregate sets of complete leaves in a cell to its parent, resulting in ~20-25% fewer cells.
Returns:
  a set of cells (no dups), sorted, immutable, non-null

#### getNodes

    public List<Node> getNodes(com.spatial4j.core.shape.Point p,
                      int detailLevel,
                      boolean inclParents)

A Point-optimized implementation of `getNodes(com.spatial4j.core.shape.Shape, int, boolean, boolean)`. That method in facts calls this for points.

This implementation depends on `getNode(String)` being fast, as its called repeatedly when incPlarents is true.

#### nodesToTokenStrings

    public static List<String> nodesToTokenStrings(Collection<Node> nodes)

Will add the trailing leaf byte for leaves. This isn't particularly efficient.