Package org.apache.uima.internal.util.rb_trees

Class RBTNode<T>

java.lang.Object

org.apache.uima.internal.util.rb_trees.RBTNode<T>

class RBTNode<T>
extends java.lang.Object

Node used in RedBlackTree, holds int Object pairs and links Red-Black Tree node. Not for public use. Use the interface in RedBlackTree instead. This should probably be an internal class to RedBlackTree, but it's easier to read in a seperate file. See comments in RedBlackTree.

Field Summary

Fields

Modifier and Type	Field	Description
private static boolean	BLACK
private boolean	color
(package private) T	element
private static int	indentInc
private int	key
(package private) RBTNode<T>	left
private RBTNode<T>	parent
private static boolean	RED
(package private) RBTNode<T>	right

Constructor Summary

Constructors

Modifier	Constructor	Description
private	RBTNode(int key, boolean color, RBTNode<T> parent, RBTNode<T> left, RBTNode<T> right, T element)	The real constructor, used only internally.
(package private)	RBTNode(int key, T element)	The standard constructor as used by RedBlackTree.

Method Summary

Modifier and Type	Method	Description
private static <T> boolean	colorOf(RBTNode<T> x)
(package private) static <T> void	delete(RedBlackTree<T> tree, RBTNode<T> z)	Delete a given node from the tree.
private static <T> void	deleteFixup(RedBlackTree<T> tree, RBTNode<T> x)	From CLR.
private static <T> void	deleteFixupNull(RedBlackTree<T> tree, RBTNode<T> x)	Like deleteFixup(), only that the node we should be working on is null, and we actually hand in the node's mother.
(package private) static <T> RBTNode<T>	find(RBTNode<T> x, int key)	Find a node with a certain key.
(package private) void	getBinaryTree(BinaryTree tree)
(package private) static <T> boolean	insert(RedBlackTree<T> tree, RBTNode<T> x)	Insert a node into a tree.
(package private) int	keys(int pos, int[] keys)	Fill an array with the keys contained in the tree.
private static <T> RBTNode<T>	leftOf(RBTNode<T> x)
private void	leftRotate(RedBlackTree<T> tree)	Left rotation, used to keep the tree balanced.
void	printElements(int indent)
void	printKeys(int indent)
private static <T> RBTNode<T>	rightOf(RBTNode<T> x)
private void	rightRotate(RedBlackTree<T> tree)	Right rotation, used to keep the tree balanced.
private static <T> void	setColor(RBTNode<T> x, boolean c)
(package private) RBTNode<T>	successor()	Find the successor node to this.
private static <T> boolean	treeInsert(RedBlackTree<T> tree, RBTNode<T> z)	Auxiliary function for insert().

Methods inherited from class java.lang.Object

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

Field Detail

RED

private static final boolean RED

See Also:

Constant Field Values

BLACK

private static final boolean BLACK

See Also:

Constant Field Values

key

private int key

color

private boolean color

parent

private RBTNode<T> parent

left

RBTNode<T> left

right

RBTNode<T> right

element

T element

indentInc

private static final int indentInc

See Also:

Constant Field Values

Constructor Detail

RBTNode

private RBTNode(int key,
                boolean color,
                RBTNode<T> parent,
                RBTNode<T> left,
                RBTNode<T> right,
                T element)

The real constructor, used only internally.

RBTNode

RBTNode(int key,
        T element)

The standard constructor as used by RedBlackTree.

Parameters:

key - The key to be inserted.

element - The value to be inserted.

Method Detail

find

static final <T> RBTNode<T> find(RBTNode<T> x,
                                 int key)

Find a node with a certain key. Returns null if no such node exists.

successor

final RBTNode<T> successor()

Find the successor node to this.

insert

static final <T> boolean insert(RedBlackTree<T> tree,
                                RBTNode<T> x)

Insert a node into a tree. See CLR.

treeInsert

private static final <T> boolean treeInsert(RedBlackTree<T> tree,
                                            RBTNode<T> z)

Auxiliary function for insert(). See CLR.

leftRotate

private final void leftRotate(RedBlackTree<T> tree)

Left rotation, used to keep the tree balanced. See CLR.

rightRotate

private final void rightRotate(RedBlackTree<T> tree)

Right rotation, used to keep the tree balanced. See CLR.

delete

static final <T> void delete(RedBlackTree<T> tree,
                             RBTNode<T> z)

Delete a given node from the tree. The node must be contained in the tree! Our code is more complicated than CLR because we don't use a NIL sentinel.

deleteFixup

private static final <T> void deleteFixup(RedBlackTree<T> tree,
                                          RBTNode<T> x)

From CLR. x must not be null.

deleteFixupNull

private static final <T> void deleteFixupNull(RedBlackTree<T> tree,
                                              RBTNode<T> x)

Like deleteFixup(), only that the node we should be working on is null, and we actually hand in the node's mother. Special case because we don't use sentinels.

keys

int keys(int pos,
         int[] keys)

Fill an array with the keys contained in the tree. The array must at least have the size of the tree! Returns the size of the tree, for internal reasons.

colorOf

private static final <T> boolean colorOf(RBTNode<T> x)

setColor

private static final <T> void setColor(RBTNode<T> x,
                                       boolean c)

leftOf

private static final <T> RBTNode<T> leftOf(RBTNode<T> x)

rightOf

private static final <T> RBTNode<T> rightOf(RBTNode<T> x)

printKeys

public void printKeys(int indent)

printElements

public void printElements(int indent)

getBinaryTree

void getBinaryTree(BinaryTree tree)