quickcheck.scala

package quickcheck

import common._

import org.scalacheck._
import Arbitrary._
import Gen._
import Prop._

abstract class QuickCheckHeap extends Properties("Heap") with IntHeap {

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

  property("check is empty after removing all elems") = forAll { a: Int =>
    val h = insert(a, empty)
    empty == deleteMin(h)
  }

  property("min of two") = forAll { (h1: H, h2: H) =>
    val min1 = findMin(h1)
    val min2 = findMin(h2)
    val h12 = meld(h1, h2)
    findMin(h12) == Math.min(min1, min2)
  }

  property("removing min from heap results in sorted list") = forAll { h: H =>
    def checkHeapResultsAreSorted(h: H, n: A): Boolean = {
      if (isEmpty(h)) true
      else {
        val min = findMin(h)
        if (ord.gt(n, min)) false
        else checkHeapResultsAreSorted(deleteMin(h), min)
      }
    }
    checkHeapResultsAreSorted(deleteMin(h), findMin(h))
  }

  property("heap minumum gets smaller afer deleteing minimum") = forAll { h: H =>
    (!isEmpty(h) && !isEmpty(deleteMin(h))) ==> {
      val min = findMin(h)
      val h1 = deleteMin(h)
      ord.lteq(min, findMin(h1))
    }
  }

  lazy val genHeap: Gen[H] = {
    for {
      a <- arbitrary[A]
      node <- oneOf(value(empty), genHeap)
    } yield insert(a, node)
  }

  implicit lazy val arbHeap: Arbitrary[H] = Arbitrary(genHeap)

}