///|
/// Opaque snapshot of a structurally checked dominator tree. Arrays are owned
/// privately: later mutations of the input tree cannot change indexed answers.
struct DominanceIndex {
root_node : Int32
reachable : Array[Bool]
entered : Array[Int32]
left : Array[Int32]
depth : Array[Int32]
ancestors : Array[Array[Int32]]
}
///|
/// Validate a public tree once, then index its parent topology. Frontier
/// validity is structural only, as with dominates; indexing cannot establish
/// that supplied dominance/frontier sets correspond to an original graph.
pub fn index_dominance(tree : Dominance) -> DominanceIndex raise GraphError {
validate_dominance(tree)
let n = tree.reachable.length()
let reachable = tree.reachable.copy()
let parents = Array::makei(n, node => tree.immediate[node].unwrap_or(node))
let children : Array[Array[Int32]] = Array::makei(n, _ => [])
for node in 0..= 0; i = i - 1 {
let child = children[node][i]
depth[child] = depth[node] + 1
stack.push((child, false))
}
}
}
let mut levels = 1
while 1 << levels <= n {
levels += 1
}
let ancestors = [parents]
for level in 1.. previous[previous[node]]))
}
{ root_node: tree.root, reachable, entered, left, depth, ancestors, }
}
///|
fn DominanceIndex::check_node(
self : Self,
node : Int32,
) -> Unit raise GraphError {
if node < 0 || node >= self.reachable.length() {
raise Invalid("dominance query index is outside the tree")
}
}
///|
/// Root index, including the synthetic exit for a postdominator snapshot.
pub fn DominanceIndex::root(self : Self) -> Int32 {
self.root_node
}
///|
/// Number of slots, including unreachable vertices and any synthetic exit.
pub fn DominanceIndex::node_count(self : Self) -> Int32 {
self.reachable.length()
}
///|
/// Reachability from this tree's root. For postdominance this means a declared
/// exit is reachable within the documented finite-exit-path scope.
pub fn DominanceIndex::is_reachable(
self : Self,
node : Int32,
) -> Bool raise GraphError {
self.check_node(node)
self.reachable[node]
}
///|
/// Returns None for the root and for unreachable nodes.
pub fn DominanceIndex::immediate_parent(
self : Self,
node : Int32,
) -> Int32? raise GraphError {
self.check_node(node)
if !self.reachable[node] || node == self.root_node {
None
} else {
Some(self.ancestors[0][node])
}
}
///|
/// Constant-time interval containment after construction. Unreachable operands
/// yield false, including reflexive queries. Both indices are checked first.
pub fn DominanceIndex::dominates(
self : Self,
ancestor : Int32,
node : Int32,
) -> Bool raise GraphError {
self.check_node(ancestor)
self.check_node(node)
self.reachable[ancestor] &&
self.reachable[node] &&
self.entered[ancestor] <= self.entered[node] &&
self.entered[node] < self.left[ancestor]
}
///|
// Both nodes are known reachable and in the index's single rooted tree.
fn DominanceIndex::common_pair(
self : Self,
first : Int32,
second : Int32,
) -> Int32 {
let mut a = first
let mut b = second
if self.depth[a] < self.depth[b] {
let swap = a
a = b
b = swap
}
let difference = self.depth[a] - self.depth[b]
for level in 0..= 0; level = level - 1 {
if self.ancestors[level][a] != self.ancestors[level][b] {
a = self.ancestors[level][a]
b = self.ancestors[level][b]
}
}
self.ancestors[0][a]
}
///|
/// Nearest shared dominator of all supplied nodes, O(k log n) after indexing.
/// Empty input or any unreachable operand gives None. Every index is validated,
/// even after an unreachable operand. Postdominance can return its virtual root.
pub fn DominanceIndex::nearest_common(
self : Self,
nodes : Array[Int32],
) -> Int32? raise GraphError {
let mut all_reachable = true
for node in nodes {
self.check_node(node)
if !self.reachable[node] {
all_reachable = false
}
}
if nodes.is_empty() || !all_reachable {
return None
}
let mut common = nodes[0]
for i in 1..