org.apache.uima.internal.util.rb_trees
Class IntRBTArray

java.lang.Object
  extended by org.apache.uima.internal.util.rb_trees.IntRBTArray

public class IntRBTArray
extends java.lang.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:

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
static int LEFTDTR
          Code for a node with only a left daughter.
static int RIGHTDTR
          Code for a node with only a right daughter.
static int TERMINAL
          Code for a terminal node in the array.
static int TWODTRS
          Code for a node with two daughters.
 
Constructor Summary
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
 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 Detail

TERMINAL

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

See Also:
Constant Field Values

LEFTDTR

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

See Also:
Constant Field Values

RIGHTDTR

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

See Also:
Constant Field Values

TWODTRS

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

See Also:
Constant Field Values
Constructor Detail

IntRBTArray

public IntRBTArray(int[] array,
                   int start)
Constructor that takes a start point as parameter.

Parameters:
start - Address of the root node of the tree.
array - The array containing the search 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 Detail

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 java.util.NoSuchElementException
Retrieve the value for a certain key.

Parameters:
i - The input key.
Returns:
The value, if key was found.
Throws:
java.util.NoSuchElementException - If the key is not defined in the tree.

getPosition

public int getPosition(int i)
                throws java.util.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:
java.util.NoSuchElementException


Copyright © 2012. All Rights Reserved.