xxl.indexStructures
Class Tree

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

Direct Known Subclasses:

ORTree

public abstract class Tree

extends java.lang.Object

The Tree-class is a generic and highly flexible super-class that implements features used by grow and post-trees. To use this class you have to subclass the inner class Descriptor (which describes the region represented by a given subtree) and Node (which reoresents leaf- and non-leaf nodes). The structure of this class including all abstract methods is as follows:

	public abstract class Tree {
		public static interface Descriptor extends Cloneable {
			public abstract boolean overlaps (Descriptor descriptor);
			public abstract boolean contains (Descriptor descriptor);
			public abstract void union (Descriptor descriptor);
			public abstract boolean equals (Object object);
			public abstract Object clone ();
		}

		protected abstract Object createPostData (Node.SplitInfo splitInfo, IndexEntry newEntry);
		protected abstract Node.SplitInfo createRoot (Object data, Descriptor descriptor);

		protected static class IndexEntry {
		}

		protected static abstract class Node {
			public class SplitInfo {
			}
			protected abstract Iterator entries ();
			protected abstract int number ();
			protected abstract IndexEntry chooseSubtree (Object data, Descriptor descriptor, IndexEntry indexEntry, boolean [] dirty);
			protected abstract void grow (Object data, Descriptor descriptor);
			protected abstract SplitInfo split (Stack path);
			protected abstract void post (Object postData);
		}

		public abstract Iterator query (Function assessment, Function selection, Queue queue, int level);
		protected static abstract class QueryIterator implements Iterator {
			protected static class Candidate {
			}
			protected abstract Iterator expand (Node node, Descriptor nodeDescriptor, Function currentAssessment);
		}
	}

Inner Class Summary

static interface	Tree.Descriptor The Descriptor describes the region represented by a given subtree.
class	Tree.IndexEntry An IndexEntry is a non-leaf node.
class	Tree.Node Node is the class used to represent leaf- and non-leaf nodes.
class	Tree.Query Queries on the Tree are evaluated lazily (ONC).

Field Summary

protected Function	determineContainer Returns the Container that is used to store a new node created by a split operation.
protected Function	getContainer Returns the Container that is used to store the node the IndexEntry is pointing to.
protected Function	getDescriptor Returns the Descriptor of a given data item.
protected Function	getSplitMaxRatio
protected Function	getSplitMinRatio Returns the minimal relative number of entries the node may contain after a split.
protected int	height Number of tree-levels (0 = tree is empty, 1 = tree contains only one node).
protected Function	overflows Returns the maximum capacity of a node.
protected Tree.Descriptor	rootDescriptor The Descriptor of the tree.
protected Tree.IndexEntry	rootEntry The root node of the tree.
protected Function	underflows Returns the current load of a node.

Constructor Summary

Tree()

Method Summary

Tree.IndexEntry	chooseLeaf(java.lang.Object data)
Tree.IndexEntry	chooseLeaf(Tree.Descriptor descriptor, int targetLevel)
protected Tree.IndexEntry	chooseLeaf(Tree.Descriptor descriptor, int targetLevel, java.util.Stack path)
Tree.IndexEntry	createIndexEntry(int parentLevel)
abstract Tree.Node	createNode(int level)
protected Tree.Node	down(java.util.Stack path, Tree.IndexEntry indexEntry)
protected java.util.Map.Entry	grow(java.lang.Object entry)
int	height() Returns height.
protected Tree.IndexEntry	indexEntry(java.util.Stack path)
Tree	initialize(Function getDescriptor, Container container, int minCapacity, int maxCapacity)
Tree	initialize(Function getDescriptor, Function getContainer, Function determineContainer, Function underflows, Function overflows, Function getSplitMinRatio, Function getSplitMaxRatio)
Tree	initialize(Tree.IndexEntry rootEntry, Tree.Descriptor rootDescriptor, int height, Function getDescriptor, Container container, int minCapacity, int maxCapacity)
Tree	initialize(Tree.IndexEntry rootEntry, Tree.Descriptor rootDescriptor, int height, Function getDescriptor, Function getContainer, Function determineContainer, Function underflows, Function overflows, Function getSplitMinRatio, Function getSplitMaxRatio) Creates a new (empty) Tree.
void	insert(java.lang.Object data) Inserts an Object into the tree (This function calls insert on the root-node by default).
protected void	insert(java.lang.Object data, Tree.Descriptor descriptor, int targetLevel) Inserts an Object into the tree.
protected int	level(java.util.Stack path)
protected Tree.Node	node(java.util.Stack path)
java.util.Iterator	query() Returns a new QueryIterator.
java.util.Iterator	query(int level) Returns a new QueryIterator.
java.util.Iterator	query(Tree.Descriptor queryDescriptor) Returns an iterator for all leaf-entries whose descriptors overlap with the given queryDescriptor
java.util.Iterator	query(Tree.Descriptor queryDescriptor, int targetLevel) Returns an iterator for all objects whose descriptors overlap with the given queryDescriptor
Tree.Descriptor	rootDescriptor() Returns rootDescriptor.
Tree.IndexEntry	rootEntry() Returns rootEntry.
protected Tree.IndexEntry	up(java.util.Stack path)
protected void	update(java.util.Stack path)

Methods inherited from class java.lang.Object

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

Field Detail

getDescriptor

protected Function getDescriptor

Returns the Descriptor of a given data item.
Function: Object -> Descriptor.

determineContainer

protected Function determineContainer

Returns the Container that is used to store a new node created by a split operation.
Function Node.SplitInfo -> Container,
Node.SplitInfo: information on the split. If the container of a new root has to be determined, splitInfo.path.isEmpty() == true.

getContainer

protected Function getContainer

Returns the Container that is used to store the node the IndexEntry is pointing to.
Function IndexEntry x int -> Container,
int: level of the node the index entry references

overflows

protected Function overflows

Returns the maximum capacity of a node. The measure has to be chosen by the user.
Function Node -> int

• Example 1: If the entries have equal size getCapacity can return the maximum number of nodes.
• Example 2: If the entries are to be stored on secondary storage getCapacity might return the size in bytes.

See Also:

Tree.Node#getSize

underflows

protected Function underflows

Returns the current load of a node. The measure has to be chosen by the user.
Function Node -> int

• Example 1: If the entries have equal size getSize can return the current number of nodes.
• Example 2: If the entries are to be stored on secondary storage getSize might return the current size in bytes.

See Also:

Tree#getCapacity

getSplitMinRatio

protected Function getSplitMinRatio

Returns the minimal relative number of entries the node may contain after a split. The point of reference is assumed to be the number of entries of the node that was split (before the split).
Function Node -> double

getSplitMaxRatio

protected Function getSplitMaxRatio

rootEntry

protected Tree.IndexEntry rootEntry

The root node of the tree. NOTE: if rootEntry contains a descriptor it will be ignored by the algorithms of Tree.

See Also:

rootDescriptor

rootDescriptor

protected Tree.Descriptor rootDescriptor

The Descriptor of the tree.

See Also:

rootEntry

height

protected int height

Number of tree-levels (0 = tree is empty, 1 = tree contains only one node).

Constructor Detail

Tree

public Tree()

Method Detail

initialize

public Tree initialize(Tree.IndexEntry rootEntry,
                       Tree.Descriptor rootDescriptor,
                       int height,
                       Function getDescriptor,
                       Function getContainer,
                       Function determineContainer,
                       Function underflows,
                       Function overflows,
                       Function getSplitMinRatio,
                       Function getSplitMaxRatio)

Creates a new (empty) Tree. If the Tree is to be created for an existing persistent Tree the Tree has to be initialized by calling Tree.init().

initialize

public Tree initialize(Function getDescriptor,
                       Function getContainer,
                       Function determineContainer,
                       Function underflows,
                       Function overflows,
                       Function getSplitMinRatio,
                       Function getSplitMaxRatio)

initialize

public Tree initialize(Tree.IndexEntry rootEntry,
                       Tree.Descriptor rootDescriptor,
                       int height,
                       Function getDescriptor,
                       Container container,
                       int minCapacity,
                       int maxCapacity)

initialize

public Tree initialize(Function getDescriptor,
                       Container container,
                       int minCapacity,
                       int maxCapacity)

rootEntry

public Tree.IndexEntry rootEntry()

Returns rootEntry.

rootDescriptor

public Tree.Descriptor rootDescriptor()

Returns rootDescriptor.

height

public int height()

Returns height.

createIndexEntry

public Tree.IndexEntry createIndexEntry(int parentLevel)

createNode

public abstract Tree.Node createNode(int level)

insert

public void insert(java.lang.Object data)

Inserts an Object into the tree (This function calls insert on the root-node by default).

insert

protected void insert(java.lang.Object data,
                      Tree.Descriptor descriptor,
                      int targetLevel)

Inserts an Object into the tree. level is the tree-level into which data has to be inserted. If level>0 data is an index entry (This only makes sense for trees whose index nodes support Node.grow()).

chooseLeaf

public Tree.IndexEntry chooseLeaf(java.lang.Object data)

chooseLeaf

public Tree.IndexEntry chooseLeaf(Tree.Descriptor descriptor,
                                  int targetLevel)

chooseLeaf

protected Tree.IndexEntry chooseLeaf(Tree.Descriptor descriptor,
                                     int targetLevel,
                                     java.util.Stack path)

grow

protected java.util.Map.Entry grow(java.lang.Object entry)

indexEntry

protected Tree.IndexEntry indexEntry(java.util.Stack path)

node

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

level

protected int level(java.util.Stack path)

down

protected Tree.Node down(java.util.Stack path,
                         Tree.IndexEntry indexEntry)

update

protected void update(java.util.Stack path)

up

protected Tree.IndexEntry up(java.util.Stack path)

query

public java.util.Iterator query(Tree.Descriptor queryDescriptor,
                                int targetLevel)

Returns an iterator for all objects whose descriptors overlap with the given queryDescriptor

Parameters:

queryDescriptor - describes the query in terms of a descriptor

level - the tree-level to provide the answer-objects

query

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

Returns an iterator for all leaf-entries whose descriptors overlap with the given queryDescriptor

Parameters:

queryDescriptor - describes the query in terms of a descriptor

query

public java.util.Iterator query(int level)

Returns a new QueryIterator.

query

public java.util.Iterator query()

Returns a new QueryIterator.