Package ghidra.util.database.spatial

# Class AbstractRStarConstraintsTree<DS extends BoundedShape<NS>,DR extends DBTreeDataRecord<DS,NS,T>,NS extends BoundingShape<NS>,NR extends DBTreeNodeRecord<NS>,T,Q extends Query<DS,NS>>

java.lang.Object
ghidra.util.database.spatial.AbstractConstraintsTree<DS,DR,NS,NR,T,Q>
ghidra.util.database.spatial.AbstractRStarConstraintsTree<DS,DR,NS,NR,T,Q>

Type Parameters:
  `DS` - The shape of each data entry
  `DR` - The record type for each data entry
  `NS` - The shape of each node
  `NR` - The record type for each node
  `T` - The type of value stored in a data entry
  `Q` - The type of supported queries

Direct Known Subclasses:
  `Abstract2DRStarTree`, `AbstractHyperRStarTree`

public abstract class AbstractRStarConstraintsTree<DS extends BoundedShape<NS>,DR extends DBTreeDataRecord<DS,NS,T>,NS extends BoundingShape<NS>,NR extends DBTreeNodeRecord<NS>,T,Q extends Query<DS,NS>> extends AbstractConstraintsTree<DS,DR,NS,NR,T,Q>
An R*-Tree implementation of `AbstractConstraintsTree`

The implementation follows The R*-tree: An Efficient and Robust Access Method for Points and Rectangles. Comments in code referring to "the paper", specific sections, or steps of algorithms, are referring specifically to that paper.

- ## Nested Class Summary

  Nested Classes
  Modifier and Type
  Class
  Description
  `protected class`
  `AbstractRStarConstraintsTree.LeastAreaEnlargementThenLeastArea`
  `protected class`
  `AbstractRStarConstraintsTree.LeastDistanceFromCenterToPoint`
  `protected static class`
  `AbstractRStarConstraintsTree.LevelInfo`

  ## Nested classes/interfaces inherited from class ghidra.util.database.spatial.AbstractConstraintsTree

  `AbstractConstraintsTree.TreeRecordVisitor, AbstractConstraintsTree.VisitResult`

- ## Field Summary

  Fields
  Modifier and Type
  Field
  Description
  `protected static final int`
  `CHEAT_OVERLAP_COUNT`
  `protected static final double`
  `FILL_RATE`
  `protected static final int`
  `MAX_LEVELS`
  `protected final int`
  `maxChildren`
  `protected final int`
  `minChildren`
  `protected static final double`
  `REINSERT_RATE`
  `protected final int`
  `reinsertCount`

  ### Fields inherited from class ghidra.util.database.spatial.AbstractConstraintsTree

  `cachedDataChildren, cachedNodeChildren, dataStore, leafLevel, nodeStore, root`

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `AbstractRStarConstraintsTree(DBCachedObjectStoreFactory storeFactory, String tableName, Class<DR> dataType, Class<NR> nodeType, boolean upgradable, int maxChildren)`

- ## Method Summary

  Modifier and Type
  Method
  Description
  `protected void`
  `checkNodeIntegrity(NR n)`
  Check the integrity of a single node entry.
  `protected double`
  `computeOverlap(NS n, Iterable<NR> all, NR ignore)`
  Computes the overlap of a bounding shape (with respect to its siblings)
  `protected Comparator<NS>`
  `doChooseSplitAxis(List<DBTreeRecord<?,? extends NS>> children)`
  `protected int`
  `doChooseSplitIndex(List<DBTreeRecord<?,? extends NS>> children, Comparator<NS> axis)`
  `protected NR`
  `doChooseSubtree(int dstLevel, NS bounds)`
  The ChooseSubtree algorithm as defined in Section 4.1 of the paper.
  `protected void`
  `doInsert(DBTreeRecord<?,? extends NS> entry, AbstractRStarConstraintsTree.LevelInfo levelInfo)`
  `protected DR`
  `doInsertData(DS shape, T value)`
  `protected NR`
  `doOverflowTreatment(NR n, AbstractRStarConstraintsTree.LevelInfo levelInfo)`
  `protected void`
  `doReInsert(NR n, AbstractRStarConstraintsTree.LevelInfo levelInfo)`
  `protected NR`
  `doSplit(NR n)`
  The Split algorithm as defined in Section 4.2 of the paper.
  `protected NR`
  `findChildByMinimumEnlargementCost(NR n, NS bounds)`
  For ChooseSubTree, the part which chooses a leaf node using the minimum area enlargement cost.
  `protected NR`
  `findChildByNearlyMinimumOverlapCost(NR n, NS bounds)`
  For ChooseSubtree, the part which chooses a leaf node using the nearly minimum overlap enlargement cost as defined in Section 4.1 of the paper, at the bottom of page 325.
  `protected abstract List<Comparator<NS>>`
  `getSplitAxes()`

  ### Methods inherited from class ghidra.util.database.spatial.AbstractConstraintsTree

  `asSpatialMap, checkDataIntegrity, checkIntegrity, clear, computeLeafLevel, count, createDataEntry, createNodeEntry, destroySubtree, doAddToCachedChildren, doDecrementDataCount, doDeleteEntry, doFindExact, doRecomputeBounds, doRemoveData, doRemoveFromCachedChildren, doSetParentKey, doUnparentEntry, doUpdateOrDeleteAlongPath, dump, first, getChildrenOf, getDataByKey, getDataChildrenOf, getDataChildrenOf, getDefaultBoundsComparator, getNodeChildrenOf, getNodeChildrenOf, getOrCreateRoot, getParentOf, getUserIndex, init, invalidateCache, isEmpty, iterator, iterator, orderedIterator, resyncMetadata, unionStream, visit, visit, visitAllData`

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

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

- ## Field Details

  - ### MAX_LEVELS

    protected static final int MAX_LEVELS
    See Also:
      - Constant Field Values

  - ### FILL_RATE

    protected static final double FILL_RATE
    See Also:
      - Constant Field Values

  - ### REINSERT_RATE

    protected static final double REINSERT_RATE
    See Also:
      - Constant Field Values

  - ### CHEAT_OVERLAP_COUNT

    protected static final int CHEAT_OVERLAP_COUNT
    See Also:
      - Constant Field Values

  - ### maxChildren

    protected final int maxChildren

  - ### minChildren

    protected final int minChildren

  - ### reinsertCount

    protected final int reinsertCount

- ## Constructor Details

  - ### AbstractRStarConstraintsTree

    public AbstractRStarConstraintsTree(DBCachedObjectStoreFactory storeFactory, String tableName, Class<DR> dataType, Class<NR> nodeType, boolean upgradable, int maxChildren) throws VersionException, IOException
    Throws:
      `VersionException`
      `IOException`

- ## Method Details

  - ### getSplitAxes

    protected abstract List<Comparator<NS>> getSplitAxes()

  - ### doChooseSubtree

    protected NR doChooseSubtree(int dstLevel, NS bounds)
    The ChooseSubtree algorithm as defined in Section 4.1 of the paper.
    Parameters:
      `dstLevel` - the level of the node to choose
      `bounds` - the bounds of the object being inserted
    Returns:
      the leaf node into which the object should be inserted

  - ### findChildByMinimumEnlargementCost

    protected NR findChildByMinimumEnlargementCost(NR n, NS bounds)
    For ChooseSubTree, the part which chooses a leaf node using the minimum area enlargement cost.
    Parameters:
      `n` -
      `bounds` -
    Returns:

  - ### findChildByNearlyMinimumOverlapCost

    protected NR findChildByNearlyMinimumOverlapCost(NR n, NS bounds)
    For ChooseSubtree, the part which chooses a leaf node using the nearly minimum overlap enlargement cost as defined in Section 4.1 of the paper, at the bottom of page 325.

    Ties are resolved using the minimum area enlargement cost.

    Parameters:
      `n` - the node whose children are leaf nodes
      `bounds` - the bounds of the object being inserted
    Returns:
      the leaf node into which the object should be inserted

  - ### computeOverlap

    protected double computeOverlap(NS n, Iterable<NR> all, NR ignore)
    Computes the overlap of a bounding shape (with respect to its siblings)

    This measure is defined in Section 4.1 of the paper.

    Parameters:
      `n` - the shape to measure
      `all` - the sibling nodes (may contain `n`, which is ignored)
      `ignore` - the node whose shape is being considered
    Returns:
      the overlap measure

  - ### doSplit

    protected NR doSplit(NR n)
    The Split algorithm as defined in Section 4.2 of the paper.
    Parameters:
      `n` - the node to split
    Returns:
      the new node (containing the second group)

  - ### doChooseSplitAxis

    protected Comparator<NS> doChooseSplitAxis(List<DBTreeRecord<?,? extends NS>> children)

  - ### doChooseSplitIndex

    protected int doChooseSplitIndex(List<DBTreeRecord<?,? extends NS>> children, Comparator<NS> axis)

  - ### doInsertData

    protected DR doInsertData(DS shape, T value)
    Specified by:
      `doInsertData` in class `AbstractConstraintsTree<DS extends BoundedShape<NS>,DR extends DBTreeDataRecord<DS,NS,T>,NS extends BoundingShape<NS>,NR extends DBTreeNodeRecord<NS>,T,Q extends Query<DS,NS>>`

  - ### doInsert

    protected void doInsert(DBTreeRecord<?,? extends NS> entry, AbstractRStarConstraintsTree.LevelInfo levelInfo)

  - ### doOverflowTreatment

    protected NR doOverflowTreatment(NR n, AbstractRStarConstraintsTree.LevelInfo levelInfo)

  - ### doReInsert

    protected void doReInsert(NR n, AbstractRStarConstraintsTree.LevelInfo levelInfo)

  - ### checkNodeIntegrity

    protected void checkNodeIntegrity(NR n)
    Description copied from class: `AbstractConstraintsTree`
    Check the integrity of a single node entry.

    This method is for tree developers and testers. Override this method if you have additional integrity checks.

    Overrides:
      `checkNodeIntegrity` in class `AbstractConstraintsTree<DS extends BoundedShape<NS>,DR extends DBTreeDataRecord<DS,NS,T>,NS extends BoundingShape<NS>,NR extends DBTreeNodeRecord<NS>,T,Q extends Query<DS,NS>>`
    Parameters:
      `n` - the entry to check