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

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

org::apache::uima::internal::util::rb_trees::RedBlackTree< T > Class Reference

Collaboration diagram for org::apache::uima::internal::util::rb_trees::RedBlackTree< T >:
Collaboration graph
[legend]

List of all members.

Classes

class  RBTIterator< T >

Public Member Functions

final void clear ()
final boolean containsKey (int key)
final boolean containsValue (T o)
final T get (int key)
BinaryTree getBinaryTree ()
final T getFirst ()
final boolean isEmpty ()
Iterator< T > iterator ()
final int[] keySet ()
void printKeys ()
final boolean put (int key, T el)
 RedBlackTree ()
final T remove (int key)
final int size ()

Static Public Member Functions

static void main (String[] args)

Package Attributes

RBTNode< T > root = null
int size = 0

Private Member Functions

final RBTNode< T > getFirstNode ()
final boolean put (RBTNode< T > node)

Detailed Description

An implementation of Red-Black Trees. This implementation follows quite closely the algorithms described in Cormen, Leiserson and Rivest (1990): "Introduction to Algorithms" (henceforth CLR). The main difference between our implementation and CLR is that our implementation does not allow duplicate keys in a tree. Since we will generally use our implementation to represent sets, this is a sensible restriction.

The difference between this implementation and TreeMap is that we assume that keys are ints. This should provide for a constant factor speed-up. We also assume that we may copy this implementation to specialize for particular data element types.

This class implements most methods required for a Map. However, since we use ints as keys, we can't implement the interface, as ints are not Objects, and so for example RedBlackTree.containsKey(int key) does not specialize Map.containsKey(Object key).

Note that this implementation is not thread-safe. A thread-safe version could easily be provided, but would come with additional overhead.

Definition at line 51 of file RedBlackTree.java.


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

Generated by  Doxygen 1.6.0   Back to index