public class TST<Value> extends Object
TST
class represents a symbol table of key-value
pairs, with string keys and generic values.
It supports the usual put, get, contains,
delete, size, and is-empty methods.
It also provides character-based methods for finding the string
in the symbol table that is the longest prefix of a given prefix,
finding all strings in the symbol table that start with a given prefix,
and finding all strings in the symbol table that match a given pattern.
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 ternary search trie.
For additional documentation, see Section 5.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
Constructor and Description |
---|
TST()
Initializes an empty string symbol table.
|
Modifier and Type | Method and Description |
---|---|
boolean |
contains(String key)
Does this symbol table contain the given key?
|
Value |
get(String key)
Returns the value associated with the given key.
|
Iterable<String> |
keys()
Returns all keys in the symbol table as an
Iterable . |
Iterable<String> |
keysThatMatch(String pattern)
Returns all of the keys in the symbol table that match
pattern ,
where the character '.' is interpreted as a wildcard character. |
Iterable<String> |
keysWithPrefix(String prefix)
Returns all of the keys in the set that start with
prefix . |
String |
longestPrefixOf(String query)
Returns the string in the symbol table that is the longest prefix of
query ,
or null , if no such string. |
static void |
main(String[] args)
Unit tests the
TST data type. |
void |
put(String 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 int size()
public boolean contains(String key)
key
- the keytrue
if this symbol table contains key
and
false
otherwiseIllegalArgumentException
- if key
is null
public Value get(String key)
key
- the keynull
if the key is not in the symbol tableIllegalArgumentException
- if key
is null
public void put(String key, Value val)
null
, this effectively deletes the key from the symbol table.key
- the keyval
- the valueIllegalArgumentException
- if key
is null
public String longestPrefixOf(String query)
query
,
or null
, if no such string.query
- the query stringquery
,
or null
if no such stringIllegalArgumentException
- if query
is null
public Iterable<String> keys()
Iterable
.
To iterate over all of the keys in the symbol table named st
,
use the foreach notation: for (Key key : st.keys())
.Iterable
public Iterable<String> keysWithPrefix(String prefix)
prefix
.prefix
- the prefixprefix
,
as an iterableIllegalArgumentException
- if prefix
is null
public Iterable<String> keysThatMatch(String pattern)
pattern
,
where the character '.' is interpreted as a wildcard character.pattern
- the patternpattern
,
as an iterable, where . is treated as a wildcard character.public static void main(String[] args)
TST
data type.args
- the command-line arguments