Use the recorded child list as the depth-first traversal order. A leaf of a tree has no children, so it contributes its own identity once. Closure cancels the remaining traversal; a normal completion closes the output so that a consumer can detect end-of-fringe.
def dfFringe(node: Array[Node], root: NodeId, fringe: ![NodeId]): PROC = proc {
def walk(v: NodeId): Unit = {
val cs = node(v).children
if (cs.isEmpty) fringe ! v
else cs.foreach(walk)
}
try { walk(root) }
catch { case _: io.threadcso.process.Stopped => () }
finally { fringe.closeOut }
}A completed finite spanning tree has no recursive child graph cycle, so this visits a finite number of vertices. A blocked leaf send is released if its output closes. A singleton root is itself a leaf of a tree and is output once. With sufficient call-stack space,
Run two
dfFringe producers on synchronous one-to-one message-passing channels, and compare one received leaf from each. Catch closure separately on each input: otherwise the first closure could hide an extra value in the other fringe. An extra value or unequal pair is enough to stop immediately.def sameFringe(node1: Array[Node], root1: NodeId,
node2: Array[Node], root2: NodeId): Boolean = {
val a = OneOne[NodeId]
val b = OneOne[NodeId]
var equal = true
def next(p: ?[NodeId]): Option[NodeId] =
try { Some(p ? ()) }
catch { case _: io.threadcso.process.Stopped => None }
val compare = proc {
var done = false
try {
while (!done) {
val x = next(a)
val y = next(b)
(x, y) match {
case (None, None) => done = true
case (Some(u), Some(v)) if u == v => ()
case _ => equal = false; done = true
}
}
} finally { a.closeIn; b.closeIn }
}
(dfFringe(node1, root1, a) || dfFringe(node2, root2, b) || compare)()
equal
}After successful comparisons, the first identities in the two leaf sequences agree. The first differing pair disproves equality of sequences; simultaneous exhaustion proves it; exhaustion on exactly one side disproves it. Therefore,Closing both inputs on every comparator exit releases either producer if it is waiting in an output. The closure handler in
dfFringe then returns normally, and the parallel composition joins before equal is read. For finite trees and eventual scheduling, the comparator's next read either obtains a leaf or observes completion, so there is no deadlock caused by reading the two inputs in a fixed order.Only a constant amount of leaf data is stored. After an early mismatch, each producer may already have traversed toward its next leaf and be blocked offering it; cancellation prevents unbounded speculation or deliberate construction of the remaining fringe. Occasionally a short unequal fringe is already completely traversed when its final distinguishing value is compared. The streaming guarantee is that neither complete fringe needs to be materialized in advance, and work stops as soon as inequality is established.
Articles by others on the same topic
There are currently no matching articles.