Scala problème en utilisant PriorityQueue ordre par défaut pour Stack [A]

Question

J'essaye d'écrire une implémentation simple d'un tri de patience, en utilisant Scala.
J'ai correctement réussi à créer les piles initiales; Cependant, mon utilisation d'une file d'attente prioritaire pour simplifier la génération de liste de sortie me cause un mal de tête.

Il semble que ma mise en œuvre de commande est soit erronée ou être ignoré:

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 
}) 

Le PriorityQueue semble être commandé par (j'imagine la valeur par défaut Stack commande) taille de la pile, plutôt que ma commande. Y a-t-il quelque chose qui saute aux yeux comme étant manifestement erroné? Toute aide serait grandement appréciée.
Merci,

Edit: je ne pas clairement dans la question initiale: J'utilise Scala 2.8.1.
Edit2: Je m'attendais à ce que returnVal contienne un ordre d'éléments le plus petit à le plus grand, trouvé en prenant le plus petit élément de la tête de toutes les piles. Daniel a fait remarquer que mon Ordre ordonnerait mes Piles du plus grand au plus petit (les piles elles-mêmes sont déjà ordonnées correctement, avec le plus petit élément sur le dessus), ce qui semble être le problème.

Answer 1

N'êtes-vous pas se confondre par le fait que le premier élément dans la file d'attente prioritaire est celui avec plus grande valeur, selon la commande? Le code semble s'attendre à ce que le premier élément soit celui qui a la plus petite valeur.

Answer 2

Il est un peu difficile de répondre à ce qui se passe parce que vous n'avez pas inclus le programme entier avec les entrées et les sorties. Ma conjecture est que cela est dû à l'ancienne mise en œuvre de PriorityQueue en 2.8.1. Le programme suivant utilise la commande personnalisée, et remplit une file d'attente prioritaire avec une liste des piles:

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)                       
    }                            
    }                             
} 

Les sorties du programme:

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

avec le tronc Scala, qui semble être correcte. Je tiens à souligner que PriorityQueue est passé par quelques changements, qui ne sont pas inclus dans 2.8.1 pour des raisons de compatibilité binaire, mais sera disponible en 2.9:

• qu'elle était une séquence, et il n'y a plus de séquence - apply et update ne peuvent pas être mises en œuvre de façon significative
• appelant toString ou itérer sur les éléments ne donneront pas l'ordre tas - la seule façon de l'obtenir est d'utiliser dequeue