edu.princeton.cs.algorithms

Class TrieST<Value>

java.lang.Object

edu.princeton.cs.algorithms.TrieST<Value>

public class TrieST<Value>
extends Object

The TrieST class represents an 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 256-way trie. The put, contains, delete, and longest prefix operations take time proportional to the length of the key (in the worst case). Construction takes constant time. The size, and is-empty operations take constant time. Construction takes constant time.

For additional documentation, see Section 5.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Constructor Summary

Constructors

Constructor and Description
TrieST()

Method Summary

Methods

Modifier and Type	Method and Description
boolean	contains(String key) Does this symbol table contain the given key?
void	delete(String key) Removes the key from the set if the key is present.
Value	get(String key) Returns the value associated with the given key.
boolean	isEmpty() Is this symbol table empty?
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 .
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 TrieSET 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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

TrieST

public TrieST()

Method Detail

get

public Value get(String key)

Returns the value associated with the given key.

Parameters:

key - the key

Returns:

the value associated with the given key if the key is in the symbol table and null if the key is not in the symbol table

Throws:

NullPointerException - if key is null

contains

public boolean contains(String key)

Does this symbol table contain the given key?

Parameters:

key - the key

Returns:

true if this symbol table contains key and false otherwise

Throws:

NullPointerException - if key is null

put

public 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. If the value is null, this effectively deletes the key from the symbol table.

Parameters:

key - the key

val - the value

Throws:

NullPointerException - if key is null

size

public int size()

Returns the number of key-value pairs in this symbol table.

Returns:

the number of key-value pairs in this symbol table

isEmpty

public boolean isEmpty()

Is this symbol table empty?

Returns:

true if this symbol table is empty and false otherwise

keys

public Iterable<String> keys()

Returns all keys in the symbol table as an Iterable. To iterate over all of the keys in the symbol table named st, use the foreach notation: for (Key key : st.keys()).

Returns:

all keys in the sybol table as an Iterable

keysWithPrefix

public Iterable<String> keysWithPrefix(String prefix)

Returns all of the keys in the set that start with prefix.

Parameters:

prefix - the prefix

Returns:

all of the keys in the set that start with prefix, as an iterable

keysThatMatch

public Iterable<String> keysThatMatch(String pattern)

Returns all of the keys in the symbol table that match pattern, where . symbol is treated as a wildcard character.

Parameters:

pattern - the pattern

Returns:

all of the keys in the symbol table that match pattern, as an iterable, where . is treated as a wildcard character.

longestPrefixOf

public String longestPrefixOf(String query)

Returns the string in the symbol table that is the longest prefix of query, or null, if no such string.

Parameters:

query - the query string

Returns:

the string in the symbol table that is the longest prefix of query, or null if no such string

Throws:

NullPointerException - if query is null

delete

public void delete(String key)

Removes the key from the set if the key is present.

Parameters:

key - the key

Throws:

NullPointerException - if key is null

main

public static void main(String[] args)

Unit tests the TrieSET data type.