overlaps.scala

sealed abstract class Token[T <: Ordered[T]](location: T) extends Ordered[Token[T]] {
  override def compare(other: Token[T]): Int = {
    location compare other.location()
  }
  def location(): T = location
}
case class Start[T <: Ordered[T]](loc: T) extends Token[T](loc)
case class End[T <: Ordered[T]](loc: T) extends Token[T](loc)


class MyRange[T <: Ordered[T]](start: T, end: T) {
  override def toString: String = "%s -> %s".format(start, end)

  def getEdges: List[Token[T]] = List(Start(start), End(end))
}

object MyRange {
  def apply[T <% Ordered[T]](start: T, end: T) = new MyRange[T](start, end)

  def overlaps[T <% Ordered[T]](inputRanges: List[MyRange[T]]): List[MyRange[T]] =
    overlaps[T]((inputRanges map { range => range.getEdges } flatten) sorted, 0, List(), None)


  private def overlaps[T <: Ordered[T]](sortedTokens: List[Token[T]], state: Int, acc: List[MyRange[T]], lastStart: Option[Start[T]]): List[MyRange[T]] = sortedTokens match {
    case Start(location) :: xs if state == 1 =>
      overlaps(xs, state + 1, acc, Some(Start(location)))

    case Start(location) :: xs if state >= 0 =>
      overlaps(xs, state + 1, acc, lastStart)

    case End(location) :: xs if state == 2 =>
      overlaps(xs, state - 1, acc ::: List(MyRange(lastStart.get.location(), location)), None)

    case End(location) :: xs if state >= 0 =>
      overlaps(xs, state - 1, acc, lastStart)

    case Nil => acc

    case _ => throw new IllegalArgumentException("The tokens are in incorrect order. (An end before a start???)")
  }
}

class ListOfMyRanges[T <: Ordered[T]](xs: List[MyRange[T]]) {
  def overlaps = MyRange.overlaps(xs)
}


object RangeTest extends App {
  implicit def listExtension[T <: Ordered[T]](xs: List[MyRange[T]]) = new ListOfMyRanges[T](xs)

  Console.println(List(MyRange(1, 2), MyRange(1.4, 5), MyRange(1.8, 5)) overlaps)

  Console.println(List(MyRange(0, 5), MyRange(4, 15), MyRange(12, 15)) overlaps)
}