Class IntRBTNode

java.lang.Object
org.apache.uima.internal.util.rb_trees.IntRBTNode

class IntRBTNode extends 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 Details

  • 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

      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)