An example of usage of the ScalaCheck and ScalaTest frameworks.

ScalaCheckExample.scala

package com.liveperson.predictivedialer.examples.misc

import org.scalatest.junit.JUnitRunner
import org.scalatest.prop.Checkers
import org.scalacheck.Prop._
import org.scalacheck.Arbitrary._
import org.scalacheck.Arbitrary
import org.scalacheck.Gen
import scala.collection.immutable.{HashSet, SortedSet, TreeSet}
import org.junit.runner.RunWith
import org.scalatest.FunSuite

/**
 * Created with IntelliJ IDEA.
 * User: mishaelr
 * Date: 1/29/14
 * Time: 11:51 AM
 *
 * The following tests are examples of ScalaCheck and ScalaTest frameworks usage.
 *
 * They test two possible heuristics for solving the following problem:
 *
 * We are given a set of integer intervals, which we denote as S.
 * Given a new interval i, we wish to perform the following query:
 * Find all the intervals in S that contain i.
 *
 * For example:
 * S = {(1, 5), (1, 7), (3, 8), (1, 10)}
 * i = (2, 7)
 * Result should be: {(1, 7), (1, 10)}
 *
 * Assumptions:
 * S can be assumed to be fixed.
 * The intervals in S are assumed to be short.
 * We wish to store the above set in a data structure that enables fast queries.
 * The time complexity of the preprocessing process can be expensive.
 * The space complexity of the data structure can also be reasonably expensive.
 */

trait SetWithContainsIntervalQuery[T <: Set[(Int, Int)]] {
  def intervalsSet: T
  def apply(interval: (Int, Int)): T
}

/**
 * A solution using TreeSets and range queries (from, until).
 * Query complexity: O(log(number of intervals))
 * Space complexity: O(number of intervals)
 */
class TreeSetWithContainsIntervalQuery(val intervalsSet: TreeSet[(Int, Int)]) extends SetWithContainsIntervalQuery[SortedSet[(Int, Int)]]{
  val endsSet = intervalsSet.map(_.swap)

  def apply(interval: (Int, Int)) = {
    endsSet.from((interval._2, Int.MinValue)).map(_.swap) intersect intervalsSet.until((interval._1, Int.MaxValue))
  }
}

/**
 * A faster solution using HashSets.
 * The space complexity for this solution is not as good as the TreeSet based solution, and is dependent on the intervals lengths.
 * Expected Query complexity: O(1)
 * Space complexity: O(number of intervals * E[Interval length]). Where the expectation is on the intervals in S, which we assumed to be short.
 */
class HashSetWithContainsIntervalQuery(val intervalsSet: HashSet[(Int, Int)]) extends SetWithContainsIntervalQuery[HashSet[(Int, Int)]] {
  val mapping = for {
    (i, j) <- intervalsSet
    k <- i to j
  } yield (k, (i, j))

  val grouped = mapping.groupBy(_._1)

  def apply(interval: (Int, Int)) = {
    val resultOption = for {
      containStart <- grouped.get(interval._1)
      containEnd <- grouped.get(interval._2)
    } yield containStart.map(_._2) intersect containEnd.map(_._2)

    resultOption match {
      case Some(set) => set
      case _ => HashSet[(Int, Int)]()
    }
  }
}

/**
 * Tests
 */
@RunWith(classOf[JUnitRunner])
class ScalaCheckExample extends FunSuite with Checkers {

  implicit class Interval(interval: (Int, Int)) {
    def contains(other: (Int, Int)) = interval._1 <= other._1 && interval._2 >= other._2
  }

  implicit override val generatorDrivenConfig = PropertyCheckConfig(minSuccessful = 1000, minSize = 0, maxSize = 1000)

  val supremum = 1000
  val maximalLength = 8

  val intervalGenerator = for {
    i <- Gen.choose(0, supremum)
    j <- Gen.choose(i, math.min(supremum, i + maximalLength - 1))
  } yield (i, j)

  implicit def arbInterval(implicit a: Arbitrary[(Int, Int)]) = Arbitrary(intervalGenerator)
  implicit def arbIntervalSet(implicit a: Arbitrary[(Int, Int)]) = Arbitrary(Gen.containerOf[Set, (Int, Int)](intervalGenerator))

  test("Interval are generated correctly") {
    check{
      (interval: (Int, Int)) =>
        val (i, j) = interval
        (i >= 0) && (j >= i) && (supremum >= j) && (maximalLength > j-i)
    }
  }

  test("Contains interval using trees") {
    check{
      (interval: (Int, Int), intervalsSet: Set[(Int, Int)]) =>
        val treeContainsInterval = new TreeSetWithContainsIntervalQuery(TreeSet[(Int, Int)]() ++ intervalsSet)
        val treeResult = treeContainsInterval(interval)
        (treeResult forall(_ contains interval)) && (!(intervalsSet -- treeResult).exists(_ contains interval))
    }
  }

  test("Contains interval using hash") {
    check{
      (interval: (Int, Int), intervalsSet: Set[(Int, Int)]) =>
        val hashContainsInterval = new HashSetWithContainsIntervalQuery(HashSet[(Int, Int)]() ++ intervalsSet)
        val hashResult = hashContainsInterval(interval)
        (hashResult forall(_ contains interval)) && (!(intervalsSet -- hashResult).exists(_ contains interval))
    }
  }
}