Package ghidra.util.datastruct

Class RedBlackTree<K extends Comparable<K>,V>

java.lang.Object
ghidra.util.datastruct.RedBlackTree<K,V>
All Implemented Interfaces:
Iterable<RedBlackEntry<K,V>>
public class RedBlackTree<K extends Comparable<K>,V> extends Object implements Iterable<RedBlackEntry<K,V>>
A RedBlack Tree implementation with K type keys and place to store V type values.

  • Constructor Details

    • RedBlackTree

      public RedBlackTree()
      Creates a new RedBlackKeySet that can store keys between 0 and n.

  • Method Details

    • 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 ListIterator<RedBlackEntry<K,V>> iterator()
      Specified by:
      iterator in interface Iterable<K extends Comparable<K>>

    • iterator

      public ListIterator<RedBlackEntry<K,V>> iterator(boolean forward)

    • iterator

      public ListIterator<RedBlackEntry<K,V>> iterator(RedBlackEntry<K,V> firstEntry, boolean forward)

    • iterator

      public 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.