# Ordering

## Ordering in Scala

Ordering in scala implemended with following types located at `scala.math`:

* `Ordering[T]` - trait whose instances each represent a strategy for sorting instances of a type.
* `PartialOrdering[T]` - representation of partial ordering on some type.
* `Equiv[T]` - representation of equivalence on some type.
* `Ordered[T]` - trait for data that have a single, natural ordering.
* `Ordering.Implicits` - access to other implicit orderings.

### Ordering

`Ordering` is a trait whose instances each represent a strategy for sorting instances of a type. An `Ordering[T]` is implemented by specifying `compare(a:T, b:T)`, which decides how to order two instances `a` and `b`. Ordering has the same purpose as `Comparator` in Java, but with scala extensions, implicit and related math properties.

Most sorting functionality implemented in the scala library operates using instances of `Ordering`, so usage of sorting is a preferable way to implement order relation in scala. Providing an ordering directly eliminates an implicit conversion in most cases.

Instances of `Ordering[T]` can be used by things like `scala.util.Sorting` to sort collections like `Array[T]`.

```scala
import scala.util.Sorting

case class Person(name:String, age:Int)
val people = Array(Person("bob", 30), Person("ann", 32), Person("carl", 19))

// sort by age
object AgeOrdering extends Ordering[Person] {
  def compare(a:Person, b:Person) = a.age compare b.age
}
Sorting.quickSort(people)(AgeOrdering)
```

### Ordering companion object

Ordering's companion object defines many implicit objects to deal with subtypes of `AnyVal` (e.g. `Int`, `Double`), `String`, and others.

* `Ordering.by`
* `Ordering.on`

```scala
case class Employee(id: Int, firstName: String, lastName: String)

object Employee {
  // Note that because `Ordering[A]` is not contravariant, the declaration
  // must be type-parametrized in the event that you want the implicit
  // ordering to apply to subclasses of `Employee`.
  implicit def orderingByName[A <: Employee]: Ordering[A] =
    Ordering.by(e => (e.lastName, e.firstName))

  val orderingById: Ordering[Employee] = Ordering.by(e => e.id)
}
```

Given `es: SeqLike[Employee]`, `es.sorted()` will sort by name, and `es.sorted(Employee.orderingById)` will sort by `id`.

For case classes ordering on deconstruction can be used:

```scala
object A {
  implicit val ord = Ordering.by(unapply)
}
```

This has the benefit that it is updated automatically whenever `A` changes. But, `A`'s fields need to be placed in the order by which the ordering will use them.

### Ordered

Trait `Ordered` is the analogue of `Comparable` in Java. Classes that implement `Ordered` trait can be sorted with `scala.util.Sorting` and can be compared with standard comparison operators (e.g. > and <). `Ordered` and `Ordering` both provide implicits allowing them to be used interchangeably.

```scala
case class A(tag: String, load: Int) extends Ordered[A] {
  // Required as of Scala 2.11 for reasons unknown - the companion to Ordered
  // should already be in implicit scope
  import scala.math.Ordered.orderingToOrdered

  def compare(that: A): Int = (this.tag, this.load) compare (that.tag, that.load)
}
```

Note that `Ordering` and `Ordered` does not provide implementation of `equals` methods. Developers must implement this method by itself and make sure that it consistent with ordering.

### Extra Implicits

This works: why??

```
import scala.math.Ordering.Implicits._
var x = (1,2,3) < (1,2,4)
```

#### Partial Ordering

Partial Ordering trait defines only one method `def lteq(x: T, y: T): Boolean` which returns `true` iff `x` comes before `y` in the ordering.

A partial ordering is a binary relation on a type `T`, exposed as the `lteq` method of this trait. This relation must be: *reflexive*: `lteq(x, x) == true`, for any `x` of type `T`. *anti-symmetric*: if `lteq(x, y) == true` and `lteq(y, x) == true` then `equiv(x, y) == true`, for any x and y of type T. *transitive*: if `lteq(x, y) == true` and `lteq(y, z) == true` then `lteq(x, z) == true`, for any `x`, `y`, and `z` of type `T`.

Additionally, a partial ordering induces an *equivalence relation* on a type `T`: `x` and `y` of type `T` are equivalent if and only if `lteq(x, y) && lteq(y, x) == true`.

#### Equivalence relation

An equivalence relation is a binary relation on a type. This relation is exposed as the `equiv` method of the `Equiv` trait. The relation must be: *reflexive*: `equiv(x, x) == true` for any `x` of type `T`. *symmetric*: `equiv(x, y) == equiv(y, x)` for any `x` and `y` of type `T`. *transitive*: if `equiv(x, y) == true` and `equiv(y, z) == true`, then `equiv(x, z) == true` for any `x`, `y`, and `z`s of type `T`.

## Sorting in Scala

Sorting in scala implemented in `scala.util.Sorting` object.&#x20;

Вопросы:

* Какие типы отвечают за упорядочивание в scala?
* Как работает trait `Ordering`, какие у него возможности.
* Способы применения `Ordering`.
* В чем отличие `Ordered` от `Ordering`.
* Как подключить реализованные неявные Ordering для разных типов данных?
* Как задать частичный порядок на типе T?
* Какие свойства частичного порядка есть?
* Как задать отношение эквивалентности на типе T. Какими свойствами должно обладать отношение эквивалентности.
* Как реализована сортировка в Scala.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://strctr.gitbook.io/programming/01-languages/scala/01-scala-language/scala-ordering.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.