org.apache.uima.internal.util.rb_trees
public class IntArrayRBT extends java.lang.Object
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.
Modifier and Type | Field and Description |
---|---|
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 and Description |
---|
IntArrayRBT()
Constructor for IntArrayRBT.
|
IntArrayRBT(int initialSize) |
Modifier and Type | Method and Description |
---|---|
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) |
protected int[] key
protected int[] left
protected int[] right
protected int[] parent
protected boolean[] color
protected int root
protected int greatestNode
protected static final int default_size
public static final int NIL
protected static final boolean red
protected static final boolean black
protected final java.util.Random rand
public IntArrayRBT()
public IntArrayRBT(int initialSize)
public void flush()
public final int size()
public int getKeyForNode(int node)
protected int treeInsert(int k)
protected int treeInsertWithDups(int k)
protected int newNode(int k)
public int insertKey(int k)
public int insertKeyWithDups(int k)
public int findKey(int k)
public int findInsertionPoint(int k)
public int findInsertionPointNoDups(int k)
public final boolean containsKey(int k)
protected final int nextNode(int node)
public boolean deleteKey(int aKey)
public ComparableIntIterator iterator(IntComparator comp)
public IntListIterator iterator()
public IntPointerIterator pointerIterator()
public IntPointerIterator pointerIterator(int aKey)
public ComparableIntPointerIterator pointerIterator(IntComparator comp, int[] detectIllegalIndexUpdates, int typeCode)
public boolean satisfiesRedBlackProperties()
public int maxDepth()
public int minDepth()
public int nodeDepth(int k)
public final void printKeys()
public static void main(java.lang.String[] args)
Copyright © 2014. All Rights Reserved.