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

Class IntRBTNode

java.lang.Object

org.apache.uima.internal.util.rb_trees.IntRBTNode

class IntRBTNode
extends java.lang.Object

Integer Red-Black Tree node. Not for public use. Use the interface in IntRedBlackTree instead. This should probably be an internal class to IntRedBlackTree, but it's easier to read in a seperate file. See comments in IntRedBlackTree.

Field Summary

Fields

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

Constructor Summary

Constructors

Modifier	Constructor	Description
private	IntRBTNode(int key, boolean color, IntRBTNode parent, IntRBTNode left, IntRBTNode right, int element)	The real constructor, used only internally.
(package private)	IntRBTNode(int key, int element)	The standard constructor as used by IntRedBlackTree.

Method Summary

Modifier and Type	Method	Description
private static boolean	colorOf(IntRBTNode x)
(package private) IntRBTNode	copyNode(IntRBTNode parent)
(package private) static IntRBTNode	copyNode(IntRBTNode parent, IntRBTNode n)
(package private) static void	delete(IntRedBlackTree tree, IntRBTNode z)	Delete a given node from the tree.
private static void	deleteFixup(IntRedBlackTree tree, IntRBTNode x)	From CLR.
private static void	deleteFixupNull(IntRedBlackTree tree, IntRBTNode 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 IntRBTNode	find(IntRBTNode x, int key)	Find a node with a certain key.
(package private) static boolean	insert(IntRedBlackTree tree, IntRBTNode 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 IntRBTNode	leftOf(IntRBTNode x)
private void	leftRotate(IntRedBlackTree tree)	Left rotation, used to keep the tree balanced.
void	printElements(int indent)
void	printKeys(int indent)
private static IntRBTNode	rightOf(IntRBTNode x)
private void	rightRotate(IntRedBlackTree tree)	Right rotation, used to keep the tree balanced.
private static void	setColor(IntRBTNode x, boolean c)
(package private) IntRBTNode	successor()	Find the successor node to this.
(package private) int[]	toArray(int offset)	Create an array representation for the tree under this node.
private static boolean	treeInsert(IntRedBlackTree tree, IntRBTNode 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 IntRBTNode parent

left

IntRBTNode left

right

IntRBTNode right

element

int element

indentInc

private static final int indentInc

See Also:

Constant Field Values

Constructor Detail

IntRBTNode

private IntRBTNode(int key,
                   boolean color,
                   IntRBTNode parent,
                   IntRBTNode left,
                   IntRBTNode right,
                   int element)

The real constructor, used only internally.

IntRBTNode

IntRBTNode(int key,
           int element)

The standard constructor as used by IntRedBlackTree.

Parameters:

key - The key to be inserted.

element - The value to be inserted.

Method Detail

find

static final IntRBTNode find(IntRBTNode x,
                             int key)

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

successor

final IntRBTNode successor()

Find the successor node to this.

insert

static final boolean insert(IntRedBlackTree tree,
                            IntRBTNode x)

Insert a node into a tree. See CLR.

treeInsert

private static final boolean treeInsert(IntRedBlackTree tree,
                                        IntRBTNode z)

Auxiliary function for insert(). See CLR.

leftRotate

private final void leftRotate(IntRedBlackTree tree)

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

rightRotate

private final void rightRotate(IntRedBlackTree tree)

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

delete

static final void delete(IntRedBlackTree tree,
                         IntRBTNode 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 void deleteFixup(IntRedBlackTree tree,
                                      IntRBTNode x)

From CLR. x must not be null.

deleteFixupNull

private static final void deleteFixupNull(IntRedBlackTree tree,
                                          IntRBTNode 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.

toArray

int[] toArray(int offset)

Create an array representation for the tree under this node. See IntRBTArray for a definition of the resulting array format.

Parameters:

offset - See IntRedBlackTree.toArray() for comments.

Returns:

The generated array.

colorOf

private static final boolean colorOf(IntRBTNode x)

setColor

private static final void setColor(IntRBTNode x,
                                   boolean c)

leftOf

private static final IntRBTNode leftOf(IntRBTNode x)

rightOf

private static final IntRBTNode rightOf(IntRBTNode x)

printKeys

public void printKeys(int indent)

printElements

public void printElements(int indent)

copyNode

IntRBTNode copyNode(IntRBTNode parent)

copyNode

static IntRBTNode copyNode(IntRBTNode parent,
                           IntRBTNode n)