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)
}
}