<> <> DIRECTORY TiogaPathOrder, TiogaNode, TiogaNodeOps, TiogaPathOps; TiogaPathOrderImpl: CEDAR MONITOR IMPORTS TiogaPathOps EXPORTS TiogaPathOrder SHARES TiogaNode = BEGIN OPEN TiogaPathOrder; <<***** FullPath support routines>> 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.