/*class TerminateGenerator[T] {
class Terminator[T](val id: Int) {
def compareTo(that: T) = 1
def compareTo(that: Terminator[T]) = this.id - that.id
}
var id = 0
def generateTerminator(): Terminator = {
id += 1
new Terminator[T](id - 1)
}
}*/
import scala.collection.immutable.TreeMap
import scala.collection.mutable.HashSet
/*class SuffixTree[T]() {
var currentContentCounter = 0;
var cur_id = 0
var linkMap = new TreeMap[Int, Vertex]
var root = new Vertex(Nil, null, cur_id)
}*/
object SuffixTree {
var cur_id = 1
def generateId() = {
cur_id += 1
cur_id - 1
}
def generateRoot() = new Vertex(null, 0, 0, 0, 0)
}
class SuffixTree(var olderTree: SuffixTree = null) {
var root = SuffixTree.generateRoot()
var currentStringCounter = 0
var linkMap = new TreeMap[Int, Vertex] + (root.id -> root)
var oldLinks = new HashSet[Int]
var last : Int = -1
var maskAllStringsPassed = 0
var LongestCommonPath : Vertex = root
if (olderTree != null) initializeByOtherTree(olderTree)
def initializeByOtherTree(other: SuffixTree) = {
root = other.root.duplicate()
currentStringCounter = other.currentStringCounter
linkMap = other.linkMap + (root.id -> root)
oldLinks ++= other.linkMap.keySet - root.id
last = other.last
maskAllStringsPassed = ((other.maskAllStringsPassed + 1) << 1) - 1
LongestCommonPath = root
}
def addSuffixToVertex(begin_id: Int, newString: String, start: Int): Int = {
var begin = linkMap(begin_id)
val passedStringMask = 1 << currentStringCounter
begin.passedStringsMask |= passedStringMask
var currentVertex = begin
var currentChar = newString.charAt(start)
var i = start
if (currentVertex.children.contains(currentChar)) {
currentVertex = linkMap(currentVertex.children(currentChar))
var j = currentVertex.startIndex
while (true) {
if (j == currentVertex.endIndex + 1) {
currentVertex.passedStringsMask |= passedStringMask
return addSuffixToVertex(currentVertex.id, 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.parentId, SuffixTree.generateId())
if (oldLinks contains currentVertex.parentId) {
linkMap += (currentVertex.parentId -> parent(currentVertex).duplicate())
oldLinks -= currentVertex.parentId
}
linkMap += (newVertex.id -> newVertex)
parent(currentVertex).children += (currentChar -> newVertex.id)
if (oldLinks contains currentVertex.id) {
currentVertex = currentVertex.duplicate()
linkMap += (currentVertex.id -> currentVertex)
oldLinks -= currentVertex.id
}
currentVertex.startIndex = j
currentVertex.parentId = newVertex.id
newVertex.children += (treeStringCurChar -> currentVertex.id)
newVertex.passedStringsMask = currentVertex.passedStringsMask
newVertex.pathLength = parent(newVertex).pathLength + newVertex.workStringLength() + 1
newVertex.passedStringsMask |= passedStringMask
return addSuffixToVertex(newVertex.id, newString, i)
}
}
i += 1
j += 1
}
}
var newVertex = new Vertex(newString, start, newString.length() - 1, begin.id, SuffixTree.generateId())
if (oldLinks contains currentVertex.parentId) {
linkMap += (currentVertex.parentId -> parent(currentVertex).duplicate())
oldLinks -= currentVertex.parentId
}
linkMap += (newVertex.id -> newVertex)
begin.children += (currentChar -> newVertex.id)
newVertex.pathLength = begin.pathLength + newVertex.workStringLength() + 1
newVertex.passedStringsMask |= passedStringMask
return newVertex.id
}
def SearchPosition(begin_id: Int, SearchStr: String, start: Int, end: Int): Int = {
var begin = linkMap(begin_id)
var passedStringMask = 1 << currentStringCounter
begin.passedStringsMask |= passedStringMask
if (start > end) {
return begin_id
}
var currentVertex = linkMap(begin.children(SearchStr.charAt(start)))
if ((end - start) >= currentVertex.workStringLength()) {
currentVertex.passedStringsMask |= passedStringMask
return SearchPosition(currentVertex.id, 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.id, SuffixTree.generateId())
if (oldLinks contains begin.id) {
begin = begin.duplicate()
linkMap += (begin.id -> begin)
oldLinks -= begin.id
}
linkMap += (newVertex.id -> newVertex)
begin.children += (currentChar -> newVertex.id)
if (oldLinks contains currentVertex.id) {
currentVertex = currentVertex.duplicate()
linkMap += (currentVertex.id -> currentVertex)
oldLinks -= currentVertex.id
}
currentVertex.startIndex = currentVertex.startIndex + end - start + 1
currentVertex.parentId = newVertex.id
newVertex.passedStringsMask = currentVertex.passedStringsMask
newVertex.children += (currentVertex.workString.charAt(currentVertex.startIndex) -> currentVertex.id)
newVertex.pathLength = begin.pathLength + newVertex.workStringLength() + 1
newVertex.passedStringsMask |= passedStringMask
return newVertex.id
}
}
def addSuffix(newString: String, start: Int) = {
var lastVertex = vertexById(last)
if (parent(lastVertex) == root) {
last = addSuffixToVertex(root.id, newString, start)
} else if (parent(parent(lastVertex)) == root) {
var oldLastParent = parent(lastVertex)
var foundPosition = SearchPosition(root.id, parent(lastVertex).workString, parent(lastVertex).startIndex + 1, parent(lastVertex).endIndex)
var addedId = addSuffixToVertex(foundPosition, lastVertex.workString, lastVertex.startIndex)
oldLastParent.suffixLink = foundPosition
last = addedId
} else {
var oldLastParent = parent(lastVertex)
var foundPosition = SearchPosition(parent(parent(lastVertex)).suffixLink, parent(lastVertex).workString, parent(lastVertex).startIndex, parent(lastVertex).endIndex)
var addedId = addSuffixToVertex(foundPosition, lastVertex.workString, lastVertex.startIndex)
oldLastParent.suffixLink = foundPosition
last = addedId
}
}
def addString(newString: String) = {
var newTree = new SuffixTree(this)
newTree.addStringInternal(newString)
}
def addStringInternal(newString: String): SuffixTree = {
var passedStringMask = 1 << currentStringCounter
root.passedStringsMask |= passedStringMask
if (currentStringCounter == 0) {
var newVertex = new Vertex(newString, 0, newString.length()-1, root.id, SuffixTree.generateId())
linkMap += (newVertex.id -> newVertex)
root.children += (newString.charAt(0) -> newVertex.id)
last = newVertex.id
newVertex.pathLength = newVertex.workStringLength() + 1
newVertex.passedStringsMask |= passedStringMask
} else {
last = addSuffixToVertex(root.id, newString, 0)
}
for (i <- 1 until newString.length()) {
this addSuffix(newString, i)
}
currentStringCounter += 1
this
}
def findLCP(vertex: Vertex = root) {
if ((vertex.passedStringsMask == maskAllStringsPassed) && (vertex.pathLength > LongestCommonPath.pathLength)) {
LongestCommonPath = vertex
}
if (vertex.children != null) {
vertex.children foreach{ case (key, id) => findLCP(vertexById(id))}
}
}
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(parent(v), partOfLCPString :: list)
}
}
var pathNameList = getLCPRec(LongestCommonPath, Nil)
print(pathNameList)
}
def TraverseAndPrint() {
print("digraph graphname {\n")
TraverseAndPrintRecursive(this.root)
println("}")
}
def TraverseAndPrintRecursive(currentVertex: Vertex) {
if (currentVertex.id != 0) {
var curParent = parent(currentVertex)
var cur = currentVertex
var image = currentVertex.workString
var start = currentVertex.startIndex
var end = currentVertex.endIndex
println(cur.id + "[label=\"" + currentVertex.pathLength + "\"];");
println(curParent.id + "[label=\"" + curParent.pathLength + "\"];");
if (currentVertex.passedStringsMask == maskAllStringsPassed) {
println(cur.id + "[color=green];");
}
println(curParent.id + "->" + cur.id +"[label=\"" + image.substring(start, end+1) + "\"];\n");
if (currentVertex.suffixLink != -1) {
var link = currentVertex.suffixLink
println(cur.id + "->" + link +"[color=red];")
}
}
if (currentVertex.children != null) {
currentVertex.children foreach{ case (key, id) => TraverseAndPrintRecursive(vertexById(id))}
}
}
def parent(v: Vertex) = linkMap(v.parentId)
def vertexById(id: Int) = linkMap(id)
}
import scala.collection.immutable.TreeMap
class Vertex(var workString : String, var startIndex : Int, var endIndex : Int, var parentId : Int, var id : Int) {
var suffixLink = -1
var children = new TreeMap[Char, Int]
var passedStringsMask = 0
var pathLength = 0
def workStringLength(): Int = (endIndex - startIndex)
def duplicate() : Vertex = {
var newVertex = new Vertex(workString, startIndex, endIndex, parentId, id)
newVertex.suffixLink = suffixLink
newVertex.children = children
newVertex.pathLength = pathLength
newVertex.passedStringsMask = passedStringsMask
newVertex
}
}
/**
* Created by Const on 4/23/14.
*/
object MainObject {
def main(args: Array[String]) {
var tree = new SuffixTree()
var uniq_symbol = List('!', '@', '#')
tree.maskAllStringsPassed = (1<<0) - 1
var tree1 = tree.addString("1234" + uniq_symbol(0))
var tree2 = tree1.addString("123" + uniq_symbol(1))
var tree3 = tree2.addString("123" + uniq_symbol(2))
tree3.findLCP()
tree3.printLCP()
tree1.TraverseAndPrint()
}
}