Package ghidra.util.datastruct

Class BitTree

  • All Implemented Interfaces:
    ShortKeySet, java.io.Serializable
    public class BitTree
extends java.lang.Object
implements ShortKeySet, java.io.Serializable
    The BitTree class maintains a set of ordered keys between the values of 0 and N. It can quickly (O(log(n))) add keys, remove keys, find the next key greater than some value , and find the prev key less than some value. It can determine if a key is in the set in O(1) time. This implementation has been limited to short keys so that it can implement the ShortKeySet interface.
    See Also:
    Serialized Form

    • Constructor Summary

      Constructors 
      Constructor Description
      BitTree​(short maxKey)
      The BitTree constructor takes the maximum key value.
      BitTree​(short maxKey, boolean isFull)
      The BitTree constructor takes the maximum key value.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean containsKey​(short key)
      Determines if a given key is in the set.
      short getFirst()
      Returns the first (lowest) key in the set.
      short getLast()
      Returns the last (highest) key in the set.
      short getNext​(short key)
      finds the next key that is in the set that is greater than the given key.
      short getPrevious​(short key)
      Finds the next key that is in the set that is less than the given key.
      boolean isEmpty()
      Checks if the set is empty.
      void put​(short key)
      Adds a key to the set.
      boolean remove​(short key)
      Removes the key from the set.
      void removeAll()
      Removes all keys from the set.
      int size()
      Returns the number of keys currently in the set.

      • Methods inherited from class java.lang.Object

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

    • Constructor Detail

      • BitTree

        public BitTree​(short maxKey)
        The BitTree constructor takes the maximum key value. The legal keys for this set range from 0 to maxKey.
        Parameters:
        maxKey - the maximum key that will ever be put into this BitTree.

      • BitTree

        public BitTree​(short maxKey,
               boolean isFull)
        The BitTree constructor takes the maximum key value. The legal keys for this set range from 0 to maxKey.
        Parameters:
        maxKey - the maximum key value.
        isFull - if true, then the set is initilized to contain all legal keys.

    • Method Detail

      • removeAll

        public void removeAll()
        Removes all keys from the set.
        Specified by:
        removeAll in interface ShortKeySet

      • size

        public int size()
        Returns the number of keys currently in the set.
        Specified by:
        size in interface ShortKeySet

      • put

        public void put​(short key)
        Adds a key to the set.
        Specified by:
        put in interface ShortKeySet
        Parameters:
        key - to be added.
        Throws:
        java.lang.IndexOutOfBoundsException - if the given key is not in the range [0, size-1].

      • remove

        public boolean remove​(short key)
        Removes the key from the set.
        Specified by:
        remove in interface ShortKeySet
        Parameters:
        key - The key to remove.
        Throws:
        java.lang.IndexOutOfBoundsException - if the given key is not in the range [0, size-1].

      • containsKey

        public boolean containsKey​(short key)
        Determines if a given key is in the set.
        Specified by:
        containsKey in interface ShortKeySet
        Parameters:
        key - the key to check if it is in this set.
        Returns:
        true if the key is in the set.

      • getNext

        public short getNext​(short key)
        finds the next key that is in the set that is greater than the given key.
        Specified by:
        getNext in interface ShortKeySet
        Parameters:
        key - from which to search forward.
        Returns:
        the next key greater than the given key or -1 if there is no key greater than the given key.
        Throws:
        java.lang.IndexOutOfBoundsException - if the given key is not in the range [0, size-1].

      • getPrevious

        public short getPrevious​(short key)
        Finds the next key that is in the set that is less than the given key.
        Specified by:
        getPrevious in interface ShortKeySet
        Parameters:
        key - the key to search before.
        Returns:
        the next key less than the given key or -1 if there is no key less than the given key.
        Throws:
        java.lang.IndexOutOfBoundsException - if the given key is not in the range [0, size-1].

      • isEmpty

        public boolean isEmpty()
        Checks if the set is empty.
        Specified by:
        isEmpty in interface ShortKeySet
        Returns:
        true if the set is empty.

      • getFirst

        public short getFirst()
        Returns the first (lowest) key in the set.
        Specified by:
        getFirst in interface ShortKeySet

      • getLast

        public short getLast()
        Returns the last (highest) key in the set.
        Specified by:
        getLast in interface ShortKeySet