1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

【Kotlin】Sequenceでスターリンソート

1
Last updated at Posted at 2019-07-31

スターリンソートは 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
            }
    }
}

一人ずつ呼び出され、粛正されたものは帰ってこない。

1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?