Package ghidra.util.datastruct
Class BitTree
- java.lang.Object
-
- ghidra.util.datastruct.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
-
-
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.
-
-
-
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 interfaceShortKeySet
-
size
public int size()
Returns the number of keys currently in the set.- Specified by:
size
in interfaceShortKeySet
-
put
public void put(short key)
Adds a key to the set.- Specified by:
put
in interfaceShortKeySet
- 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 interfaceShortKeySet
- 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 interfaceShortKeySet
- 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 interfaceShortKeySet
- 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 interfaceShortKeySet
- 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 interfaceShortKeySet
- Returns:
- true if the set is empty.
-
getFirst
public short getFirst()
Returns the first (lowest) key in the set.- Specified by:
getFirst
in interfaceShortKeySet
-
getLast
public short getLast()
Returns the last (highest) key in the set.- Specified by:
getLast
in interfaceShortKeySet
-
-