Class IntRBTArray
- java.lang.Object
-
- 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. SeeIntRedBlackTree
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 arraya
. Then the expected memory layout ofa
is:a[i]
is the key of the nodea[i+1]
is the element of the nodea[i+2]
is one of:IntRBTArray.TERMINAL
: this is a terminal nodeIntRBTArray.LEFTDTR
: this node only has a left daughter, soa[i+3]
is the first cell of the left daughter nodeIntRBTArray.RIGHTDTR
: this node only has a right daughter, soa[i+3]
is the first cell of the right daughter nodeIntRBTArray.TWODTRS
: this node has two daughters.a[i+3]
contains the address of the right daughter, anda[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).
-
-
Constructor Summary
Constructors Constructor Description IntRBTArray(int[] array)
This constructor assumes that the root node is located at0
.IntRBTArray(int[] array, int start)
Constructor that takes a start point as parameter.
-
Method Summary
All Methods Instance Methods Concrete Methods 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.
-
-
-
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 at0
.- 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 anArrayIndexOutOfBoundsException
. - Throws:
java.util.NoSuchElementException
-
-