diff options
author | Aleksandar Pokopec <aleksandar.prokopec@epfl.ch> | 2009-11-20 16:11:53 +0000 |
---|---|---|
committer | Aleksandar Pokopec <aleksandar.prokopec@epfl.ch> | 2009-11-20 16:11:53 +0000 |
commit | 1a104aefd68088fdd2452561cf31fbda333a130a (patch) | |
tree | bf9062485e35ee1dfb85a9c1aca68b6fd8921f7b /test | |
parent | 781eb073f3e50bba64236268523f9f77c8b1c309 (diff) | |
download | scala-1a104aefd68088fdd2452561cf31fbda333a130a.tar.gz scala-1a104aefd68088fdd2452561cf31fbda333a130a.tar.bz2 scala-1a104aefd68088fdd2452561cf31fbda333a130a.zip |
Priority queue test.
Diffstat (limited to 'test')
-rw-r--r-- | test/files/run/priorityQueue.scala | 282 |
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) + } + } + + + + + + + + + + + + + + + + + + |