TrieSET (Algorithms 4/e)

Object
- edu.princeton.cs.algs4.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.

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

Method Summary

All Methods Static Methods Instance Methods Concrete 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 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.

Methods inherited from class Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface Iterable
forEach, spliterator

- 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:
    
    IllegalArgumentException - 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:
    
    IllegalArgumentException - 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 the character '.' is interpreted 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:
    
    IllegalArgumentException - 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:
    
    IllegalArgumentException - if key is null
  - main
```
public static void main(String[] args)
```
    Unit tests the TrieSET data type.
    
    Parameters:
    
    args - the command-line arguments

Class TrieSET

Constructor Summary

Method Summary

Methods inherited from class Object

Methods inherited from interface Iterable

Constructor Detail

TrieSET

Method Detail

contains

add

size

isEmpty

iterator

keysWithPrefix

keysThatMatch

longestPrefixOf

delete

main