Class ST<K extends Comparable<? super K>,V>
- All Implemented Interfaces:
Iterable<K>
Comparable
.
It supports the usual put, get, contains,
and remove methods.
It also provides ordered methods for finding the minimum,
maximum, floor, and ceiling.
The class implements the associative array abstraction: when associating a value with a key that is already in the table, the convention is to replace the old value with the new value. The class also uses the convention that values cannot be null. Setting the value associated with a key to null is equivalent to removing the key.
This class implements the Iterable interface for compatiblity with the version from Introduction to Programming in Java: An Interdisciplinary Approach.
This implementation uses a balanced binary search tree. The put, contains, remove, minimum, maximum, ceiling, and floor methods take logarithmic time.
For additional documentation, see Section 4.5 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
-
Constructor Summary
-
Method Summary
Modifier and TypeMethodDescriptionReturn the smallest key in the table>= k
.boolean
Is the key in the table?Delete the key (and paired value) from table.Return the largest key in the table<= k
.Return the value paired with given key; null if key is not in table.iterator()
Return anIterator
for the keys in the table.keys()
Return anIterable
for the keys in the table.static void
max()
Return the largest key in the table.min()
Return the smallest key in the table.void
Put key-value pair into the symbol table.int
size()
How many keys are in the table?Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
Methods inherited from interface java.lang.Iterable
forEach, spliterator
-
Constructor Details
-
ST
public ST()Create an empty symbol table.
-
-
Method Details
-
put
Put key-value pair into the symbol table. Remove key from table if value is null. -
get
Return the value paired with given key; null if key is not in table. -
delete
Delete the key (and paired value) from table. Return the value paired with given key; null if key is not in table. -
contains
Is the key in the table? -
size
How many keys are in the table? -
keys
Return anIterable
for the keys in the table. To iterate over all of the keys in the symbol tablest
, use the foreach notation:for (K key : st.keys())
. -
iterator
Return anIterator
for the keys in the table. To iterate over all of the keys in the symbol tablest
, use the foreach notation:for (K key : st)
. This method is for backward compatibility with the version from Introduction to Programming in Java: An Interdisciplinary Approach.- Specified by:
iterator
in interfaceIterable<K extends Comparable<? super K>>
-
min
Return the smallest key in the table. -
max
Return the largest key in the table. -
ceil
Return the smallest key in the table>= k
. -
floor
Return the largest key in the table<= k
. -
main
-