DIRECTORY TiogaPathOrder, TiogaNode, TiogaNodeOps, TiogaPathOps; TiogaPathOrderImpl: CEDAR MONITOR IMPORTS TiogaPathOps EXPORTS TiogaPathOrder SHARES TiogaNode = BEGIN OPEN TiogaPathOrder; freeFullPath: FullPath; -- free list numFreeFullPaths: NAT _ 0; maxFreeFullPaths: NAT = 15; minFullPathSize: NAT = 10; GetFullPath: ENTRY PROC [len: NAT] RETURNS [fp: FullPath] = { ENABLE UNWIND => NULL; IF freeFullPath # NIL THEN { -- look on free list prev: FullPath; IF freeFullPath.maxLength >= len THEN { -- take the first from list fp _ freeFullPath; freeFullPath _ freeFullPath.next; fp.next _ NIL; numFreeFullPaths _ numFreeFullPaths-1; RETURN }; prev _ freeFullPath; FOR fp: FullPath _ freeFullPath.next, fp.next UNTIL fp=NIL DO IF fp.maxLength >= len THEN { -- take this one prev.next _ fp.next; fp.next _ NIL; numFreeFullPaths _ numFreeFullPaths-1; RETURN [fp] }; prev _ fp; ENDLOOP }; RETURN [NEW[FullPathArray[MAX[len,minFullPathSize]]]] }; FreeFullPath: PUBLIC ENTRY PROC [fp: FullPath] = { ENABLE UNWIND => NULL; IF fp=NIL OR numFreeFullPaths >= maxFreeFullPaths OR fp.maxLength < minFullPathSize THEN RETURN; FOR i:NAT IN [0..fp.length) DO fp[i] _ NIL; ENDLOOP; fp.next _ freeFullPath; freeFullPath _ fp; numFreeFullPaths _ numFreeFullPaths+1 }; CompareFullPaths: PUBLIC PROC [fp1, fp2: FullPath] RETURNS [order: Order] = { fp1Len, fp2Len: NAT; IF fp1=NIL OR fp2=NIL OR (fp1Len_fp1.length)=0 OR (fp2Len_fp2.length)=0 OR fp1[0] # fp2[0] THEN RETURN [disjoint]; FOR i:NAT _ 1, i+1 DO -- know that fp1[j]=fp2[j] for j { IF i=fp2Len THEN RETURN [same]; -- fp1Last=fp2Last RETURN [before] }; -- fp1Last is a parent of fp2Last fp2Len => RETURN [after]; -- fp2Last is a parent of fp1Last ENDCASE; IF fp1[i] # fp2[i] THEN { -- they are siblings, so can check order by scanning siblings fp2Node: Ref _ fp2[i]; FOR n: Ref _ fp1[i], n.next DO -- search from fp1 to fp2 IF fp2Node=n THEN RETURN [before]; IF n.last THEN RETURN [after]; ENDLOOP }; ENDLOOP }; Compare: PUBLIC PROC [path1, path2: Path] RETURNS [order: Order] = { fp1, fp2: FullPath; IF path1.node=NIL OR path2.node=NIL THEN RETURN [disjoint]; IF TiogaPathOps.Equal[path1, path2] THEN RETURN [same]; fp1 _ MakeFullPath[path1]; fp2 _ MakeFullPath[path2]; order _ CompareFullPaths[fp1,fp2]; FreeFullPath[fp1]; FreeFullPath[fp2] }; MakeFullPath: PUBLIC PROC [p: Path] RETURNS [fp: FullPath] = { FullPathMaker: PROC [path: Path, height: NAT] RETURNS [level: NAT] = { height _ height+1; IF path.node=NIL THEN { -- have gone beyond root fp _ GetFullPath[height]; RETURN [0] }; level _ FullPathMaker[PathParent[path],height]; fp[level] _ path.node; RETURN [level+1] }; PathParent: PROC [p: Path] RETURNS [parent: Path] = INLINE { node: Ref; IF (node _ p.node)=NIL THEN RETURN [[NIL,NIL]]; UNTIL node.last DO node _ node.next; ENDLOOP; IF node.next # NIL THEN RETURN [[node.next, p.path]]; IF p.path=NIL THEN RETURN [[NIL,NIL]]; RETURN [p.path^] }; IF p.node=NIL THEN RETURN; fp.length _ FullPathMaker[p,0] }; END. ÈTiogaPathOrderImpl.mesa; written by Bill Paxton, June 1981 edited by Bill Paxton, July 18, 1983 2:40 pm ***** FullPath support routines determines relative order in tree of last nodes in the fps returns "same" if fps are identical returns "before" if last node of fp1 comes before last node of fp2 returns "after" if last node of fp1 comes after last node of fp2 returns "disjoint" if fps are not from the same tree Since applications and formals are included in full paths, can simply use next pointers in nodes rather than calling TiogaPathOps.Next before[0]=root; before[i]=PathParent[before[i+1]]; before[before.length-1]=p.node Similar to TiogaPathOps.Parent, but includes applications and formals. Ê‹˜Jšœ:™:Jšœ,™,J˜JšÏk ˜ Jšœ˜J˜ J˜ J˜ J˜šœ œ˜"Jšœœœ ˜DJšœ˜—J˜Jšœ™J˜JšœÏc ˜$Jšœœ˜Jšœœ˜Jšœœ˜J˜š Ïn œœœœœ˜=Jšœœœ˜šœœœž˜1J˜šœœž˜CJ˜4Jšœ œ˜Jšœ'œ˜0—J˜šœ+œœ˜=šœœž˜.Jšœœ˜#Jšœ'œ˜5—J˜ Jšœ˜ ——Jšœœœ˜8J˜—šŸ œ œœ˜2Jšœœœ˜šœœœ&œ˜SJšœœ˜ —Jš œœœœ œœ˜4J˜*J˜(J˜—šŸœ œœ˜MJ˜Jšœ:™:Jšœ#™#JšœB™BJšœ@™@Jšœ4™4J™Jšœœ˜šœœœœœœœ˜ZJšœœ ˜—šœœ œž"˜8šœ˜ ˜ Jšœ œœ ž˜2Jšœ ž!˜4—Jšœ œ ž!˜;Jšœ˜—šœœž=˜WJ™†J˜šœœž˜8Jšœ œœ ˜"Jšœœœ ˜Jšœ˜ ——Jšœ˜ J˜——šŸœœœœ˜DJ˜Jš œ œœ œœœ ˜;Jšœ"œœ˜7Jšœ˜Jšœ˜J˜"J˜'J˜—šŸ œœœ œ˜>JšœQ™QJ˜š Ÿ œœœœ œ˜FJ˜šœ œœž˜0J˜Jšœ˜ —J˜/J˜Jšœ ˜—J˜šŸ œœ œœ˜