import scala.collection.immutable.HashMap
class CritBitTree[T](nodes: HashMap[String, CritBitTree[T]], isExternalNode: Boolean, data: Option[T]) {
def this(isExternalNode: Boolean, data: Option[T]) = this(HashMap[String, CritBitTree[T]](), isExternalNode, data)
/*def contains(bitString: String): Boolean = {
get(bitString) != None
}*/
/*def get(bitString: String): Option[T] = {
if (bitString.isEmpty) {
if (isExternalNode) {
return data
} else {
return None
}
}
val commonPrefix = findCommonPrefix(bitString)
if (commonPrefix.isEmpty) {
return None
}
val keyVal = nodes.find(kv => kv._1.startsWith(commonPrefix)).get
if (keyVal._1 != commonPrefix) {
return None
}
keyVal._2.get(bitString.substring(commonPrefix.length))
}*/
def findIndex(index: Int, newString: String, existPrefix: String): Int = {
if (index < newString.length && index < existPrefix.length && newString(index) == existPrefix(index)) {
findIndex(index + 1, newString, existPrefix)
}
index
}
private def findCommonPrefix(bitString: String): String = {
for (existPrefixes <- nodes.keys) {
if (findIndex(0, bitString, existPrefixes) != 0) {
return bitString.substring(0, findIndex(0, bitString, existPrefixes))
}
}
bitString.substring(0, 0)
}
def findNodeWithPrefix(prefix: String): (String, CritBitTree[T]) = {
val nodeWIthCommonPrefix = nodes.find(node => node._1.startsWith(prefix)).get
(nodeWIthCommonPrefix._1, nodeWIthCommonPrefix._2)
}
def add(bitString: String, value: T): CritBitTree[T] = {
if (bitString.length == 0)
return new CritBitTree[T](nodes, true, Option[T](value))
val commonPrefix = findCommonPrefix(bitString)
if (commonPrefix.length == 0) {
val newNode = bitString -> new CritBitTree[T](true, Option[T](value))
return new CritBitTree[T](nodes + newNode, isExternalNode, data)
}
/*val nodeWIthCommonPrefix = nodes.find(node => node._1.startsWith(commonPrefix)).get
val existPrefix = nodeWIthCommonPrefix._1
val subtree = nodeWIthCommonPrefix._2*/
val (subtree, existPrefix) = findNodeWithPrefix(commonPrefix)
//добавление новой вершины
if (existPrefix == commonPrefix) {
val newLeaf = existPrefix -> trie.add(bitString.substring(existPrefix.length), value)
val newNodes = nodes + newLeaf
new CritBitTree[T](newNodes, isExternalNode, data)
} else {
val end = existPrefix.substring(commonPrefix.length)
val middleVertex = new CritBitTree[T](HashMap(end -> trie), false, None)
val newLeaf = commonPrefix -> middleVertex.add(bitString.substring(commonPrefix.length), value)
val newNodes = (nodes - existPrefix) + newLeaf
new CritBitTree[T](newNodes, isExternalNode, data)
}
}
/* def remove(bitString: String): CritBitTree[T] = {
if (bitString.isEmpty) {
return new CritBitTree(nodes, false, None)
}
val commonPrefix = findCommonPrefix(bitString)
if (commonPrefix.isEmpty) {
return this
}
val keyVal = nodes.find(kv => kv._1.startsWith(commonPrefix)).get
val edge = keyVal._1
val trie = keyVal._2
if (edge == commonPrefix) {
val newLeaf = edge -> trie.remove(bitString.substring(edge.length))
if (newLeaf._2.size() == 0) {
val newNodes = nodes - edge
val size = countWords(newNodes)
new CritBitTree[T](newNodes, isExternalNode, size, data)
} else {
newLeaf._2.nodesNumber() match {
case 1 =>
val nextLeaf = newLeaf._2.getSingleLeaf()
if (newLeaf._2.size() == nextLeaf._2.size()) {
val leaf = (edge + nextLeaf._1) -> nextLeaf._2
val newNodes = (nodes - edge) + leaf
val size = countWords(newNodes)
new CritBitTree[T](newNodes, isExternalNode, size, data)
} else {
val newNodes = nodes + newLeaf
val size = countWords(newNodes)
new CritBitTree[T](newNodes, isExternalNode, size, data)
}
case _ =>
val newNodes = nodes + newLeaf
val size = countWords(newNodes)
new CritBitTree[T](newNodes, isExternalNode, size, data)
}
}
} else {
this
}
}*/
def print(indent: Int = 0) {
if (isExternalNode) println(" " * indent + "$(" + data.get + ")$")
for (kv <- nodes) {
println(" " * indent + kv._1)
kv._2.print(indent + kv._1.length)
}
}
/*private def nodesNumber() = nodes.size
private def getSingleLeaf() = nodes.last*/
}
object CritBitTree {
def apply[T](): CritBitTree[T] = {
new CritBitTree[T](false, None)
}
}