diff options
author | chrisokasaki <cokasaki@gmail.com> | 2016-05-22 21:54:06 -0400 |
---|---|---|
committer | chrisokasaki <cokasaki@gmail.com> | 2016-05-22 21:54:06 -0400 |
commit | 093c9346dec958c46d0ae2e0473eaca463a5f922 (patch) | |
tree | 07371741d05d307fb69a5298285d569303241da4 /test/files/scalacheck/MutablePriorityQueue.scala | |
parent | a79b9b7220c87ba21b374eda25702c7bc446dc29 (diff) | |
download | scala-093c9346dec958c46d0ae2e0473eaca463a5f922.tar.gz scala-093c9346dec958c46d0ae2e0473eaca463a5f922.tar.bz2 scala-093c9346dec958c46d0ae2e0473eaca463a5f922.zip |
SI-9776: Fix type of PriorityQueue.newBuilder and improve performance
- Fix the return type of mutable.PriorityQueue.newBuilder to be
Builder[A, PriorityQueue[A]] rather than PriorityQueue[A].
- Improve performance of bulk inserts from O(N log N) to O(N),
primarily in the builder, ++=, and reverse. These changes
indirectly benefit the many other methods that use the builder or ++=.
- Improve performance of clone.
- Fix SI-9757 space leak in dequeue.
Diffstat (limited to 'test/files/scalacheck/MutablePriorityQueue.scala')
-rw-r--r-- | test/files/scalacheck/MutablePriorityQueue.scala | 102 |
1 files changed, 102 insertions, 0 deletions
diff --git a/test/files/scalacheck/MutablePriorityQueue.scala b/test/files/scalacheck/MutablePriorityQueue.scala new file mode 100644 index 0000000000..687e2e7c62 --- /dev/null +++ b/test/files/scalacheck/MutablePriorityQueue.scala @@ -0,0 +1,102 @@ +import scala.collection.mutable.PriorityQueue +import org.scalacheck._ +import Prop._ +import Arbitrary._ + +object Test extends Properties("PriorityQueue") { + type E = Int // the element type used for most/all of the tests + + def checkInvariant[A](pq: PriorityQueue[A])(implicit ord: Ordering[A]): Boolean = { + // The ordering invariant in the heap is that parent >= child. + // A child at index i has a parent at index i/2 in the priority + // queue's internal array. However, that array is padded with + // an extra slot in front so that the first real element is at + // index 1. The vector below is not padded, so subtract 1 from + // every index. + import ord._ + val vec = pq.toVector // elements in same order as pq's internal array + 2 until pq.size forall { i => vec(i/2-1) >= vec(i-1) } + } + + property("newBuilder (in companion)") = forAll { list: List[E] => + val builder = PriorityQueue.newBuilder[E] + for (x <- list) builder += x + val pq = builder.result() + checkInvariant(pq) && + pq.dequeueAll == list.sorted.reverse + } + + property("to[PriorityQueue]") = forAll { list: List[E] => + val pq = list.to[PriorityQueue] + checkInvariant(pq) && + pq.dequeueAll == list.sorted.reverse + } + + property("apply (in companion)") = forAll { list: List[E] => + val pq = PriorityQueue.apply(list : _*) + checkInvariant(pq) && + pq.dequeueAll == list.sorted.reverse + } + + property("size, isEmpty") = forAll { list: List[E] => + val pq = PriorityQueue(list : _*) + pq.size == list.size && pq.isEmpty == list.isEmpty + } + + property("+=") = forAll { (x: E, list: List[E]) => + val pq = PriorityQueue(list : _*) + pq += x + checkInvariant(pq) && + pq.dequeueAll == (x :: list).sorted.reverse + } + + property("++= on empty") = forAll { list: List[E] => + val pq = PriorityQueue.empty[E] + pq ++= list + checkInvariant(pq) && + pq.dequeueAll == list.sorted.reverse + } + + property("++=") = forAll { (list1: List[E], list2: List[E]) => + val pq = PriorityQueue(list1 : _*) + pq ++= list2 + checkInvariant(pq) && + pq.dequeueAll == (list1 ++ list2).sorted.reverse + } + + property("reverse") = forAll { list: List[E] => + val pq = PriorityQueue(list : _*).reverse + checkInvariant(pq)(implicitly[Ordering[E]].reverse) && + pq.dequeueAll == list.sorted + } + + property("reverse then ++=") = forAll { list: List[E] => + val pq = PriorityQueue.empty[E].reverse ++= list + checkInvariant(pq)(implicitly[Ordering[E]].reverse) && + pq.dequeueAll == list.sorted + } + + property("reverse then +=") = forAll { (x: E, list: List[E]) => + val pq = PriorityQueue(list : _*).reverse += x + checkInvariant(pq)(implicitly[Ordering[E]].reverse) && + pq.dequeueAll == (x +: list).sorted + } + + property("clone") = forAll { list: List[E] => + val pq = PriorityQueue(list : _*) + val c = pq.clone() + (pq ne c) && + checkInvariant(c) && + c.dequeueAll == pq.dequeueAll + } + + property("dequeue") = forAll { list: List[E] => + list.nonEmpty ==> { + val pq = PriorityQueue(list : _*) + val x = pq.dequeue() + checkInvariant(pq) && + x == list.max && pq.dequeueAll == list.sorted.reverse.tail + } + } + +} |