Сортировка по частному заказу в Scala

Question

Partially sorting collections in Scala спрашивает, как сортировать по PartialOrdering в Scala. В комментариях указано, что автор не должен частично сортироваться в приведенном примере. I do необходимо отсортировать с помощью частичного заказа - у меня есть страны, которые могут быть анклавами других стран, и это вызывает частичный заказ.

So: данный List[T], где T распространяется PartialOrdering[T], существует ли разумный способ сортировки в соответствии с частичным заказом?

Answer 1

Я сам написал соответствующий вид. Такие случаи всегда заставляют меня думать, что я пропустил стандартную библиотечную функцию.

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 
    } 

Комментарии или улучшения будут приветствоваться - я не пишу столько Scala.