sclass OccTree<A> {
  int count;
  new HashMap<A, OccTree> followUp;
  OccTree<A> parent;
  
  void add(L<A> script) {
    OccTree node = this;
    ++count;
    for (A c : script)
      (node = node.getOrMakeFollowUp(c)).count++;
  }
  
  OccTree getOrMakeFollowUp(A c) {
    OccTree node = followUp.get(c);
    if (node == null)
      followUp.put(c, node = newChild());
    ret node;
  }
  
  OccTree followUp(A a) {
    ret followUp.get(a);
  }
  
  Set<A> followUpKeys() {
    ret keys(followUp);
  }
  
  A randomChoice() {
    MultiSet<A> ms = new MultiSet(false);
    for (A c : keys(followUp))
      ms.add(c, followUp.get(c).count);
    ret msOneOf(ms);
  }
  
  OccTree<A> newChild() {
    new OccTree<A> child;
    child.parent = this;
    ret child;
  }
  
  // size including all nodes
  int size() {
    int n = 1;
    for (OccTree t : values(followUp))
      n += t.size();
    ret n;
  }
  
  L<OccTree<A>> allLeaves() {
    new L l;
    collectLeaves(l);
    ret l;
  }
  
  void collectLeaves(L<OccTree> l) {
    if (isLeaf())
      l.add(this);
    else
      for (OccTree t : values(followUp))
        t.collectLeaves(l);
  }
  
  bool isLeaf() {
    ret isEmpty(followUp);
  }
}