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?

Your approach requires the use of reflection. Are you sure you want this? — ziggystar
– ziggystar, Commented Feb 15, 2016 at 11:08
@ziggystar, it doesn't, if the OP can enumerate all possible fields in the book class (then the ordering becomes a list of "if field a is in fields then compare fields a of the two objects.. if field z is in fields then compare fields of the two objects...". ). — The Archetypal Paul
– The Archetypal Paul, Commented Feb 15, 2016 at 12:04
@ziggystar I can map string names of class fields to actual fields, yes — arctica
– arctica, Commented Feb 15, 2016 at 13:43

0__ · Accepted Answer · 2016-02-15 20:02:37Z

6

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

edited Feb 15, 2016 at 20:02

answered Feb 15, 2016 at 12:36

0__

67.5k21 gold badges180 silver badges271 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

0__ Over a year ago

For descending, you'd have Book.by(_.author).reverse

arctica Over a year ago

Thank you! I wrote my complete solution below.

Community · Accepted Answer · 2017-05-23 11:45:01Z

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)
  }
}

Sascha Kolberg · Accepted Answer · 2016-02-15 12:21:37Z

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))

dth · Accepted Answer · 2016-02-15 12:59:00Z

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))

Collectives™ on Stack Overflow

Scala sort by unknown number of fields

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related