From 093c9346dec958c46d0ae2e0473eaca463a5f922 Mon Sep 17 00:00:00 2001
From: chrisokasaki <cokasaki@gmail.com>
Date: Sun, 22 May 2016 21:54:06 -0400
Subject: 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.
---
 test/files/scalacheck/MutablePriorityQueue.scala | 102 +++++++++++++++++++++++
 1 file changed, 102 insertions(+)
 create mode 100644 test/files/scalacheck/MutablePriorityQueue.scala

(limited to 'test/files/scalacheck')

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
+    }
+  }
+
+}
-- 
cgit v1.2.3