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