class PrefixMatcher {
  private var set = new scala.collection.immutable.TreeSet[String]()
  private def successor(s: String) = s.take(s.length - 1) + (s.charAt(s.length - 1) + 1).toChar

  def add(s: String) = set += s

  def findMatches(prefix: String): Set[String] =
    if (prefix.isEmpty) set
    else set.range(prefix, successor(prefix))
}

object PrefixMatcherApp extends App {
  import scala.io.Source
  def time[R](block: => R): R = {
    val t0 = System.nanoTime()
    val result = block    // call-by-name
    val t1 = System.nanoTime()
    println("Elapsed time: " + (t1 - t0) / 1000000.0 + "ms")
    result
  }

  val matcher = new PrefixMatcher()
  time {
    Source.fromFile("/usr/share/dict/words").getLines.foreach(matcher.add)
  }
  time {
    val matches = matcher.findMatches("ar")
    println(matches.size)
  }
}