edu.princeton.cs.algorithms

Class TrieSET

java.lang.Object

edu.princeton.cs.algorithms.TrieSET

All Implemented Interfaces:

Iterable<String>

public class TrieSET
extends Object
implements Iterable<String>

The TrieSET class represents an ordered set of strings over the extended ASCII alphabet. It supports the usual add, contains, and delete methods. It also provides character-based methods for finding the string in the set that is the longest prefix of a given prefix, finding all strings in the set that start with a given prefix, and finding all strings in the set that match a given pattern.

This implementation uses a 256-way trie. The add, contains, delete, and longest prefix methods take time proportional to the length of the key (in the worst case). Construction takes constant time.

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

Author:

Robert Sedgewick, Kevin Wayne

Constructor Summary

Constructors

Constructor and Description
TrieSET() Initializes an empty set of strings.

Method Summary

Methods

Modifier and Type	Method and Description
void	add(String key) Adds the key to the set if it is not already present.
boolean	contains(String key) Does the set contain the given key?
void	delete(String key) Removes the key from the set if the key is present.
boolean	isEmpty() Is the set empty?
Iterator<String>	iterator() Returns all of the keys in the set, as an iterator.
Iterable<String>	keysThatMatch(String pattern) Returns all of the keys in the set 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 set that is the longest prefix of query, or null, if no such string.
static void	main(String[] args) Unit tests the TrieSET data type.
int	size() Returns the number of strings in the set.

Methods inherited from class java.lang.Object

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

Constructor Detail

TrieSET

public TrieSET()

Initializes an empty set of strings.

Method Detail

contains

public boolean contains(String key)

Does the set contain the given key?

Parameters:

key - the key

Returns:

true if the set contains key and false otherwise

Throws:

NullPointerException - if key is null

add

public void add(String key)

Adds the key to the set if it is not already present.

Parameters:

key - the key to add

Throws:

NullPointerException - if key is null

size

public int size()

Returns the number of strings in the set.

Returns:

the number of strings in the set

isEmpty

public boolean isEmpty()

Is the set empty?

Returns:

true if the set is empty, and false otherwise

iterator

public Iterator<String> iterator()

Returns all of the keys in the set, as an iterator. To iterate over all of the keys in a set named set, use the foreach notation: for (Key key : set).

Specified by:

iterator in interface Iterable<String>

Returns:

an iterator to all of the keys in the set

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 set that match pattern, where . symbol is treated as a wildcard character.

Parameters:

pattern - the pattern

Returns:

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

longestPrefixOf

public String longestPrefixOf(String query)

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

Parameters:

query - the query string

Returns:

the string in the set 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.