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 booleanprivate boolean(package private) intprivate static final intprivate int(package private) IntRBTNodeprivate IntRBTNodeprivate static final boolean(package private) IntRBTNode -
Constructor Summary
ConstructorsModifierConstructorDescriptionprivateIntRBTNode(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) IntRBTNodecopyNode(IntRBTNode parent) (package private) static IntRBTNodecopyNode(IntRBTNode parent, IntRBTNode n) (package private) static final voiddelete(IntRedBlackTree tree, IntRBTNode z) Delete a given node from the tree.private static final voiddeleteFixup(IntRedBlackTree tree, IntRBTNode x) From CLR.private static final voiddeleteFixupNull(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 IntRBTNodefind(IntRBTNode x, int key) Find a node with a certain key.(package private) static final booleaninsert(IntRedBlackTree tree, IntRBTNode x) Insert a node into a tree.(package private) intkeys(int pos, int[] keys) Fill an array with the keys contained in the tree.private static final IntRBTNodeleftOf(IntRBTNode x) private final voidleftRotate(IntRedBlackTree tree) Left rotation, used to keep the tree balanced.voidprintElements(int indent) voidprintKeys(int indent) private static final IntRBTNodeprivate final voidrightRotate(IntRedBlackTree tree) Right rotation, used to keep the tree balanced.private static final voidsetColor(IntRBTNode x, boolean c) (package private) final IntRBTNodeFind the successor node to this.(package private) int[]toArray(int offset) Create an array representation for the tree under this node.private static final booleantreeInsert(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. SeeIntRBTArrayfor 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
-