case class Point(x: Int, y: Int)

case class Delta(dx: Int, dy: Int) {
  def applyTo(point: Point): Point = Point(point.x + dx, point.y + dy)
}

class GilbertLazyStream {

  val u = 1

  private def a(i: Int): Stream[Delta] = {
    if (i > 0) {
      d(i - 1) #::: Delta(u, 0) #:: a(i - 1) #::: Delta(0, u) #:: a(i - 1) #::: Delta(-u, 0) #:: c(i - 1)
    } else {
      Stream.empty
    }
  }

  private def b(i: Int): Stream[Delta] = {
    if (i > 0) {
      c(i - 1) #::: Delta(-u, 0) #:: b(i - 1) #::: Delta(0, -u) #:: b(i - 1) #::: Delta(u, 0) #:: d(i - 1)
    } else {
      Stream.empty
    }
  }

  private def c(i: Int): Stream[Delta] = {
    if (i > 0) {
      b(i - 1) #::: Delta(0, -u) #:: c(i - 1) #::: Delta(-u, 0) #:: c(i - 1) #::: Delta(0, u) #:: a(i - 1)
    } else {
      Stream.empty
    }
  }

  private def d(i: Int): Stream[Delta] = {
    if (i > 0) {
      a(i - 1) #::: Delta(0, u) #:: d(i - 1) #::: Delta(u, 0) #:: d(i - 1) #::: Delta(0, -u) #:: b(i - 1)
    } else {
      Stream.empty
    }
  }

  def nlz(xArg: Int): Int = {
    var x = xArg
    var n = 0
    if (x == 0) return 32
    n = 1
    if ((x >>> 16) == 0) {
      n += 16
      x <<= 16
    }
    if ((x >>> 24) == 0) {
      n += 8
      x <<= 8
    }
    if ((x >>> 28) == 0) {
      n += 4
      x <<= 4
    }
    if ((x >>> 30) == 0) {
      n += 2
      x <<= 2
    }
    n = n - (x >>> 31)
    n
  }

  def log2up(x: Int): Int = {
    if (x < 1) return 0
    32 - nlz(x - 1)
  }

  def gilbertPoinsStream(size : Int) : Stream[Point] = {
    val level = log2up(size)
    a(level).scanLeft(Point(0, 0))((point, delta) => delta.applyTo(point))
  }

}