diff options
author | Aleksandar Pokopec <aleksandar.prokopec@epfl.ch> | 2009-11-24 16:35:09 +0000 |
---|---|---|
committer | Aleksandar Pokopec <aleksandar.prokopec@epfl.ch> | 2009-11-24 16:35:09 +0000 |
commit | 4ad672b0b279ee5b28d166483928a5acc6d136d7 (patch) | |
tree | e14eb4d555a24c182fb533b0d82d736fb8c04c00 | |
parent | d26b2f2b94af88eab8494c04924c86e6efd8e888 (diff) | |
download | scala-4ad672b0b279ee5b28d166483928a5acc6d136d7.tar.gz scala-4ad672b0b279ee5b28d166483928a5acc6d136d7.tar.bz2 scala-4ad672b0b279ee5b28d166483928a5acc6d136d7.zip |
Added reverse capabilities to PriorityQueue.
-rw-r--r-- | src/library/scala/collection/mutable/PriorityQueue.scala | 20 | ||||
-rw-r--r-- | test/files/run/priorityQueue.scala | 49 |
2 files changed, 68 insertions, 1 deletions
diff --git a/src/library/scala/collection/mutable/PriorityQueue.scala b/src/library/scala/collection/mutable/PriorityQueue.scala index 54505dbdf6..5338d358f3 100644 --- a/src/library/scala/collection/mutable/PriorityQueue.scala +++ b/src/library/scala/collection/mutable/PriorityQueue.scala @@ -202,7 +202,25 @@ class PriorityQueue[A](implicit ord: Ordering[A]) } } - override def reverse = throw new UnsupportedOperationException("Priority queue cannot be reversed.") + /** + * Returns the reverse of this queue. The priority queue that gets + * returned will have an inversed ordering - if for some elements + * <code>x</code> and <code>y</code> the original queue's ordering + * had <code>compare</code> returning an integer w, the new one will return -w, + * assuming the original ordering abides its contract. + * + * Note that the order of the elements will be reversed unless the + * <code>compare</code> method returns 0. In this case, such elements + * will be subsequent, but their corresponding subinterval may be inappropriately + * reversed. However, due to the compare-equals contract, they will also be equal. + */ + override def reverse = { + val revq = new PriorityQueue[A]()(new math.Ordering[A] { + def compare(x: A, y: A) = ord.compare(y, x) + }) + for (i <- 1 until resarr.length) revq += resarr(i) + revq + } override def reverseIterator = new Iterator[A] { val arr = new Array[Any](size) diff --git a/test/files/run/priorityQueue.scala b/test/files/run/priorityQueue.scala index 54090091ec..20f7a3cb44 100644 --- a/test/files/run/priorityQueue.scala +++ b/test/files/run/priorityQueue.scala @@ -22,6 +22,7 @@ object Test { testUpdates testEquality testMisc + testReverse } def testInsertionsAndEqualities { @@ -274,6 +275,54 @@ object Test { 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) } } |