Inversions exercise from fayimora

gistfile1.scala

import scala.io.Source
import System.{ currentTimeMillis => now }

object Inv extends App {

  // An int set that knows how many members are greater than a given number.
  sealed trait GSet {
    def ngt(n: Int): Int // number greater than `n`
    def +(n: Int): GSet
  }

  // A leaf node, which is empty
  case object GNil extends GSet {
    def ngt(n: Int) = 0
    def +(n: Int) = GCons(n, GNil, GNil, 1, 0)
  }

  // Cons nodes contain a value, a frequency count for that value, left and right subtrees, 
  // and (the magic optimization) a count of the size of the right subtree.
  case class GCons(value: Int, left: GSet, right: GSet, count: Int, gt: Int) extends GSet {

    def ngt(n: Int) =
      if (n < value) count + left.ngt(n) + gt
      else if (n > value) right.ngt(n)
      else gt

    def +(n: Int) =
      if (n < value) copy(left = left + n)
      else if (n > value) copy(right = right + n, gt = gt + 1)
      else copy(count = count + 1)

  }

  // Helper to time a computation
  def time[A](a: => A): (A, Long) = {
    val start = now
    val r = a
    (r, now - start)
  }

  // Find inversions
  def invs(ns: List[Int]) = 
    ((GNil: GSet, 0L) /: ns) { case ((t, c), n) => (t + n, c + t.ngt(n)) }._2

  // A test. You can find IntegerArray.txt at:
  // https://gist.github.com/fayimora/d5f2a5231d16d97555ee/raw/5e7e7ddc776c75854efae763eb9a6052ee8e823a/IntegerArray.txt
  val ns = Source.fromFile("IntegerArray.txt").getLines.map(_.toInt).toList
  println("Read %d ints.".format(ns.length))  
  println(time(invs(ns)))
  println(" " + 2407905288L + " // expected")
  println("More runs (ms):")
  println((1 to 10).map(_ => time(invs(ns))._2).mkString(" "))


}