Before the refactor

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
import scala.collection.mutable.Stack
class SuffixTree() {
var currentStringCounter : Int = 0
var root = new Vertex(null, 0, 0, null)
var last : Vertex = null
var maskAllStringsPassed: Int = 0
var LongestCommonPath : Vertex = root
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) = {
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 == 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)
}
}