Ordering on subclasses

I have five subclasses of Z, namely A…E and I want to impose an order on them such that A<B<C<D<E. I previously made Z extend Ordered but answers in this group encourage me to use an implicit Ordering[Z] and using typeclasses.

Currently, with my Z extends Ordered[Z], I have a compare method for every subclass that states how the order should be realised, e.g.:

class C extends Z {

    def compare(other: Z) = {

    other match {

    case _ : A => +1

    case _ : B => +1

    case that: C => this.field compare that.field

    case _ : D => -1

    case _ : E => -1

    }

}

Now, if I wanted to change the ordering such that D < E < B < A < C, I would have to go into every subclass and make sure everything was consistent again, which could introduce errors.

In the typeclass way of doing things, where you compare two items outside of any scope of a this object, is there a trick using something like Ordering[Z].by... so that an ordering is imposed? Or would this create a cross product case analysis where every subclass has to be compared with every other subclass? What I want to do is say all A’s are less than Bs … Zs, but if a A comes in, compare by each field in turn but express this once, rather than in every class.

Any pointers appreciated!

Two naive attempts:

implicit object ZOrdering extends Ordering[Z] {
  override def compare(x: Z, y: Z): Int =
    (x, y) match {
      case (a: A, b: A) => ???
      case (a: B, b: B) => ???
      // ...
      case (_: A, _) => -1
      case (_, _: A) => 1
      case (_: B, _) => -1
      case (_, _: B) => 1
      // ...
    }
}

[EDIT: reverted order]

…or…

sealed trait Z { def ordBase: Int }
object A { val ord: Int = 1 }
case class A() extends Z { override def ordBase: Int = A.ord }
// ...
implicit val zOrdering: Ordering[Z] =
  Ordering.by[Z, Int](_.ordBase).orElse(???)

There may be better approaches.

Fun little problem! I wound up digging into this, and came up with this proof of concept suggestion (it’s an Ammonite script; the bit at the bottom actually tests it):

abstract class Z
case class A() extends Z
case class B(s: String) extends Z
case class C() extends Z
case class D(i: Int) extends Z
case class E() extends Z

implicit object ZOrdering extends Ordering[Z] {
  def indexOf(z: Z): Int = {
    z match {
      case a: A => 1
      case b: B => 2
      case c: C => 3
      case d: D => 4
      case e: E => 5
    }
  }

  override def compare(x: Z, y: Z): Int = {
    (x, y) match {
      case (left: A, right: A) => 0
      case (left: B, right: B) => left.s.compare(right.s)
      case (left: C, right: C) => 0
      case (left: D, right: D) => left.i.compare(right.i)
      case (left: E, right: E) => 0
      case (_, _) => indexOf(x) - indexOf(y)
    }
  }
}

@main
def tryIt() = {
  val l: List[Z] = List(C(), B("foo"), A(), D(42), E(), D(27), B("bar"))
  println(l.sorted)
}

Basically, I would separate the two problems of “what if the types are the same” and “what if the types are different”, since they call for different approaches. In the “same” case, delegate to whatever makes sense for those types. (Which might call for individual Ordering instances for them, but that’s up to you.) If they’re different, just put them in order and compare the indexes.

Running this seems to work as expected:

Jducoeur-Mac:temp jducoeur$ amm ordertest.sc
Compiling /Users/jducoeur/temp/ordertest.sc
List(A(), B(bar), B(foo), C(), D(27), D(42), E())

Obviously you’d need to enhance this to deal with your real situation, but hopefully it’s a useful idea…

1 Like