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.