sclass SuffixTree {
  Node root;
  S fullText;

  sclass Node {
    Substring text;
    Map<Char, Node> children;
    Set<Int> positions;

    *() {}
    *(Substring *text) {}
    
    void addPosition(int i) {
      if (positions == null) positions = new Set;
      positions.add(i);
    }
    
    void addChild(Node n) {
      if (children == null) children = new Map;
      children.put(first(n.text), n);
    }
    
    Node getChild(Char c) {
      ret mapGet(children, c);
    }
  }

  *() {}
  *(S *fullText) {
    root = new Node(Substring(fullText, 0, 0), new Set);
    for i over fullText:
      addSuffix(Substring(fullText, i), i);
  }

  void addSuffix(Substring s, int position) {
    Node node = root;
    
    while (!empty(s)) {
      int n = lCommonPrefix_CharSequence(node.text, s);
      if (n >= l(node.text)) {
        s = s.substring(n);
        if (empty(s)) {
          node.addPosition(position);
          ret;
        } else {
          Node n = node.getChild(first(s));
          if (n == null) {
            n = new Node(s);
            n.addPosition(position);
            node.addChild(n);
            ret;
          } else
            node = n;
        }
      } else {
        // split node
        Node n = new Node(node.text.substring(n));
        n.addPosition(position);
        node.text = node.text.substring(0, n);
        node.addChild(n);
        node = n;
        ret;
      }
    }
  }

  public L<Int> indicesOf(S pattern) {
    new IntBuffer out;
    getIndicesOf(out, root, pattern, 0);
    ret out.asVirtualList();
  }
  
  void getIndicesOf(IntBuffer out, Node node, S pattern, int iPattern) {
    if (iPattern >= l(pattern))
      collectPositions(out, node);
    else {
      // TODO
    }
  }
  
  L<Int> getPositions(Node node) {
    new IntBuffer out;
    collectPositions(out, node);
    ret out.asVirtualList();
  }
  
  void collectPositions(IntBuffer out, Node node) {
    if (node == null) ret;
    out.addAll(node.positions);
    fOr (Node n : node.children)
      collectPositions(out, n);
  }
}