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