Tree traversal procedures
Note: If you use these routines to access the tree, you don't need to worry about converting branches to internal representation. It will be done automatically.
Parent:
PROC [p: Path]
RETURNS [Path];
-- returns NIL if p is root node
Root:
PROC [p: Path]
RETURNS [Path];
The root is found by taking Parent until get a node with parent=NIL.
Next:
PROC [p: Path]
RETURNS [nxt: Path] ;
This returns the next sibling, or NIL if p is the last sibling.
FirstSibling:
PROC [p: Path, parent: Path ← nullPath]
RETURNS [sib: Path] ;
Returns p if p is the first sibling
LastSibling:
PROC [p: Path]
RETURNS [sib: Path] ;
Returns p if p is the last sibling
Previous:
PROC [p: Path, parent: Path ← nullPath]
RETURNS [sib: Path] ;
Returns NIL if p=FirstSibling[p]
Runs faster if you can supply the parent. But ok to default it too.
LastWithin:
PROC [p: Path]
RETURNS [Path];
returns the last node within p. goes down into contents of the last branch.
Moving forward
StepForward:
PROC [p: Path]
RETURNS [nx: Path] =
INLINE { [nx,] ← Forward[p] };
returns next branch p in standard tree walk order
Forward:
PROC [p: Path]
RETURNS [nx: Path, levelDelta:
INTEGER];
returns next branch in standard tree walk order
levelDelta is level(p)-level(nx), where level is depth in tree
levelDelta = 0 if nx and p are siblings
levelDelta = 1 if nx is child of p
levelDelta < 0 if do Parent* and Next to reach nx from p
ForwardClipped:
PROC [p: Path, maxLevel:
INTEGER, nodeLevel:
INTEGER ← 0]
RETURNS [nx: Path, nxLevel: INTEGER];
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[p]]
StepForwardNode:
PROC [p: Path]
RETURNS [nx: Path];
Like StepForward, but visits contents of branches as well as children.
Moving backward
StepBackward:
PROC [p: Path, parent: Path ← nullPath]
RETURNS [back: Path] =
INLINE {
returns preceeding branch p in standard tree walk order
runs faster if can supply parent; parent can be branch, box, or list p.
[back,,] ← Backward[p,parent] };
Backward:
PROC [p: Path, parent: Path ← nullPath]
RETURNS [back: Path, backparent: Path, levelDelta: INTEGER];
for backing through tree
levelDelta same as for Forward
BackwardClipped:
PROC [
p: Path, maxLevel: INTEGER, parent: Path ← nullPath, nodeLevel: INTEGER ← 0]
RETURNS [back: Path, backparent: Path, backLevel: INTEGER];
like Backward, but limits how deep will go in tree
backLevel = Level[back] <= MAX[maxLevel,Level[p]]
StepBackwardNode:
PROC [p: Path, parent: Path ← nullPath]
RETURNS [back, backparent: Path];
Like StepBackward, but visits contents of branches as well as children.
Location procedures
LastLocWithin:
PROC [p: Path]
RETURNS [Location];
returns the last location within the branch
LocRelative:
PROC [
location: Location, count: Offset, break: NAT ← 1, skipCommentNodes: BOOL ← FALSE]
RETURNS [Location];
count is interpreted as a character offset from given location
returns <node,offset> location corresponding to count
adds in break at the end of each text subnode
if skipCommentNodes is true, then ignores them in walking the tree
LocWithin:
PROC [
p: Path, count: Offset, break: NAT ← 1, skipCommentNodes: BOOL ← FALSE]
RETURNS [Location] =
INLINE {
RETURN [LocRelative[[p,0],count,break,skipCommentNodes]] };
LocOffset:
PROC [loc1, loc2: Location,
break: NAT ← 1, skipCommentNodes: BOOL ← FALSE] RETURNS [count: Offset];
returns character offset of location2 relative to location1
loc1 and loc2 can be in same node
but loc2 must not be in node before loc1 or get ERROR BadArgs
if skipCommentNodes is true, then ignores them in walking the tree
LocNumber:
PROC [at: Location, break:
NAT ← 1, skipCommentNodes:
BOOL ←
FALSE]
RETURNS [count: Offset];
returns character offset of location relative to root
BackLoc:
PROC [loc: Location]
RETURNS [new: Location];
ForwardLoc: PROC [loc: Location] RETURNS [new: Location];
Miscellaneous
Equal:
PROC [p1, p2: Path]
RETURNS [
BOOL] ;
Contents:
PROC [p: Path]
RETURNS [Path] ;
Branches, boxes, and lists have contents.
BranchChild:
PROC [p: Path]
RETURNS [Path] ;
Returns nullPath if p doesn't point to a branch
Level:
PROC [p: Path]
RETURNS [level:
INTEGER];
-- Level[Root[x]] is 0
Apply:
PROC [span: TiogaNode.Span, proc: ApplyProc];
Apply the proc to each node in the span until complete span or proc returns TRUE.
ApplyProc: TYPE = PROC [p: Path, start, len: Offset] RETURNS [stop: BOOL];