Class IntRBTNode
java.lang.Object
org.apache.uima.internal.util.rb_trees.IntRBTNode
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
FieldsModifier and TypeFieldDescriptionprivate static final boolean
private boolean
(package private) int
private static final int
private int
(package private) IntRBTNode
private IntRBTNode
private static final boolean
(package private) IntRBTNode
-
Constructor Summary
ConstructorsModifierConstructorDescriptionprivate
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 TypeMethodDescriptionprivate static final boolean
(package private) IntRBTNode
copyNode
(IntRBTNode parent) (package private) static IntRBTNode
copyNode
(IntRBTNode parent, IntRBTNode n) (package private) static final void
delete
(IntRedBlackTree tree, IntRBTNode z) Delete a given node from the tree.private static final void
deleteFixup
(IntRedBlackTree tree, IntRBTNode x) From CLR.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.(package private) static final IntRBTNode
find
(IntRBTNode x, int key) Find a node with a certain key.(package private) static final 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 final IntRBTNode
leftOf
(IntRBTNode x) private final void
leftRotate
(IntRedBlackTree tree) Left rotation, used to keep the tree balanced.void
printElements
(int indent) void
printKeys
(int indent) private static final IntRBTNode
private final void
rightRotate
(IntRedBlackTree tree) Right rotation, used to keep the tree balanced.private static final void
setColor
(IntRBTNode x, boolean c) (package private) final IntRBTNode
Find the successor node to this.(package private) int[]
toArray
(int offset) Create an array representation for the tree under this node.private static final boolean
treeInsert
(IntRedBlackTree tree, IntRBTNode z) Auxiliary function for insert().
-
Field Details
-
RED
private static final boolean RED- See Also:
-
BLACK
private static final boolean BLACK- See Also:
-
key
private int key -
color
private boolean color -
parent
-
left
IntRBTNode left -
right
IntRBTNode right -
element
int element -
indentInc
private static final int indentInc- See Also:
-
-
Constructor Details
-
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 Details
-
find
Find a node with a certain key. Returns null if no such node exists. -
successor
Find the successor node to this. -
insert
Insert a node into a tree. See CLR. -
treeInsert
Auxiliary function for insert(). See CLR. -
leftRotate
Left rotation, used to keep the tree balanced. See CLR. -
rightRotate
Right rotation, used to keep the tree balanced. See CLR. -
delete
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
From CLR. x must not be null. -
deleteFixupNull
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
-
setColor
-
leftOf
-
rightOf
-
printKeys
public void printKeys(int indent) -
printElements
public void printElements(int indent) -
copyNode
-
copyNode
-