Package dsa

Class TrieST<Value>

  • public class TrieST<Value>
extends Object
    A data type to represent the trie data structure, which is a symbol table with with string keys.

    • Constructor Detail

      • TrieST

        public TrieST()
        Constructs an empty symbol table.

    • Method Detail

      • 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,
                Value value)
        Inserts the key and value pair into this symbol table.
        Parameters:
        key - the key.
        value - the value.

      • get

        public Value 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.