Scala Problem mit PriorityQueue nicht standardmäßige Reihenfolge für Stack [A]

Question

Ich versuche, eine einfache Implementierung einer Geduldsart zu schreiben, mit Scala.
Ich habe es richtig geschafft, die Anfangspfähle zu erstellen; Allerdings bereitet mir die Verwendung einer Prioritätswarteschlange zur Vereinfachung der Generierung von Ausgangslisten Kopfschmerzen.

Es scheint, dass meine Bestellung Implementierung entweder falsch ist oder nicht berücksichtigt zu werden:

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

Die Priorityqueue erscheint durch bestellt werden (man stelle ich den Standard-Stack-Ordering) Stackgröße, anstatt meine Bestellung.

Fällt irgendetwas als offensichtlich falsch aus? Jede Hilfe würde sehr erhalten werden.
Danke,

Edit: ich es in der ursprünglichen Frage nicht machen klar: Ich bin mit Scala 2.8.1.
Edit2: Ich habe erwartet, dass returnVal eine kleinste bis größte Anordnung von Elementen enthält, die gefunden wird, indem das kleinste Element aus den Köpfen aller Stapel entnommen wird. Daniel hat darauf hingewiesen, dass meine Bestellung meine Stacks von Groß- zu Kleinst sortieren wird (die Stacks selbst sind bereits richtig sortiert, mit dem kleinsten Element oben), was das Problem zu sein scheint.

Answer 1

zu verwenden sind Sie nicht durch die Tatsache verwirrt dass das erste Element in der priority queue ist der mit größte wert, nach der bestellung? Der Code scheint zu erwarten, dass das erste Element derjenige mit dem kleinsten Wert ist.

Answer 2

Es ist etwas schwierig zu beantworten, was passiert, weil Sie nicht das gesamte Programm mit Ein- und Ausgängen versehen haben. Meine Vermutung ist, dass dies auf die alte Implementierung von PriorityQueue in 2.8.1 zurückzuführen ist. Das folgende Programm verwendet individuelle Bestellung und füllt eine Prioritätswarteschlange mit einer Liste von Stapeln:

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

Das Programm gibt:

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

mit Scala Stamm, der korrekt zu sein scheint. Ich möchte darauf hinweisen, dass PriorityQueue durch einige Änderungen gingen, die nicht in 2.8.1 für binäre Kompatibilitätsgründen enthalten waren, aber in 2.9 zur Verfügung:

• früher eine Folge, und es ist nicht mehr ein Sequenz - apply und update nicht sinnvoll
• toString oder über die Elemente nicht um ergeben Haufen Iterieren Aufruf implementiert werden - der einzige Weg, um es zu erhalten ist dequeue