Scala idiom for ordering by multiple criteria
Asked Answered
M

5

21

I want to do something like this:

class Foo extends Ordered[Foo] {
   val x
   val y
   val z
   .
   .
   .
   .
   def compare(that: Foo) = {
      val c0 = this.length compareTo that.length          // primary comparison
      lazy val c1 = this.x compareTo that.x               // secondary comparison
      lazy val c2 = this.y.size compareTo that.y.size     // tertiary comparison
      lazy val c3 = this.z.head compareTo that.z.head     // final tie breaker
      if (c0 != 0) c0 else if (c1 != 0) c1 else if (c2 != 0) c2 else if (c3 != 0) c3 else c4
   }    
}

I was wondering if there was any cleaner way to write this kind of thing. I am expecting some thing like Ordering.multipleBy(ordering: Ordered[A]*) signature which takes a varargs of comparables and selects first non zero.

Milka answered 4/2, 2013 at 21:18 Comment(0)
S
35

It is often better to use Ordering instead of Ordered. Ordering is a type class and is much more flexible than Ordered (if only because Ordered must be implemented by the type to compare, while with Ordering you can define this outside). To define the natural ordering (default Ordering instance) for your type, you just define an implicit ordering value in the companion object.

So, enough with the preamble. The nice thing is that when using Ordering what you want to do is pretty simple, as there is an implicit ordering for tuples (provided that the tuple elements themselves have a orderings)`:

object Foo {
  implicit val FooOrdering = Ordering.by{ foo: Foo => 
    (foo.length, foo.x, foo.y, foo.z) 
  }
}

In addition, there is an implicit conversion that converts any value that has an Ordering type class instance into an Ordered value (see Ordered.orderingToOrdered) so we have nothing special to do to automagically being able to pass any instance of Foo to a function that expects an Ordered[Foo])


UPDATE: Concerning your new question:

Slightly related - is there any way to compose orderings?

One way to do it would be to use mostly the same technic based on Ordering.by and conversion to tuples, but explicitly passing the orderings to compose:

val byXOrdering = Ordering.by{ foo: Foo => foo.x }
val byYOrdering = Ordering.by{ foo: Foo => foo.y }
val byZOrdering = Ordering.by{ foo: Foo => foo.z }

// Compose byXOrdering and byYOrdering:
val byXThenYOrdering = Ordering.by{ foo: Foo => (foo, foo) }(Ordering.Tuple2(byXOrdering, byYOrdering))

// Compose byXOrdering and byYOrdering and byZOrdering:
val byXThenYThenZOrdering = Ordering.by{ foo: Foo => (foo, foo, foo) }(Ordering.Tuple3(byXOrdering, byYOrdering, byZOrdering))

But it is relatively "noisy". I could not find anything better using only the standard library, and so I would actually advise to use our own helper:

final class CompositeOrdering[T]( val ord1: Ordering[T], val ord2: Ordering[T] ) extends Ordering[T] {
  def compare( x: T, y: T ) = {
    val comp = ord1.compare( x, y )
    if ( comp != 0 ) comp else ord2.compare( x, y )
  }
}
object CompositeOrdering {
  def apply[T]( orderings: Ordering[T] * ) = orderings reduceLeft (_ orElse _)
}
implicit class OrderingOps[T]( val ord: Ordering[T] ) extends AnyVal {
  def orElse( ord2: Ordering[T] ) = new CompositeOrdering[T]( ord, ord2 )
}

Which can be used like this:

val byXOrdering = Ordering.by{ foo: Foo => foo.x }
val byYOrdering = Ordering.by{ foo: Foo => foo.y }
val byZOrdering = Ordering.by{ foo: Foo => foo.z }

// Compose byXOrdering and byYOrdering:
val byXThenYOrdering = byXOrdering orElse byYOrdering

// Compose byXOrdering and byYOrdering and byZOrdering:
val byXThenYThenZOrdering = byXOrdering orElse byYOrdering orElse byZOrdering

Or even simpler, like this:

// Compose byXOrdering and byYOrdering:
val byXThenYOrdering = CompositeOrdering(byXOrdering, byYOrdering)

// Compose byXOrdering and byYOrdering and byZOrdering:
val byXThenYThenZOrdering = CompositeOrdering(byXOrdering, byYOrdering, byZOrdering)

CompositeOrdering.apply is basically what you called Ordering.multipleBy in your question.

Sym answered 4/2, 2013 at 21:58 Comment(5)
I think you meant "Ordering is a type class and is much more flexible than Ordered" instead of "Ordering is a type class and is much more flexible than Ordering". :)Gallinule
Lol, yes indeed. Thanks for reporting this, this is now fixed.Schedule
Slightly related - is there any way to compose orderings? For example, I have AgeOrdering: Ordered[Person] and HeightOrdering: Ordered[Person] and I want to create AgeThenHeightOrdering: Ordered[Person]Milka
I think more concisely, the following would work: val byXThenYOrdering = Ordering.by{ foo: Foo => (foo.x, foo.y) } And yes, it'll be limited to the cardinality limit of tuples.Laliberte
@XianXu: Maybe I am missing something, but isn't it exactly what I recommended in the first part of my answer...? The second part was only in response to a comment that I treated like another question. If you were precisely referring to that second question, then your code snippet is irrelevant as the question was how to compose existing Ordering instances, and not how to make this particular example more concise.Schedule
P
5

If you want maximal speed--not what you asked for, I know!--and still decent clarity, you can

def compare(that: Foo): Int = {
  this.length compareTo that.length match { case 0 =>; case c => return c }
  this.x      compareTo that.x      match { case 0 =>; case c => return c }
  this.y.size compareTo that.y.size match { case 0 =>; case c => return c }
  this.z.head compareTo that.z.head match { case 0 =>; case c => return c }
  0
}

There are various nice collection-based and other solutions also, which I will leave to others to explain. (Note all the boilerplate and observe that all you really need to know is _.length in each case...which motivates a compareBy, for example.)

Parturifacient answered 4/2, 2013 at 21:37 Comment(0)
M
3

The best I can think of is this:

def compare(that: Foo) = multiCompare(
  this.length compareTo that.length      // primary comparison
  this.x      compareTo that.x,          // secondary comparison
  this.y.size compareTo that.y.size,     // tertiary comparison
  this.z.head compareTo that.z.head,     // final tie breaker
)

def multiCompare(c: ( => Int)*) = c find {_ != 0} getOrElse 0
Milka answered 4/2, 2013 at 21:48 Comment(0)
B
0

Avoid Ordered and Ordering if you can. The easiest way to sort by multiple criteria is to use sortBy. Here is an example:

val foos: Seq[Foo] = ???
foos.sortBy(f => (f.x, f.y, f.z, ...))

If you really want to implement Ordered I suggest you look at https://mcmap.net/q/186383/-easy-idiomatic-way-to-define-ordering-for-a-simple-case-class

If you really want an Ordering, the simplest way to write one is as follows:

val fooOrdering: Ordering[Foo] = Ordering.by(f => (f.x, f.y, f.z))
Bes answered 26/1, 2022 at 13:36 Comment(0)
C
-1

I use this syntax because it's self-documenting:

  val compositeOrdering: Ordering[Foo] =
    Comparator.comparing[Foo, CustomType](_.x, new ExplicitOrderingForCustomType)
    .thenComparingDouble(_.y)
    .thenComparingInt(_.z)
    .compare

It's constructing a composite java.util.Comparator, then casting its compare method to scala.math.Ordering

Cenac answered 11/2, 2021 at 5:59 Comment(0)

© 2022 - 2024 — McMap. All rights reserved.