rx_programming_1.scala

trait Generator[+T] {

  self =>

  def generate: T

  def map[S](f: T => S): Generator[S] = new Generator[S] {
    def generate = f.apply(self.generate)
  }

  def flatMap[S](f: T => Generator[S]): Generator[S] = new Generator[S] {
    def generate = f.apply(self.generate).generate
  }

}

val integers = new Generator[Int] {
  def generate = scala.util.Random.nextInt()
}

val booleans = integers.map(_ >= 0)

// -- properties

// From the assignment.

property("min1") = forAll { a: Int =>
  val h = insert(a, empty)
  findMin(h) == a
}

// If you insert any two elements into an empty heap, finding the minimum of the resulting heap should get the smallest of the two elements back.

property("min2") = forAll { a: Int, b: Int =>
  if (a > b) findMin(insert(a, insert(b, empty))) == b
  else findMin(insert(a, insert(b, empty))) == a
}

// If you insert an element into an empty heap, then delete the minimum, the resulting heap should be empty.

property("empty1") = forAll { a: Int =>
  deleteMin(insert(a, empty)).isEmpty
}

// Given any heap, you should get a sorted sequence of elements when continually finding and deleting minima. (Hint: recursion and helper functions are your friends.)

def compareTo(h: H, a: A): Boolean = {
  if (h.isEmpty) true
  else if (findMin(h) < a) false
  else compareTo(deleteMin(h), findMin(h))
}

property("sorted1") = forAll { h: H =>
  compareTo(deleteMin(h), findMin(h))
}

// Finding a minimum of the melding of any two heaps should return a minimum of one or the other.

property("meld1") = forAll { h1: H, h2: H =>
  if (findMin(h1) < findMin(h2)) findMin(meld(h1, h2)) == findMin(h1)
  else findMin(meld(h1, h2)) == findMin(h2)
}

// Delete a minimum from an empty heap should return an empty heap.

property("delete1") = forAll {
  deleteMin(empty).isEmpty
}

// -- heap generator

def heaps: Generator[H] = for {
  isFull <- booleans
  heap <- if (isFull) empty else insert(integers.generate, heaps)
} yield heap