Идиоматический Котлин для прохождения уровня порядка BST - PullRequest
Новая
       23

Идиоматический Котлин для прохождения уровня порядка BST

0 голосов
/ 06 июня 2018

Ниже приведена моя реализация обхода порядка уровней для BST: 

fun levelOrder(): Iterable<Pair<Key, Int>> {
    class InternalNode(val node: Node<Key>, val level: Int)

    val yetToVisit = emptyQueue<InternalNode>()
    val visited = emptyQueue<Pair<Key, Int>>()

    root?.also { yetToVisit.enqueue(InternalNode(it, 1)) }

    while (!yetToVisit.isEmpty) {
        do {
            val node = yetToVisit.dequeue().also { visited.enqueue(it.node.key to it.level) }
            listOf(node.node.left, node.node.right)
                    .filter(Objects::nonNull)
                    .map { InternalNode(it!!, node.level + 1) }
                    .forEach(yetToVisit::enqueue)
        } while (!yetToVisit.isEmpty && yetToVisit.peek().level == node.level)
    }

    return visited
}

Мне интересно, можно ли реализовать вышеперечисленное более идиоматическим / функциональным образом без использования while и do-while,Идеи?

1 Ответ

0 голосов
/ 06 июня 2018

Да, вы можете, используя sequence (скажем, generateSequence): 

fun levelOrder(): Iterable<Pair<Key, Int>> {
    class InternalNode(val node: Node<Key>, val level: Int)

    val yetToVisit = emptyQueue<InternalNode>()
    val visited = emptyQueue<Pair<Key, Int>>()
    fun peek() = yetToVisit.dequeue()
            .also { visited.enqueue(it.node.key to it.level) }

    root?.also { yetToVisit.enqueue(InternalNode(it, 1)) }
    if (yetToVisit.isEmpty) return visited
    generateSequence(peek()) { node ->
        if (!yetToVisit.isEmpty && yetToVisit.peek().level == node.level) peek()
        else null
    }.forEach { node ->
        listOfNotNull(node.node.left, node.node.right)
                .map { InternalNode(it, node.level + 1) }
                .forEach(yetToVisit::enqueue)
    }

    return visited
}

И кстати, вы можете использовать listOfNotNull или listOf().filterNotNull для замены filter(Objects::nonNull).

Примечание. Я только что синтаксически реорганизовал ваш код, но, поскольку я не могу скомпилировать ваш код, я не могу проверить его правильность.Если это не работает, как ожидается, оставьте комментарий.

...