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

Class IntRBTArray

java.lang.Object
org.apache.uima.internal.util.rb_trees.IntRBTArray
public class IntRBTArray extends Object
Helper class to read array-based binary search trees with integers as keys and values. No write access to the tree is provided. See IntRedBlackTree on how to generate such an array representation. The name is a bit of a misnomer, since nothing in this class is specific to red-black trees.

Suppose i is the position of the first cell encoding a tree node in array a. Then the expected memory layout of a is:

  • a[i] is the key of the node
  • a[i+1] is the element of the node
  • a[i+2] is one of:
    • IntRBTArray.TERMINAL: this is a terminal node
    • IntRBTArray.LEFTDTR: this node only has a left daughter, so a[i+3] is the first cell of the left daughter node
    • IntRBTArray.RIGHTDTR: this node only has a right daughter, so a[i+3] is the first cell of the right daughter node
    • IntRBTArray.TWODTRS: this node has two daughters. a[i+3] contains the address of the right daughter, and a[i+4] is the start of the left daughter node

Note that the array from which an IntRBTArray object is constructed can contain other data as well. However, we assume that the addressing (the right daughter addresses, to be precise), must be absolute (i.e., not relative to some starting point within the array).

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final int
    LEFTDTR
    Code for a node with only a left daughter.
    static final int
    RIGHTDTR
    Code for a node with only a right daughter.
    static final int
    TERMINAL
    Code for a terminal node in the array.
    static final int
    TWODTRS
    Code for a node with two daughters.

  • Constructor Summary

    Constructors
    Constructor
    Description
    IntRBTArray(int[] array)
    This constructor assumes that the root node is located at 0.
    IntRBTArray(int[] array, int start)
    Constructor that takes a start point as parameter.

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    get(int i)
    Retrieve the value for a certain key.
    int
    getPosition(int i)
    Get the position of a value for a key.
    void
    setRootAddress(int start)
    Set the address of the root node of the tree.
    int[]
    toArray()
    Getter for the internal array.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • TERMINAL

      public static final int TERMINAL
      Code for a terminal node in the array.
      See Also:

    • LEFTDTR

      public static final int LEFTDTR
      Code for a node with only a left daughter.
      See Also:

    • RIGHTDTR

      public static final int RIGHTDTR
      Code for a node with only a right daughter.
      See Also:

    • TWODTRS

      public static final int TWODTRS
      Code for a node with two daughters.
      See Also:

  • Constructor Details

    • IntRBTArray

      public IntRBTArray(int[] array, int start)
      Constructor that takes a start point as parameter.
      Parameters:
      array - The array containing the search tree.
      start - Address of the root node of the tree.

    • IntRBTArray

      public IntRBTArray(int[] array)
      This constructor assumes that the root node is located at 0.
      Parameters:
      array - The array containing the search tree.

  • Method Details

    • toArray

      public int[] toArray()
      Getter for the internal array.
      Returns:
      The internal array.

    • setRootAddress

      public void setRootAddress(int start)
      Set the address of the root node of the tree.
      Parameters:
      start - the address.

    • get

      public int get(int i) throws NoSuchElementException
      Retrieve the value for a certain key.
      Parameters:
      i - The input key.
      Returns:
      The value, if key was found.
      Throws:
      NoSuchElementException - If the key is not defined in the tree.

    • getPosition

      public int getPosition(int i) throws NoSuchElementException
      Get the position of a value for a key.
      Parameters:
      i - The key.
      Returns:
      The address of the value for i, if it's found; -1, else. This routine may also return -1 when the tree is corrupted. Of course, with a corrupted tree, results will in general be unpredictable. However, this routine will not throw an ArrayIndexOutOfBoundsException.
      Throws:
      NoSuchElementException