sclass SuffixTree {
  Node root;
  S fullText;
  S textWithTerminator; // all Substrings are constructed off this

  private static final String WORD_TERMINATION = "$";
  private static final int POSITION_UNDEFINED = -1;
  
  sclass Node {
    Substring text;
    new L<Node> children;
    int position;

    *(Substring *text, int *position) {}

    Substring getText() { ret text; }
    void setText(Substring text) {
      //print("Setting text: " + quote(this.text) + " => " + quote(text);
      this.text = text;
    }

    int getPosition() { ret position; }
    void setPosition(int position) { this.position = position; }
    L<Node> getChildren() { ret children; }
    void setChildren(L<Node> children) { this.children = children; }

    S printTree(String depthIndicator) {
        S str = "";
        S positionStr = position > -1 ? "[" + position + "]" : "";
        str += depthIndicator + text + positionStr + "\n";

        for (int i = 0; i < children.size(); i++)
          str += children.get(i).printTree(depthIndicator + "\t");
        return str;
    }

    toString { ret printTree(""); }
  }
  
  *(S text) {
    textWithTerminator = text + WORD_TERMINATION;
    root = new Node(Substring(textWithTerminator, 0, 0), POSITION_UNDEFINED);
    for i over text:
      addSuffix(Substring(textWithTerminator, i), i);
    fullText = text;
  }

  public LS markText(S pattern) {
    //LOGGER.info("Searching for pattern \"{}\"", pattern);
    new LS result;
    L<Node> nodes = getAllNodesInTraversePath(pattern, root, false);

    if (nodes.size() > 0) {
        Node lastNode = nodes.get(nodes.size() - 1);
        if (lastNode != null) {
            L<Int> positions = getPositions(lastNode);
            sortInPlace(positions);
            positions.forEach(m -> result.add((markPatternInText(m, pattern))));
        }
    }
    return result;
  }

  private void addSuffix(Substring suffix, int position) {
      //print("Adding new suffix: " + quote(suffix));
      List<Node> nodes = getAllNodesInTraversePath(suffix, root, true);
      if (nodes.size() == 0) {
          addChildNode(root, suffix, position);
          //LOGGER.info("{}", printTree());
      } else {
          Node lastNode = nodes.remove(nodes.size() - 1);
          Substring newText = suffix;
          if (nodes.size() > 0) {
              Substring existingSuffixUptoLastNode = joinSubstringObjects(map(nodes, a -> a.getText()));

              // Remove prefix from newText already included in parent
              newText = newText.substring(existingSuffixUptoLastNode.length());
          }
          extendNode(lastNode, newText, position);
          //LOGGER.info("{}", printTree());
      }
  }

  private List<Integer> getPositions(Node node) {
      List<Integer> positions = new ArrayList<>();
      if (node.getText()
          /*.endsWith(WORD_TERMINATION)*/.endsAtEnd()) {
          positions.add(node.getPosition());
      }
      for (int i = 0; i < node.getChildren()
          .size(); i++) {
          positions.addAll(getPositions(node.getChildren()
              .get(i)));
      }
      return positions;
  }

  private String markPatternInText(Integer startPosition, String pattern) {
      String matchingTextLHS = fullText.substring(0, startPosition);
      String matchingText = fullText.substring(startPosition, startPosition + pattern.length());
      String matchingTextRHS = fullText.substring(startPosition + pattern.length());
      return matchingTextLHS + "[" + matchingText + "]" + matchingTextRHS;
  }

  private void addChildNode(Node parentNode, Substring text, int position) {
      parentNode.getChildren()
          .add(new Node(text, position));
  }

  private void extendNode(Node node, Substring newText, int position) {
      Substring currentText = node.getText();
      Substring commonPrefix = getLongestCommonPrefix(currentText, newText);

      if (neq(commonPrefix, currentText)) {
          Substring parentText = currentText.substring(0, commonPrefix.length());
          Substring childText = currentText.substring(commonPrefix.length());
          splitNodeToParentAndChild(node, parentText, childText);
      }

      Substring remainingText = newText.substring(commonPrefix.length());
      addChildNode(node, remainingText, position);
  }

  private void splitNodeToParentAndChild(Node parentNode, Substring parentNewText, Substring childNewText) {
      Node childNode = new Node(childNewText, parentNode.getPosition());

      while (parentNode.getChildren().size() > 0)
        childNode.getChildren().add(parentNode.getChildren().remove(0));

      parentNode.getChildren().add(childNode);
      parentNode.setText(parentNewText);
      parentNode.setPosition(POSITION_UNDEFINED);
  }

  private Substring getLongestCommonPrefix(Substring str1, Substring str2) {
    int compareLength = Math.min(str1.length(), str2.length());
    for (int i = 0; i < compareLength; i++)
        if (str1.charAt(i) != str2.charAt(i))
            ret str1.substring(0, i);
    ret str1.substring(0, compareLength);
  }

  private L<Node> getAllNodesInTraversePath(CharSequence pattern, Node startNode, boolean isAllowPartialMatch) {
      new L<Node> nodes;
      for (int i = 0; i < startNode.getChildren().size(); i++) {
          Node currentNode = startNode.getChildren().get(i);
          CharSequence nodeText = currentNode.getText();
          if (empty(nodeText)) fail("Node text empty: " + currentNode);
          if (pattern.charAt(0) == nodeText.charAt(0)) {
              if (isAllowPartialMatch && pattern.length() <= nodeText.length()) {
                  nodes.add(currentNode);
                  return nodes;
              }

              int compareLength = Math.min(nodeText.length(), pattern.length());
              for (int j = 1; j < compareLength; j++) {
                  if (pattern.charAt(j) != nodeText.charAt(j)) {
                      if (isAllowPartialMatch) {
                          nodes.add(currentNode);
                      }
                      return nodes;
                  }
              }

              nodes.add(currentNode);
              if (pattern.length() > compareLength) {
                  List<Node> nodes2 = getAllNodesInTraversePath(subCharSequence(pattern, compareLength), currentNode, isAllowPartialMatch);
                  if (nodes2.size() > 0) {
                      nodes.addAll(nodes2);
                  } else if (!isAllowPartialMatch) {
                      nodes.add(null);
                  }
              }
              return nodes;
          }
      }
      return nodes;
  }

  S printTree() { ret root.printTree(""); }
}