DIRECTORY PLAOps, Process, IO, Rope, Basics USING[BITAND, BITOR, BITXOR]; PLAOpsImplB: CEDAR PROGRAM IMPORTS Basics, IO, PLAOps, Process, Rope EXPORTS PLAOps = BEGIN OPEN Basics, PLAOps; c: ARRAY Use OF CARDINAL; essInterList: TermList _ NEW[TermListRec _ [ ]]; delInterList: TermList _ NEW[TermListRec _ [ ]]; FindAMinimalCover: PUBLIC PROC[ list: TermList, time: CARDINAL, log: IO.STREAM _ IO.noWhereStream] RETURNS[initEss, initDel, bestCov: CARDINAL, unfinished: BOOL] = { intersection: Term _ CopyTerm[list.begin]; interList: TermList _ NEW[TermListRec _ [inBits: list.inBits, outBits: list.outBits]]; c _ ALL[0]; SavedTerms _ NIL; log.PutRope["\n\nInitialize kin lists"]; FOR t1: Term _ list.begin, t1.next WHILE t1#NIL DO t1.kin _ NIL; FOR t2: Term _ list.begin, t2.next WHILE t2#NIL DO IF t1=t2 THEN LOOP; IF Intersection[t1, t2, intersection] THEN t1.kin _ CONS[t2, t1.kin] ENDLOOP; ENDLOOP; log.PutRope["\nFind essential terms"]; FOR t1: Term _ list.begin, t1.next WHILE t1#NIL DO IF ~Abort AND TermCoveredByUsedEssKin[availToo, t1, intersection, interList] THEN IF ~Abort THEN {t1.old_t1.best_used;t1.use_avail;c[avail]_c[avail]+1; SaveListTerms[interList];LOOP}; t1.old_t1.best_t1.use_ess; c[ess]_c[ess]+1; SaveListTerms[interList]; ENDLOOP; log.PutF[" - %g of %g were essential", IO.card[c[ess]], IO.card[list.length]]; log.PutRope["\nFind initial deleted terms"]; FOR t1: Term _ list.begin, t1.next WHILE t1#NIL AND ~Abort DO IF t1.use = ess THEN LOOP; IF TermCoveredByUsedEssKin[notAvail, t1, intersection, interList] THEN IF ~Abort THEN {t1.best _ t1.old _ t1.use _ del; c[del]_c[del]+1; c[avail]_c[avail]-1}; SaveListTerms[interList]; ENDLOOP; log.PutF[" - %g of %g were deleted", IO.card[c[del]], IO.card[c[del]+c[avail]]]; SaveTerm[intersection]; initDel_c[del]; initEss_c[ess]; bestCov_c[avail]+c[ess]; unfinished_TRUE; IF Abort THEN RETURN; PutUseAtEndOfList[use: del, atTop: TRUE, list: list]; PutUseAtEndOfList[use: avail, atTop: FALSE, list: list]; -- essentials in middle [bestCov, unfinished] _ SearchIndependentAvailSets[list, time, log]; FOR t1: Term _ list.begin, t1.next WHILE t1#NIL DO t1.use _ t1.best ENDLOOP; WHILE list.begin.use=del DO DeleteTerm[list.begin, list] ENDLOOP; FOR t1: Term _ list.begin, t1.next WHILE t1.next#NIL DO WHILE t1.next.use=del DO DeleteTerm[t1.next, list]; IF t1.next=NIL THEN GOTO Exit REPEAT Exit => EXIT ENDLOOP; ENDLOOP }; SearchIndependentAvailSets: PROC[ list: TermList, time: CARDINAL, log: IO.STREAM] RETURNS[nextBest: CARDINAL, unfinished: BOOL] = { timer: PROCESS; index: CARDINAL _1; nofSets: CARDINAL; listTList: LIST OF TList; firstA: Term _ NIL; FOR firstA _ list.begin, firstA.next WHILE firstA#NIL AND firstA.use#avail DO ENDLOOP; nextBest _ 0; unfinished _ FALSE; [nofSets, listTList] _ GetSetList[list]; IF nofSets=0 THEN RETURN[c[ess], FALSE]; FOR setList: LIST OF TList _ listTList, setList.rest WHILE setList#NIL DO minCover: CARDINAL; quit: BOOL; setRope: IO.ROPE; FOR tList: TList _ setList.first, tList.rest WHILE tList#NIL DO c[del]_c[del]-1; c[avail]_c[avail]+1; tList.first.use _ avail; ENDLOOP; IF Size[setList.first]#c[avail] THEN ERROR; setRope _ IO.PutFR["Set%2g of%2g size:%3g +%3g(ess) =%3g", IO.card[index],IO.card[nofSets],IO.card[c[avail]],IO.card[c[ess]],IO.card[c[avail]+c[ess]]]; IF Trace THEN log.PutRope[setRope]; IF Abort THEN {minCover _ c[ess]+c[avail]; quit_TRUE} ELSE { timer _ FORK TimeOut[time]; [minCover, quit] _ CoverAvails[list, setRope, firstA, log]; TimeOutQuit[]; TRUSTED{JOIN timer} }; nextBest _ nextBest + minCover - c[ess]; -- sum of ind avails which must be used unfinished _ unfinished OR quit; FinishMin _ FALSE; FOR tList: TList _ setList.first, tList.rest WHILE tList#NIL DO tList.first.old _ tList.first.best; -- should be safe here until restoration in next section tList.first.use _ del; c[del] _ c[del]+1; c[avail] _ c[avail]-1 ENDLOOP; index _ index+1; ENDLOOP; nextBest _ nextBest + c[ess]; FOR setList: LIST OF TList _ listTList, setList.rest WHILE setList#NIL DO FOR tList: TList _ setList.first, tList.rest WHILE tList#NIL DO c[tList.first.use] _ c[tList.first.use] -1; c[tList.first.old] _ c[tList.first.old] +1; tList.first.use _ tList.first.best _ tList.first.old ENDLOOP ENDLOOP }; CoverAvails: PROC[ list: TermList, setRope: IO.ROPE, firstA: Term, log: IO.STREAM] RETURNS[nextBest: CARDINAL, unfinished: BOOL] = { nAvail,top: Term _ NIL; stack: REF TermSeqRec _ NEW[TermSeqRec [list.length]]; stackTop: CARDINAL _ 0; aCnt, sCnt: CARDINAL _ 0; initEss: CARDINAL _ c[ess]; yieldCnt: CARDINAL _ 0; nextBest _ c[avail]+c[ess]; FOR nAvail _ firstA, nAvail.next WHILE nAvail#NIL AND nAvail.use#avail DO ENDLOOP; DO ENABLE UNWIND => EXIT; instack: BOOL; IF (yieldCnt _ ((yieldCnt+1) MOD 20))=0 THEN Process.Yield[]; IF Trace THEN { log.PutF["\nBest:%3g ", IO.card[nextBest]]; instack _ stackTop>0; FOR t: Term_firstA, t.next WHILE t#NIL DO SELECT t.use FROM avail => log.PutRope["A"]; used => log.PutRope["u"]; ess => log.PutRope["e"]; skip => log.PutRope["S"]; ENDCASE => log.PutRope["."]; IF stackTop>0 THEN instack _ instack AND stack[stackTop-1]#t ENDLOOP; log.PutRope[" "]}; IF nAvail # NIL AND (c[skip]+c[avail])>0 AND (c[ess]+c[used]+1) < nextBest THEN { ok: BOOL; stack[stackTop] _ nAvail; stackTop _ stackTop+1; top _ stack[stackTop-1]; top.use _ skip; c[avail] _ c[avail] - 1; c[skip] _ c[skip] + 1; [ok, aCnt] _ MarkEssentialAvails -- check new skip's kin to see if essential [list: list, kkin: top, lim: nextBest-c[ess]-c[used]-1]; c[avail] _ c[avail] - aCnt; c[ess] _ c[ess] + aCnt; IF ~ok THEN {nAvail _ NIL; RestoreKin[top, ess]; LOOP}; -- can't help IF aCnt>0 THEN FOR ref: TList _ top.kin, ref.rest WHILE ref#NIL DO -- for each new ess IF ref.first.kkin #top THEN LOOP; IF ref.first.use #ess THEN ERROR; [aCnt, sCnt] _ DeleteCoveredAvailSkips[list, ref.first]; c[del] _ c[del] + aCnt + sCnt; c[avail] _ c[avail] - aCnt; c[skip] _ c[skip] - sCnt; ENDLOOP; IF (c[ess]+c[used]+1) >= nextBest OR (c[skip]+c[avail])=0 OR FinishMin THEN nAvail _ NIL -- => POP again ELSE FOR nAvail _ top.next, nAvail.next WHILE nAvail#NIL AND nAvail.use#avail DO ENDLOOP; LOOP}; IF (c[skip]+c[avail])=0 AND (c[ess]+c[used]) < nextBest THEN { nextBest _ c[ess]+c[used]; log.PutF["\n%g -> Cover:%3g +%3g(ess) =%3g %g", IO.rope[setRope], IO.card[nextBest-initEss], IO.card[initEss], IO.card[nextBest], TOD[]]; TimeOutReset[]; FOR t: Term _ list.begin, t.next WHILE t#NIL DO t.best _ t.use ENDLOOP }; IF stackTop=0 THEN EXIT; top _ stack[stackTop-1]; SELECT stack[stackTop-1].use FROM skip, del => { -- del only when skip => essentials => self coverage FOR essByTop: TList_top.kin, essByTop.rest WHILE essByTop # NIL DO IF essByTop.first.kkin#top THEN LOOP; essByTop.first.kkin _ NIL; IF essByTop.first.use # ess THEN ERROR; IF essByTop.first.old # avail THEN ERROR; essByTop.first.use _ essByTop.first.old; c[ess] _ c[ess] - 1; c[avail] _ c[avail] + 1; RestoreKin[kkin: essByTop.first, curUse: del] ENDLOOP; IF top.use#skip THEN ERROR; -- del should have been fixed top.use _ used; c[skip] _ c[skip] - 1; c[used] _ c[used] + 1; [aCnt, sCnt] _ DeleteCoveredAvailSkips[list: list, kkin: top]; c[del] _ c[del] + aCnt + sCnt; c[avail] _ c[avail] - aCnt; c[skip] _ c[skip] - sCnt; IF (c[ess]+c[used]+1) >= nextBest OR (c[skip]+c[avail])=0 OR FinishMin THEN nAvail _ NIL -- => POP again ELSE FOR nAvail _ top.next, nAvail.next WHILE nAvail#NIL AND nAvail.use#avail DO ENDLOOP; LOOP }; used => { stackTop _ stackTop-1; RestoreKin[kkin: top, curUse: del]; top.use _ avail; -- reset all stacked up skips to avail c[used] _ c[used] - 1; c[avail] _ c[avail] + 1; nAvail _ NIL; -- backup until top.use = skip; LOOP}; ENDCASE => ERROR; ENDLOOP; IF (unfinished _ FinishMin) THEN log.PutF[" <> %g",TOD[]] }; Size: PROC [tList: TList] RETURNS[size: CARDINAL] = {size_0; FOR t1: TList _ tList, t1.rest WHILE t1#NIL DO size _ size +1 ENDLOOP}; GetSetList: PROC[ list: TermList] RETURNS[count: CARDINAL, listTList: LIST OF TList] = { listTList _ NIL; count _ 0; FOR t1: Term _ list.begin, t1.next WHILE t1#NIL DO tList: TList _ NIL; MarkAvailKinDeleted: PROC[ref: Term] = { FOR t2: TList _ ref.kin, t2.rest WHILE t2#NIL DO IF t2.first.use # avail THEN LOOP; c[del]_c[del]+1; c[avail]_c[avail]-1; t2.first.use _ del; tList _ CONS[t2.first, tList]; MarkAvailKinDeleted[t2.first]; ENDLOOP}; IF t1.use # avail THEN LOOP; c[del]_c[del]+1; c[avail]_c[avail]-1; t1.use_del; tList_CONS[t1, tList]; MarkAvailKinDeleted[t1]; listTList _ CONS[tList, listTList]; count _ count+1; ENDLOOP; DO OrderList: PROC [sList: LIST OF TList] RETURNS[LIST OF TList] = { IF sList=NIL THEN RETURN[NIL]; IF sList.rest=NIL THEN RETURN[sList]; IF Size[sList.first] > Size[sList.rest.first] THEN { ok _ FALSE; sList _ CONS[sList.rest.first, CONS[sList.first, sList.rest.rest]] }; sList.rest _ OrderList[sList.rest]; RETURN[sList]}; ok: BOOL _ TRUE; listTList _ OrderList[listTList]; IF ok THEN EXIT ENDLOOP }; RestoreKin: PROC[kkin: Term, curUse: Use] = INLINE { FOR kin: TList _ kkin.kin, kin.rest WHILE kin#NIL DO IF kin.first.kkin # kkin THEN LOOP; kin.first.kkin _ NIL; IF kin.first.use # curUse THEN ERROR; kin.first.use _ kin.first.old; SELECT kin.first.old FROM avail => {c[curUse] _ c[curUse] - 1; c[avail] _ c[avail] + 1}; skip => {c[curUse] _ c[curUse] - 1; c[skip] _ c[skip] + 1}; ENDCASE => ERROR ENDLOOP }; TOD: PROC RETURNS[IO.Value] = { time: IO.ROPE _ IO.PutFR["%g", IO.time[]]; time _ time.Substr[time.Index[s2:"198"]+5]; time _ time.Substr[len: time.Index[s2:" "]]; IF time.Length[] = 7 THEN time _ Rope.Cat[" ", time]; RETURN[IO.rope[time]]}; PutUseAtEndOfList: PROC[use: Use, atTop: BOOL, list: TermList] = { top: Term _ list.begin; bot: Term _ list.end; temp: Term _ NIL; DO -- swaps links to preserve lists FOR top_top, top.next WHILE top#bot AND (top.use = use)=atTop DO ENDLOOP; FOR bot_bot, bot.last WHILE bot#top AND (bot.use # use)=atTop DO ENDLOOP; IF bot=top THEN RETURN; temp_top.next; top.next_bot.next; bot.next_temp; bot.next.last_bot; IF top.next=NIL THEN list.end_top ELSE top.next.last_top; temp_top.last; top.last_bot.last; bot.last_temp; top.last.next_top; IF bot.last=NIL THEN list.begin_bot ELSE bot.last.next_bot; temp_top; top_bot; bot_temp; ENDLOOP}; MarkEssentialAvails: PROC[ -- Not covered by [esss, used or avail ~(del or skip)] list: TermList, kkin: Term, -- This term contains the kin list to be checked (all avails are below it) lim: INT] RETURNS[ok: BOOL, aCnt: CARDINAL] = { intersection: Term _ CopyTerm[list.begin]; essInterList^ _ [inBits: list.inBits, outBits: list.outBits]; aCnt _ 0; ok _ TRUE; FOR ref: TList _ kkin.kin, ref.rest WHILE ref#NIL DO IF (lim-aCnt) <= 0 THEN {ok_FALSE; EXIT}; IF ~(ref.first.use IN [avail..skip]) THEN LOOP; IF ~TermCoveredByUsedEssKin[availToo, ref.first, intersection, essInterList] THEN { IF ref.first.use=skip THEN {ok_FALSE; IF aCnt#0 THEN ERROR; EXIT}; ref.first.kkin_kkin; ref.first.old_ref.first.use; ref.first.use_ess; aCnt_aCnt+1}; SaveListTerms[essInterList]; ENDLOOP; SaveListTerms[essInterList]; SaveTerm[intersection] }; DeleteCoveredAvailSkips: PROC[ -- Covered by [E U but not (D S A)] list: TermList, kkin: Term] -- This term's kin must be checked RETURNS[aCnt, sCnt: CARDINAL] = INLINE { intersection: Term _ CopyTerm[list.begin]; delInterList^ _ [inBits: list.inBits, outBits: list.outBits]; aCnt _ sCnt _ 0; FOR ref: TList _ kkin.kin, ref.rest WHILE ref#NIL DO IF ~(ref.first.use IN [avail..skip]) THEN LOOP; IF TermCoveredByUsedEssKin[notAvail, ref.first, intersection, delInterList] THEN { IF ref.first.use=skip THEN sCnt _ sCnt+1 ELSE aCnt _ aCnt+1; ref.first.kkin_kkin; ref.first.old_ref.first.use; ref.first.use_del}; SaveListTerms[delInterList]; ENDLOOP; SaveListTerms[delInterList]; SaveTerm[intersection] }; TermCoveredByUsedEssKin: PROC[ mode: {availToo, notAvail}, -- availToo for ess test, notAvail for delete test ref: Term, intersection: Term, -- Passed in to prevent repetitive NEW's interList: TermList] -- Passed in to prevent repetitive NEW's RETURNS[BOOL] = INLINE { FOR test: TList _ ref.kin, test.rest WHILE test#NIL DO SELECT test.first.use FROM avail => IF mode=notAvail THEN LOOP; skip => LOOP; used => { }; ess => { }; del => LOOP; ENDCASE => ERROR; IF Intersection[ref, test.first, intersection] THEN DO -- Will repeat if FinishCS set IF ~UpdateCompleteSumWithTerm[interList, intersection, TRUE, TRUE] THEN EXIT; ENDLOOP; ENDLOOP; RETURN[(interList.length=1 AND SameTerm[ref, interList.begin])] }; Intersection: PUBLIC PROC[ref, test, intersection: Term] RETURNS[valid: BOOL] = --INLINE-- { valid _ FALSE; FOR i: CARDINAL IN [0..ref.in.wdSize) DO IF BITAND[BITAND[ref.in[i].m, test.in[i].m], BITXOR[ref.in[i].d, test.in[i].d]]#0 THEN RETURN[FALSE]; -- FALSE if inputs crossed intersection.in[i].d _ BITOR[ref.in[i].d, test.in[i].d]; intersection.in[i].m _ BITOR[ref.in[i].m, test.in[i].m] ENDLOOP; FOR i: CARDINAL IN [0..ref.out.wdSize) DO intersection.out[i].d _ BITAND [ref.out[i].d, test.out[i].d]; intersection.out[i].m _ BITOR [ref.out[i].m, test.out[i].m]; valid _ valid OR intersection.out[i].d#0; ENDLOOP }; SameTerm: PROC[ref, test: Term] RETURNS[same: BOOL] = INLINE { same _ TRUE; FOR i: CARDINAL IN [0..ref.in.wdSize) WHILE same DO same _ same AND (BITXOR[ref.in[i].m, test.in[i].m]=0) AND (BITXOR[ref.in[i].d, test.in[i].d]=0) ENDLOOP; FOR i: CARDINAL IN [0..ref.out.wdSize) WHILE same DO same _ same AND (BITXOR[ref.out[i].m, test.out[i].m]=0) AND (BITXOR[ref.out[i].d, test.out[i].d]=0) ENDLOOP }; END. .PLAOpsImplB.mesa Copyright c 1984 by Xerox Corporation. All rights reserved. Last edited by Curry, September 24, 1984 5:01:52 am PDT Initialize kin lists with all other terms which intersect Initialize essentials Initialize deletes Get Avail lists Try to find better cover Restore best state Êö˜šÐbl™Jšœ Ïmœ1™Jšœ˜šœ0˜0Jš ŸœŸœŸœŸœŸœ˜Z—Jšœ˜Jš ŸœŸœŸœŸœŸœ˜I—J˜JšŸœ ŸœŸœ˜Jšœ˜šŸœŸ˜!šœ¢4˜CšŸœ(Ÿœ ŸœŸ˜BJšŸœŸœŸœŸœ˜AJšŸœŸœŸœ˜(JšŸœŸœŸœ˜*Jšœ)˜)Jšœ˜Jšœ˜Jšœ.Ÿœ˜6—JšŸœŸœŸœ¢˜9Jšœ˜Jšœ˜Jšœ˜Jšœ>˜>Jšœ"˜"Jšœ˜Jšœ˜šŸœ ŸœŸœ ˜FJšŸœ Ÿœ¢˜!š ŸœŸœ ŸœŸœŸœ˜MJšŸœŸœ˜ ——JšŸœ˜—šœ ˜ Jšœ˜Jšœ#˜#Jšœ¢&˜9Jšœ˜Jšœ˜Jšœ Ÿœ¢˜-JšŸœ˜—JšŸœŸœ˜—JšŸœ˜Jš ŸœŸœ ÏfLœ£Ðfk£˜€——J˜š œŸœŸœŸœ˜3Jš œ ŸœŸœŸœŸœŸœ˜P—J˜š  œŸœ˜šœ˜JšŸœŸœ ŸœŸœ ˜6—Jšœ Ÿœ˜Jšœ ˜ šŸœ ŸœŸœŸ˜2JšœŸœ˜š œŸœ˜(JšŸœŸœŸœŸ˜0JšŸœŸœŸœ˜"Jšœ%˜%Jšœ˜JšœŸœ˜JšœŸœ˜(—JšŸœŸœŸœ˜Jšœ%˜%JšœŸœ ˜#Jšœ˜Jšœ Ÿœ$˜4JšŸœ˜—šŸ˜š  œŸœ ŸœŸœŸœŸœŸœ ˜AJš ŸœŸœŸœŸœŸœ˜JšŸœ ŸœŸœŸœ˜%šŸœ,Ÿœ˜4JšœŸœ˜ JšœŸœŸœ"˜E—Jšœ$Ÿœ ˜3—JšœŸœŸœ˜Jšœ!˜!JšŸœŸœŸœŸœ˜——J˜š  œŸœŸœ˜4JšŸœ!ŸœŸœŸ˜4JšŸœŸœŸœŸœ˜:JšŸœŸœŸœ ˜EšŸœŸ˜Jšœ?˜?Jšœ=˜=JšŸœŸœŸœ˜——J˜šÐbkœŸœŸœŸœ ˜Jš œŸœŸœŸœ Ÿœ ˜*J˜+J˜,JšŸœŸœ˜5JšŸœŸœ˜—J˜š œŸœŸœ˜BJšœ˜Jšœ˜Jšœ Ÿœ˜šŸœ¢ ˜#Jš ŸœŸœ ŸœŸœŸœ˜IJš ŸœŸœ ŸœŸœŸœ˜IJšŸœ ŸœŸœ˜šœC˜CJšŸœ ŸœŸœŸœ˜9—šœD˜DJšŸœ ŸœŸœŸœ˜;—JšœŸœ˜&——J˜š œŸœ¢6˜QJšœ˜Jšœ¢J˜XšœŸœ˜ JšŸœŸœŸœ˜%—Jšœ*˜*Jšœ=˜=Jšœ ˜ JšœŸœ˜ šŸœ!ŸœŸœŸ˜4JšŸœŸœŸœŸœ˜)JšŸœŸœŸœŸœ˜/šŸœJ˜LšŸœ˜JšŸœŸœŸœŸœŸœŸœŸœ˜BJšœR˜R——JšœŸœ˜%—Jšœ6˜6—J˜š œŸœ¢#˜BJšœ˜šœ¢"˜0JšŸœ ŸœŸœ˜(—Jšœ*˜*Jšœ>˜>Jšœ˜šŸœ!ŸœŸœŸ˜4JšŸœŸœŸœŸœ˜/šŸœI˜KšŸœ˜JšŸœŸœŸœ˜JšœŸœ˜ š ŸœŸœŸœŸœŸ˜3šœ Ÿ˜JšœŸœŸ˜)JšœŸœŸœ˜.——š ŸœŸœŸœŸœŸ˜4šœ Ÿ˜JšœŸœ!Ÿ˜+JšœŸœ!Ÿœ˜2———J˜J˜J˜JšŸœ˜J˜J˜—…—5:H^