First implementation of a Trie in Scala. Only supports Strings as of now.

Main.scala

import scala.language.postfixOps
import sys.process._

import trie._ 

object Main {
  val ENTER = 10
  val BACKSPACE = 127
  val BUFFER_SUGGESTION_THRESHOLD = 2

  // Dict sample
  val words = io.Source.fromFile("/usr/share/dict/words").getLines
                  .map(x => x.toLowerCase).toList
  val sample = Trie(words)

  def suggestBasedOn(input: String) =
    sample.getPrefix(input.mkString) match {
      case Some(prefix) => 
        println(Trie.availableWords(prefix).mkString(", "))
      case None => println("No words matching input")
    }

  def runAutoCompleter = {
    var run = true
    var buffer = ""
    while (run) {
      val cin = Console.in.read
      if (cin == ENTER)
        run = false
      else if (cin == BACKSPACE && buffer.length > 0) {
        buffer = buffer.substring(0, buffer.length-1)
        println(": " + buffer)
      } else {
        buffer = buffer + cin.toChar
        println(": " + buffer)
        if (buffer.length > BUFFER_SUGGESTION_THRESHOLD)
          suggestBasedOn(buffer)
      }
    }
  }

  def main(args: Array[String]): Unit = { 
    // required to capture every keystroke on *nix-like systems
    (Seq("sh", "-c", "stty -icanon min 1 < /dev/tty") !)
    (Seq("sh", "-c", "stty -echo < /dev/tty") !)   
    
    println("Start typing a word")
    runAutoCompleter
    
    //suggestBasedOn("ada")
  }
}

Trie.scala

package trie
/*
 * Semi-functional implementation of a Trie
 * 
 * Only operates on Strings as of now
 */ 

// weights in edges (frequency of usgae for ex)

// the node data is mutable
case class Node(value: String, 
                var children: Map[Char, Node] = Map(),
                var isValidWord: Boolean = false)

class Trie {
  private val root = Node("")

  def addWord(word: String) = {
    val chars = word.toCharArray
    var curnode = root
    for (ch <- chars) {
      if (!curnode.children.contains(ch))
        curnode.children += (ch -> Node(curnode.value + ch))

      curnode = curnode.children(ch)
    }
    curnode.isValidWord = true
  }

  def containsPrefix(prefix: String): Boolean = contains(prefix, false)

  def containsWord(word: String): Boolean = contains(word, true)

  def contains(word: String, isWord: Boolean): Boolean = getNode(word) match {
    case Some(n: Node) => ((n.isValidWord && isWord) || (!isWord))
    case None => false
  }

  def getWord(word: String): Option[Node] = getNode(word) match {
    case Some(n) if n.isValidWord => Some(n)
    case _ => None
  }

  def getPrefix(prefix: String): Option[Node] = getNode(prefix)

  def getNode(arg: String): Option[Node] = {
    def nodeFinder(node: Node, chpos: Int): Option[Node] =
      node.children.get(arg(chpos)) match {
        case Some(n) if chpos == arg.length-1 => Some(n)
        case Some(n) => nodeFinder(n, chpos+1)
        case None => None
      } 
    nodeFinder(root, 0)
  }
}

// companion object
object Trie {
  def apply(words: List[String]): Trie = {
    val t = new Trie
    for (word <- words) 
      t.addWord(word)
    t
  }

  // this works but looks kind of crazy
  def availableWords(n: Node): List[String] = {
    def helper(node: Node): List[String] = {
      var acc = List[String]()

      if (node.isValidWord)
        acc ::= node.value

      for (child <- node.children.values)
        acc :::= helper(child)

      acc
    }

    helper(n)
  }
}