Scala problem using PriorityQueue non-default ordering for Stack[A]

I'm trying to write a simple implementation of a patience sort, using Scala开发者_高级运维.

I've correctly managed to create the initial piles; however, my use of a priority queue to simplify output list generation is causing me a headache.

It appears that my ordering implementation is either wrong or being ignored:

def PileOrdering = new Ordering[Stack[A]] {
    def compare(a : Stack[A], b : Stack[A]) = a.head.compare(b.head)
}

// Use a priority queue, ordering on stack heads (smallest stack elems)
val pq = new PriorityQueue[Stack[A]]()(PileOrdering)

// piles is a List[Stack[A]]
pq ++= piles

// Extract an ordered list of elements
val returnVal = (0 until count) map (_ => {
    val smallestList = pq.dequeue
    val smallestVal = smallestList.pop

    if (smallestList.length > 0){
        pq.enqueue(smallestList)
    }

    smallestVal
})

The PriorityQueue appears to be ordered by (I imagine the default Stack Ordering) Stack size, rather than my Ordering.

Does anything jump out as obviously wrong? Any help would be greatly received.

Thanks,

Edit: I didn't make it clear in the original question: I'm using Scala 2.8.1.

Edit2: I was expecting returnVal to contain a smallest-to-largest ordering of elements, found by taking the smallest element from the heads of all stacks. Daniel has pointed out that my Ordering will order my Stacks from largest-to-smallest (the stacks themselves are already ordered correctly, with smallest element on top), which appears to be the issue.

---

Aren't you getting confused by the fact that the first element in the priority queue is the one with greatest value, according to the ordering? The code seems to be expecting the first element to be the one with the smallest value.

---

It's slightly hard to answer what's going on because you didn't include the entire program with inputs and outputs. My guess is that this is due to the old implementation of PriorityQueue in 2.8.1. The following program uses custom ordering, and fills a priority queue with a list of stacks:

import collection._                                                                                                 
import collection.mutable.PriorityQueue                                                                             
import collection.mutable.Stack                                                                                     



class Test[A](piles: Traversable[Stack[A]])(implicit ord: Ordering[A]) {                                            

  def PileOrdering = new Ordering[Stack[A]] {                                                                       
    def compare(a : Stack[A], b : Stack[A]) = ord.compare(a.head, b.head)                                           
  }                                                                                                                 

  // Use a priority queue, ordering on stack heads (smallest stack elems)                                           
  val pq = new PriorityQueue[Stack[A]]()(PileOrdering)                                                              

  // piles is a List[Stack[A]]                                                                                      
  pq ++= piles                                                                                                      

}                                                                                                                   

object Main {                                                                                                       
  def main(args: Array[String]) {                                                                                   
    val t = new Test(Seq(Stack(1, 2, 3), Stack(15, 8), Stack(3, 4, 9, 0, -1), Stack(45, 1, 2, 3, 4)))               
    while (t.pq.nonEmpty) {                                                                                         
      println(t.pq.dequeue)                                                                                         
    }                                                                                                               
  }                                                                                                                 
}  

The program outputs:

Stack(45, 1, 2, 3, 4)                                                                                               
Stack(15, 8)                                                                                                        
Stack(3, 4, 9, 0, -1)                                                                                               
Stack(1, 2, 3)

with Scala trunk, which appears to be correct. I should point out that PriorityQueue went through some changes, which weren't included in 2.8.1 for binary compatibility reasons, but will be available in 2.9:

• it used to be a sequence, and it's no longer a sequence - apply and update cannot be implemented meaningfully
• calling toString or iterating over the elements will not yield heap order - the only way to obtain it is to use dequeue