From 6965b470d433f501203c4e3d77b0919f826691ba Mon Sep 17 00:00:00 2001 From: Dmitry Petrashko Date: Fri, 22 May 2015 16:07:23 +0200 Subject: Enable 440 run tests that pass. Note that some of them may pass due to several bugs that interfere. --- tests/run/priorityQueue.scala | 373 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 373 insertions(+) create mode 100644 tests/run/priorityQueue.scala (limited to 'tests/run/priorityQueue.scala') diff --git a/tests/run/priorityQueue.scala b/tests/run/priorityQueue.scala new file mode 100644 index 000000000..56f7ac3c8 --- /dev/null +++ b/tests/run/priorityQueue.scala @@ -0,0 +1,373 @@ + + + +import scala.collection.mutable.PriorityQueue + + + + + + +// populate a priority queue a few different ways and make sure they all seem equal +object Test { + + def main(args: Array[String]): Unit = { + // testInsertionsAndEqualities + // testIntensiveEnqueueDequeue + // testTails + // testInits + // testFilters + // testDrops + // testEquality + // testMisc + // testReverse + // testToList + // testForeach + } + + // 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) { + // val l1: List[String] = queue1.dequeueAll[String, List[String]] + // val l2: List[String] = queue2.dequeueAll[String, List[String]] + // assert(l1 == l2) + // assert(queue1.max == queue2.max) + // } + + // assertPriorityDestructive(pq1) + // } + + // not a sequence anymore, Mildred + // 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 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) + // } + + // // your sequence days have ended, foul priority queue + // // 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) + + // 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) + + // 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 iq = new PriorityQueue[Int] + // iq ++= (0 until 50) + // assert(iq.reverse == iq.reverseIterator.toSeq) + // assert(iq.reverse.reverse == iq) + + // 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) + // } + + // def testToList { + // val pq = new PriorityQueue[Int] + + // pq += 1 + // pq += 4 + // pq += 0 + // pq += 5 + // pq += 3 + // pq += 2 + // assert(pq.toList == pq) + // assert(pq == List(5, 4, 3, 2, 1, 0)) + // assert(pq.reverse == List(0, 1, 2, 3, 4, 5)) + + // pq.clear + // for (i <- -50 until 50) pq += i + // assert(pq.toList == pq) + // assert(pq.toList == (-50 until 50).reverse) + // } + + // def testForeach { + // val pq = new PriorityQueue[Char] + + // pq += 't' + // pq += 'o' + // pq += 'b' + // pq += 'y' + // val sbf = new StringBuilder + // val sbi = new StringBuilder + // pq.foreach(sbf += _) + // pq.iterator.foreach(sbi += _) + // assert(sbf.toString == sbi.toString) + // assert(sbf.toString == "ytob") + // } + +} + + + + + + + + + + + + + + + + + + -- cgit v1.2.3