xxl.indexStructures
Class Tree.Node

java.lang.Object
  |
  +--xxl.indexStructures.Tree.Node

Direct Known Subclasses:

ORTree.Node

public abstract class Tree.Node

extends java.lang.Object

Node is the class used to represent leaf- and non-leaf nodes. Nodes are stored in Containers.

See Also:

Tree.determineContainer, Tree.getContainer

Inner Class Summary

class

Tree.Node.SplitInfo SplitInfo contains information on a split.

Field Summary

protected int

level The maximum distance to the leaves of the subtree (i.e.

Constructor Summary

Tree.Node()

Method Summary

protected abstract Tree.IndexEntry	chooseSubtree(Tree.Descriptor descriptor, java.util.Stack path) Chooses the subtree which is followed during an insert operation.
protected Tree.IndexEntry	chooseSubtree(Tree.Descriptor descriptor, java.util.Stack path, java.util.Set forbiddenEntries) Chooses the subtree which is followed during an insert operation.
abstract java.util.Iterator	descriptors(Tree.Descriptor nodeDescriptor) Returns an Iterator pointing to the descriptors of each entry in this node
abstract java.util.Iterator	entries() Returns an Iterator pointing to all entries stored in this node.
protected abstract void	grow(java.lang.Object data, java.util.Stack path) Inserts data into the current node.
Tree.Node	initialize(int level)
protected abstract Tree.Node.SplitInfo	initialize(java.lang.Object entry)
int	level() Returns the level the node is located on.
abstract int	number() Returns the number of Entries that are currently stored in this Node.
protected boolean	overflows() Returns true if the node contains more elements then its capacity allows.
protected abstract void	post(Tree.Node.SplitInfo splitInfo, Tree.IndexEntry newIndexEntry) Updates the current node with the information created by postData().
abstract java.util.Iterator	query(Tree.Descriptor queryDescriptor) Returns an Iterator of entries whose descriptors overlap with the queryDescriptor.
protected Tree.Node	redressOverflow(java.util.Stack path)
protected abstract Tree.Node.SplitInfo	split(java.util.Stack path) Splits the current node (i.e..
protected int	splitMaxNumber() Returns the maximal number of entries that stay in the node when the node is split.
protected double	splitMaxRatio() Returns Tree.getSplitMaxRatio().
protected int	splitMinNumber() Returns the minimal number of entries that stay in the node when the node is split.
protected double	splitMinRatio() Returns Tree.getSplitMinRatio().
protected boolean	underflows() Returns true if the node contains more elements then its capacity allows.

Methods inherited from class java.lang.Object

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

Field Detail

level

protected int level

The maximum distance to the leaves of the subtree (i.e. for leafs level == 0).

Constructor Detail

Tree.Node

public Tree.Node()

Method Detail

initialize

public Tree.Node initialize(int level)

initialize

protected abstract Tree.Node.SplitInfo initialize(java.lang.Object entry)

redressOverflow

protected Tree.Node redressOverflow(java.util.Stack path)

level

public int level()

Returns the level the node is located on.

number

public abstract int number()

Returns the number of Entries that are currently stored in this Node.

entries

public abstract java.util.Iterator entries()

Returns an Iterator pointing to all entries stored in this node.

descriptors

public abstract java.util.Iterator descriptors(Tree.Descriptor nodeDescriptor)

Returns an Iterator pointing to the descriptors of each entry in this node

Parameters:

nodeDescriptor - the descriptor of this node

tree - the tree the node belongs to

query

public abstract java.util.Iterator query(Tree.Descriptor queryDescriptor)

Returns an Iterator of entries whose descriptors overlap with the queryDescriptor.

Parameters:

queryDescriptor - the descriptor describing the query

tree - the tree the node belongs to

chooseSubtree

protected abstract Tree.IndexEntry chooseSubtree(Tree.Descriptor descriptor,
                                                 java.util.Stack path)

Chooses the subtree which is followed during an insert operation.

Parameters:

descriptor - the Descriptor of data

indexEntry - TODO

dirty - is a reference-parameter (array.length == 1) that should be set to true if the current node was modified by this function

chooseSubtree

protected Tree.IndexEntry chooseSubtree(Tree.Descriptor descriptor,
                                        java.util.Stack path,
                                        java.util.Set forbiddenEntries)

Chooses the subtree which is followed during an insert operation.

Parameters:

descriptor - the Descriptor of data

indexEntry - TODO

dirty - is a reference-parameter (array.length == 1) that should be set to true if the current node was modified by this function

grow

protected abstract void grow(java.lang.Object data,
                             java.util.Stack path)

Inserts data into the current node. If level>0 data is an index entry (this only makes sense for trees whose index-nodes support grow()).

Parameters:

descriptor - the Descriptor of data

split

protected abstract Tree.Node.SplitInfo split(java.util.Stack path)

Splits the current node (i.e.. overflows() == true). A new node is created but no handle is reserved for this node in its container (i.e. container.insert() or container.reserve() are not called at this stage). This means that no index entry for this node is passed to its parent-node.

Parameters:

indexEntry - TODO

tree - the current tree

path - the nodes already visited during this insert

post

protected abstract void post(Tree.Node.SplitInfo splitInfo,
                             Tree.IndexEntry newIndexEntry)

Updates the current node with the information created by postData(). e.g. creates an index-entry for the new node.

Parameters:

postData - the information created by postData()

underflows

protected boolean underflows()

Returns true if the node contains more elements then its capacity allows.

overflows

protected boolean overflows()

Returns true if the node contains more elements then its capacity allows.

splitMinRatio

protected double splitMinRatio()

Returns Tree.getSplitMinRatio().

splitMaxRatio

protected double splitMaxRatio()

Returns Tree.getSplitMaxRatio().

splitMinNumber

protected int splitMinNumber()

Returns the minimal number of entries that stay in the node when the node is split.

splitMaxNumber

protected int splitMaxNumber()

Returns the maximal number of entries that stay in the node when the node is split.