Sortierung nach einer Teilauforder in Scala

Question

Partially sorting collections in Scala fragt, wie nach einem PartialOrdering in Scala sortiert wird. Kommentare geben an, dass der Autor im Beispiel nicht teilweise sortiert werden soll. I tun müssen nach einer partiellen Reihenfolge sortieren - ich habe Länder, die Enklaven anderer Länder sein können, und dies induziert eine teilweise Bestellung.

Also: bei List[T], wo T erweitert PartialOrdering[T], gibt es eine sinnvolle Art der Sortierung nach der Teilbestellung?

Answer 1

Ich habe eine passende Art selbst geschrieben. Fälle wie diese lassen mich immer denken, dass ich eine Standardbibliotheksfunktion verpasst habe.

def sortByPartialOrdering[T](ts: Array[T], lessThan: (T, T) => Boolean): ListBuffer[T] = { 
    val len = ts.size 
    val visited = Array.fill[Boolean](len)(false) 
    val postOrder = ListBuffer.empty[Int] 

    def visit(n: Int): Unit = { 
     visited(n) = true 
     for (i <- 0 until len) 
     if (!visited(i) && lessThan(ts(i), ts(n))) 
      visit(i) 
     postOrder += n 
    } 

    for (i <- 0 until len) 
     if (!visited(i)) 
     visit(i) 

    assert(postOrder.size == len) 

    postOrder map ts 
    } 

Kommentare/Verbesserungen wäre willkommen - ich schreibe nicht so viel Scala.