How to order a collection with PartialOrdering?

Question

I need to order a collection of envelopes. Each envelope is described with its height and width. Envelope1 is smaller than envelope2 if it can be inserted in envelope2. If envelope1 cannot be inserted in envelope2 and vice versa, then they couldn't be compared.

How can i order these envelopes in scala? I couldn't find any information about that on the internet.

Here is some code I have:

object EnvelopeOrdering extends PartialOrdering[(Int, Int)] {
  override def tryCompare(x: (Int, Int), y: (Int, Int)): Option[Int] = {
    if (x._1 < y._1 && x._2 < y._2) return Some(1)
    if (x._1 > y._1 && x._2 > y._2) return Some(-1)
    if (x._1 == y._1 && x._2 == y._2) return Some(0)
    None
  }

  override def lteq(x: (Int, Int), y: (Int, Int)): Boolean = x._1 < y._1 && x._2 < y._2
}

Answer 1

What you are interested in is topological sort and there is a classical algorithm to perform it with complexity in the order of number of edges. In your case you will have an edge between two envelopes if and only if the first one is smaller(and the edge should point from the smaller to the bigger one).