2010-11-29 3 views
1

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.Scala Problem mit PriorityQueue nicht standardmäßige Reihenfolge für Stack [A]

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.

+0

Bitte geben Sie _compilable_ code ein. Dieser wird nicht kompiliert, da sowohl "A" als auch "count" unbekannt sind. –

+0

Ja, du hast Recht. Ich denke, das ist das Problem mit Fragen in den frühen Morgenstunden. Ich bin jetzt nicht zu Hause, aber ich werde die Frage später bearbeiten, wenn ich es bin. – owst

+0

Bitte machen Sie klar, was der Code in 'returnVal' auch tun soll - sonst wird es schwierig zu wissen, ob Ihr Code" falsch "ist oder nicht. :-) –

Antwort

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.

+0

Ich vermute, dass du Recht hast; Ich muss die spezifischen Werte überprüfen, die ich zu Hause benutzt habe, aber ja, ich denke schon. – owst

+0

Argh! Ja, du hast recht. Ich habe die falsche Reihenfolge benutzt. – owst

0

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
+0

Ja, ein Beispiel zu veröffentlichen wäre definitiv vernünftig gewesen ... Ich werde überprüfen müssen, was mit meinem konkreten Beispiel passiert ist, wenn ich nach Hause komme, aber am Beispiel (am 2.8.1) gibt mir das: Stapel (8, 15) Stapel (4, 3, 2, 1, 45) Stapel (3, 2, 1) Stapel (-1, 0, 9, 4, 3) Welche scheint nur zu zeigen, dass die init. Reihenfolge des Stapels hat sich geändert. Es ist durchaus möglich, dass ich die Ausgabe, die ich früher bekommen habe, falsch interpretiert habe - Daniel hat darauf hingewiesen, dass der Code, den ich eingefügt habe, nicht einmal kompilieren würde. Ich hatte zu dieser Zeit offensichtlich keinen klaren Kopf! Danke für die Antwort! – owst