Package ghidra.util.datastruct
Class RedBlackTree<K extends java.lang.Comparable<K>,V>
- java.lang.Object
-
- ghidra.util.datastruct.RedBlackTree<K,V>
-
- All Implemented Interfaces:
java.lang.Iterable<RedBlackEntry<K,V>>
public class RedBlackTree<K extends java.lang.Comparable<K>,V> extends java.lang.Object implements java.lang.Iterable<RedBlackEntry<K,V>>
A RedBlack Tree implementation with K type keys and place to store V type values.
-
-
Constructor Summary
Constructors Constructor Description RedBlackTree()
Creates a new RedBlackKeySet that can store keys between 0 and n.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
containsKey(K key)
Returns true if the key is in the set.void
deleteEntry(RedBlackEntry<K,V> p)
Delete node p, and then rebalance the tree.RedBlackEntry<K,V>
getEntry(K key)
RedBlackEntry<K,V>
getEntryGreaterThanEqual(K key)
Returns the node with largest key in the set that is less or equal to the given key.RedBlackEntry<K,V>
getEntryLessThanEqual(K key)
Returns the node with largest key in the set that is less or equal to the given key.RedBlackEntry<K,V>
getFirst()
Returns the first entry in this set.RedBlackEntry<K,V>
getLast()
Returns the last entry in this set.RedBlackEntry<K,V>
getOrCreateEntry(K key)
boolean
isEmpty()
Test if the set is empty.java.util.ListIterator<RedBlackEntry<K,V>>
iterator()
java.util.ListIterator<RedBlackEntry<K,V>>
iterator(boolean forward)
java.util.ListIterator<RedBlackEntry<K,V>>
iterator(RedBlackEntry<K,V> firstEntry, boolean forward)
java.util.ListIterator<RedBlackEntry<K,V>>
iterator(K key, boolean forward)
V
put(K key, V value)
Adds the given key,value to the map.V
remove(K key)
Removes the given key (first if duplicates are allowed) from the set.void
removeAll()
Removes all entries from the set.void
removeNode(RedBlackEntry<K,V> node)
int
size()
Returns the number keys in this set.
-
-
-
Method Detail
-
size
public int size()
Returns the number keys in this set.
-
containsKey
public boolean containsKey(K key)
Returns true if the key is in the set.- Parameters:
key
- the key whose presence is to be tested.
-
getFirst
public RedBlackEntry<K,V> getFirst()
Returns the first entry in this set.
-
getLast
public RedBlackEntry<K,V> getLast()
Returns the last entry in this set.
-
getEntryLessThanEqual
public RedBlackEntry<K,V> getEntryLessThanEqual(K key)
Returns the node with largest key in the set that is less or equal to the given key. Returns null if there are no keys less than or equal to the given key.- Parameters:
key
- the search key
-
getEntryGreaterThanEqual
public RedBlackEntry<K,V> getEntryGreaterThanEqual(K key)
Returns the node with largest key in the set that is less or equal to the given key. Returns null if there are no keys less than or equal to the given key.- Parameters:
key
- the search key
-
put
public V put(K key, V value)
Adds the given key,value to the map. If the map does not allow duplicate keys and a key already exists, the old value will be replaced by the new value and the old value will be returned.- Parameters:
key
- the key to add to the set.- Returns:
- the old value associated with the key, or null if the key was not previously in the map.
-
getOrCreateEntry
public RedBlackEntry<K,V> getOrCreateEntry(K key)
-
getEntry
public RedBlackEntry<K,V> getEntry(K key)
-
remove
public V remove(K key)
Removes the given key (first if duplicates are allowed) from the set.- Parameters:
key
- the key to remove from the set.- Returns:
- the value associated with the key removed or null if the key not found.
-
removeNode
public void removeNode(RedBlackEntry<K,V> node)
-
removeAll
public void removeAll()
Removes all entries from the set.
-
isEmpty
public boolean isEmpty()
Test if the set is empty.- Returns:
- true if the set is empty.
-
iterator
public java.util.ListIterator<RedBlackEntry<K,V>> iterator()
-
iterator
public java.util.ListIterator<RedBlackEntry<K,V>> iterator(boolean forward)
-
iterator
public java.util.ListIterator<RedBlackEntry<K,V>> iterator(RedBlackEntry<K,V> firstEntry, boolean forward)
-
iterator
public java.util.ListIterator<RedBlackEntry<K,V>> iterator(K key, boolean forward)
-
deleteEntry
public void deleteEntry(RedBlackEntry<K,V> p)
Delete node p, and then rebalance the tree.
-
-