スターリンソートは Sequence 向きです。
普通のソートでは内部処理にリストが必要になりますが、
スターリンソートでは不要です。
というわけで、実装しました。
fun <T : Comparable<T>> Sequence<T>.stalinSorted(): Sequence<T> =
stalinSortedWith(naturalOrder())
fun <T : Comparable<T>> Sequence<T>.stalinSortedDescending(): Sequence<T> =
stalinSortedWith(reverseOrder())
inline fun <T, R : Comparable<R>> Sequence<T>.stalinSortedBy(
crossinline selector: (T) -> R?
): Sequence<T> =
stalinSortedWith(compareBy(selector))
inline fun <T, R : Comparable<R>> Sequence<T>.stalinSortedByDescending(
crossinline selector: (T) -> R?
): Sequence<T> =
stalinSortedWith(compareByDescending(selector))
fun <T> Sequence<T>.stalinSortedWith(
comparator: Comparator<in T>
): Sequence<T> = sequence {
val itr = iterator()
.takeIf { it.hasNext() }
?: return@sequence
var previous = itr.next().also {
yield(it)
}
while (itr.hasNext()) {
itr.next()
.takeIf { comparator.compare(previous, it) <= 0 }
?.also {
yield(it)
previous = it
}
}
}
一人ずつ呼び出され、粛正されたものは帰ってこない。