Package ghidra.util.datastruct

Class RedBlackTree<K extends java.lang.Comparable<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 Detail

      • RedBlackTree

        public RedBlackTree()
        Creates a new RedBlackKeySet that can store keys between 0 and n.
        Parameters:
        n - the maximum key for 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.

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

      • 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()
        Specified by:
        iterator in interface java.lang.Iterable<K extends java.lang.Comparable<K>>

      • iterator

        public java.util.ListIterator<RedBlackEntry<K,​V>> iterator​(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.