Package edu.princeton.cs.algs4

Class ST<Key extends Comparable<Key>,​Value>

  • Type Parameters:
    Key - the generic type of keys in this symbol table
    Value - the generic type of values in this symbol table
    All Implemented Interfaces:
    Iterable<Key>
    public class ST<Key extends Comparable<Key>,​Value>
extends Object
implements Iterable<Key>
    The ST class represents an ordered symbol table of generic key-value pairs. It supports the usual put, get, contains, delete, size, and is-empty methods. It also provides ordered methods for finding the minimum, maximum, floor, and ceiling. It also provides a keys method for iterating over all of the keys. A symbol table implements the associative array abstraction: when associating a value with a key that is already in the symbol table, the convention is to replace the old value with the new value. Unlike Map, this class uses the convention that values cannot be null—setting the value associated with a key to null is equivalent to deleting the key from the symbol table.

    It requires that the key type implements the Comparable interface and calls the compareTo() and method to compare two keys. It does not call either equals() or hashCode().

    This implementation uses a red-black BST. The put, get, contains, remove, minimum, maximum, ceiling, and floor operations each take Θ(log n) time in the worst case, where n is the number of key-value pairs in the symbol table. The size and is-empty operations take Θ(1) time. Construction takes Θ(1) time.

    For additional documentation, see Section 3.5 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

    Author:
    Robert Sedgewick, Kevin Wayne

    • Constructor Summary

      Constructors 
      Constructor Description
      ST()
      Initializes an empty symbol table.

    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      Key ceiling​(Key key)
      Returns the smallest key in this symbol table greater than or equal to key.
      boolean contains​(Key key)
      Returns true if this symbol table contain the given key.
      void delete​(Key key)
      Removes the specified key and its associated value from this symbol table (if the key is in this symbol table).
      Key floor​(Key key)
      Returns the largest key in this symbol table less than or equal to key.
      Value get​(Key key)
      Returns the value associated with the given key in this symbol table.
      boolean isEmpty()
      Returns true if this symbol table is empty.
      Iterable<Key> keys()
      Returns all keys in this symbol table in ascending order, as an Iterable.
      static void main​(String[] args)
      Unit tests the ST data type.
      Key max()
      Returns the largest key in this symbol table.
      Key min()
      Returns the smallest key in this symbol table.
      void put​(Key key, Value val)
      Inserts the specified key-value pair into the symbol table, overwriting the old value with the new value if the symbol table already contains the specified key.
      void remove​(Key key)
      Removes the specified key and its associated value from this symbol table (if the key is in this symbol table).
      int size()
      Returns the number of key-value pairs in this symbol table.

    • Constructor Detail

      • ST

        public ST()
        Initializes an empty symbol table.

    • Method Detail

      • get

        public Value get​(Key key)
        Returns the value associated with the given key in this symbol table.
        Parameters:
        key - the key
        Returns:
        the value associated with the given key if the key is in this symbol table; null if the key is not in this symbol table
        Throws:
        IllegalArgumentException - if key is null

      • put

        public void put​(Key key,
                Value val)
        Inserts the specified key-value pair into the symbol table, overwriting the old value with the new value if the symbol table already contains the specified key. Deletes the specified key (and its associated value) from this symbol table if the specified value is null.
        Parameters:
        key - the key
        val - the value
        Throws:
        IllegalArgumentException - if key is null

      • delete

        public void delete​(Key key)
        Removes the specified key and its associated value from this symbol table (if the key is in this symbol table). This is equivalent to remove(), but we plan to deprecate delete().
        Parameters:
        key - the key
        Throws:
        IllegalArgumentException - if key is null

      • remove

        public void remove​(Key key)
        Removes the specified key and its associated value from this symbol table (if the key is in this symbol table). This is equivalent to delete(), but we plan to deprecate delete().
        Parameters:
        key - the key
        Throws:
        IllegalArgumentException - if key is null

      • contains

        public boolean contains​(Key key)
        Returns true if this symbol table contain the given key.
        Parameters:
        key - the key
        Returns:
        true if this symbol table contains key and false otherwise
        Throws:
        IllegalArgumentException - if key is null

      • size

        public int size()
        Returns the number of key-value pairs in this symbol table.
        Returns:
        the number of key-value pairs in this symbol table

      • isEmpty

        public boolean isEmpty()
        Returns true if this symbol table is empty.
        Returns:
        true if this symbol table is empty and false otherwise

      • keys

        public Iterable<Key> keys()
        Returns all keys in this symbol table in ascending order, as an Iterable.

        To iterate over all of the keys in the symbol table named st, use the foreach notation: for (Key key : st.keys()).

        Returns:
        all keys in this symbol table in ascending order

      • min

        public Key min()
        Returns the smallest key in this symbol table.
        Returns:
        the smallest key in this symbol table
        Throws:
        NoSuchElementException - if this symbol table is empty

      • max

        public Key max()
        Returns the largest key in this symbol table.
        Returns:
        the largest key in this symbol table
        Throws:
        NoSuchElementException - if this symbol table is empty

      • ceiling

        public Key ceiling​(Key key)
        Returns the smallest key in this symbol table greater than or equal to key.
        Parameters:
        key - the key
        Returns:
        the smallest key in this symbol table greater than or equal to key
        Throws:
        NoSuchElementException - if there is no such key
        IllegalArgumentException - if key is null

      • floor

        public Key floor​(Key key)
        Returns the largest key in this symbol table less than or equal to key.
        Parameters:
        key - the key
        Returns:
        the largest key in this symbol table less than or equal to key
        Throws:
        NoSuchElementException - if there is no such key
        IllegalArgumentException - if key is null

      • main

        public static void main​(String[] args)
        Unit tests the ST data type.
        Parameters:
        args - the command-line arguments