|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg.apache.uima.internal.util.rb_trees.IntRBTArray
public class IntRBTArray
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 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, so
a[i+3]
is the first cell of the left daughter nodeIntRBTArray.RIGHTDTR
: this node only has a right daughter, so
a[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, and a[i+4]
is the start of the left
daughter nodeNote 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 |
---|
public static final int TERMINAL
public static final int LEFTDTR
public static final int RIGHTDTR
public static final int TWODTRS
Constructor Detail |
---|
public IntRBTArray(int[] array, int start)
start
- Address of the root node of the tree.array
- The array containing the search tree.public IntRBTArray(int[] array)
0
.
array
- The array containing the search tree.Method Detail |
---|
public int[] toArray()
public void setRootAddress(int start)
start
- the address.public int get(int i) throws java.util.NoSuchElementException
i
- The input key.
java.util.NoSuchElementException
- If the key is not defined in the tree.public int getPosition(int i) throws java.util.NoSuchElementException
i
- The key.
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
.
java.util.NoSuchElementException
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |