diff options
Diffstat (limited to 'test/files/run/priorityQueue.scala')
-rw-r--r-- | test/files/run/priorityQueue.scala | 354 |
1 files changed, 338 insertions, 16 deletions
diff --git a/test/files/run/priorityQueue.scala b/test/files/run/priorityQueue.scala index 9f453788fc..20f7a3cb44 100644 --- a/test/files/run/priorityQueue.scala +++ b/test/files/run/priorityQueue.scala @@ -1,24 +1,346 @@ + + +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 + testMisc + testReverse + } + + 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') + + pq.clear + "abcdefghijklmnopqrstuvwxyz".foreach(pq += _) + for (i <- 0 until 26) assert(pq(i) == ('z' - i)) + + 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 + + assert(pq.size == 20) + + 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 testMisc { + val pq = new PriorityQueue[Int] + pq ++= (0 until 100) + assert(pq.size == 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 + assert(pq.size == 11) + + val ind = pq.lastIndexWhere(_ == 5) + assert(ind == 5) + assertPriorityDestructive(pq) + + pq.clear + pq ++= (0 until 10) + assert(pq.lastIndexWhere(_ == 9) == 0) + assert(pq.lastIndexOf(8) == 1) + assert(pq.lastIndexOf(7) == 2) + + pq += 5 + pq += 9 + assert(pq.lastIndexOf(9) == 1) + assert(pq.lastIndexWhere(_ % 2 == 1) == 10) + assert(pq.lastIndexOf(5) == 6) + + val lst = pq.reverseIterator.toList + for (i <- 0 until 5) assert(lst(i) == i) + assert(lst(5) == 5) + assert(lst(6) == 5) + assert(lst(7) == 6) + assert(lst(8) == 7) + assert(lst(9) == 8) + assert(lst(10) == 9) + assert(lst(11) == 9) + + pq.clear + assert(pq.reverseIterator.toList.isEmpty) + + pq ++= (50 to 75) + assert(pq.lastIndexOf(70) == 5) - val strings = (1 to 20).toList map (i => List.fill((Math.abs(nextInt % 20)) + 1)("x").mkString) + pq += 55 + pq += 70 + assert(pq.lastIndexOf(70) == 6) + assert(pq.lastIndexOf(55) == 22) + assert(pq.lastIndexOf(55, 21) == 21) + assert(pq.lastIndexWhere(_ > 54) == 22) + assert(pq.lastIndexWhere(_ > 54, 21) == 21) + assert(pq.lastIndexWhere(_ > 69, 5) == 5) + } + + def testReverse { + val pq = new PriorityQueue[(Int, Int)] + pq ++= (for (i <- 0 until 10) yield (i, i * i % 10)) + + assert(pq.reverse.size == pq.reverseIterator.toList.size) + assert((pq.reverse zip pq.reverseIterator.toList).forall(p => p._1 == p._2)) + assert(pq.reverse.sameElements(pq.reverseIterator.toSeq)) + assert(pq.reverse(0)._1 == pq(9)._1) + assert(pq.reverse(1)._1 == pq(8)._1) + assert(pq.reverse(4)._1 == pq(5)._1) + assert(pq.reverse(9)._1 == pq(0)._1) - pq1 ++= strings - pq2 ++= strings.reverse - for (s <- strings) pq3 += s - for (s <- strings.reverse) pq4 += s + pq += ((7, 7)) + pq += ((7, 9)) + pq += ((7, 8)) + assert(pq.reverse.reverse == pq) + assert(pq.reverse.lastIndexWhere(_._2 == 6) == 6) + assertPriorityDestructive(pq.reverse.reverse) - val pqs = List(pq1, pq2, pq3, pq4, pq1.clone, pq2.clone) + val iq = new PriorityQueue[Int] + iq ++= (0 until 50) + assert(iq.reverse == iq.reverseIterator.toSeq) + assert(iq.reverse.reverse == iq) - for (queue1 <- pqs ; queue2 <- pqs) { - assert(queue1 == queue2) - assert(queue1.max == queue2.max) + iq += 25 + iq += 40 + iq += 10 + assert(iq.reverse == iq.reverseIterator.toList) + assert(iq.reverse.reverse == iq) + assert(iq.reverse.lastIndexWhere(_ == 10) == 11) + assertPriorityDestructive(iq.reverse.reverse) } + } + + + + + + + + + + + + + + + + + + |