DIRECTORY AbSets, Basics, BiRels, LichenArrayStuff, LichenDataOps, LichenDataStructure, Rope, SetBasics; LichenNewArrayImpl2: CEDAR PROGRAM IMPORTS AbSets, BiRels, LichenArrayStuff, LichenDataStructure, SetBasics = BEGIN OPEN LichenDataOps, LichenDataStructure, LichenArrayStuff, Sets:AbSets; Array: TYPE ~ LichenDataStructure.Array; Cycle: TYPE ~ LORA --where elements are StatEdges, and the first element is the StatEdge at the lowest address--; cycleSpace: SetBasics.Space ~ SetBasics.CreateLORASpace[NIL, LIST[SetBasics.refs]]; FindSimpleCycles: PROC [a: Array] RETURNS [cD: Function--Cycle _ D--] ~ { seenVerts: Set ~ Sets.CreateHashSet[]; Start: PROC [sv: StatVertex] RETURNS [BOOL] ~ { IF NOT seenVerts.AddA[sv] THEN RETURN [FALSE]; {inPath: Set--of StatVertex-- ~ Sets.CreateHashSet[]; stack: LORA _ NIL; ExploreFrom: PROC [sv: StatVertex] ~ { [] _ seenVerts.AddA[sv]; IF inPath.AddA[sv] THEN { CrossEdge: PROC [se: StatEdge, ob: BOOL] RETURNS [BOOL] ~ { stack _ CONS[se, stack]; ExploreFrom[se.vs[ob]]; stack _ stack.rest; RETURN [FALSE]}; stack _ CONS[sv, stack]; IF ScanStatEdgesFrom[a.statrep, sv, CrossEdge].found THEN ERROR; stack _ stack.rest; } ELSE { head, min, minPrev, tail: Cycle _ NIL; setPrev: BOOL _ FALSE; D: Int2 _ ALL[0]; at: StatVertex _ sv; FOR sp: LORA _ stack, sp.rest.rest DO se: StatEdge ~ NARROW[sp.first]; next: StatVertex ~ NARROW[sp.rest.first]; b: BOOL ~ at = se.vs[TRUE]; IF se.vs[b] # at THEN ERROR; D _ IF b THEN Int2Sub[D, se.d] ELSE Int2Add[D, se.d]; head _ CONS[se, head]; IF tail=NIL THEN tail _ head; IF min=NIL OR LOOPHOLE[head.first, INT] < LOOPHOLE[min.first, INT] THEN {min _ head; setPrev _ TRUE} ELSE IF setPrev THEN {minPrev _ head; setPrev _ FALSE}; IF next=sv THEN EXIT; ENDLOOP; IF setPrev THEN min _ head ELSE { IF minPrev.rest#min THEN ERROR; tail.rest _ head; minPrev.rest _ NIL}; [] _ cD.AddAA[min, NEW [Int2 _ D]]; }; IF NOT inPath.RemA[sv] THEN ERROR; }; ExploreFrom[sv]; RETURN [FALSE]}}; cD _ BiRels.CreateHashFn[spaces: [cycleSpace, SetBasics.refs], invable: FALSE]; IF ScanStatVertices[a, Start].found THEN ERROR; RETURN}; HasHardBasis: PROC [act: CellType] RETURNS [BOOL] ~ { IF act.asArray=NIL THEN RETURN [FALSE]; {a: Array ~ act.asArray; cD: Function--Cycle _ D-- ~ FindSimpleCycles[a]; basis: ARRAY Dim OF NATURAL _ ALL[NATURAL.LAST]; Pass1: PROC [left, right: REF ANY] ~ { cycle: Cycle ~ NARROW[left]; D: REF Int2 ~ NARROW[right]; IF D^ = ALL[0] THEN RETURN; IF D[Foo]#0 AND D[Bar]#0 THEN RETURN; {dim: Dim ~ IF D[Foo]#0 THEN Foo ELSE Bar; basis[dim] _ MIN[D[dim], basis[dim]]}}; Pass2: PROC [pair: BiRels.Pair] RETURNS [BOOL] ~ { D: REF Int2 ~ NARROW[pair[right].VA]; RETURN [D[Foo] MOD basis[Foo] # 0 OR D[Bar] MOD basis[Bar] # 0]}; cD.EnumAA[Pass1]; RETURN [cD.Scan[Pass2].found]}}; END. dLichenNewArrayImpl2.Mesa Last tweaked by Mike Spreitzer on December 16, 1987 10:17:05 pm PST Κΐ– "cedar" style˜code™KšœC™C—K˜KšΟk œ_˜hK˜šΟnœœ˜"KšœA˜HK˜—K˜Kšœœ7žœ˜MK˜Kšœœ˜(K˜KšœœœΟc]œ˜qK˜Kšœ8œœ˜SK˜šžœœ œΟgœ ŸΠcmŸΠcgŸœ˜IK˜&šžœœœœ˜/Kš œœœœœ˜.Kšœ Ÿœ˜5Kšœœœ˜šž œœ˜&K˜šœœ˜š ž œœœœœ˜;Kšœœ ˜Kšœ˜K˜Kšœœ˜—Kšœœ ˜Kšœ3œœ˜@K˜K˜—šœ˜Kšœ"œ˜&Kšœ œœ˜KšΠgnœ œ˜K˜šœœ˜%Kšœœ ˜ Kšœœ˜)Kšœœœ˜Kšœœœ˜Kš œœœ  œ œœ  œ œ˜5Kšœœ ˜Kšœœœ ˜šœœœœ œœ œ˜BKšœœ˜!Kšœœ œœ˜7—Kšœ œœ˜Kšœ˜—šœ œ œ˜!Kšœœœ˜K˜Kšœœ˜—Kšœ œ œ  œ˜#K˜—Kšœœœœ˜"K˜—Kšœ˜Kšœœ˜—Kšœ œFœ˜OKšœ"œœ˜/Kšœ˜—K˜šž œœœœ˜5Kš œ œœœœ˜'K˜Kš œ œ Ÿ‘Ÿ’Ÿœ˜0Kš œœœœœœœ˜0šžœœœœ˜&Kšœœ˜Kš£œœœ˜Kš œ œœœœ˜Kš œ œœ œœœ˜%Kš œ œ œœœ˜*Kšœ œ œ˜'—šžœœœœ˜2Kš£œœœ œ˜%Kš œ œœœ œœ˜A—Kšœ œ˜Kšœ œ˜ —K˜Kšœ˜—…— Τψ