Package dsa

Class TrieST<V>

java.lang.Object
dsa.TrieST<V>
Type Parameters:
V - the type of values in the trie.
public class TrieST<V> extends Object
A data type to represent the trie data structure, which is a symbol table with string keys.

  • Constructor Summary

    Constructors
    Constructor
    Description
    TrieST()
    Constructs an empty symbol table.

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    contains(String key)
    Returns true if this symbol table contains key, and false otherwise.
    void
    delete(String key)
    Deletes key and the associated value from this symbol table.
    V
    get(String key)
    Returns the value associated with key in this symbol table, or null.
    boolean
    isEmpty()
    Returns true if this symbol table is empty, and false otherwise.
    Iterable<String>
    keys()
    Returns all the keys in this symbol table.
    Iterable<String>
    keysThatMatch(String pattern)
    Returns all the keys in this symbol table that match pattern, where the . symbol is treated as a wildcard character.
    Iterable<String>
    keysWithPrefix(String prefix)
    Returns all the keys in this symbol table that start with prefix.
    String
    longestPrefixOf(String query)
    Returns the string in this symbol table that is the longest prefix of query, or null.
    static void
    main(String[] args)
    Unit tests the data type.
    void
    put(String key, V value)
    Inserts the key and value pair into this symbol table.
    int
    size()
    Returns the number of key-value pairs in this symbol table.
    String
    toString()
    Returns a string representation of this symbol table.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • TrieST

      public TrieST()
      Constructs an empty symbol table.

  • Method Details

    • isEmpty

      public boolean isEmpty()
      Returns true if this symbol table is empty, and false otherwise.
      Returns:
      true if this symbol table is empty, and false otherwise.

    • 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.

    • put

      public void put(String key, V value)
      Inserts the key and value pair into this symbol table.
      Parameters:
      key - the key.
      value - the value.

    • get

      public V get(String key)
      Returns the value associated with key in this symbol table, or null.
      Parameters:
      key - the key.
      Returns:
      the value associated with key in this symbol table, or null.

    • contains

      public boolean contains(String key)
      Returns true if this symbol table contains key, and false otherwise.
      Parameters:
      key - the key.
      Returns:
      true if this symbol table contains key, and false otherwise.

    • delete

      public void delete(String key)
      Deletes key and the associated value from this symbol table.
      Parameters:
      key - the key.

    • keys

      public Iterable<String> keys()
      Returns all the keys in this symbol table.
      Returns:
      all the keys in this symbol table.

    • keysWithPrefix

      public Iterable<String> keysWithPrefix(String prefix)
      Returns all the keys in this symbol table that start with prefix.
      Parameters:
      prefix - the prefix.
      Returns:
      all the keys in this symbol table that start with prefix.

    • keysThatMatch

      public Iterable<String> keysThatMatch(String pattern)
      Returns all the keys in this symbol table that match pattern, where the . symbol is treated as a wildcard character.
      Parameters:
      pattern - the pattern.
      Returns:
      all the keys in this symbol table that match pattern, where the . symbol is treated as a wildcard character.

    • longestPrefixOf

      public String longestPrefixOf(String query)
      Returns the string in this symbol table that is the longest prefix of query, or null.
      Parameters:
      query - the string.
      Returns:
      the string in this symbol table that is the longest prefix of query, or null.

    • toString

      public String toString()
      Returns a string representation of this symbol table.
      Overrides:
      toString in class Object
      Returns:
      a string representation of this symbol table.

    • main

      public static void main(String[] args)
      Unit tests the data type.
      Parameters:
      args - the command-line arguments.