TextNodeImpl.mesa
Copyright © 1985, 1986 by Xerox Corporation. All rights reserved.
written by Bill Paxton, March 1981
last edit by Bill Paxton, August 11, 1982 9:51 am
Michael Plass, March 27, 1985 3:50:32 pm PST
Rick Beach, March 27, 1985 10:13:12 am PST
Doug Wyatt, September 22, 1986 3:15:58 pm PDT
DIRECTORY
Rope USING [ROPE, Size],
Tioga USING [Location, maxLen, Node, NodeBody, nodeItself, Props, Runs];
TextNodeImpl: CEDAR PROGRAM
IMPORTS Rope
EXPORTS Tioga
= BEGIN OPEN Tioga;
ROPE: TYPE ~ Rope.ROPE;
NewNode: PUBLIC PROC RETURNS [n: Node] = {
n ← NEW[NodeBody]; n.last ← TRUE;
};
InlineParent: PROC [n: Node] RETURNS [Node] = INLINE {
DO
IF n=NIL OR n.deleted THEN RETURN [NIL];
IF n.last THEN RETURN [n.next];
n ← n.next;
ENDLOOP;
};
Parent: PUBLIC PROC [n: Node] RETURNS [Node] = { RETURN [InlineParent[n]] };
Root: PUBLIC PROC [n: Node] RETURNS [Node] = {
applies Parent repeatedly until reaches root
x: Node ← n;
DO
p: Node ~ InlineParent[x];
IF p=NIL THEN RETURN [IF x=NIL OR x.deleted THEN NIL ELSE x];
x ← p;
ENDLOOP;
};
Next: PUBLIC PROC [n: Node] RETURNS [Node] = {
RETURN[IF n=NIL OR n.last OR n.deleted THEN NIL ELSE n.next];
};
Previous: PUBLIC PROC [n: Node, parent: Node ← NIL] RETURNS [nx: Node] = {
nx2: Node;
IF parent=NIL THEN parent ← InlineParent[n];
IF n=NIL OR parent=NIL OR (nx ← parent.child)=n THEN RETURN [NIL];
DO IF (nx2←nx.next)=n THEN RETURN; nx ← nx2; ENDLOOP;
};
InlineForward: PROC [node: Node] RETURNS [nx: Node, levelDelta: INT] = INLINE {
returns next node in standard tree walk order
child: Node;
IF node=NIL THEN RETURN [NIL, 0];
IF (child ← node.child) # NIL THEN RETURN [child, 1]; -- descend in the tree
levelDelta ← 0;
DO -- move to next node, sibling or up* then sibling
IF NOT node.last THEN RETURN [node.next, levelDelta]; -- the sibling
IF (node ← node.next) = NIL THEN RETURN [NIL, levelDelta]; -- the parent
levelDelta ← levelDelta-1;
ENDLOOP;
};
Forward: PUBLIC PROC [node: Node] RETURNS [nx: Node, levelDelta: INT] = {
[nx, levelDelta] ← InlineForward[node];
};
Backward: PUBLIC PROC [node: Node, parent: Node ← NIL]
RETURNS [back, backparent: Node, levelDelta: INT] = {
returns preceding node in standard tree walk order
child, child2: Node;
IF parent = NIL THEN parent ← InlineParent[node];
IF parent = NIL OR node = NIL THEN RETURN [NIL, NIL, 0];
IF (child ← parent.child) = node THEN RETURN [parent, Parent[parent], -1];
DO
IF child.last THEN ERROR; -- incorrect value supplied for parent
IF (child2 ← child.next)=node THEN EXIT;
child ← child2;
ENDLOOP;
levelDelta ← 0;
DO
IF (child2 ← LastChild[child]) = NIL THEN RETURN [child, parent, levelDelta];
levelDelta ← levelDelta+1;
parent ← child; child ← child2;
ENDLOOP;
};
StepForward: PUBLIC PROC [node: Node] RETURNS [Node] = {
returns next node in standard tree walk order
RETURN[Forward[node].nx];
};
StepBackward: PUBLIC PROC [node: Node, parent: Node ← NIL] RETURNS [Node] = {
returns preceding node in standard tree walk order
RETURN[Backward[node, parent].back];
};
Level: PUBLIC PROC [n: Node] RETURNS [level: INT ← 0] = {
Level[Root[x]] == 0; Level[FirstChild[n]]=Level[n]+1
UNTIL (n ← InlineParent[n])=NIL DO level ← level+1 ENDLOOP;
};
ForwardClipped: PUBLIC PROC [node: Node, maxLevel: INT, nodeLevel: INT ← 0] RETURNS [nx: Node, nxLevel: INT] = {
like Forward, but limits how deep will go in tree
if pass nodeLevel=0, correct value will be computed
nxLevel = Level[nx] <= MAX[maxLevel, Level[node]]
child: Node;
IF node=NIL THEN RETURN [NIL, 0];
IF nodeLevel <= 0 THEN nodeLevel ← Level[node];
IF nodeLevel < maxLevel AND (child ← node.child) # NIL THEN
RETURN [child, nodeLevel+1]; -- return the child
DO -- move to next node, sibling or up* then sibling
IF NOT node.last THEN RETURN [node.next, nodeLevel]; -- return the sibling
IF (node ← node.next) = NIL THEN RETURN [NIL, 0]; -- go to the parent
nodeLevel ← nodeLevel-1;
ENDLOOP;
};
BackwardClipped: PUBLIC PROC [
node: Node, maxLevel: INT, parent: Node ← NIL, nodeLevel: INT ← 0]
RETURNS [back, backparent: Node, backLevel: INT] = {
like Backward, but limits how deep will go in tree
backLevel = Level[back] <= MAX[maxLevel, Level[node]]
child, child2: Node;
IF parent = NIL THEN parent ← InlineParent[node];
IF parent = NIL OR node = NIL THEN RETURN [NIL, NIL, 0];
IF nodeLevel <= 0 THEN nodeLevel ← Level[node];
IF (child ← parent.child) = node THEN RETURN [parent, InlineParent[parent], nodeLevel-1];
DO -- search for sibling just before node
IF child.last THEN ERROR; -- incorrect value supplied for parent
IF (child2 ← child.next)=node THEN EXIT;
child ← child2;
ENDLOOP;
DO -- go deeper in tree until reach maxLevel
IF nodeLevel >= maxLevel OR (child2 ← LastChild[child]) = NIL THEN
RETURN [child, parent, nodeLevel];
nodeLevel ← nodeLevel+1;
parent ← child;
child ← child2;
ENDLOOP;
};
LocRelative: PUBLIC PROC [location: Location, count: INT ← 0,
break: INT ← 1, skipCommentNodes: BOOL ← FALSE] RETURNS [Location] = {
n: Node ← location.node;
size, lastSize, where: INT ← 0;
init: Node ← n;
lastTxt: Node;
IF count=0 AND InlineParent[n]=NIL THEN
RETURN [[FirstChild[n], 0]]; -- avoid returning root node
where ← MAX[location.where, 0]; -- where we are in the current node
WHILE n # NIL DO
IF n # NIL AND (NOT skipCommentNodes OR NOT n.comment) THEN {
lastSize ← size ← Rope.Size[n.rope];
IF (count ← count-(size-where)) <= 0 THEN RETURN [[n, MAX[0, count+size]]];
lastTxt ← n;
count ← count-break;
};
[n, ] ← InlineForward[n];
where ← 0;
ENDLOOP;
IF lastTxt # NIL THEN RETURN [[lastTxt, lastSize]]; -- end of last text node
RETURN [[init, 0]];
};
LocWithin: PUBLIC PROC [n: Node, count: INT, break: INT ← 1, skipCommentNodes: BOOL ← FALSE] RETURNS [Location] = {
RETURN[LocRelative[[n, 0], count, break, skipCommentNodes]];
};
BadArgs: PUBLIC ERROR = CODE;
LocOffset: PUBLIC PROC [loc1, loc2: Location, break: INT ← 1, skipCommentNodes: BOOL ← FALSE] RETURNS [count: INT ← 0] = {
returns character offset of location2 relative to location1
node: Node ← loc2.node;
n: Node ← loc1.node;
count ← IF loc2.where # nodeItself THEN loc2.where ELSE 0;
count ← count - MAX[loc1.where, 0];
DO -- add in counts for text nodes before location
SELECT n FROM
node => RETURN;
NIL => ERROR BadArgs;
ENDCASE;
IF n # NIL AND (NOT skipCommentNodes OR NOT n.comment) THEN
count ← count+Rope.Size[n.rope]+break;
[n, ] ← InlineForward[n];
ENDLOOP;
};
LocNumber: PUBLIC PROC [at: Location, break: INT ← 1, skipCommentNodes: BOOL ← FALSE] RETURNS [count: INT] = {
returns character offset of location relative to root
RETURN[LocOffset[[Root[at.node], 0], at, break, skipCommentNodes]];
};
FirstSibling: PUBLIC PROC [n: Node] RETURNS [Node] = {
RETURN[FirstChild[Parent[n]]];
};
LastSibling: PUBLIC PROC [n: Node] RETURNS [Node] = {
IF n=NIL THEN RETURN [NIL];
UNTIL n.last DO n ← n.next ENDLOOP;
RETURN[n];
};
FirstChild: PUBLIC PROC [n: Node] RETURNS [Node] = {
RETURN[IF n=NIL THEN NIL ELSE n.child];
};
LastChild: PUBLIC PROC [n: Node] RETURNS [Node] = {
RETURN[LastSibling[FirstChild[n]]];
};
LastWithin: PUBLIC PROC [n: Node] RETURNS [Node] = {
nxt: Node;
IF n=NIL THEN RETURN [NIL];
IF (nxt ← n.child)=NIL THEN RETURN [n];
n ← nxt;
DO -- keep going to child of last sibling
IF n.last THEN {
IF (nxt ← n.child)=NIL THEN RETURN [n];
n ← nxt;
}
ELSE n ← n.next;
ENDLOOP;
};
LastLocWithin: PUBLIC PROC [n: Node] RETURNS [Location] = {
last: Node ← LastWithin[n];
where: INT ← IF last # NIL THEN Rope.Size[last.rope] ELSE nodeItself;
RETURN [[last, where]];
};
NthChild: PUBLIC PROC [n: Node, index: INT ← 0] RETURNS [child: Node] = {
note: NthChild[n, 0]==FirstChild[n]; NthChild[n, k+1]==Next[NthChild[n, k]]
IF n=NIL OR (child ← n.child)=NIL THEN RETURN;
THROUGH [0..index) DO
IF child.last THEN RETURN [NIL]
ELSE child ← child.next;
ENDLOOP;
};
NthSibling: PUBLIC PROC [n: Node, index: INT ← 0] RETURNS [Node] = {
note: NthSibling[n, 0]==n; NthSibling[n, k+1]==Next[NthSibling[n, k]]
IF n=NIL THEN RETURN [NIL];
THROUGH [0..index) DO
IF n.last THEN RETURN [NIL]
ELSE n ← n.next;
ENDLOOP;
RETURN [n];
};
CountChildren: PUBLIC PROC [n: Node] RETURNS [count: INT ← 0] = {
child: Node;
IF (child ← FirstChild[n])=NIL THEN RETURN;
DO count ← count+1;
IF child.last THEN RETURN;
child ← child.next;
ENDLOOP;
};
CountFollowing: PUBLIC PROC [n: Node] RETURNS [count: INT ← 0] = {
IF n=NIL THEN RETURN;
UNTIL n.last DO
n ← n.next;
count ← count+1;
ENDLOOP;
};
CountToParent: PUBLIC PROC [n: Node] RETURNS [count: INT ← 0, parent: Node] = {
IF n=NIL THEN RETURN;
UNTIL n.last DO
n ← n.next;
count ← count+1;
ENDLOOP;
parent ← n.next;
};
CountToChild: PUBLIC PROC [parent, child: Node] RETURNS [count: INT ← 0] = {
note: CountToChild[parent, FirstChild[parent]]==0
n: Node;
IF parent=NIL OR child=NIL THEN RETURN;
n ← parent.child;
DO
SELECT n FROM
child => RETURN [count];
NIL => RETURN [maxLen];
ENDCASE;
n ← Next[n];
count ← count+1;
ENDLOOP;
};
IsLastSibling: PUBLIC PROC [n: Node] RETURNS [BOOL] = {
RETURN[IF n=NIL THEN FALSE ELSE n.last];
};
END.