Scala sort by unknown number of fields

Question

I have simple class with N fields.

case class Book(a: UUID... z: String)

and function:

def sort(books:Seq[Book], fields:Seq[SortingFields]) = {...}

where

case class SortingField(field: String, asc: Boolean)

where field - a field of the Book class, asc - a sorting direction.

So, in advance I dont know which fields (from 0 to N) and sorting orders come into my function to sort a books collection. It may be just a single ID field or all exist fields of a class in a particular order.

How could it be implemented?

Answer 1

With the nice answer provided by @0__ I've come up to folowing:

def by[A: Ordering](e: Book => A): Ordering[Book] = Ordering.by(e)

with

implicit class OrderingAndThen[A](private val self: Ordering[A]) extends AnyVal {
    def andThen(that: Ordering[A]): Ordering[A] = new Ordering[A] {
      def compare(x: A, y: A): Int = {
      val a = self.compare(x, y)
      if (a != 0) a else that.compare(x, y)
    }
  }
}

next I map name of a class field with a direction to actual ordering

def toOrdering(name: String, r: Boolean): Ordering[Book] = {
    (name match {
      case "id" => Book.by(_.id)
      case "name" =>  Book.by(_.name)
   }) |> (o => if (r) o.reverse else o)
}

using a forward pipe operator:

implicit class PipedObject[A](value: A) {
    def |>[B](f: A => B): B = f(value)
}

and finally I combine all the ordering with the reduce function:

val fields = Seq(SortedField("name", true), SortedField("id", false))
val order = fields.map(f => toOrdering(f.field, f.reverse)).reduce(combines(_,_))
coll.sorted(order)

where

val combine = (x: Ordering[Book], y: Ordering[Book]) => x andThen y

An aternate way is to use @tailrec:

def orderingSeq[T](os: Seq[Ordering[T]]): Ordering[T] = new Ordering[T] {
  def compare(x: T, y: T): Int = {
    @tailrec def compare0(rest: Seq[Ordering[T]], result: Int): Int = result match   {
      case 0 if rest.isEmpty => 0
      case 0 => compare0(rest.tail, rest.head.compare(x, y))
      case a => a
    }

    compare0(os, 0)
  }
}

Answer 2

I would use the existing Ordering trait for this and use a function that maps from Book to a field, i.e. Ordering.by[Book, String](_.author). Then you can simply sort with books.sorted(myOrdering). If I define a helper method on Book's companion object, getting these orderings is very simple:

object Book {
  def by[A: Ordering](fun: Book => A): Ordering[Book] = Ordering.by(fun)
}
case class Book(author: String, title: String, year: Int)

val xs = Seq(Book("Deleuze" /* and Guattari */, "A Thousand Plateaus", 1980),
             Book("Deleuze", "Difference and Repetition", 1968),
             Book("Derrida", "Of Grammatology", 1967))

xs.sorted(Book.by(_.title)) // A Thousand, Difference, Of Grammatology
xs.sorted(Book.by(_.year )) // Of Grammatology, Difference, A Thousand

Then to chain the ordering by multiple fields, you can create custom ordering that proceeds through the fields until one comparison is non-zero. For example, I can add an extension method andThen to Ordering like this:

implicit class OrderingAndThen[A](private val self: Ordering[A]) extends AnyVal {
  def andThen(that: Ordering[A]): Ordering[A] = new Ordering[A] {
    def compare(x: A, y: A): Int = {
      val a = self.compare(x, y)
      if (a != 0) a else that.compare(x, y)
    }
  }
}

So I can write:

val ayt = Book.by(_.author) andThen Book.by(_.year) andThen Book.by(_.title)
xs.sorted(ayt)  // Difference, A Thousand, Of Grammatology

Answer 3

Case classes are Products, so you can iterate over all field values using instance.productIterator. This gives you the fields in order of declaration. You can also access them directly via their index. As far as I can see, there is however no way to get the field names. This would have to be done using reflection or macros. (Maybe some library as Shapeless can already do that).

An other way would be to not define fields to sort by with names but with functions:

case class SortingField[T](field: Book => T, asc: Boolean)(implicit ordering: Ordering[T])

new SortingField(_.fieldName, true)

And then declare sort as:

def sort(books: Seq[Book], fields: Seq[SortingField[_]]) = {...}

And use the following compare method to implement the combined ordering:

def compare[T](b1: Book, b2: Book, field: SortingField[T]) =
  field.ordering.compare(field.field(b1), field.field(b2))

Answer 4

It is possible. But as far as I can see you will have to use reflection.

Additionally, you would have to change your SortingField class a bit as there is no way the scala compiler can figure out the right Ordering type class for each field.

Here is a simplified example.

import scala.reflect.ClassTag

/** You should be able to figure out the correct field ordering here. Use `reverse` to decide whether you want to sort ascending or descending. */
case class SortingField[T](field: String, ord: Ordering[T]) { type FieldType = T }
case class Book(a: Int, b: Long, c: String, z: String)

def sort[T](unsorted: Seq[T], fields: Seq[SortingField[_]])(implicit tag: ClassTag[T]): Seq[T] = {
  val bookClazz = tag.runtimeClass

  fields.foldLeft(unsorted) { case (sorted, currentField) =>
    // keep in mind that scala generates a getter method for field 'a'
    val field = bookClazz.getMethod(currentField.field)
    sorted.sortBy[currentField.FieldType](
      field.invoke(_).asInstanceOf[currentField.FieldType]
    )(currentField.ord)
  }
}

However, for sorting by multiple fields you would have to either sort the sequence multiple times or better yet compose the various orderings correctly.

So this is getting a bit more 'sophisticated' without any guarantees about correctness and completeness, but with a little test that it does not fail spectacularly:

def sort[T](unsorted: Seq[T], fields: Seq[SortingField[_]])(implicit tag: ClassTag[T]): Seq[T] = {
  @inline def invokeGetter[A](field: Method, obj: T): A = field.invoke(obj).asInstanceOf[A]
  @inline def orderingByField[A](field: Method)(implicit ord: Ordering[A]): Ordering[T] = {
    Ordering.by[T, A](invokeGetter[A](field, _))
  }

  val bookClazz = tag.runtimeClass
  if (fields.nonEmpty) {
    val field = bookClazz.getMethod(fields.head.field)

    implicit val composedOrdering: Ordering[T] = fields.tail.foldLeft {
      orderingByField(field)(fields.head.ord)
    } { case (ordering, currentField) =>
      val field = bookClazz.getMethod(currentField.field)
      val subOrdering: Ordering[T] = orderingByField(field)(currentField.ord)

      new Ordering[T] {
        def compare(x: T, y: T): Int = {
          val upperLevelOrderingResult = ordering.compare(x, y)

          if (upperLevelOrderingResult == 0) {
            subOrdering.compare(x, y)
          } else {
            upperLevelOrderingResult
          }
        }
      }
    }

    unsorted.sorted(composedOrdering)
  } else {
    unsorted
  }
}

sort(
  Seq[Book](
    Book(1, 5L, "foo1", "bar1"),
    Book(10, 50L, "foo10", "bar15"),
    Book(2, 3L, "foo3", "bar3"),
    Book(100, 52L, "foo4", "bar6"),
    Book(100, 51L, "foo4", "bar6"),
    Book(100, 51L, "foo3", "bar6"),
    Book(11, 15L, "foo5", "bar7"),
    Book(22, 45L, "foo6", "bar8")
  ),
  Seq(
    SortingField("a", implicitly[Ordering[Int]].reverse),
    SortingField("b", implicitly[Ordering[Long]]),
    SortingField("c", implicitly[Ordering[String]])
  )
)

>> res0: Seq[Book] = List(Book(100,51,foo3,bar6), Book(100,51,foo4,bar6), Book(100,52,foo4,bar6), Book(22,45,foo6,bar8), Book(11,15,foo5,bar7), Book(10,50,foo10,bar15), Book(2,3,foo3,bar3), Book(1,5,foo1,bar1))