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
    Modifier and Type | Field and Description
    --- | ---
    `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
    Modifier and Type | Method and Description
    --- | ---
    `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.

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