
<<TiogaTreeOpsImpl.mesa; Written by S. McGregor, February 1983>>
<<Edited by Paxton, July 26, 1983 11:07 am>>
<<Edited by McGregor, May 12, 1983 5:00 pm>>

DIRECTORY
TiogaNode,
TiogaNodeOps,
CreateNode,
TiogaTreeOps;

TiogaTreeOpsImpl: CEDAR PROGRAM
IMPORTS CreateNode, TiogaNodeOps
EXPORTS TiogaTreeOps
SHARES TiogaNode =

BEGIN OPEN TiogaTreeOps;

RefBoxNode: TYPE = TiogaNode.RefBoxNode;
RefListNode: TYPE = TiogaNode.RefListNode;
<<>>
<<Tree traversal>>
<<>>
Parent: PUBLIC PROC [n: Ref] RETURNS [Ref] = {
IF n=NIL OR n.deleted THEN RETURN [NIL];
UNTIL n.last DO n _ n.next; ENDLOOP;
IF n.next # NIL THEN RETURN [n.next];
RETURN [NIL] };

Root: PUBLIC PROC [n: Ref] RETURNS [RefBranchNode] = { 
p: Ref;
DO IF (p_Parent[n])=NIL THEN RETURN[TiogaNodeOps.NarrowToBranchNode[n]]; n _ p; ENDLOOP };

Next: PUBLIC PROC [n: Ref] RETURNS [Ref] = {
IF n.last THEN RETURN [NIL];
WITH n _ n.next SELECT FROM
br: RefBranchNode => CheckInternalRep[br];
ENDCASE;
RETURN [n] };

Contents: PUBLIC PROC [n: Ref] RETURNS [Ref] = {
IF n=NIL THEN RETURN [NIL];
WITH n SELECT FROM
br: RefBranchNode => { CheckInternalRep[br]; n _ br.contents };
bx: RefBoxNode => n _ bx.contents;
ls: RefListNode => n _ ls.contents;
ENDCASE => RETURN [NIL];
RETURN [n] };

BranchChild: PUBLIC PROC [n: RefBranchNode] RETURNS [RefBranchNode] = {
IF n=NIL THEN RETURN [NIL];
CheckInternalRep[n];
IF (n _ n.child)=NIL THEN RETURN [NIL];
CheckInternalRep[n];
RETURN [n] };

FirstSibling: PUBLIC PROC [n: Ref, parent: Ref _ NIL] RETURNS [sib: Ref] = {
<<Returns n if n is the first sibling>>
IF n=NIL THEN RETURN [NIL];
IF parent=NIL THEN parent _ Parent[n];
IF parent=NIL THEN RETURN [NIL];
WITH parent SELECT FROM
br: RefBranchNode =>
IF TiogaNodeOps.IsBranch[n] THEN
CheckInternalRep[TiogaNodeOps.NarrowToBranchNode[sib _ br.child]]
ELSE sib _ br.contents;
bx: RefBoxNode => sib _ bx.contents;
ls: RefListNode => sib _ ls.contents;
ENDCASE => ERROR -- parent must be a branch, a box, or a list -- };

LastSibling: PUBLIC PROC [n: Ref] RETURNS [sib: Ref] = {
<<Returns n if n is the last sibling>>
DO IF n.last THEN EXIT; n _ n.next; ENDLOOP;
WITH n SELECT FROM
br: RefBranchNode => CheckInternalRep[br];
ENDCASE };

Previous: PUBLIC PROC [n: Ref, parent: Ref _ NIL] RETURNS [sib: Ref] = {
<<Returns NIL if n=FirstSibling[n]>>
nxt: Ref;
IF (sib _ FirstSibling[n, parent])=n THEN RETURN [NIL];
DO IF sib.last THEN ERROR; IF (nxt _ sib.next)=n THEN EXIT; sib _ nxt; ENDLOOP;
WITH sib SELECT FROM
br: RefBranchNode => CheckInternalRep[br];
ENDCASE };

LastWithin: PUBLIC PROC [n: Ref] RETURNS [Ref] = {
nxt: Ref;
DO
IF n=NIL THEN RETURN [NIL];
IF (nxt _ BranchChild[TiogaNodeOps.NarrowToBranchNode[n]])=NIL THEN nxt _ Contents[n];
IF nxt=NIL THEN RETURN [n];
n _ LastSibling[nxt];
ENDLOOP };

ContainingStatement: PUBLIC PROC [n: Ref] RETURNS [s: RefBranchNode] = {
UNTIL (s _ TiogaNodeOps.NarrowToBranchNode[n]) # NIL DO n _ Parent[n]; ENDLOOP };

<<Forward and Backward in Tree>>

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 };

<<Miscellaneous>>
<<>>
LastBranchWithin: PUBLIC PROC [n: RefBranchNode] RETURNS [RefBranchNode] = {
nxt: RefBranchNode;
IF n=NIL THEN RETURN [NIL];
DO
IF (nxt _ BranchChild[n])=NIL THEN RETURN [n];
n _ TiogaNodeOps.NarrowToBranchNode[LastSibling[nxt]];
ENDLOOP };

Level: PUBLIC PROC [n: Ref] RETURNS [level: INTEGER] = {
level _ 0;  UNTIL (n _ Parent[n])=NIL DO level _ level+1; ENDLOOP };

MakeTreeLoc: PUBLIC PROC [n: Ref] RETURNS [TreeLoc] = {
RETURN [[n, TiogaNode.NodeItself]] };

MakeTreeSpan: PUBLIC PROC [first, last: Ref] RETURNS [TreeSpan] = {
RETURN [[MakeTreeLoc[first], MakeTreeLoc[last]]] };

MakeBranchLoc: PUBLIC PROC [n: RefBranchNode] RETURNS [BranchLoc] = {
RETURN [[n, TiogaNode.NodeItself]] };

MakeBranchSpan: PUBLIC PROC [first, last: RefBranchNode] RETURNS [BranchSpan] = {
RETURN [[MakeBranchLoc[first], MakeBranchLoc[last]]] };

BackLoc: PUBLIC PROC [loc: TreeLoc] RETURNS [new: TreeLoc] = {
text: TiogaNode.RefTextNode;
new.node _ StepBackwardNode[loc.node].back;
new.where _ IF loc.where=TiogaNode.NodeItself OR (text _ TiogaNodeOps.NarrowToTextNode[new.node])=NIL
THEN TiogaNode.NodeItself ELSE TiogaNodeOps.Size[text] };

ForwardLoc: PUBLIC PROC [loc: TreeLoc] RETURNS [new: TreeLoc] = {
new.node _ StepForwardNode[loc.node];
new.where _ IF loc.where=TiogaNode.NodeItself OR TiogaNodeOps.NarrowToTextNode[new.node]=NIL
THEN TiogaNode.NodeItself ELSE 0 };

CheckInternalRep: PROC [br: TiogaNode.RefBranchNode] = INLINE {
IF ~br.internalRepCreated THEN CreateNode.CreateInternalRep[br] };

END.