package quickcheck

import common._

import org.scalacheck._
import Arbitrary._
import Gen._
import Prop.{forAll, BooleanOperators}

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

  lazy val genHeap: Gen[H] = for {
    k <- arbitrary[Int]
    m <- oneOf(const(empty), genHeap)
  } yield insert(k, m)

  implicit lazy val arbHeap: Arbitrary[H] = Arbitrary(genHeap)
//  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("gen1") = forAll { (m: A, n: A) =>
      (m < n) ==> (findMin(insert(m, insert(n, empty))) == m)
  }

//  If you insert an element into an empty heap,
//  then delete the minimum, the resulting heap should be empty.
  property("gen2") = forAll { (m: A) =>
    isEmpty(deleteMin(insert(m, empty)))
  }


//  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.)
  property("gen3") = forAll { (h: H) => {
    def aux(h: H, list: List[A]): Boolean = h match {
        case _ if isEmpty(h) => list.sorted == list
        case _ => aux(deleteMin(h), list :+ findMin(h))
      }

      aux(h, List())
    }
  }

//  Finding a minimum of the melding of any two
//  heaps should return a minimum of one or the other.
  property("gen4") = forAll { (h1: H, h2: H) =>
    val min = findMin(meld(h1, h2))
    findMin(h1) == min || findMin(h2) == min
  }

}