## 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
`protected com.spatial4j.core.context.SpatialContext` `ctx`
`protected int` `maxLevels`
`protected static Charset` `UTF8`

Constructor Summary
`SpatialPrefixTree(com.spatial4j.core.context.SpatialContext ctx, int maxLevels)`

Method Summary
`static List<String>` `cellsToTokenStrings(Collection<Cell> cells)` Will add the trailing leaf byte for leaves.
`abstract Cell` `getCell(byte[] bytes, int offset, int len)`
`Cell` `getCell(byte[] bytes, int offset, int len, Cell target)`
`protected Cell` `getCell(com.spatial4j.core.shape.Point p, int level)` Returns the cell containing point `p` at the specified `level`.
`abstract Cell` `getCell(String token)` The cell for the specified token.
`List<Cell>` `getCells(com.spatial4j.core.shape.Point p, int detailLevel, boolean inclParents)` A Point-optimized implementation of `getCells(com.spatial4j.core.shape.Shape, int, boolean, boolean)`.
`List<Cell>` `getCells(com.spatial4j.core.shape.Shape shape, int detailLevel, boolean inclParents, boolean simplify)` Gets the intersecting cells for the specified shape, without exceeding detail level.
`double` `getDistanceForLevel(int level)` Given a cell having the specified level, returns the distance from opposite corners.
`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()`
`com.spatial4j.core.context.SpatialContext` `getSpatialContext()`
`Cell` `getWorldCell()` Returns the level 0 cell which encompasses all spatial data.
`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]

### getDistanceForLevel

    public double getDistanceForLevel(int level)

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

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

### getWorldCell

    public Cell getWorldCell()

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

### getCell

    public abstract Cell getCell(String token)

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

### getCell

    public abstract Cell getCell(byte[] bytes,
                                 int offset,
                                 int len)

### getCell

    public final Cell getCell(byte[] bytes,
                              int offset,
                              int len,
                              Cell target)

### getCell

    protected Cell getCell(com.spatial4j.core.shape.Point p,
                           int level)

  Returns the cell containing point `p` at the specified `level`.

### getCells

    public List<Cell> getCells(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 `getCells(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

### getCells

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

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

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

### cellsToTokenStrings

    public static List<String> cellsToTokenStrings(Collection<Cell> cells)

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

Copyright © 2000-2013 Apache Software Foundation. All Rights Reserved.