public class TrieSET extends Object implements Iterable<String>
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.
Constructor and Description |
---|
TrieSET()
Initializes an empty set of strings.
|
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 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 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.
|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
forEach, spliterator
public boolean contains(String key)
key
- the keytrue
if the set contains key
and
false
otherwiseIllegalArgumentException
- if key
is null
public void add(String key)
key
- the key to addIllegalArgumentException
- if key
is null
public int size()
public boolean isEmpty()
true
if the set is empty, and false
otherwisepublic Iterator<String> iterator()
set
, use the
foreach notation: for (Key key : set)
.public Iterable<String> keysWithPrefix(String prefix)
prefix
.prefix
- the prefixprefix
,
as an iterablepublic 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 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 void delete(String key)
key
- the keyIllegalArgumentException
- if key
is null
public static void main(String[] args)
TrieSET
data type.args
- the command-line arguments