Keep a FIFO queue of pending child iterators, ordered by the breadth-first order of their parents. Defer even the call creating a node's children until that iterator reaches the front and is needed:
def breadthFirst[T](node: Node[T]): Iter[Node[T]] = {
def childrenLater(n: Node[T]): Iter[Node[T]] = new Iter[Node[T]] {
private lazy val children = n.children()
def hasNext: Boolean = children.hasNext
def next(): Node[T] = {
require(children.hasNext, "empty child iterator")
children.next()
}
}
val pending = scala.collection.mutable.Queue.empty[Iter[Node[T]]]
pending.enqueue(childrenLater(node))
new Iter[Node[T]] {
private def normalize(): Unit = {
while (pending.nonEmpty && !pending.head.hasNext) pending.dequeue()
}
def hasNext: Boolean = {
normalize()
pending.nonEmpty
}
def next(): Node[T] = {
normalize()
require(pending.nonEmpty, "no more descendants")
val answer = pending.head.next()
pending.enqueue(childrenLater(answer))
answer
}
}
}Here “descendants” excludes the supplied root: the first output is its first child. A self-inclusive convention can prepend
unitIter(node) without changing the traversal logic. The queue invariant says its iterators enumerate the still-unreported children of already encountered parents, in parent breadth-first order. Consuming one child appends that child's deferred iterator after all earlier parents' pending children. Exhausted child iterators contribute nothing and can be discarded. This proves increasing depth and sibling order without constructing a complete level in advance.This lazy breadth-first traversal with child iterators never eagerly materializes all children or the whole tree. A finite prefix can therefore be traversed on a genuinely infinite tree. As with any strict breadth-first ordering, an infinite earlier level prevents reaching a deeper level; no algorithm can place a deeper node after every member of an infinite earlier level at a finite output position. For a locally finite tree, every finite-depth level is finite and each descendant is eventually reached, assuming the underlying iterator operations terminate. Fresh child iterators and exclusive ownership of consumed iterator states are essential to this argument.
Use the heap-numbered binary tree with root label zero and children . Its strict descendants in breadth-first search order are . A machine-safe
Node[Int] version stops at the largest representable label:class NumberNode(val label: Int) extends Node[Int] {
require(label >= 0)
def children(): Iter[Node[Int]] = new Iter[Node[Int]] {
private var candidate = 2L * label.toLong + 1L
private val last = candidate + 1L
def hasNext: Boolean = candidate <= last && candidate <= Int.MaxValue
def next(): Node[Int] = {
require(hasNext)
val answer = new NumberNode(candidate.toInt)
candidate += 1L
answer
}
}
}
val traversal = breadthFirst(new NumberNode(0))
var expected = 1
while (expected <= 1000) {
assert(traversal.hasNext)
assert(traversal.next().label == expected)
expected += 1
}The arithmetic is widened before computing child labels, so no negative wrapped labels occur. Repeated
hasNext calls should not skip nodes; a leaf root should produce immediate exhaustion, and uneven finite trees should retain sibling order across parents. A fresh second traversal should start again at one.Literal unbounded increase is impossible with the bounded
Int type. For a genuinely infinite test, change the label and child arithmetic to BigInt; the same construction then has no representational endpoint. The shown finite-prefix test already exercises lazy traversal without allocating the entire very large Int-labelled tree. Articles by others on the same topic
There are currently no matching articles.