Key
- the generic type of keys in this symbol tableValue
- the generic type of values in this symbol tablepublic class ST<Key extends Comparable<Key>,Value>
extends Object
implements Iterable<Key>
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 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.
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.
Constructor and Description |
---|
ST()
Initializes an empty symbol table.
|
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.
|
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.
|
public Value get(Key key)
key
- the keynull
if the key is not in this symbol tableIllegalArgumentException
- if key
is null
public void put(Key key, Value val)
null
.key
- the keyval
- the valueIllegalArgumentException
- if key
is null
@Deprecated public void delete(Key key)
remove(Comparable key)
.key
- the keyIllegalArgumentException
- if key
is null
public void remove(Key key)
key
- the keyIllegalArgumentException
- if key
is null
public boolean contains(Key key)
key
- the keytrue
if this symbol table contains key
and
false
otherwiseIllegalArgumentException
- if key
is null
public int size()
public boolean isEmpty()
true
if this symbol table is empty and false
otherwisepublic Iterable<Key> keys()
To iterate over all of the keys in the symbol table named st
,
use the foreach notation: for (Key key : st.keys())
.
@Deprecated public java.util.Iterator<Key> iterator()
keys()
.st
, use the
foreach notation: for (Key key : st)
.public Key min()
java.util.NoSuchElementException
- if this symbol table is emptypublic Key max()
java.util.NoSuchElementException
- if this symbol table is emptypublic Key ceiling(Key key)
key
.key
- the keykey
java.util.NoSuchElementException
- if there is no such keyIllegalArgumentException
- if key
is null
public Key floor(Key key)
key
.key
- the keykey
java.util.NoSuchElementException
- if there is no such keyIllegalArgumentException
- if key
is null
public static void main(String[] args)
ST
data type.args
- the command-line arguments