Package ghidra.util.datastruct

Class BitTree

java.lang.Object
ghidra.util.datastruct.BitTree
All Implemented Interfaces:
ShortKeySet, Serializable
public class BitTree extends Object implements ShortKeySet, 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:

  • 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

    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 Details

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

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