fn nextOnDirection(node: *Node, direction: u1) ?*Nodenode: *Nodedirection: u169
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87 fn nextOnDirection(node: *Node, direction: u1) ?*Node {
if (node.children[direction]) |child| {
return extremeInSubtreeOnDirection(child, direction ^ 1);
}
var cur = node;
// Traversing upward until we find `parent` to `cur` is NOT on
// `direction`, or equivalently, `cur` to `parent` IS on
// `direction` thus `parent` is the next.
while (true) {
if (cur.parent) |parent| {
// If `parent -> node` is NOT on `direction`, then
// `node -> parent` IS on `direction`
if (parent.children[direction] != cur) return parent;
cur = parent;
} else {
return null;
}
}
}