Trie is a data structure can be used for auto complete feature. Following a a rudimentary implementation of a Trie in Scala.
Trie can be constructed similar to a tree structure. Following code snippet illustrated a node in the Trie tree *
package ashika.datastructure.trie
case class Node(content: Char,
children: collection.mutable.Map[Char,Node],
words:collection.mutable.Set[String],
var metaData: Map[String,String] = null)
Tree implementation including addWord() and find() methods are implemented as follows :
package ashika.datastructure.trie
import scala.collection.mutable
import scala.collection.mutable.ListBuffer
import util.control.Breaks._
case class Entry(words: Set[String], meta: Map[String,String])
class Trie {
val root : Node = Node(Char.MinValue,mutable.Map[Char,Node](), collection.mutable.Set());
/**
* find matches for a given prefix
* @param str
* @return
*/
def find(str: String) : Seq[Entry] = {
val lb = ListBuffer[Entry]()
var i = 0
var node = root
breakable {
while (i < str.length) {
val ch = str.charAt(i)
val nnode = node.children.get(ch.toLower)
if (nnode.isDefined) {
if (nnode.get.words.nonEmpty && i>=str.length) {
lb.addOne(Entry(nnode.get.words.toSet, nnode.get.metaData))
}
node=nnode.get
} else {
return lb.toList
}
i+=1
}
}
//break
def dfs(node: Node, charLst : Seq[Char]) : Unit = {
if (node.words.nonEmpty) {
lb.addOne(Entry(node.words.toSet, node.metaData))
}
node.children.foreach(elm => {
dfs(elm._2, charLst:+ elm._2.content)
})
}
dfs(node,Seq[Char]())
lb.toSeq
}
/**
* add new word to the Trie with optional meta data
* @param str
*/
def addWord(str: String, meta: Map[String,String] = null): Unit = {
var node = root
var i = 0
breakable {
while (i < str.length) {
val ch = str.charAt(i)
val containerNode = node.children.get(ch.toLower)
//node exists
if (containerNode.isDefined) {
node = containerNode.get
if(i == str.length-1) {
node.words.addOne(str)
node.metaData = meta
}
} else {
//no node for this char
break
}
i += 1
}
}
while(i < str.length) {
val ch = str.charAt(i)
val nnode : Node = if (i==str.length-1) {
Node(ch,mutable.Map[Char,Node](), collection.mutable.Set(str), meta)
} else {
Node(ch,mutable.Map[Char,Node](), collection.mutable.Set(), meta)
}
node.children.addOne(ch.toLower,nnode)
node = nnode
i+=1
}
}
}
Sample driver program :
object Trie {
def main(args:Array[String]) = {
val trie = new Trie
trie.addWord("Ashika")
trie.addWord("Ashola")
trie.addWord("Airplane")
trie.addWord("Asしか")
trie.addWord("Ash")
trie.addWord("ash")
trie.addWord("AsH",Map("id"->"productId"))
trie.addWord("日本語")
trie.addWord("日本人")
trie.addWord("cat")
trie.addWord("catterpillar", Map("id"->"a"))
trie.addWord("日本")
trie.addWord("日人")
(1 to 11).foreach(i => {
trie.addWord("dummy name here with some name"+i)
})
(trie.find("as").foreach(e => {
println(e.words, e.meta)
}))
}
}
Ashika learns to blog 