Logo Search packages:      
Sourcecode: uimaj version File versions  Download package

Classes | Public Member Functions | Static Public Member Functions | Static Public Attributes | Protected Member Functions | Protected Attributes | Static Protected Attributes | Private Member Functions | Private Attributes | Static Private Attributes

org::apache::uima::internal::util::rb_trees::IntArrayRBT Class Reference

Inheritance diagram for org::apache::uima::internal::util::rb_trees::IntArrayRBT:
Inheritance graph
Collaboration diagram for org::apache::uima::internal::util::rb_trees::IntArrayRBT:
Collaboration graph

List of all members.


class  ComparableIterator
class  ComparablePointerIterator
class  IntArrayRBTKeyIterator
class  PointerIterator

Public Member Functions

final boolean containsKey (int k)
boolean deleteKey (int aKey)
int findInsertionPoint (int k)
int findInsertionPointNoDups (int k)
int findKey (int k)
void flush ()
int getKeyForNode (final int node)
int insertKey (int k)
int insertKeyWithDups (int k)
 IntArrayRBT (int initialSize)
 IntArrayRBT ()
ComparableIntIterator iterator (IntComparator comp)
IntListIterator iterator ()
int maxDepth ()
int minDepth ()
int nodeDepth (int k)
IntPointerIterator pointerIterator (int aKey)
ComparableIntPointerIterator pointerIterator (IntComparator comp, int[] detectIllegalIndexUpdates, int typeCode)
IntPointerIterator pointerIterator ()
final void printKeys ()
boolean satisfiesRedBlackProperties ()
final int size ()

Static Public Member Functions

static void main (String[] args)

Static Public Attributes

static final int NIL = 0

Protected Member Functions

int newNode (int k)
final int nextNode (int node)
int treeInsert (int k)
int treeInsertWithDups (int k)

Protected Attributes

boolean[] color
int greatestNode
int[] key
int[] left
int[] parent
final Random rand
int[] right
int root

Static Protected Attributes

static final boolean black = false
static final int default_size = 1024
static final boolean red = true

Private Member Functions

void deleteFixup (int x)
void deleteNode (int z)
final int getFirstNode ()
void grow (int initialSize)
final int[] grow (int[] array, int newSize)
final boolean[] grow (boolean[] array, int newSize)
void initVars ()
int insertKey (int k, boolean withDups)
final boolean isLeftDtr (int node)
final void leftRotate (int x)
int maxDepth (int node, int depth)
int minDepth (int node, int depth)
int nodeDepth (int node, int depth, int k)
final int previousNode (int node)
final void printKeys (int node, int offset, StringBuffer buf)
final void rightRotate (int x)
boolean satisfiesRBProps (int node, final int blackDepth, int currentBlack)
final void setAsRoot (int x)

Private Attributes

int growth_factor
int multiplication_limit
int next
int size

Static Private Attributes

static final int default_growth_factor = 2
static final int default_multiplication_limit = 2000000

Detailed Description

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.

Definition at line 45 of file IntArrayRBT.java.

The documentation for this class was generated from the following file:

Generated by  Doxygen 1.6.0   Back to index