skalka

import scala.collection.mutable.Stack

class SuffixTree() {
  var currentStringCounter : Int = 0
  var root : Vertex = null
  var last : Vertex = null
  var maskAllStringsPassed: Int = 0

  var LongestCommonPath : Vertex = null

  def addSuffixToVertex(begin: Vertex, newString: String, start: Int): Vertex = {
    val passedStringMask = 1 << currentStringCounter
    begin.passedStringsMask |= passedStringMask
    var currentVertex = begin
    var currentChar = newString.charAt(start)
    var i = start
    if (currentVertex.children.contains(currentChar)) {
      currentVertex = currentVertex.children apply currentChar
      var j = currentVertex.startIndex
      while (true) {
        if (j == currentVertex.endIndex + 1) {
          currentVertex.passedStringsMask |= passedStringMask
          return addSuffixToVertex(currentVertex, newString, i)
        } else {
          var newStringCurChar = newString.charAt(i)
          var treeStringCurChar = currentVertex.workString.charAt(j)

          if (newStringCurChar != treeStringCurChar) {
            var newVertex = new Vertex(currentVertex.workString, currentVertex.startIndex, j - 1, currentVertex.parent)
            currentVertex.parent.children += (currentChar -> newVertex)
            currentVertex.startIndex = j
            currentVertex.parent = newVertex
            newVertex.children += (treeStringCurChar -> currentVertex)
            newVertex.passedStringsMask = currentVertex.passedStringsMask
            newVertex.pathLength = newVertex.parent.pathLength + newVertex.workStringLength() + 1
            newVertex.passedStringsMask |= passedStringMask
            return addSuffixToVertex(newVertex, newString, i)
          }
        }
        i += 1
        j += 1
      }
    }
    var newVertex = new Vertex(newString, start, newString.length() - 1, begin)
    begin.children += (currentChar -> newVertex)
    newVertex.pathLength = begin.pathLength + newVertex.workStringLength() + 1
    newVertex.passedStringsMask |= passedStringMask
    return newVertex
  }

  def SearchPosition(begin: Vertex, SearchStr: String, start: Int, end: Int): Vertex = {
    var passedStringMask = 1 << currentStringCounter
    begin.passedStringsMask |= passedStringMask
    if (start > end) {
      return begin
    }
    var currentVertex = begin.children apply SearchStr.charAt(start)
    if ((end - start) >= currentVertex.workStringLength()) {
      currentVertex.passedStringsMask |= passedStringMask
      return SearchPosition(currentVertex, SearchStr, start + currentVertex.workStringLength() + 1, end)
    } else {
      var currentChar = SearchStr.charAt(start)
      var newVertex = new Vertex(currentVertex.workString, currentVertex.startIndex, currentVertex.startIndex + (end - start), begin)
      begin.children += (currentChar -> newVertex)
      currentVertex.startIndex = currentVertex.startIndex + end - start + 1
      currentVertex.parent = newVertex
      newVertex.passedStringsMask = currentVertex.passedStringsMask
      newVertex.children += (currentVertex.workString.charAt(currentVertex.startIndex) -> currentVertex)

      newVertex.pathLength = begin.pathLength + newVertex.workStringLength() + 1
      newVertex.passedStringsMask |= passedStringMask

      return newVertex
    }
  }

  def addSuffix(newString: String, start: Int) = {
    if (last.parent == root) {
      var newVertex = addSuffixToVertex(root, newString, start)
      last = newVertex
    } else if (last.parent.parent == root) {
      var oldLastParent = last.parent
      var foundPosition = SearchPosition(root, last.parent.workString, last.parent.startIndex + 1, last.parent.endIndex)
      var newVertex = addSuffixToVertex(foundPosition, last.workString, last.startIndex)
      oldLastParent.suffixLink = foundPosition
      last = newVertex
    } else {
      var oldLastParent = last.parent
      var foundPosition = SearchPosition(last.parent.parent.suffixLink, last.parent.workString, last.parent.startIndex, last.parent.endIndex)
      var newVertex = addSuffixToVertex(foundPosition, last.workString, last.startIndex)
      oldLastParent.suffixLink = foundPosition
      last = newVertex
    }
  }

  def addString(newString: String) = {
    if  (root == null) {
      root = new Vertex(null, 0, 0, null)
    }
    var passedStringMask = 1 << currentStringCounter
    root.passedStringsMask |= passedStringMask

    if (currentStringCounter == 0) {
      var newVertex = new Vertex(newString, 0, newString.length()-1, root)
      root.children += (newString.charAt(0) -> newVertex)
      last = newVertex
      newVertex.pathLength = newVertex.workStringLength() + 1
      newVertex.passedStringsMask |= passedStringMask
    } else {
      last = addSuffixToVertex(root, newString, 0)
    }

    // Debug: print the SuffixTree
    //TraverseAndPrint(this);
    var i = 1
    for (i <- 1 until newString.length()) {
      this addSuffix(newString, i)
      // Debug: print the SuffixTree
      //TraverseAndPrint(this);
    }
    currentStringCounter += 1
  }

  def findLCP(vertex: Vertex = root) {
    if ((vertex.passedStringsMask == maskAllStringsPassed) && (vertex.pathLength > LongestCommonPath.pathLength)) {
      LongestCommonPath = vertex
    }
    if (vertex.children != null) {
      vertex.children foreach{ case (k, v) => findLCP(v)}
    }
  }

  def printLCP() {
    def getLCPRec(v: Vertex, list: List[String]):List[String] = v match {
      case vertex if vertex.parent == root   => list
      case _   => {
        val partOfLCPString = v.workString.substring(v.startIndex, v.endIndex + 1)
        getLCPRec(v.parent, partOfLCPString :: list)
      }
    }
    var pathNameList = getLCPRec(LongestCommonPath, Nil)
    print(pathNameList)
  }
}