/**
 * High performance string map.
 * <br/>
 * <br/>
 * Please <i>note</i> that:
 * <ul>
 * <li>The key should not be null.</li>
 * <li>The key should not be empty.</li>
 * <li>The key should contains <b>only ASCII</b> characters.</li>
 * <li>The value should not be null.</li>
 * </ul>
 * <b>No runtime validation is provided in favor of performance.</b>
 */
public class TrieMap<T> {

  private static class Node<T> {

    @SuppressWarnings("unchecked")
    Node<T>[] next = new Node[128];

    T value;
  }

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

  /**
   * Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced.
   *
   * @param key Key with which the specified value is to be associated.
   * @param value Value to be associated with the specified key.
   */
  public void put(String key, T value) {
    Node<T> node = root;
    for (int i = 0; i < key.length(); i++) {
      int c = key.charAt(i);
      if (node.next[c] == null) {
        node.next[c] = new Node<T>();
      }
      node = node.next[c];
    }
    node.value = value;
  }

  /**
   * Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
   *
   * @param key The key whose associated value is to be returned.
   * @return The value to which the specified key is mapped, or null if this map contains no mapping for the key.
   */
  public T get(String key) {
    Node<T> node = root;
    for (int i = 0; i < key.length(); i++) {
      int c = key.charAt(i);
      if (node.next[c] == null) {
        return null;
      }
      node = node.next[c];
    }
    return node.value;
  }

  /**
   * Returns true if this map contains a mapping for the specified key.
   *
   * @param key The key whose presence in this map is to be tested.
   * @return True if this map contains a mapping for the specified key.
   */
  public boolean has(String key) {
    return get(key) == null;
  }
}