Rectangle search algo

rectangle.scala

package example

case class Rectangle(x1: Int, x2: Int, y1: Int, y2: Int) {
  def xInterval: Interval = Interval(x1, x2)
  def yInterval: Interval = Interval(y1, y2)
}
case class Interval(from: Int, to: Int) {
  def contains(x: Int): Boolean = x >= from && x <= to
  def intersect(other: Interval): Boolean = to > other.from && from < other.to
}

sealed trait Action[T] {
  def value: T
  def fold[S](add: T => S, remove: T => S): S = this match {
    case Add(t) => add(t)
    case Remove(t) => remove(t)
  }
}
final case class Add[T](value: T) extends Action[T]
final case class Remove[T](value: T) extends Action[T]


sealed trait RectangleBoundaryAction {
  def x: Int
  def yInterval: Interval
}
final case class AddRectBoundary(x: Int, yInterval: Interval) extends RectangleBoundaryAction
final case class RemoveRectBoundary(x: Int, yInterval: Interval) extends RectangleBoundaryAction


object Algo {
  def isRectangleContainedIn(search: Rectangle, rectangles: Seq[Rectangle]): Boolean = {
    val boundaryLists = rectangles
      .flatMap { r => Seq(AddRectBoundary(r.x1, r.yInterval), RemoveRectBoundary(r.x2, r.yInterval)) }
      .sortWith { (a1, a2) => a1.x <= a2.x }
      .scanLeft((Int.MinValue, Seq.empty[Interval])) {
        case ((x, intervals), action) => action match {
          case AddRectBoundary(xx, yInterval) => (action.x, intervals :+ yInterval)
          case RemoveRectBoundary(xx, yInterval) => (action.x, dropFirstMatch(intervals, yInterval))
        }
      }
      .groupBy(_._1)
      .map { case (x, is) => is.last }

      boundaryLists.keys.toList.sorted
        .sliding(2).toSeq.map(_.toSeq)
        .filter { xs => search.xInterval.intersect(Interval(xs(0), xs(1))) }
        .map { xs => boundaryLists(xs(0)) }
        .forall(intervals => isIntervalContainedIn(search.yInterval, intervals))
  }

  def isIntervalContainedIn(search: Interval, intervals: Seq[Interval]): Boolean = {
    if (intervals.isEmpty) false
    else {

      val intervalCounts: Map[Int, Int] = intervals
        .flatMap { i => Seq[Action[Int]](Add(i.from), Remove(i.to)) }
        .sortWith { (a1, a2) => a1.value <= a2.value }
        .scanLeft((Int.MinValue, 0)) {
          case ((x, count), action) =>
            println(s"current count: $count")
            println(s"action value: ${action.fold[Int](_ => 1, _ => -1)}" )
            (action.value, count + action.fold[Int](_ => 1, _ => -1))
        }
        .groupBy(_._1)
        .map { case (x, counts) => counts.last }
        .updated(Int.MaxValue, 0)

      intervalCounts.keys.toList.sorted
        .sliding(2).toSeq.map(_.toSeq)
        .filter { xs => search.intersect(Interval(xs(0), xs(1))) }
        .map { xs => intervalCounts(xs(0)) }
        .forall(_ > 0)
    }
  }

  def dropFirstMatch[A](ls: Seq[A], value: A): Seq[A] = {
    val index = ls.indexOf(value)  //index is -1 if there is no match
    if (index < 0) {
      ls
    } else if (index == 0) {
      ls.tail
    } else {
      // splitAt keeps the matching element in the second group
      val (a, b) = ls.splitAt(index)
      a ++ b.tail
    }
  }
}