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
All Methods Static Methods Instance Methods Concrete Methods 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().
-
-
-
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. SeeIntRBTArray
for a definition of the resulting array format.- Parameters:
offset
- SeeIntRedBlackTree.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)
-
-