diff options
author | Aleksandar Pokopec <aleksandar.prokopec@epfl.ch> | 2010-07-29 14:00:04 +0000 |
---|---|---|
committer | Aleksandar Pokopec <aleksandar.prokopec@epfl.ch> | 2010-07-29 14:00:04 +0000 |
commit | 69ff5578c011c79011e02ca0f49292b1687d5b44 (patch) | |
tree | 843cee73794609e2575c9625691ed75e58a41a66 /src | |
parent | e3ca222e48fa917d631c1ee6ecbc8a594ae76d10 (diff) | |
download | scala-69ff5578c011c79011e02ca0f49292b1687d5b44.tar.gz scala-69ff5578c011c79011e02ca0f49292b1687d5b44.tar.bz2 scala-69ff5578c011c79011e02ca0f49292b1687d5b44.zip |
Fixes priority queues and makes them iterables ...
Fixes priority queues and makes them iterables now.
Diffstat (limited to 'src')
6 files changed, 118 insertions, 72 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] +} + |