diff options
7 files changed, 455 insertions, 418 deletions
diff --git a/src/library/scala/collection/generic/GenericCompanion.scala b/src/library/scala/collection/generic/GenericCompanion.scala index 4552867a9f..cfcd2a94cf 100644 --- a/src/library/scala/collection/generic/GenericCompanion.scala +++ b/src/library/scala/collection/generic/GenericCompanion.scala @@ -48,3 +48,4 @@ abstract class GenericCompanion[+CC[X] <: Traversable[X]] { b.result } } + diff --git a/src/library/scala/collection/generic/GenericOrderedCompanion.scala b/src/library/scala/collection/generic/GenericOrderedCompanion.scala new file mode 100644 index 0000000000..edf942e41d --- /dev/null +++ b/src/library/scala/collection/generic/GenericOrderedCompanion.scala @@ -0,0 +1,33 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2010, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + + + +package scala.collection +package generic + +import mutable.Builder + + + + + +abstract class GenericOrderedCompanion[+CC[X] <: Traversable[X]] { + type Coll = CC[_] + + def newBuilder[A](implicit ord: Ordering[A]): Builder[A, CC[A]] + + def empty[A: Ordering]: CC[A] = newBuilder[A].result + + def apply[A](elems: A*)(implicit ord: Ordering[A]): CC[A] = { + val b = newBuilder[A] + b ++= elems + b.result + } +} + diff --git a/src/library/scala/collection/generic/GenericOrderedTraversableTemplate.scala b/src/library/scala/collection/generic/GenericOrderedTraversableTemplate.scala new file mode 100644 index 0000000000..0ff4e86bdf --- /dev/null +++ b/src/library/scala/collection/generic/GenericOrderedTraversableTemplate.scala @@ -0,0 +1,25 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2010, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + + + +package scala.collection +package generic + +import mutable.Builder +import annotation.unchecked.uncheckedVariance + + + + +trait GenericOrderedTraversableTemplate[+A, +CC[X] <: Traversable[X]] extends HasNewBuilder[A, CC[A] @uncheckedVariance] { + implicit protected[this] val ord: Ordering[A] + def orderedCompanion: GenericOrderedCompanion[CC] + def genericOrderedBuilder[B](implicit ord: Ordering[B]): Builder[B, CC[B]] = orderedCompanion.newBuilder[B] +} + diff --git a/src/library/scala/collection/generic/GenericTraversableTemplate.scala b/src/library/scala/collection/generic/GenericTraversableTemplate.scala index 54f4a07c10..ca07c462fb 100644 --- a/src/library/scala/collection/generic/GenericTraversableTemplate.scala +++ b/src/library/scala/collection/generic/GenericTraversableTemplate.scala @@ -121,3 +121,4 @@ trait GenericTraversableTemplate[+A, +CC[X] <: Traversable[X]] extends HasNewBui } } + diff --git a/src/library/scala/collection/generic/OrderedTraversableFactory.scala b/src/library/scala/collection/generic/OrderedTraversableFactory.scala new file mode 100644 index 0000000000..a94df9e39a --- /dev/null +++ b/src/library/scala/collection/generic/OrderedTraversableFactory.scala @@ -0,0 +1,25 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2006-2010, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + + +package scala.collection +package generic + + + + + +abstract class OrderedTraversableFactory[CC[X] <: Traversable[X] with GenericOrderedTraversableTemplate[X, CC]] +extends GenericOrderedCompanion[CC] { + + class GenericCanBuildFrom[A](implicit ord: Ordering[A]) extends CanBuildFrom[CC[_], A, CC[A]] { + def apply(from: CC[_]) = from.genericOrderedBuilder[A] + def apply = newBuilder[A] + } + +} diff --git a/src/library/scala/collection/mutable/PriorityQueue.scala b/src/library/scala/collection/mutable/PriorityQueue.scala index 397fc5e30b..37a5a8fc88 100644 --- a/src/library/scala/collection/mutable/PriorityQueue.scala +++ b/src/library/scala/collection/mutable/PriorityQueue.scala @@ -33,9 +33,10 @@ import annotation.migration * @define willNotTerminateInf */ @serializable @cloneable -class PriorityQueue[A](implicit ord: Ordering[A]) - extends Seq[A] - with SeqLike[A, PriorityQueue[A]] +class PriorityQueue[A](implicit val ord: Ordering[A]) + extends Iterable[A] + with GenericOrderedTraversableTemplate[A, PriorityQueue] + with IterableLike[A, PriorityQueue[A]] with Growable[A] with Builder[A, PriorityQueue[A]] { @@ -53,57 +54,15 @@ class PriorityQueue[A](implicit ord: Ordering[A]) private val resarr = new ResizableArrayAccess[A] - resarr.p_size0 += 1 // we do not use array(0) - override def length: Int = resarr.length - 1 // adjust length accordingly + resarr.p_size0 += 1 // we do not use array(0) + def length: Int = resarr.length - 1 // adjust length accordingly override def size: Int = length override def isEmpty: Boolean = resarr.p_size0 < 2 override def repr = this - /** A version of `foreach` that traverses elements in an unspecified order. - * - * This method is faster than `foreach` as it does not copy the heap to - * traverse it. - * - * @tparam U the return type of `f` - * @param f the function to be applied at each element, return value ignored - */ - def foreachUnordered[U](f: A => U) { - // hey foreach, our 0th element doesn't exist - var i = 1 - while (i < resarr.p_size0) { - f(toA(resarr.p_array(i))) - i += 1 - } - } - - def update(idx: Int, elem: A) { - if (idx < 0 || idx >= size) throw new IndexOutOfBoundsException("Indices must be nonnegative and lesser than the size.") - - var i = 0 - val iter = iterator - clear - while (iter.hasNext) { - val curr = iter.next - if (i == idx) this += elem - else this += curr - i += 1 - } - } + def result = this - def apply(idx: Int) = { - if (idx < 0 || idx >= size) throw new IndexOutOfBoundsException("Indices must be nonnegative and lesser than the size.") - - var left = idx - val iter = iterator - var curr = iter.next - while (left > 0) { - curr = iter.next - left -= 1 - } - curr - } - - def result = clone + override def orderedCompanion = PriorityQueue private def toA(x: AnyRef): A = x.asInstanceOf[A] protected def fixUp(as: Array[AnyRef], m: Int): Unit = { @@ -190,6 +149,14 @@ class PriorityQueue[A](implicit ord: Ordering[A]) } else throw new NoSuchElementException("no element to remove from heap") + def dequeueAll[A1 >: A, That](implicit bf: CanBuildFrom[_, A1, That]): That = { + val b = bf.apply + while (nonEmpty) { + b += dequeue() + } + b.result + } + /** Returns the element with the highest priority in the queue, * or throws an error if there is no element contained in the queue. * @@ -208,16 +175,12 @@ class PriorityQueue[A](implicit ord: Ordering[A]) * @return an iterator over all elements sorted in descending order. */ override def iterator: Iterator[A] = new Iterator[A] { - val as: Array[AnyRef] = new Array[AnyRef](resarr.p_size0) - Array.copy(resarr.p_array, 0, as, 0, resarr.p_size0) - var i = resarr.p_size0 - 1 - def hasNext: Boolean = i > 0 + private var i = 1 + def hasNext: Boolean = i < resarr.p_size0 def next(): A = { - val res = toA(as(1)) - as(1) = as(i) - i = i - 1 - fixDown(as, 1, i) - res + val n = resarr.p_array(i) + i += 1 + toA(n) } } @@ -235,7 +198,7 @@ class PriorityQueue[A](implicit ord: Ordering[A]) * * @return A reversed priority queue. */ - override def reverse = { + def reverse = { val revq = new PriorityQueue[A]()(new math.Ordering[A] { def compare(x: A, y: A) = ord.compare(y, x) }) @@ -243,15 +206,13 @@ class PriorityQueue[A](implicit ord: Ordering[A]) revq } - override def reverseIterator = new Iterator[A] { - val arr = new Array[Any](PriorityQueue.this.size) - iterator.copyToArray(arr) - var i = arr.size - 1 - def hasNext: Boolean = i >= 0 + def reverseIterator = new Iterator[A] { + private var i = resarr.p_size0 - 1 + def hasNext: Boolean = i >= 1 def next(): A = { - val curr = arr(i) + val n = resarr.p_array(i) i -= 1 - curr.asInstanceOf[A] + toA(n) } } @@ -288,9 +249,9 @@ class PriorityQueue[A](implicit ord: Ordering[A]) // } } -// !!! TODO - but no SortedSeqFactory (yet?) -// object PriorityQueue extends SeqFactory[PriorityQueue] { -// def empty[A](implicit ord: Ordering[A]): PriorityQueue[A] = new PriorityQueue[A](ord) -// implicit def canBuildFrom[A](implicit ord: Ordering[A]): CanBuildFrom[Coll, A, PriorityQueue] = -// } -// + +object PriorityQueue extends OrderedTraversableFactory[PriorityQueue] { + def newBuilder[A](implicit ord: Ordering[A]) = new PriorityQueue[A] + implicit def canBuildFrom[A](implicit ord: Ordering[A]): CanBuildFrom[Coll, A, PriorityQueue[A]] = new GenericCanBuildFrom[A] +} + diff --git a/test/files/run/priorityQueue.scala b/test/files/run/priorityQueue.scala index e47e7c8616..327d8bf137 100644 --- a/test/files/run/priorityQueue.scala +++ b/test/files/run/priorityQueue.scala @@ -12,354 +12,345 @@ import scala.collection.mutable.PriorityQueue object Test { def main(args: Array[String]) { - testInsertionsAndEqualities - testIntensiveEnqueueDequeue - testIndexing - testTails - testInits - testFilters - testDrops - testUpdates - testEquality - testMisc - testReverse - testToList - testForeach + // 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) { - 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) - - 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") - } + // 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") + // } } |