// A = type of element in keys.
// B = type of value in nodes.
// Can be case-sensitive or case-insensitive
// values can't be null
sclass ListTrie<A, B> {
  B value;
  Comparator<A> comparator;
  TreeMap<L<A>, ListTrie<A, B>> children;
  
  *() {}
  *(Comparator<A> *comparator) {}
  
  void add(L<A> string, B value) {
    ifdef ListTrie_debug printFunctionCall("ListTrie add", string, value); endifdef
    // case 1: empty string
    if (empty(string)) ret with this.value = value;
    
    // case 2: some prefix of new string exists
    L<A> existingPrefix = longestCommonPrefixOfNavigableSetAndList(string, navigableKeys(children), comparator);
      
    ifdef ListTrie_debug print(+existingPrefix); endifdef
    if (nempty(existingPrefix)) {
      ListTrie<A, B> child = children.get(existingPrefix);
      L<A> substring = subList(string, l(existingPrefix));
      
      // case 2a: new string is complete suffix of existing child
      ifdef ListTrie_debug print(+child); endifdef
      if (child != null)
        ret with child.add(substring, value);
      
      // case 2b: make new branch
      ListTrie<A, B> branch = newChild(null);
      Map.Entry<L<A>, ListTrie<A, B>> e = children.higherEntry(existingPrefix);
      L<A> key = e.getKey();
      child = e.getValue();
      children.remove(e.getKey());
      children.put(existingPrefix, branch);
      branch.makeChildren().put(subList(key, l(existingPrefix)), child);
      branch.children.put(substring, newChild(value));
      ret;
    }
   
    // case 3: no existing prefix, just add new child
    makeChildren().put(string, newChild(value));
  }
  
  Map<L<A>, B> asMap() {
    Map<L<A>, B> map = new TreeMap(listComparator(comparator));
    new L<A> buf;
    collectMap(buf, map);
    ret map;
  }
  
  private void collectMap(L<A> buf, Map<L<A>, B> map) {
    if (value != null) map.put(cloneList(buf), value);
    int n = l(buf);
    for (L<A> string, ListTrie<A, B> child : children) {
      buf.addAll(string);
      child.collectMap(buf, map);
      truncateList(buf, 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 (L<A> string, ListTrie<A, B> child : children) {
      buf.append(spaces(indent)).append(string);
      child.toString(buf, indent);
    }
  }
  
  private ListTrie<A, B> newChild(B value) {
    ListTrie<A, B> child = new(comparator);
    child.value = value;
    ret child;
  }  
  
  private TreeMap<L<A>, ListTrie<A, B>> makeChildren() {
    if (children == null) children = new TreeMap(listComparator(comparator));
    ret children;
  }
  
  Set<L<A>> childStrings() { ret keys(children); }
  ListTrie<A, B> getChild(L<A> string) { ret children.get(string); }
  NavigableMap<L<A>, ListTrie<A, B>> children() { ret children; }
}

Began life as a copy of #1030153