DIRECTORY Rope USING [ROPE, Size], Tioga USING [Location, maxLen, Node, NodeBody, nodeItself]; TextNodeImpl: CEDAR PROGRAM IMPORTS Rope EXPORTS Tioga = BEGIN OPEN Tioga; ROPE: TYPE ~ Rope.ROPE; 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] = { 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; }; IsLastSibling: PUBLIC PROC [n: Node] RETURNS [BOOL] = { RETURN[IF n=NIL THEN FALSE ELSE n.last]; }; 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]]]; }; 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]; }; 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; }; Level: PUBLIC PROC [n: Node] RETURNS [level: INT _ 0] = { UNTIL (n _ InlineParent[n])=NIL DO level _ level+1 ENDLOOP; }; NthChild: PUBLIC PROC [n: Node, index: INT _ 0] RETURNS [child: Node] = { 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] = { 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] = { 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; }; InlineForward: PROC [node: Node] RETURNS [nx: Node, levelDelta: INT] = INLINE { 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] = { 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] = { RETURN[Forward[node].nx]; }; StepBackward: PUBLIC PROC [node: Node, parent: Node _ NIL] RETURNS [Node] = { RETURN[Backward[node, parent].back]; }; ForwardClipped: PUBLIC PROC [node: Node, maxLevel: INT, nodeLevel: INT _ 0] RETURNS [nx: Node, nxLevel: INT] = { 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] = { 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; }; BadArgs: PUBLIC ERROR = CODE; 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]]; }; LocOffset: PUBLIC PROC [loc1, loc2: Location, break: INT _ 1, skipCommentNodes: BOOL _ FALSE] RETURNS [count: INT _ 0] = { 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] = { RETURN[LocOffset[[Root[at.node], 0], at, break, skipCommentNodes]]; }; 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]]; }; NewNode: PUBLIC PROC RETURNS [n: Node] = { n _ NEW[NodeBody]; n.last _ TRUE; }; END. ”TextNodeImpl.mesa Copyright c 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 23, 1986 11:19:52 am PDT applies Parent repeatedly until reaches root Level[Root[x]] == 0; Level[FirstChild[n]]=Level[n]+1 note: NthChild[n, 0]==FirstChild[n]; NthChild[n, k+1]==Next[NthChild[n, k]] note: NthSibling[n, 0]==n; NthSibling[n, k+1]==Next[NthSibling[n, k]] note: CountToChild[parent, FirstChild[parent]]==0 returns next node in standard tree walk order returns preceding node in standard tree walk order returns next node in standard tree walk order returns preceding node in standard tree walk order 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]] like Backward, but limits how deep will go in tree backLevel = Level[back] <= MAX[maxLevel, Level[node]] returns character offset of location2 relative to location1 returns character offset of location relative to root Κ “˜codešœ™Kšœ Οmœ7™BKšœ"™"Kšœ1™1Kšœ,™,K™*Kšœ.™.—K™šΟk ˜ Kšœžœžœ ˜Kšœžœ0˜;—K˜KšΠbl œžœž˜Kšžœ˜ Kšžœ˜ Kšœžœžœ˜K˜Kšžœžœžœ˜K˜šΟn œžœ žœ žœ˜7šž˜Kš žœžœžœ žœžœžœ˜(Kšžœžœžœ ˜K˜ Kšžœ˜—K˜K˜—š  œžœžœ žœ žœ˜LK˜—š œžœžœ žœ ˜/Kšœ,™,K˜ šž˜Kšœ˜Kšžœžœžœžœžœžœžœ žœžœžœ˜=K˜Kšžœ˜—K˜K˜—š œžœžœ žœ ˜.Kšžœžœžœžœžœ žœžœžœ ˜=K˜K˜—š  œžœžœžœžœ˜JK˜ Kšžœžœžœ˜,Kšžœžœžœžœžœžœžœžœ˜BKš žœžœžœžœ žœ˜5K˜K˜—š   œžœžœ žœžœ˜7Kš žœžœžœžœžœžœ ˜(K˜K˜—š  œžœžœ žœ ˜4Kš žœžœžœžœžœžœ ˜'K˜K˜—š  œžœžœ žœ ˜3Kšžœ˜#K˜K˜—š  œžœžœ žœ ˜6Kšžœ˜K˜K˜—š  œžœžœ žœ ˜5Kš žœžœžœžœžœ˜Kšžœžœ žœ˜#Kšžœ˜ K˜K˜—š  œžœžœ žœ ˜4K˜ Kš žœžœžœžœžœ˜Kšžœžœžœžœ˜'K˜šžœΟc&˜)šžœžœ˜Kšžœžœžœžœ˜'K˜K˜—Kšžœ ˜Kšžœ˜—K˜K˜—š  œžœžœ žœ žœ ˜9Kšœ4™4Kšžœžœžœžœ˜;K˜K˜—K˜š  œžœžœžœžœ˜IKšœK™KKš žœžœžœžœžœžœ˜.šžœ ž˜Kšžœ žœžœžœ˜Kšžœ˜Kšžœ˜—K˜K˜—š   œžœžœžœžœ ˜DKšœE™EKš žœžœžœžœžœ˜šžœ ž˜Kšžœžœžœžœ˜Kšžœ ˜Kšžœ˜—Kšžœ˜ K˜K˜—š   œžœžœ žœ žœ ˜AK˜ Kšžœžœžœžœ˜+šžœ˜Kšžœ žœžœ˜K˜Kšžœ˜—K˜K˜—š  œžœžœ žœ žœ ˜BKšžœžœžœžœ˜šžœž˜K˜ K˜Kšžœ˜—K˜K˜—š   œžœžœ žœ žœ˜OKšžœžœžœžœ˜šžœž˜K˜ K˜Kšžœ˜—K˜K˜K˜—š   œžœžœžœ žœ ˜LKšœ1™1K˜Kš žœžœžœžœžœžœ˜'K˜šž˜šžœž˜ Kšœ žœ ˜Kšžœžœ ˜Kšžœ˜—K˜ K˜Kšžœ˜—K˜K˜—K˜š   œžœžœžœžœ˜OKšœ-™-K˜ Kš žœžœžœžœžœ˜!Kš žœžœžœžœ ‘˜LK˜šžœ‘œ‘˜4Kš žœžœ žœžœ‘˜DKš žœžœžœžœžœ‘ ˜HK˜Kšžœ˜—K˜K˜—š  œžœžœžœžœ˜IK˜'K˜K˜—š œžœžœžœ˜6Kšžœ&žœ˜5Kšœ2™2K˜Kšžœ žœžœ˜1Kšžœ žœžœžœžœžœžœžœ˜8Kšžœžœžœ˜Jšž˜Kšžœ žœžœ‘&˜@Kšžœžœžœ˜(K˜Kšžœ˜—K˜šž˜Kšžœžœžœžœ˜MK˜Kšœ˜Kšžœ˜—K˜K˜—š  œžœžœžœ ˜8Kšœ-™-Kšžœ˜Kšœ˜K˜—š   œžœžœžœžœ ˜MKšœ2™2Kšžœ˜$Kšœ˜K˜—š œžœžœžœ žœžœžœ˜pKšœ1™1Kšœ4™4Kšœ1™1K˜ Kš žœžœžœžœžœ˜!Kšžœžœ˜/šžœžœžœž˜;Kšžœ‘˜0—šžœ‘œ‘˜4Kš žœžœ žœžœ‘˜JKš žœžœžœžœžœ‘˜EK˜Kšžœ˜—K˜K˜—š œžœžœ˜Kšœžœžœ žœ˜BKšžœ%žœ˜4Kšœ2™2Kšœ5™5K˜Kšžœ žœžœ˜1Kšžœ žœžœžœžœžœžœžœ˜8Kšžœžœ˜/Kšžœžœžœ-˜Yšžœ‘&˜)Kšžœ žœžœ‘&˜@Kšžœžœžœ˜(K˜Kšžœ˜—šžœ‘)˜,Kšžœžœžœž˜BKšžœ˜"K˜K˜K˜Kšžœ˜—K˜K˜—K˜šœ žœžœžœ˜K˜—š  œžœžœžœ˜>Kš œžœžœžœžœ˜FK˜Kšœžœ˜K˜K˜Kšžœ žœžœž˜'Kšžœ‘˜9Kšœžœ‘#˜Cšžœžœž˜šžœžœžœžœžœžœ žœ˜=Kšœ$˜$Kšžœ#žœžœžœ˜KK˜ K˜K˜—K˜K˜ Kšžœ˜—Kš žœ žœžœžœ‘˜LKšžœ ˜K˜K˜—š  œžœžœžœ žœžœžœžœ˜sKšžœ6˜