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 Summary

  Constructors
  Constructor
  Description
  `RedBlackTree()`
  Creates a new RedBlackKeySet that can store keys between 0 and n.

- ## Method Summary

  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.
  `ListIterator<RedBlackEntry<K,V>>`
  `iterator()`
  `ListIterator<RedBlackEntry<K,V>>`
  `iterator(boolean forward)`
  `ListIterator<RedBlackEntry<K,V>>`
  `iterator(RedBlackEntry<K,V> firstEntry, boolean forward)`
  `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.

  ### Methods inherited from class java.lang.Object

  `clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

  ### Methods inherited from interface java.lang.Iterable

  `forEach, spliterator`

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