|
||||||||||
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.RedBlackTree<T>
public class RedBlackTree<T>
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.
Constructor Summary | |
---|---|
RedBlackTree()
Default constructor, does nothing. |
Method Summary | |
---|---|
void |
clear()
Remove all elements from the tree. |
boolean |
containsKey(int key)
Checks if the key is contained in the tree. |
boolean |
containsValue(T o)
Check if the value object is contained in the tree. |
T |
get(int key)
Get the object for a key. |
BinaryTree |
getBinaryTree()
Return a copy of the red-black tree as a BinaryTree. |
T |
getFirst()
|
boolean |
isEmpty()
Check if the map is empty. |
java.util.Iterator<T> |
iterator()
|
int[] |
keySet()
Return the set of keys as a sorted array. |
static void |
main(java.lang.String[] args)
|
void |
printKeys()
Debugging aid. |
boolean |
put(int key,
T el)
Insert an object with a given key into the tree. |
T |
remove(int key)
Delete the node with the given key from the tree, if it exists. |
int |
size()
|
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
---|
public RedBlackTree()
Method Detail |
---|
public final int size()
public final void clear()
public final boolean containsKey(int key)
key
- The key.
true
, if key is defined; false
, else.public final boolean containsValue(T o)
o
- The value we want to check.
true
, if value is there; false
, else.public final boolean put(int key, T el)
key
- The key under which the Object is to be inserted.el
- The Object to be inserted.
true
, if the key was not in the tree; false
, if an
element with that key was already in the tree. The old element is overwritten with the
new one.public final T remove(int key)
key
- The key to be deleted.public final T get(int key)
null
.
Since null
can also be a regular value, use containsKey()
to check if a
key is defined or not.
key
- The key.
null
if key is not defined.public final boolean isEmpty()
true
if map is empty; false
, else.public final int[] keySet()
public final T getFirst()
null
if the tree is
empty.public java.util.Iterator<T> iterator()
iterator
in interface java.lang.Iterable<T>
public BinaryTree getBinaryTree()
public void printKeys()
public static void main(java.lang.String[] args)
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |