// A = type of value in nodes.

// Can be case-sensitive or case-insensitive

// values can't be null

sclass StringTrie<A> {

  A value;

  TreeMap<S, StringTrie<A>> children;

  *() {}

  *(A *value) {}

  *(Iterable<S> strings) { addAll(strings, null); } // give all leaves null values

  void makeCaseInsensitive() {

    children = asCIMap(children);

  }

  bool isCaseInsensitive() {

    ret isCIMap(children);

  }

  void addAll(Iterable<S> strings, A value) {

    fOr (S s : strings)

      add(s, value);

  }

  void put(S string, A value) { add(string, value); }

  void add(S string, A value) {

    ifdef StringTrie_debug printFunctionCall("StringTrie add", string, value); endifdef

    // case 1: empty string

    if (empty(string)) ret with this.value = value;

    // case 2: some prefix of new string exists

    S existingPrefix = longestLocalPrefix(string);

    ifdef StringTrie_debug print(+existingPrefix); endifdef

    if (nempty(existingPrefix)) {

      StringTrie<A> child = children.get(existingPrefix);

      S substring = substring(string, l(existingPrefix));

      // case 2a: new string is complete suffix of existing child

      ifdef StringTrie_debug print(+child); endifdef

      if (child != null)

        ret with child.add(substring, value);

      // case 2b: make new branch

      StringTrie<A> branch = newChild(null);

      if (branch.children == null) branch.children = new TreeMap;

      Map.Entry<S, StringTrie<A>> e = children.higherEntry(existingPrefix);

      S key = e.getKey();

      child = e.getValue();

      children.remove(e.getKey());

      children.put(existingPrefix, branch);

      branch.children.put(substring(key, l(existingPrefix)), child);

      branch.children.put(substring, newChild(value));

      ret;

    }

    // case 3: no existing prefix, just add new child

    if (children == null) children = new TreeMap;

    children.put(string, newChild(value));

  }

  // returns TreeMap or ciMap

  Map<S, A> asMap() {

    Map<S, A> map = isCaseInsensitive() ? ciMap() : new TreeMap;

    new StringBuilder buf;

    collectMap(buf, map);

    ret map;

  }

  private void collectMap(StringBuilder buf, Map<S, A> map) {

    if (value != null) map.put(str(buf), value);

    int n = l(buf);

    for (S string, StringTrie<A> child : children) {

      buf.append(string);

      child.collectMap(buf, map);

      buf.setLength(n);

    }

  }

  toString {

    new StringBuilder buf;

    if (value != null) {

      buf.append("\"\" => ").append(value).append("\n");

      childrenToString(buf, 2);

    } else

      childrenToString(buf, 0);

    ret str(buf);

  }

  void toString(StringBuilder buf, int indent) {

    if (value != null)

      buf.append(" => ").append(value);

    buf.append("\n");

    childrenToString(buf, indent+2);

  }

  void childrenToString(StringBuilder buf, int indent) {

    for (S string, StringTrie<A> child : children) {

      buf.append(spaces(indent)).append(quote(string));

      child.toString(buf, indent);

    }

  }

  private StringTrie<A> newChild(A value) {

    StringTrie<A> child = new(value);

    if (isCaseInsensitive()) child.makeCaseInsensitive();

    ret child;

  }

  S longestLocalPrefix(S string) {

    ret isCaseInsensitive()

      ? longestCommonPrefixOfCISetAndString(string, navigableKeys(children))

      : longestCommonPrefixOfNavigableSetAndString(string, navigableKeys(children));

  }

  Set<S> childStrings() { ret keys(children); }

  StringTrie<A> getChild(S string) { ret children.get(string); }

  NavigableMap<S, StringTrie<A>> children() { ret children; }

}