**Challenge:** sort a list of objects by name, but some names have priority. If these names appear, they should be ordered by the position they have in the priority list.

For example:

```
val priorityList = Seq("Willow", "James", "Ezra")
val input = Seq("Olivier", "Charlotte", "Willow", "Declan", "Aurora", "Ezra")
val ordered = ???
assert(ordered == Seq("Willow", "Ezra", "Aurora", "Charlotte", "Declan", "Olivier"))
```

Challenge accepted.

Luckily Scala has strong support for sorting in the standard library. All sequences have a `sorted` method which accepts an `Ordering`. The ordering is an implicit parameter which means that normally we don't need to provide it; it will be derived to the natural ordering of the items. However, we are going to provide this parameter explicitly. Let's build an `Ordering`!

The challenge explains we have 2 orderings:

- first order by the priority list
- failing that, order by alphabet

Let's focus on the first ordering. The idea is to assign an integer 'priority-value' to each possible string that is based on the position in the priority list. If the string is not in the list, we use some high integer. The first ordering will simply order by this priority-value. Lower numbers go before higher number, just like the natural ordering of integers.

```
// attempt 1
val priorityValue = priorityList.indexOf(name)
```

This works well for any name on the priority list. E.g. `Willow` gets `0` and `Ezra` gets `2`. Unfortunately, all the other names get priority value `-1` which orders them even *before* `Willow`. We need to convert the `-1` to something higher.

Since I like to program without `if` statements whenever possible, I looked at math for a solution. Modulus can do the trick:

```
// attempt 2
val priorityValue = priorityList.indexOf(name) % priorityList.size
```

Oops, wrong modulus implementation: `-1 % 3 == -1`. Let's use `floorMod`:

```
// attempt 3
val priorityValue = Math.floorMod(priorityList.indexOf(name), priorityList.size)
```

Now `-1` gets converted into `priorityList.size` which is definitely higher than the other priority-values. However, since we don't really care what the higher number is we can just use `Int.MaxValue`:

```
val priorityValue = Math.floorMod(priorityList.indexOf(name), Int.MaxValue)
```

Now we wrap that in an `Ordering`:

```
val priorityOrdering: Ordering[String] =
Ordering.by(name => Math.floorMod(priorityList.indexOf(name), Int.MaxValue))
```

Unfortunately Scala can't derive the type. We either need to type the value directly, or add a type on the `name` parameter.

Now we need to add the second ordering. We can simply use `Ordering.String` from the library. We combine the orderings with `orElse`, available since Scala 2.13. The second ordering is used when `priorityOrdering` can't decide because the priority-value is the same.

Note that for the special case where we compare a priority value with itself, e.g. `Willow` with `Willow`, the second ordering is also applied. This is okay though, the outcome doesn't change because these values are the same for the alphabetic ordering also.

Here is the complete code:

```
val priorityList = Seq("Willow", "James", "Ezra")
val priorityOrdering: Ordering[String] =
Ordering.by(name => Math.floorMod(priorityList.indexOf(name), Int.MaxValue))
val combinedOrdering: Ordering[String] =
priorityOrdering.orElse(Ordering.String)
val input = Seq("Olivier", "Charlotte", "Willow", "Declan", "Aurora", "Ezra")
val ordered = input.sorted(combinedOrdering)
assert(ordered == Seq("Willow", "Ezra", "Aurora", "Charlotte", "Declan", "Olivier"))
```

We're almost there. The challenge was to work on any object. Lets wrap it up a bit and also make it work for any type of priority value:

```
def priorityOrdering[A, B : Ordering](priorityList: Seq[B], by: A => B): Ordering[A] = {
def priorityValue(b: B): Int = Math.floorMod(priorityList.indexOf(b), Int.MaxValue)
Ordering.by[A, Int](a => priorityValue(by(a))).orElseBy(by)
}
```

We can use like this:

```
val ordered = input.sorted(priorityOrdering[String, String](priorityList, identity))
```

Or like this. Here we sort persons by birthdate, ordering today before the other days:

```
case class Person(name: String, birthdate: MonthDay)
val persons: Seq[Person] = ???
val priorityDates = Seq(MonthDay.now())
persons.sorted(priorityOrdering(priorityDates, (_: Person).birthdate))
```

**Some remarks**

Note that in all these cases type derivation is quite awful. The compiler has problems finding the correct types, even though all the information is available.

You should also know that you can't use this approach if you are stuck on Scala 2.12 or earlier since `Ordering.orElse` is not available there.

**Alternative**

You can side-step all the type derivation problems by using the `sortBy` method. Give it a function that returns a tuple of `Int`s, `String`s, or anything for which an `Ordering` is already defined. The sequence is then sorted on the first value of the tuple, then on the second value, etc.:

```
def priorityValue(name: String): Int =
Math.floorMod(priorityList.indexOf(name), Int.MaxValue)
val ordered = input.sortBy(name => (priorityValue(name), name))
```

**Conclusion**

Although I had fun learning all about `Ordering`, next time I'll avoid it and go directly for `sortBy`.

## No comments:

## Post a Comment