// 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) {}
  
  void makeCaseInsensitive() {
    children = asCIMap(children);
  }
  
  bool isCaseInsensitive() {
    ret isCIMap(children);
  }
  
  void add(S string, A value) {
    if (empty(string)) ret with this.value = value;
    
    S existingPrefix = isCaseInsensitive()
      ? longestPrefixInCISet(string, navigableKeys(children))
      : longestPrefixInNavigableSet(string, navigableKeys(children));
      
    if (nempty(existingPrefix))
      ret with children.get(existingPrefix).add(substring(string, l(existingPrefix)), value);
    
    if (children == null) children = new TreeMap;
    StringTrie<A> child = new(value);
    if (isCaseInsensitive()) child.makeCaseInsensitive();
    children.put(string, child);
  }
  
  // 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);
      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);
    }
  }
}