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

}