public class ST<Key extends java.lang.Comparable<Key>,Value> extends java.lang.Object implements java.lang.Iterable<Key>
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 3.5 of Algorithms, 4th Edition, by Robert Sedgewick and Kevin Wayne.
Constructor and Description |
---|
ST()
Initializes an empty symbol table.
|
Modifier and Type | Method and Description |
---|---|
Key |
ceil(Key key)
Returns the smallest key in the symbol table greater than or equal to key.
|
boolean |
contains(Key key)
Does this symbol table contain the given key?
|
void |
delete(Key key)
Removes the key and associated value from the symbol table
(if the key is in the symbol table).
|
Key |
floor(Key key)
Returns the largest key in the symbol table less than or equal to key.
|
Value |
get(Key key)
Returns the value associated with the given key.
|
boolean |
isEmpty()
Is this symbol table empty?
|
java.util.Iterator<Key> |
iterator()
Deprecated.
Use
keys() instead.
This method is provided for backward compatibility with the version from
Introduction to Programming in Java: An Interdisciplinary Approach. |
java.lang.Iterable<Key> |
keys()
Returns all keys in the symbol table as an Iterable.
|
static void |
main(java.lang.String[] args)
Unit tests the ST data type.
|
Key |
max()
Returns the largest key in the symbol table.
|
Key |
min()
Returns the smallest key in the symbol table.
|
void |
put(Key key,
Value val)
Inserts the key-value pair into the symbol table, overwriting the old value
with the new value if the key is already in the symbol table.
|
int |
size()
Returns the number of key-value pairs in this symbol table.
|
public Value get(Key key)
key
- the keyjava.lang.NullPointerException
- if key is nullpublic void put(Key key, Value val)
key
- the keyval
- the valuejava.lang.NullPointerException
- if key is nullpublic void delete(Key key)
key
- the keyjava.lang.NullPointerException
- if key is nullpublic boolean contains(Key key)
key
- the keyjava.lang.NullPointerException
- if key is nullpublic int size()
public boolean isEmpty()
public java.lang.Iterable<Key> keys()
public java.util.Iterator<Key> iterator()
keys()
instead.
This method is provided for backward compatibility with the version from
Introduction to Programming in Java: An Interdisciplinary Approach.public Key min()
java.util.NoSuchElementException
- if the symbol table is emptypublic Key max()
java.util.NoSuchElementException
- if the symbol table is emptypublic Key ceil(Key key)
key
- the keyjava.util.NoSuchElementException
- if the symbol table is emptyjava.lang.NullPointerException
- if key is nullpublic Key floor(Key key)
key
- the keyjava.util.NoSuchElementException
- if the symbol table is emptyjava.lang.NullPointerException
- if key is nullpublic static void main(java.lang.String[] args)