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

Change	Modifier and Type	Class	Description
	protected class	AbstractRStarConstraintsTree.LeastAreaEnlargementThenLeastArea
	protected class	AbstractRStarConstraintsTree.LeastDistanceFromCenterToPoint
	protected class	AbstractRStarConstraintsTree.LeastOverlap
	protected static class	AbstractRStarConstraintsTree.LevelInfo
	protected static class	AbstractRStarConstraintsTree.ReInsertInfo

Nested classes/interfaces inherited from class AbstractConstraintsTree

AbstractConstraintsTree.TreeRecordVisitor, AbstractConstraintsTree.VisitResult

Field Summary

Fields

Change	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 AbstractConstraintsTree

cachedDataChildren, cachedNodeChildren, dataStore, leafLevel, nodeStore, root

Constructor Summary

Constructors

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

Method Summary

Change	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 dstLevelFromTop, NS bounds)	The ChooseSubtree algorithm as defined in Section 4.1 of the paper.
	protected void	doInsert(DBTreeRecord<?, ? extends NS> entry, AbstractRStarConstraintsTree.LevelInfo levelInfo)	Insert an entry (data or node) into the tree at the given level
	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()
	protected NR	reRoot(NR n1, NR n2)	Create a new node with the two given nodes.

Methods inherited from class 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, stream, unionStream, visit, visit, visitAllData, visitDirectory, visitLeaf

Methods inherited from class 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 MODIFIED

protected NR doChooseSubtree(int dstLevelFromTop,
 NS bounds)

param 1 renamed: dstLevel → dstLevelFromTop

-NR doChooseSubtree(int dstLevel, NS bounds)

+NR doChooseSubtree(int dstLevelFromTop, NS bounds)

The ChooseSubtree algorithm as defined in Section 4.1 of the paper.

Parameters:

dstLevelFromTop (was: 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)

Insert an entry (data or node) into the tree at the given level

Parameters:

entry - the entry to insert

reRoot NEW

protected NR reRoot(NR n1,
 NR n2)

Create a new node with the two given nodes.

One of the nodes, probably n1 must be the root node. The other must be the node which resulted from splitting the root node.

Parameters:

n1 - the current root node

n2 - the node resulting from splitting the current root node

Returns:

the parent node, which must become the new root node

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