PriorityQueue fixed, should work ok now.

3 files changed, 84 insertions, 37 deletions

diff --git a/src/library/scala/collection/mutable/LinkedListLike.scala b/src/library/scala/collection/mutable/LinkedListLike.scala
index 42f37766b2..87dc095cd2 100644
--- a/src/library/scala/collection/mutable/LinkedListLike.scala
+++ b/src/library/scala/collection/mutable/LinkedListLike.scala
@@ -31,7 +31,7 @@ trait LinkedListLike[A, This <: Seq[A] with LinkedListLike[A, This]] extends Seq
 
   override def isEmpty = next eq this
 
-  override def length: Int = if (isEmpty) 0 else next.length
+  override def length: Int = if (isEmpty) 0 else next.length + 1
 
   override def head: A    = elem
 
diff --git a/src/library/scala/collection/mutable/PriorityQueue.scala b/src/library/scala/collection/mutable/PriorityQueue.scala
index b3955acacf..aea7f3a567 100644
--- a/src/library/scala/collection/mutable/PriorityQueue.scala
+++ b/src/library/scala/collection/mutable/PriorityQueue.scala
@@ -12,19 +12,13 @@
 package scala.collection
 package mutable
 
-import generic.{ Addable, Growable }
+import generic._
 
 
 /** This class implements priority queues using a heap.
  *  To prioritize elements of type T there must be an implicit
  *  Ordering[T] available at creation.
  *
- *  Martin: This class is utterly broken. It uses a resizable array
- *  as a heap, yet pretends to be a sequence via this same resizable array.
- *  Needless to say, order of elements is different in the two.
- *  So this class needs to be redesigned so that it uses the array only
- *  in its implementation, but implements a sequence interface separately.
- *
  *  @author  Matthias Zenger
  *  @version 1.0, 03/05/2004
  *  @since   1
@@ -32,32 +26,76 @@ import generic.{ Addable, Growable }
 
 @serializable @cloneable
 class PriorityQueue[A](implicit ord: Ordering[A])
-      extends ResizableArray[A]
+      extends Seq[A]
+      with SeqLike[A, PriorityQueue[A]]
       with Addable[A, PriorityQueue[A]]
       with Growable[A]
       with Cloneable[PriorityQueue[A]]
+      with Builder[A, PriorityQueue[A]]
 {
   import ord._
 
-  size0 += 1                                    // we do not use array(0)
-  override def length: Int = super.length - 1   // adjust length accordingly
-  override def isEmpty: Boolean = size0 < 2
+  private class ResizableArrayAccess[A] extends ResizableArray[A] {
+    @inline def p_size0 = size0
+    @inline def p_size0_=(s: Int) = size0 = s
+    @inline def p_array = array
+    @inline def p_ensureSize(n: Int) = super.ensureSize(n)
+    @inline def p_swap(a: Int, b: Int) = super.swap(a, b)
+  }
+
+  protected[this] override def newBuilder = new PriorityQueue[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
+  override def size: Int = length
+  override def isEmpty: Boolean = resarr.p_size0 < 2
   override def repr = this
 
   // hey foreach, our 0th element doesn't exist
   override def foreach[U](f: A => U) {
     var i = 1
-    while (i < size) {
-      f(toA(array(i)))
+    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 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
+
   private def toA(x: AnyRef): A = x.asInstanceOf[A]
   protected def fixUp(as: Array[AnyRef], m: Int): Unit = {
     var k: Int = m
     while (k > 1 && toA(as(k / 2)) < toA(as(k))) {
-      swap(k, k / 2)
+      resarr.p_swap(k, k / 2)
       k = k / 2
     }
   }
@@ -83,10 +121,10 @@ class PriorityQueue[A](implicit ord: Ordering[A])
    *  @param  elem        the element to insert
    */
   def +=(elem: A): this.type = {
-    ensureSize(size0 + 1)
-    array(size0) = elem.asInstanceOf[AnyRef]
-    fixUp(array, size0)
-    size0 += 1
+    resarr.p_ensureSize(resarr.p_size0 + 1)
+    resarr.p_array(resarr.p_size0) = elem.asInstanceOf[AnyRef]
+    fixUp(resarr.p_array, resarr.p_size0)
+    resarr.p_size0 += 1
     this
   }
 
@@ -125,11 +163,11 @@ class PriorityQueue[A](implicit ord: Ordering[A])
    *  @return   the element with the highest priority.
    */
   def dequeue(): A =
-    if (size0 > 1) {
-      size0 = size0 - 1
-      swap(1, size0)
-      fixDown(array, 1, size0 - 1)
-      toA(array(size0))
+    if (resarr.p_size0 > 1) {
+      resarr.p_size0 = resarr.p_size0 - 1
+      resarr.p_swap(1, resarr.p_size0)
+      fixDown(resarr.p_array, 1, resarr.p_size0 - 1)
+      toA(resarr.p_array(resarr.p_size0))
     } else
       throw new NoSuchElementException("no element to remove from heap")
 
@@ -138,12 +176,12 @@ class PriorityQueue[A](implicit ord: Ordering[A])
    *
    *  @return   the element with the highest priority.
    */
-  def max: A = if (size0 > 1) toA(array(1)) else throw new NoSuchElementException("queue is empty")
+  def max: A = if (resarr.p_size0 > 1) toA(resarr.p_array(1)) else throw new NoSuchElementException("queue is empty")
 
   /** Removes all elements from the queue. After this operation is completed,
    *  the queue will be empty.
    */
-  def clear(): Unit = { size0 = 1 }
+  def clear(): Unit = { resarr.p_size0 = 1 }
 
   /** Returns an iterator which yields all the elements of the priority
    *  queue in descending priority order.
@@ -151,9 +189,9 @@ 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](size0)
-    Array.copy(array, 0, as, 0, size0)
-    var i = size0 - 1
+    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
     def next(): A = {
       val res = toA(as(1))
@@ -164,14 +202,6 @@ class PriorityQueue[A](implicit ord: Ordering[A])
     }
   }
 
-  /** This is utterly broken: Two priority queues of different length can still be equal!
-   *  The method should be removed once PriotyQueue inserts correctly into the sequence class hierarchy.
-   */
-  override def equals(obj: Any): Boolean = obj match {
-    case that: PriorityQueue[_] => (this.iterator zip that.iterator) forall { case (x, y) => x == y }
-    case _                      => false
-  }
-
   /** The hashCode method always yields an error, since it is not
    *  safe to use mutable queues as keys in hash tables.
    *
@@ -196,4 +226,18 @@ class PriorityQueue[A](implicit ord: Ordering[A])
    *  @return  a priority queue with the same elements.
    */
   override def clone(): PriorityQueue[A] = new PriorityQueue[A] ++= this.iterator
+
+  // def printstate {
+  //   println("-----------------------")
+  //   println("Size: " + resarr.p_size0)
+  //   println("Internal array: " + resarr.p_array.toList)
+  //   println(toString)
+  // }
 }
+
+
+
+
+
+
+
diff --git a/src/library/scala/collection/mutable/ResizableArray.scala b/src/library/scala/collection/mutable/ResizableArray.scala
index a8fd82f726..8653ec6adf 100644
--- a/src/library/scala/collection/mutable/ResizableArray.scala
+++ b/src/library/scala/collection/mutable/ResizableArray.scala
@@ -90,9 +90,12 @@ trait ResizableArray[A] extends IndexedSeq[A]
       var newsize = array.length * 2
       while (n > newsize)
         newsize = newsize * 2
+    // println("Internal array before, size " + size0 + ": " + array.toList)
       val newar: Array[AnyRef] = new Array(newsize)
       Array.copy(array, 0, newar, 0, size0)
+    // println("Internal array after,  size " + size0 + ": " + array.toList)
       array = newar
+    // println("New array after,  size      " + size0 + ": " + newar.toList)
     }
   }