Sorting by a partial order in Scala

Question

Partially sorting collections in Scala asks how to sort by a PartialOrdering in Scala. Comments state that the author should not be partially sorting in the example given. I do need to sort by a partial ordering -- I have countries which may be enclaves of other countries, and this induces a partial ordering.

So: given a List[T], where T extends PartialOrdering[T], is there a sensible way of sorting according to the partial ordering?

Answer 1

I have written an appropriate sort myself. Cases like this always make me think I have missed a standard library function.

  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
  }

Comments/improvements would be welcome -- I don't write that much Scala.

Answer 2

I am not entirely sure I understand the problem. But perhaps this conversion from PartialOrdering to Ordering works:

def sortWithPartialSort[A : PartialOrdering](list: Seq[A]): Seq[A] = {
  list.sorted(
    Ordering.fromLessThan { case (x,y) =>
      implicitly[PartialOrdering[A]].lt(x, y)
    }
  )
}

Note that PartialOrdering.lt is defined as:

def lt(x: T, y: T): Boolean = lteq(x, y) && !equiv(x, y)
def equiv(x: T, y: T): Boolean = lteq(x,y) && lteq(y,x)

so if I understand this correctly, with just lteq you can define a full ordering.

Note also that Seq.sorted implements a stable sort so equal items are not re-ordered.