↑の記事が面白かったので Kotlin でやってみた。
作成するもの
例えばアプリケーションで定義された次のようなクラスがあったときに、
data class NameAndScore(
val name: String,
val score: Int,
)
score プロパティの値で順位付けして、
指定した順位までのオブジェクトを取得したい。
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 クラスは、次のよう実装できる。
/**
* [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 拡張関数が返すシーケンスの要素である IndexedValue クラスを参考にした。
IndexedValue の index プロパティの代わりに rank プロパティを持つ。
rankedByDescending 拡張関数
rankedByDescending 拡張関数は要素に順位付けして、その順位通りにソートしたシーケンスを返す。
Sequence<T>.sortedByDescending 拡張関数を参考にした。
順位付けした値は RankedValue クラスで表す。
rankedByDescending の実装は次のようになっている。
まず sortedByDescending を使って降順でソートする。
次に withIndex を使って各要素にインデックスを付ける。
タイの要素がない場合、このインデックスに 1 を加えたものがその要素の順位（rank）となる。
この関数の処理では、前の要素の順位 lastRank とソートキー lastSortKey を保持している。
現在の要素のソートキーが前の要素のソートキーと等価でない場合、これらを現在の値で更新し、その値（現在の要素の順位）から RankedValue オブジェクトを生成する。
等価（タイ）である場合、更新せず、前の要素の順位から RankedValue オブジェクトを生成する。
等価かどうかの判定には compareValues 関数を使用している。
-
==を使用しないのは、ここでの等価性はselectorが返したComparable<R>型のオブジェクトの大小比較に基づくべきものであって、Any.equalsに基づくものではないためだ。
これらはほとんどのクラスで同じ結果を返すが、そうである保証はない。 -
Comparableインターフェイスのメンバ関数compareToを使用しないのは、lastSortKeyが nullable であるためだ。
なお rankedByDescending 関数のコメントにある intermediate、stateful については（sortedByDescending などのコメントにもあるものだが）、Sequences | Kotlin # Sequence operations を参考にされたい。
周辺関数も合わせた一式
降順の rankedByDescending を作成したのだから、昇順の rankedBy も必要だろう。
また、レシーバーが Sequence のものを作成したのだから、Iterable のものも作成しておきたい。
というわけで次のように API 一式を作成した。（上で紹介済みの rankedByDescending と RankedValue も含めた。）
/**
* 順位付けされた値。
*/
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系
／以上