// 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; }
}