窥探迭代器

Question

Kotlin 中有没有一种方法可以“窥视”迭代器的下一个元素而不推进它？对于示例用例，请考虑此函数用于合并两个预排序的序列：

fun merge(seq1: Sequence<Int>, seq2: Sequence<Int>) = sequence<Int> {
    val it1 = seq1.iterator()
    var current1 = if (it1.hasNext()) it1.next() else null
    val it2 = seq2.iterator()
    var current2 = if (it2.hasNext()) it2.next() else null

    while (current1 != null && current2 != null) {
        if (current1 <= current2) {
            yield(current1)
            current1 = if (it1.hasNext()) it1.next() else null
        } else {
            yield(current2)
            current2 = if (it2.hasNext()) it2.next() else null
        }
    }
    while (current1 != null) {
        yield(current1)
        current1 = if (it1.hasNext()) it1.next() else null
    }
    while (current2 != null) {
        yield(current2)
        current2 = if (it2.hasNext()) it2.next() else null
    }
}

这个函数必须跳过重重困难，因为Iterator界面无法在不前进的情况下询问下一个元素。换句话说，它不遵守命令-查询分离原则。

如果我使用 Guava 的PeekingIterator，我可以使这个函数更加简洁和可读：

fun merge(seq1: Sequence<Int>, seq2: Sequence<Int>) = sequence<Int> {
    val it1: PeekingIterator<Int> = Iterators.peekingIterator(seq1.iterator())
    val it2: PeekingIterator<Int> = Iterators.peekingIterator(seq2.iterator())

    while (it1.hasNext() && it2.hasNext())
        yield((if (it1.peek() <= it2.peek()) it1 else it2).next())
    yieldAll(it1)
    yieldAll(it2)
}

相同的功能从 24 行减少到 9 行！然而，我在 Kotlin 项目中使用 Guava 感觉不太舒服。Guava 的创建是为了解决 Java API 的一些限制。Kotlin 标准库要丰富得多，我们不需要使用第三方 Java 库。有没有办法在不使用 Guava 的情况下使第一个代码示例更加简洁和可读？

附录

这是上述函数的示例单元测试，它应该让您了解它的行为方式：

import io.kotest.core.spec.style.FreeSpec
import io.kotest.matchers.shouldBe

class MyTest : FreeSpec({
    "merge test" {
        merge(emptySequence(), emptySequence()).toList() shouldBe emptyList()
        merge(emptySequence(), sequenceOf(1)).toList() shouldBe listOf(1)
        merge(emptySequence(), sequenceOf(1, 3)).toList() shouldBe listOf(1, 3)
        merge(sequenceOf(1), emptySequence()).toList() shouldBe listOf(1)
        merge(sequenceOf(1, 3), emptySequence()).toList() shouldBe listOf(1, 3)
        merge(sequenceOf(0, 3, 4), sequenceOf(1, 4, 7)).toList() shouldBe listOf(0, 1, 3, 4, 4, 7)
    }
)

Answer 1

我不认为 Kotlin stdlib 提供了这个，但我们可以自己实现它：

fun main() {
    val iter = listOf(1, 2, 3).iterator().peeking()

    println(iter.next()) // 1
    println(iter.peek()) // 2
    println(iter.peek()) // 2
    println(iter.next()) // 2
    println(iter.peek()) // 3
    println(iter.next()) // 3
    println(iter.peek()) // NoSuchElementException
}

fun <T> Iterator<T>.peeking() = object : PeekingIterator<T> {
    private var hasPeeked = false
    private var peeked: T? = null

    override fun hasNext(): Boolean = hasPeeked || this@peeking.hasNext()

    override fun next(): T  {
        return if (hasPeeked) {
            hasPeeked = false
            @Suppress("UNCHECKED_CAST")
            peeked as T
        } else {
            this@peeking.next()
        }
    }

    override fun peek(): T {
        if (!hasPeeked) {
            peeked = this@peeking.next()
            hasPeeked = true
        }
        @Suppress("UNCHECKED_CAST")
        return peeked as T
    }
}

interface PeekingIterator<T> : Iterator<T> {
    fun peek(): T
}