LichenNewArrayImpl2.Mesa
Last tweaked by Mike Spreitzer on December 16, 1987 10:17:05 pm PST
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 [c
D: Function
--Cycle
b
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 b 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.