java.io.Serializable
, java.lang.Iterable<Key>
public class SymbolTable<Key extends java.lang.Comparable<Key>,Value>
extends java.lang.Object
implements java.lang.Iterable<Key>, java.io.Serializable
The class uses the convention that values cannot be null. Setting the value associated with a key to null is equivalent to removing the key.
This implementation uses a balanced binary search tree. The add, contains, delete, minimum, maximum, ceiling, and floor methods take logarithmic time. Derived from http://introcs.cs.princeton.edu/java/44st/ST.java.html
For additional documentation, see Section 4.4 of Introduction to Programming in Java: An Interdisciplinary Approach by Robert Sedgewick and Kevin Wayne.
Constructor | Description |
---|---|
SymbolTable() |
Create an empty symbol table.
|
Modifier and Type | Method | Description |
---|---|---|
Key |
ceil(Key k) |
Return the smallest key in the table >= k.
|
boolean |
contains(Key key) |
Is the key in the table?
|
Value |
delete(Key key) |
Delete the key (and paired value) from table.
|
Key |
floor(Key k) |
Return the largest key in the table <= k.
|
Value |
get(Key key) |
Return the value paired with given key; null if key is not in table.
|
java.util.Iterator<Key> |
iterator() |
Return an Iterator for the keys in the table.
|
java.lang.Iterable<Key> |
keys() |
Return an Iterable for the keys in the table.
|
Key |
max() |
Return the largest key in the table.
|
Key |
min() |
Return the smallest key in the table.
|
void |
put(Key key,
Value val) |
Put key-value pair into the symbol table.
|
int |
size() |
How many keys are in the table?
|
public void put(Key key, Value val)
public Value delete(Key key)
public boolean contains(Key key)
public int size()
public java.util.Iterator<Key> iterator()
public java.lang.Iterable<Key> keys()
public Key min()
public Key max()