Shadower.scala

object Shadower {

  case class Term(t: String, start: Int, end: Int)

  implicit object SpanTerm extends Span[Term] {
    def start(t: Term) = t.start
    def end(t: Term) = t.end
  }

  trait Span[T]{
    def start(t: T): Int
    def end(t: T): Int
    def length(t: T): Int = end(t) - start(t)
    def covers(t1: T, t2: T) = start(t1) <= start(t2) && end(t1) >= end(t2)

    def cover(t1: T, t2: T): List[T] =
      if (covers(t1, t2)) List(t1)
      else if (covers(t2, t1)) List(t2)
      else if (end(t1) > end(t2)) List(t1, t2)
      else List(t2, t1)

  }
  
  def shadow[T](s: Seq[T])(implicit span: Span[T]): Seq[T] = {
    val byStart = s.sortBy(span.start)
    byStart.drop(1).foldLeft(byStart.take(1)){ case (acc, t) =>
      span.cover(t, acc.head) ++ acc.tail
    }
  }

  def main(args: Array[String]): Unit = {
    println {
      shadow(List(
        Term("a", 1, 10),
        Term("b", 1, 5),
        Term("c", 4, 12),
        Term("d", 2, 10),
        Term("k", 0, 4)))
    }
  }
}