Priority queue test.

1 files changed, 266 insertions, 16 deletions

diff --git a/test/files/run/priorityQueue.scala b/test/files/run/priorityQueue.scala
index 9f453788fc..78bf232d6c 100644
--- a/test/files/run/priorityQueue.scala
+++ b/test/files/run/priorityQueue.scala
@@ -1,24 +1,274 @@
 
+
+
+import scala.collection.mutable.PriorityQueue
+
+
+
+
+
+
 // populate a priority queue a few different ways and make sure they all seem equal
-object Test extends Application {
-  import scala.collection.mutable.PriorityQueue
-  import scala.util.Random.nextInt
-  val pq1 = new PriorityQueue[String]
-  val pq2 = new PriorityQueue[String]
-  val pq3 = new PriorityQueue[String]
-  val pq4 = new PriorityQueue[String]
+object Test {
+
+  def main(args: Array[String]) {
+    testInsertionsAndEqualities
+    testIntensiveEnqueueDequeue
+    testIndexing
+    testTails
+    testInits
+    testFilters
+    testDrops
+    testUpdates
+    testEquality
+    testSeq
+  }
+
+  def testInsertionsAndEqualities {
+    import scala.util.Random.nextInt
+    val pq1 = new PriorityQueue[String]
+    val pq2 = new PriorityQueue[String]
+    val pq3 = new PriorityQueue[String]
+    val pq4 = new PriorityQueue[String]
+
+    val strings = (1 to 20).toList map (i => List.fill((Math.abs(nextInt % 20)) + 1)("x").mkString)
+
+    pq1 ++= strings
+    pq2 ++= strings.reverse
+    for (s <- strings) pq3 += s
+    for (s <- strings.reverse) pq4 += s
+
+    val pqs = List(pq1, pq2, pq3, pq4, pq1.clone, pq2.clone)
+
+    for (queue1 <- pqs ; queue2 <- pqs) {
+      assert(queue1 == queue2)
+      assert(queue1.max == queue2.max)
+    }
+
+    assertPriority(pq1)
+  }
+
+  def testIndexing {
+    val pq = new PriorityQueue[Char]
+    "The quick brown fox jumps over the lazy dog".foreach(pq += _)
+
+    // val iter = pq.iterator
+    // while (iter.hasNext) println("`" + iter.next + "`")
+    assert(pq(0) == 'z')
+    assert(pq(1) == 'y')
+    assert(pq(2) == 'x')
+    assert(pq(3) == 'w')
+    assert(pq(4) == 'v')
+    assert(pq(5) == 'u')
+    assert(pq(7) == 't')
+    assert(pq(8) == 's')
+    assert(pq(9) == 'r')
+    assert(pq(10) == 'r')
 
-  val strings = (1 to 20).toList map (i => List.fill((Math.abs(nextInt % 20)) + 1)("x").mkString)
+    pq.clear
+    "abcdefghijklmnopqrstuvwxyz".foreach(pq += _)
+    for (i <- 0 until 26) assert(pq(i) == ('z' - i))
 
-  pq1 ++= strings
-  pq2 ++= strings.reverse
-  for (s <- strings) pq3 += s
-  for (s <- strings.reverse) pq4 += s
+    val intpq = new PriorityQueue[Int]
+    val intlst = new collection.mutable.ArrayBuffer ++ (0 until 100)
+    val random = new util.Random(101)
+    while (intlst.nonEmpty) {
+      val idx = random.nextInt(intlst.size)
+      intpq += intlst(idx)
+      intlst.remove(idx)
+    }
+    for (i <- 0 until 100) assert(intpq(i) == (99 - i))
+  }
+
+  def testTails {
+    val pq = new PriorityQueue[Int]
+    for (i <- 0 until 10) pq += i * 4321 % 200
+
+    assert(pq.size == 10)
+    assert(pq.nonEmpty)
+
+    val tailpq = pq.tail
+    // pq.printstate
+    // tailpq.printstate
+    assert(tailpq.size == 9)
+    assert(tailpq.nonEmpty)
+    assertPriorityDestructive(tailpq)
+  }
+
+  def assertPriorityDestructive[A](pq: PriorityQueue[A])(implicit ord: Ordering[A]) {
+    import ord._
+    var prev: A = null.asInstanceOf[A]
+    while (pq.nonEmpty) {
+      val curr = pq.dequeue
+      if (prev != null) assert(curr <= prev)
+      prev = curr
+    }
+  }
+
+  def assertPriority[A](pq: PriorityQueue[A])(implicit ord: Ordering[A]) {
+    import ord._
+    var prev: A = null.asInstanceOf[A]
+    val iter = pq.iterator
+    while (iter.hasNext) {
+      val curr = iter.next
+      if (prev != null) assert(curr <= prev)
+      prev = curr
+    }
+  }
+
+  def testInits {
+    val pq = new PriorityQueue[Long]
+    for (i <- 0 until 20) pq += (i + 313) * 111 % 300
 
-  val pqs = List(pq1, pq2, pq3, pq4, pq1.clone, pq2.clone)
+    assert(pq.size == 20)
 
-  for (queue1 <- pqs ; queue2 <- pqs) {
-    assert(queue1 == queue2)
-    assert(queue1.max == queue2.max)
+    val initpq = pq.init
+    assert(initpq.size == 19)
+    assertPriorityDestructive(initpq)
   }
+
+  def testFilters {
+    val pq = new PriorityQueue[String]
+    for (i <- 0 until 100) pq += "Some " + (i * 312 % 200)
+
+    val filpq = pq.filter(_.indexOf('0') != -1)
+    assertPriorityDestructive(filpq)
+  }
+
+  def testIntensiveEnqueueDequeue {
+    val pq = new PriorityQueue[Int]
+
+    testIntensive(1000, pq)
+    pq.clear
+    testIntensive(200, pq)
+  }
+
+  def testIntensive(sz: Int, pq: PriorityQueue[Int]) {
+    val lst = new collection.mutable.ArrayBuffer[Int] ++ (0 until sz)
+    val rand = new util.Random(7)
+    while (lst.nonEmpty) {
+      val idx = rand.nextInt(lst.size)
+      pq.enqueue(lst(idx))
+      lst.remove(idx)
+      if (rand.nextDouble < 0.25 && pq.nonEmpty) pq.dequeue
+      assertPriority(pq)
+    }
+  }
+
+  def testDrops {
+    val pq = new PriorityQueue[Int]
+    pq ++= (0 until 100)
+    val droppq = pq.drop(50)
+    assertPriority(droppq)
+
+    pq.clear
+    pq ++= droppq
+    assertPriorityDestructive(droppq)
+    assertPriority(pq)
+    assertPriorityDestructive(pq)
+  }
+
+  def testUpdates {
+    val pq = new PriorityQueue[Int]
+    pq ++= (0 until 36)
+    assertPriority(pq)
+
+    pq(0) = 100
+    assert(pq(0) == 100)
+    assert(pq.dequeue == 100)
+    assertPriority(pq)
+
+    pq.clear
+
+    pq ++= (1 to 100)
+    pq(5) = 200
+    assert(pq(0) == 200)
+    assert(pq(1) == 100)
+    assert(pq(2) == 99)
+    assert(pq(3) == 98)
+    assert(pq(4) == 97)
+    assert(pq(5) == 96)
+    assert(pq(6) == 94)
+    assert(pq(7) == 93)
+    assert(pq(98) == 2)
+    assert(pq(99) == 1)
+    assertPriority(pq)
+
+    pq(99) = 450
+    assert(pq(0) == 450)
+    assert(pq(1) == 200)
+    assert(pq(99) == 2)
+    assertPriority(pq)
+
+    pq(1) = 0
+    assert(pq(1) == 100)
+    assert(pq(99) == 0)
+    assertPriority(pq)
+    assertPriorityDestructive(pq)
+  }
+
+  def testEquality {
+    val pq1 = new PriorityQueue[Int]
+    val pq2 = new PriorityQueue[Int]
+
+    pq1 ++= (0 until 50)
+    var i = 49
+    while (i >= 0) {
+      pq2 += i
+      i -= 1
+    }
+    assert(pq1 == pq2)
+    assertPriority(pq2)
+
+    pq1 += 100
+    assert(pq1 != pq2)
+    pq2 += 100
+    assert(pq1 == pq2)
+    pq2 += 200
+    assert(pq1 != pq2)
+    pq1 += 200
+    assert(pq1 == pq2)
+    assertPriorityDestructive(pq1)
+    assertPriorityDestructive(pq2)
+  }
+
+  def testSeq {
+    val pq = new PriorityQueue[Int]
+    pq ++= (0 until 100)
+
+    val (p1, p2) = pq.partition(_ < 50)
+    assertPriorityDestructive(p1)
+    assertPriorityDestructive(p2)
+
+    val spq = pq.slice(25, 75)
+    assertPriorityDestructive(spq)
+
+    pq.clear
+    pq ++= (0 until 10)
+    pq += 5
+    val ind = pq.lastIndexWhere(_ == 5)
+    //println(ind)
+    //println(pq)
+    //assert(ind == 5)
+    //assertPriorityDestructive(pq)
+  }
+
 }
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+