ST

Object
- ST<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, remove, 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 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.
This implementation uses a balanced binary search tree. 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(). The put, contains, remove, minimum, maximum, ceiling, and floor operations each take logarithmic time in the worst case. The size, and is-empty operations take constant time. Construction takes constant time.
For additional documentation, see Section 4.4 of Computer Science: An Interdisciplinary Approach by Robert Sedgewick and Kevin Wayne.

Author:

Robert Sedgewick, Kevin Wayne

Constructor Summary

Constructors
Constructor and Description

ST()
Initializes an empty symbol table.

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

Method Summary

All Methods Static Methods Instance Methods Concrete Methods Deprecated Methods
Modifier and Type	Method and 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)` Deprecated. Replaced by `remove(Comparable key)`.
`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.
`java.util.Iterator<Key>`	`iterator()` Deprecated. Replaced by `keys()`.
`Iterable<Key>`	`keys()` Returns all keys in this symbol table in ascending order.
`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.

Methods inherited from class Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface Iterable
forEach, spliterator

- 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. Removes 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
```
@Deprecated
public void delete(Key key)
```
    Deprecated. Replaced by remove(Comparable key).
    
    Removes the specified key and its associated value from this symbol table (if the key is in this symbol table).
    
    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).
    
    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.
    To iterate over all the keys in the symbol table named st, use the foreach notation: for (Key key : st.keys()).
    
    Returns:
    
    all keys in this symbol table
  - iterator
```
@Deprecated
public java.util.Iterator<Key> iterator()
```
    Deprecated. Replaced by keys().
    
    Returns all the keys in this symbol table in ascending order. To iterate over all the keys in a symbol table named st, use the foreach notation: for (Key key : st).
    
    Specified by:
    
    iterator in interface Iterable<Key extends Comparable<Key>>
    
    Returns:
    
    an iterator to all the keys in this symbol table
  - min
```
public Key min()
```
    Returns the smallest key in this symbol table.
    
    Returns:
    
    the smallest key in this symbol table
    
    Throws:
    
    java.util.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:
    
    java.util.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:
    
    java.util.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:
    
    java.util.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

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

Constructor Summary

Method Summary

Methods inherited from class Object

Methods inherited from interface Iterable

Constructor Detail

ST

Method Detail

get

put

delete

remove

contains

size

isEmpty

keys

iterator

min

max

ceiling

floor

main