Kotlinで重複した順位付けをする方法

https://qiita.com/rocca00/items/6ef819752ba21e9c1cb9

↑の記事が面白かったので Kotlin でやってみた。

## 作成するもの

例えばアプリケーションで定義された次のようなクラスがあったときに、

```Kotlin
data class NameAndScore(
    val name: String,
    val score: Int,
)
```

`score` プロパティの値で順位付けして、
指定した順位までのオブジェクトを取得したい。

Kotlin らしいコードとして、次のように書けるとよいだろうか。

```Kotlin
sequenceOf(
    NameAndScore("Alice", 90),
    NameAndScore("Bob", 100),
    NameAndScore("Carol", 80),
    NameAndScore("Dave", 90),
).rankedByDescending { it.score } // score の降順で順位付けする。
    .takeWhile { it.rank <= 2 } // シーケンス先頭の2位タイまでのオブジェクトを取得する。
    .forEach {
        println(it)
    }
    // -> RankedValue(rank=1, value=NameAndScore(name=Bob, score=100))
    // -> RankedValue(rank=2, value=NameAndScore(name=Alice, score=90))
    // -> RankedValue(rank=2, value=NameAndScore(name=Dave, score=90))
```

このような `rankedByDescending` 拡張関数およびその周辺の API 群を作成する。


## 作成したもの

上述のコードを実現するために必要な `rankedByDescending` 拡張関数と、
それが返す `Sequence` の要素となる `RankedValue` クラスは、次のよう実装できる。

```Kotlin
/**
 * [selector] 関数が返した値の自然なソート順の降順に順位付けされ、順位でソートされた値の、シーケンスを返す。
 *
 * この操作は*安定している（stable）*。
 * これは、操作後も、等価な要素がそれらの相対的な順序を保持するということを意味する。
 *
 * この操作は*中間操作（intermediate）* であり、*状態を持つ（stateful）*。
 */
inline fun <T, R : Comparable<R>> Sequence<T>.rankedByDescending(
    crossinline selector: (T) -> R
): Sequence<RankedValue<T>> {
    var lastRank = 0
    var lastSortKey: R? = null
    return this.sortedByDescending(selector)
        .withIndex()
        .map { (index, value) ->
            val sortKey = selector(value)
            if (compareValues(sortKey, lastSortKey) != 0) {
                lastRank = index + 1
                lastSortKey = sortKey
            }
            RankedValue(lastRank, value)
        }
}

/**
 * 順位付けされた値。
 */
data class RankedValue<out T>(
    /** 1始まりの順位。 */
    val rank: Int,
    /** 値。 */
    val value: T,
) {
    init {
        require(rank > 0) {
            "rank は 0 より大きい必要があります。rank: $rank"
        }
    }
}
```

### `RankedValue` クラス

`RankedValue` クラスは順位付けされた値を表す。
[`Sequence<T>.withIndex`](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.sequences/with-index.html) 拡張関数が返すシーケンスの要素である [`IndexedValue`](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/-indexed-value/) クラスを参考にした。
`IndexedValue` の `index` プロパティの代わりに `rank` プロパティを持つ。

### `rankedByDescending` 拡張関数

`rankedByDescending` 拡張関数は要素に順位付けして、その順位通りにソートしたシーケンスを返す。
[`Sequence<T>.sortedByDescending`](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.sequences/sorted-by-descending.html) 拡張関数を参考にした。
順位付けした値は `RankedValue` クラスで表す。

`rankedByDescending` の実装は次のようになっている。

まず `sortedByDescending` を使って降順でソートする。

次に `withIndex` を使って各要素にインデックスを付ける。
タイの要素がない場合、このインデックスに 1 を加えたものがその要素の順位（`rank`）となる。

この関数の処理では、前の要素の順位 `lastRank` とソートキー `lastSortKey` を保持している。
現在の要素のソートキーが前の要素のソートキーと等価でない場合、これらを現在の値で更新し、その値（現在の要素の順位）から `RankedValue` オブジェクトを生成する。
等価（タイ）である場合、更新せず、前の要素の順位から `RankedValue` オブジェクトを生成する。

等価かどうかの判定には [`compareValues`](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.comparisons/compare-values-by.html) 関数を使用している。

- `==` を使用しないのは、ここでの等価性は `selector` が返した `Comparable<R>` 型のオブジェクトの大小比較に基づくべきものであって、[`Any.equals`](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin/-any/equals.html) に基づくものではないためだ。
  これらはほとんどのクラスで同じ結果を返すが、そうである保証はない。
- `Comparable` インターフェイスのメンバ関数 [`compareTo`](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin/-comparable/compare-to.html) を使用しないのは、`lastSortKey` が nullable であるためだ。

なお `rankedByDescending` 関数のコメントにある *intermediate*、*stateful* については（`sortedByDescending` などのコメントにもあるものだが）、[Sequences | Kotlin # Sequence operations](https://kotlinlang.org/docs/sequences.html#sequence-operations) を参考にされたい。

## 周辺関数も合わせた一式

降順の `rankedByDescending` を作成したのだから、昇順の `rankedBy` も必要だろう。
また、レシーバーが `Sequence` のものを作成したのだから、`Iterable` のものも作成しておきたい。

というわけで次のように API 一式を作成した。（上で紹介済みの `rankedByDescending` と `RankedValue` も含めた。）

```Kotlin
/**
 * 順位付けされた値。
 */
data class RankedValue<out T>(
    /** 1始まりの順位。 */
    val rank: Int,
    /** 値。 */
    val value: T,
) {
    init {
        require(rank > 0) {
            "rank は 0 より大きい必要があります。rank: $rank"
        }
    }
}

/**
 * [selector] 関数が返した値の自然なソート順の昇順に順位付けされ、順位でソートされた値の、リストを返す。
 *
 * この操作は*安定している（stable）*。
 * これは、操作後も、等価な要素がそれらの相対的な順序を保持するということを意味する。
 */
inline fun <T, R : Comparable<R>> Iterable<T>.rankedBy(
    crossinline selector: (T) -> R
): List<RankedValue<T>> =
    this.asSequence()
        .rankedBy(selector)
        .toList()

/**
 * [selector] 関数が返した値の自然なソート順の降順に順位付けされ、順位でソートされた値の、リストを返す。
 *
 * この操作は*安定している（stable）*。
 * これは、操作後も、等価な要素がそれらの相対的な順序を保持するということを意味する。
 */
inline fun <T, R : Comparable<R>> Iterable<T>.rankedByDescending(
    crossinline selector: (T) -> R
): List<RankedValue<T>> =
    this.asSequence()
        .rankedByDescending(selector)
        .toList()

/**
 * [selector] 関数が返した値の自然なソート順の昇順に順位付けされ、順位でソートされた値の、シーケンスを返す。
 *
 * この操作は*安定している（stable）*。
 * これは、操作後も、等価な要素がそれらの相対的な順序を保持するということを意味する。
 *
 * この操作は*中間操作（intermediate）* であり、*状態を持つ（stateful）*。
 */
inline fun <T, R : Comparable<R>> Sequence<T>.rankedBy(
    crossinline selector: (T) -> R
): Sequence<RankedValue<T>> {
    var lastRank = 0
    var lastSortKey: R? = null
    return this.sortedBy(selector)
        .withIndex()
        .map { (index, value) ->
            val sortKey = selector(value)
            if (compareValues(sortKey, lastSortKey) != 0) {
                lastRank = index + 1
                lastSortKey = sortKey
            }
            RankedValue(lastRank, value)
        }
}

/**
 * [selector] 関数が返した値の自然なソート順の降順に順位付けされ、順位でソートされた値の、シーケンスを返す。
 *
 * この操作は*安定している（stable）*。
 * これは、操作後も、等価な要素がそれらの相対的な順序を保持するということを意味する。
 *
 * この操作は*中間操作（intermediate）* であり、*状態を持つ（stateful）*。
 */
inline fun <T, R : Comparable<R>> Sequence<T>.rankedByDescending(
    crossinline selector: (T) -> R
): Sequence<RankedValue<T>> {
    var lastRank = 0
    var lastSortKey: R? = null
    return this.sortedByDescending(selector)
        .withIndex()
        .map { (index, value) ->
            val sortKey = selector(value)
            if (compareValues(sortKey, lastSortKey) != 0) {
                lastRank = index + 1
                lastSortKey = sortKey
            }
            RankedValue(lastRank, value)
        }
}
```

更に言えば次のようなものがあるとなおよいが、ここでは割愛する。

- `Array` をレシーバーとしたオーバーロード
- mutable なレシーバーを対象とした `rankBy` 系
- `Comparable` な要素を持つものをレシーバーとする、`selector` が不要な `rank` 系や `ranked` 系

／以上