package algs52; // section 5.2
import stdlib.*;
import algs13.Queue;
/* ***********************************************************************
 *  Compilation:  javac TrieST.java
 *  Execution:    java TrieST < words.txt
 *  Dependencies: StdIn.java
 *
 *  A string symbol table for ASCII strings, implemented using a 256-way trie.
 *
 *  % java TrieST < shellsST.txt
 *  by 4
 *  sea 6
 *  sells 1
 *  she 0
 *  shells 3
 *  shore 7
 *  the 5
 *
 *************************************************************************/

public class TrieST<V> {
  private static final int R = 256;        // extended ASCII

  private Node<V> root = new Node<>();

  private static class Node<V> {
    public Node() { }
    public V val;
    @SuppressWarnings("unchecked")
    public final Node<V>[] next = new Node[R];
  }

  /* **************************************************
   * Is the key in the symbol table?
   ****************************************************/
  public boolean contains(String key) {
    return get(key) != null;
  }

  public V get(String key) {
    Node<V> x = get(root, key, 0);
    if (x == null) return null;
    return x.val;
  }

  private Node<V> get(Node<V> x, String key, int d) {
    if (x == null) return null;
    if (d == key.length()) return x;
    char c = key.charAt(d);
    return get(x.next[c], key, d+1);
  }

  /* **************************************************
   * Insert key-value pair into the symbol table.
   ****************************************************/
  public void put(String key, V val) {
    root = put(root, key, val, 0);
  }

  private Node<V> put(Node<V> x, String key, V val, int d) {
    if (x == null) x = new Node<>();
    if (d == key.length()) {
      x.val = val;
      return x;
    }
    char c = key.charAt(d);
    x.next[c] = put(x.next[c], key, val, d+1);
    return x;
  }

  // find the key that is the longest prefix of s
  public String longestPrefixOf(String query) {
    int length = longestPrefixOf(root, query, 0, 0);
    return query.substring(0, length);
  }

  // find the key in the subtrie rooted at x that is the longest
  // prefix of the query string, starting at the dth character
  private int longestPrefixOf(Node<V> x, String query, int d, int length) {
    if (x == null) return length;
    if (x.val != null) length = d;
    if (d == query.length()) return length;
    char c = query.charAt(d);
    return longestPrefixOf(x.next[c], query, d+1, length);
  }


  public Iterable<String> keys() {
    return keysWithPrefix("");
  }

  public Iterable<String> keysWithPrefix(String prefix) {
    Queue<String> queue = new Queue<>();
    Node<V> x = get(root, prefix, 0);
    collect(x, prefix, queue);
    return queue;
  }

  private void collect(Node<V> x, String key, Queue<String> queue) {
    if (x == null) return;
    if (x.val != null) queue.enqueue(key);
    for (int c = 0; c < R; c++)
      collect(x.next[c], key + (char) c, queue);
  }


  public Iterable<String> keysThatMatch(String pat) {
    Queue<String> q = new Queue<>();
    collect(root, "", pat, q);
    return q;
  }

  private void collect(Node<V> x, String prefix, String pat, Queue<String> q) {
    if (x == null) return;
    if (prefix.length() == pat.length() && x.val != null) q.enqueue(prefix);
    if (prefix.length() == pat.length()) return;
    char next = pat.charAt(prefix.length());
    for (int c = 0; c < R; c++)
      if (next == '.' || next == c)
        collect(x.next[c], prefix + (char) c, pat, q);
  }

  public void delete(String key) {
    root = delete(root, key, 0);
  }

  private Node<V> delete(Node<V> x, String key, int d) {
    if (x == null) return null;
    if (d == key.length()) x.val = null;
    else {
      char c = key.charAt(d);
      x.next[c] = delete(x.next[c], key, d+1);
    }
    if (x.val != null) return x;
    for (int c = 0; c < R; c++)
      if (x.next[c] != null)
        return x;
    return null;
  }


  // test client
  public static void main(String[] args) {
    StdIn.fromFile("data/shellsST.txt");

    // build symbol table from standard input
    TrieST<Integer> st = new TrieST<>();
    for (int i = 0; !StdIn.isEmpty(); i++) {
      String key = StdIn.readString();
      st.put(key, i);
    }

    // print results
    for (String key : st.keys()) {
      StdOut.println(key + " " + st.get(key));
    }
  }
}