Alcorithm.scala

case class Point(x: Int, y: Int)
case class Rect(ul: Point, br: Point) {
  def covers(other: Rect): Boolean = {
    (ul.x <= other.ul.x && ul.y <= other.ul.y) &&
    (br.x >= other.br.x && br.y >= other.br.y)
  }
  def overlaps(other: Rect): Boolean = {
    // If one rectangle is on left side of other
    if (ul.x > other.br.x || other.ul.x > br.x) {
        return false
    }

    // If one rectangle is above other
    if (ul.y > other.br.y || other.ul.y > br.y) {
        return false
    }

    return true
  }
}

sealed trait QuadTree {
  def value: Double
  def count: Int
  def average: Double
  def toList: Seq[QuadTree]
  def boundary: Rect
  def covering(rect: Rect): Seq[QuadTree]
}

case class Inner(ul: QuadTree, ur: QuadTree, bl: QuadTree, br: QuadTree) extends QuadTree {
  lazy val value = ul.value + ur.value + bl.value + br.value
  lazy val count = ul.count + ur.count + bl.count + br.count
  lazy val average = value / count
  lazy val toList = Seq(ul, ur, bl, br)
  lazy val boundary = Rect(ul.boundary.ul, br.boundary.br)
  def covering(rect: Rect): Seq[QuadTree] = {
    if (rect.overlaps(boundary)) {
      if (rect.covers(boundary)) { Seq(this) }
      else {
        ul.covering(rect) ++ ur.covering(rect) ++ bl.covering(rect) ++ br.covering(rect)
      }
    } else Nil
  }
}

case class Leaf(value: Double, location: Point) extends QuadTree {
  lazy val count = 1
  lazy val average = value
  lazy val toList = Seq(this)
  lazy val boundary = Rect(location, location)
  def covering(rect: Rect): Seq[QuadTree] = {
    if (rect.covers(boundary)) { Seq(this) }
    else { Nil }
  }
}

object QuadTree {
  def reduceCovering(qs: Seq[QuadTree]): Double = {
    val (sum, count) = qs.foldLeft(0.0 -> 0)((sc, q) => (sc._1 + q.value, sc._2 + q.count))
    sum / count
  }
}

/*
[[1, 0, 12, 3],
[14, 45, 25, 2],
[62, 2, 255, 8],
[34, 35, 255, 93]]
*/

val ul: QuadTree = Inner(Leaf(1, Point(0, 0)), Leaf(0, Point(0, 1)), Leaf(14, Point(1, 0)), Leaf(45, Point(1, 1)))
val ur: QuadTree = Inner(Leaf(12, Point(0, 2)), Leaf(3, Point(0, 3)), Leaf(25, Point(1, 2)), Leaf(2, Point(1, 3)))
val bl: QuadTree = Inner(Leaf(62, Point(2, 0)), Leaf(2, Point(2, 1)), Leaf(34, Point(3, 0)), Leaf(35, Point(3, 1)))
val br: QuadTree = Inner(Leaf(255, Point(2, 2)), Leaf(8, Point(2, 3)), Leaf(255, Point(3, 2)), Leaf(93, Point(3, 3)))

val tree: QuadTree = Inner(ul, ur, bl, br)

val r1 = Rect(Point(1, 1), Point(1, 2))
val s1 = tree.covering(r1)

val r2 = Rect(Point(0, 0), Point(2, 1))
val s2 = tree.covering(r2)