StepForwardNode:
PUBLIC
PROC [node: Ref]
RETURNS [nxt: Ref] = {
returns next node in standard tree walk order; visits branch contents before branch children
isBranch: BOOL ← FALSE; -- indicates whether or not node is a branch node
IF node=NIL THEN RETURN [NIL];
WITH node
SELECT
FROM
br: RefBranchNode =>
{
isBranch ← TRUE;
CheckInternalRep[br];
IF (nxt ← br.contents)=NIL THEN nxt ← br.child };
bx: RefBoxNode => nxt ← bx.contents;
ls: RefListNode => nxt ← ls.contents;
ENDCASE => nxt ← NIL;
IF nxt # NIL THEN RETURN; -- descend in the tree
DO
IF ~node.last
THEN {
-- return the next sibling
IF isBranch THEN CheckInternalRep[TiogaNodeOps.NarrowToBranchNode[node.next]];
RETURN [node.next] };
IF (node ← node.next) = NIL THEN RETURN [NIL]; -- move to the parent
IF ~isBranch
THEN
WITH node
SELECT
FROM
br: RefBranchNode => {
-- have visited contents of this branch; now visit children
The previous node is not a branch, but its parent is.
This implies that previous node was last of branch contents since child of branch must be a branch.
IF br.child # NIL THEN RETURN[BranchChild[br]];
isBranch ← TRUE };
ENDCASE;
ENDLOOP };
Forward:
PUBLIC
PROC [node: RefBranchNode]
RETURNS [nx: RefBranchNode, levelDelta:
INTEGER] = {
returns next branch in standard tree walk order
child: RefBranchNode;
n: Ref;
IF node=NIL THEN RETURN [NIL, 0];
IF (child ← BranchChild[node]) # NIL THEN RETURN [child, 1]; -- descend in the tree
levelDelta ← 0;
n ← node;
DO
-- move to next node, sibling or up* then sibling
IF ~n.last
THEN {
-- return the sibling
br: RefBranchNode = TiogaNodeOps.NarrowToBranchNode[n.next];
CheckInternalRep[br]; RETURN [br, levelDelta] };
IF (n ← n.next) = NIL THEN RETURN [NIL, 0]; -- move to the parent
levelDelta ← levelDelta-1;
ENDLOOP };
StepBackwardNode:
PUBLIC
PROC [node: Ref, parent: Ref ←
NIL]
RETURNS [back, backparent: Ref] = {
child, child2: Ref;
isBranch: BOOL ← FALSE; -- indicates whether or not node is a branch node
IF parent = NIL THEN parent ← Parent[node];
IF parent = NIL OR node=NIL THEN RETURN [NIL, NIL];
WITH parent
SELECT
FROM
br: RefBranchNode => child ← IF TiogaNodeOps.IsBranch[node] THEN br.child ELSE br.contents;
bx: RefBoxNode => child ← bx.contents;
ls: RefListNode => child ← ls.contents;
ENDCASE => child ← NIL;
IF child = node THEN RETURN [parent, Parent[parent]]; -- node is first contents
DO
-- find predecessor of node
IF child.last THEN ERROR; -- incorrect value supplied for parent
IF (child2 ← child.next)=node THEN EXIT;
child ← child2;
ENDLOOP;
DO
-- find last node within predecessor
WITH child
SELECT
FROM
br: RefBranchNode => { CheckInternalRep[br]; IF (child2 ← br.child)=NIL THEN child2 ← br.contents };
bx: RefBoxNode => child2 ← bx.contents;
ls: RefListNode => child2 ← ls.contents;
ENDCASE => child2 ← NIL;
IF child2=NIL THEN RETURN [child, parent];
parent ← child; child ← LastSibling[child2];
ENDLOOP };
Backward:
PUBLIC
PROC [node: RefBranchNode, parent: Ref ←
NIL]
RETURNS [back: RefBranchNode, backparent: Ref, levelDelta: INTEGER] = {
returns preceeding node in standard tree walk order
child, child2: Ref;
parentBranch: RefBranchNode;
IF parent = NIL THEN parent ← Parent[node];
IF parent = NIL OR node = NIL THEN RETURN [NIL,NIL,0];
WITH parent
SELECT
FROM
br: RefBranchNode => { CheckInternalRep[parentBranch ← br]; child ← br.child };
bx: RefBoxNode => child ← bx.contents;
ls: RefListNode => child ← ls.contents;
ENDCASE => child ← NIL;
IF child = node THEN RETURN [parentBranch, Parent[parentBranch], -1]; -- node is first child
DO
-- find the predecessor
IF child.last THEN ERROR; -- incorrect value supplied for parent
IF (child2 ← child.next)=node
THEN {
CheckInternalRep[TiogaNodeOps.NarrowToBranchNode[child]]; EXIT };
child ← child2;
ENDLOOP;
levelDelta ← 0;
DO
-- find last branch within the predecessor
childBranch: RefBranchNode = TiogaNodeOps.NarrowToBranchNode[child];
IF (child2 ← childBranch.child) =
NIL
THEN
RETURN [childBranch, parent, levelDelta];
levelDelta ← levelDelta+1;
parent ← child; child ← LastSibling[child2]; ENDLOOP };