Class RedBlackKeySet

  • All Implemented Interfaces:
    ShortKeySet, java.io.Serializable

    public class RedBlackKeySet
    extends java.lang.Object
    implements ShortKeySet, java.io.Serializable
    A RedBlack Tree implementation of the ShortKeySet interface.
    See Also:
    Serialized Form
    • Field Summary

      Fields 
      Modifier and Type Field Description
      static int NODESIZE
      the number of bytes in a RedBlackKeySet node
    • Constructor Summary

      Constructors 
      Constructor Description
      RedBlackKeySet​(short n)
      Creates a new RedBlackKeySet that can store keys between 0 and n.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean containsKey​(short key)
      Returns true if the key is in the set.
      short getFirst()
      Returns the first key in this set.
      short getLast()
      Returns the last key in this set.
      short getNext​(short key)
      Returns the smallest key in the set that is greater than the given key.
      short getPrevious​(short key)
      Returns the largest key in the set that is less than the given key.
      boolean isEmpty()
      Test if the set is empty.
      void put​(short key)
      Adds the given key to the set.
      boolean remove​(short key)
      Removes the given key from the set.
      void removeAll()
      Removes all keys from the set.
      int size()
      Returns the number keys in this set.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • NODESIZE

        public static final int NODESIZE
        the number of bytes in a RedBlackKeySet node
        See Also:
        Constant Field Values
    • Constructor Detail

      • RedBlackKeySet

        public RedBlackKeySet​(short n)
        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.
        Specified by:
        size in interface ShortKeySet
      • containsKey

        public boolean containsKey​(short key)
        Returns true if the key is in the set.
        Specified by:
        containsKey in interface ShortKeySet
        Parameters:
        key - the key whose presence is to be tested.
        Returns:
        true if the key is in the set.
        Throws:
        java.lang.IndexOutOfBoundsException - thrown if the given key is not in the range [0, maxKey].
      • getFirst

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

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

        public short getNext​(short key)
        Returns the smallest key in the set that is greater than the given key. Returns -1 if there are no keys greater than the given key.
        Specified by:
        getNext in interface ShortKeySet
        Parameters:
        key - the key for which to find the next key after.
        Throws:
        java.lang.IndexOutOfBoundsException - thrown if the given key is not in the range [0, maxKey].
      • getPrevious

        public short getPrevious​(short key)
        Returns the largest key in the set that is less than the given key. Returns -1 if there are not keys less than the given key.
        Specified by:
        getPrevious in interface ShortKeySet
        Parameters:
        key - the key for which to find the previous key.
        Throws:
        java.lang.IndexOutOfBoundsException - thrown if the given key is not in the range [0, maxKey].
      • put

        public void put​(short key)
        Adds the given key to the set.
        Specified by:
        put in interface ShortKeySet
        Parameters:
        key - the key to add to the set.
        Throws:
        java.lang.IndexOutOfBoundsException - thrown if the given key is not in the range [0, maxKey].
      • remove

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

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

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