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

java.lang.Object
  extended by org.apache.uima.internal.util.rb_trees.IntArrayRBT
Direct Known Subclasses:
CompIntArrayRBT

public class IntArrayRBT
extends java.lang.Object

Red-black tree implementation based on integer arrays. Preliminary performance measurements on j2se 1.4 indicate that the performance improvement as opposed to an object-based implementation are miniscule. This seems to indicate a much improved object creation handling in this vm.

This tree implementation knows two modes of insertion: keys that are already in the tree can be rejected, or inserted as duplicates. Duplicate key insertion is randomized so that the tree's performance degrades gracefully in the presence of many identical keys.


Field Summary
protected static boolean black
           
protected  boolean[] color
           
protected static int default_size
           
protected  int greatestNode
           
protected  int[] key
           
protected  int[] left
           
static int NIL
           
protected  int[] parent
           
protected  java.util.Random rand
           
protected static boolean red
           
protected  int[] right
           
protected  int root
           
 
Constructor Summary
IntArrayRBT()
          Constructor for IntArrayRBT.
IntArrayRBT(int initialSize)
           
 
Method Summary
 boolean containsKey(int k)
           
 boolean deleteKey(int aKey)
           
 int findInsertionPoint(int k)
          Find the node such that key[node] >= k and key[previous(node)] < k.
 int findInsertionPointNoDups(int k)
          Find the node such that key[node] >= k and key[previous(node)] < k.
 int findKey(int k)
          Find the first node such that k <= key[node].
 void flush()
           
 int getKeyForNode(int node)
           
 int insertKey(int k)
           
 int insertKeyWithDups(int k)
           
 IntListIterator iterator()
           
 ComparableIntIterator iterator(IntComparator comp)
          Method iterator.
static void main(java.lang.String[] args)
           
 int maxDepth()
           
 int minDepth()
           
protected  int newNode(int k)
           
protected  int nextNode(int node)
           
 int nodeDepth(int k)
           
 IntPointerIterator pointerIterator()
           
 IntPointerIterator pointerIterator(int aKey)
           
 ComparableIntPointerIterator pointerIterator(IntComparator comp, int[] detectIllegalIndexUpdates, int typeCode)
           
 void printKeys()
           
 boolean satisfiesRedBlackProperties()
           
 int size()
           
protected  int treeInsert(int k)
           
protected  int treeInsertWithDups(int k)
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

key

protected int[] key

left

protected int[] left

right

protected int[] right

parent

protected int[] parent

color

protected boolean[] color

root

protected int root

greatestNode

protected int greatestNode

default_size

protected static final int default_size
See Also:
Constant Field Values

NIL

public static final int NIL
See Also:
Constant Field Values

red

protected static final boolean red
See Also:
Constant Field Values

black

protected static final boolean black
See Also:
Constant Field Values

rand

protected final java.util.Random rand
Constructor Detail

IntArrayRBT

public IntArrayRBT()
Constructor for IntArrayRBT.


IntArrayRBT

public IntArrayRBT(int initialSize)
Method Detail

flush

public void flush()

size

public final int size()

getKeyForNode

public int getKeyForNode(int node)

treeInsert

protected int treeInsert(int k)

treeInsertWithDups

protected int treeInsertWithDups(int k)

newNode

protected int newNode(int k)

insertKey

public int insertKey(int k)

insertKeyWithDups

public int insertKeyWithDups(int k)

findKey

public int findKey(int k)
Find the first node such that k <= key[node].


findInsertionPoint

public int findInsertionPoint(int k)
Find the node such that key[node] >= k and key[previous(node)] < k.


findInsertionPointNoDups

public int findInsertionPointNoDups(int k)
Find the node such that key[node] >= k and key[previous(node)] < k.


containsKey

public final boolean containsKey(int k)

nextNode

protected final int nextNode(int node)

deleteKey

public boolean deleteKey(int aKey)

iterator

public ComparableIntIterator iterator(IntComparator comp)
Method iterator.

Returns:
IntListIterator

iterator

public IntListIterator iterator()

pointerIterator

public IntPointerIterator pointerIterator()

pointerIterator

public IntPointerIterator pointerIterator(int aKey)

pointerIterator

public ComparableIntPointerIterator pointerIterator(IntComparator comp,
                                                    int[] detectIllegalIndexUpdates,
                                                    int typeCode)

satisfiesRedBlackProperties

public boolean satisfiesRedBlackProperties()

maxDepth

public int maxDepth()

minDepth

public int minDepth()

nodeDepth

public int nodeDepth(int k)

printKeys

public final void printKeys()

main

public static void main(java.lang.String[] args)


Copyright © 2010 The Apache Software Foundation. All Rights Reserved.