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

    All Methods Instance Methods Concrete Methods
    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`

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