AlpsHeurImpl.mesa
Created by Bertrand Serlet, August 1, 1985 11:34:40 am PDT
Last edited by serlet June 18, 1985 1:49:33 pm PDT
This program generates a file suitable for layout generation from a truth table.
DIRECTORY
AlpsBool, AlpsHeur, Commander, Convert, HashTable, Process, Rope;
AlpsHeurImpl: CEDAR PROGRAM
IMPORTS AlpsBool, Convert, HashTable, Process
EXPORTS AlpsHeur =
BEGIN
OPEN AlpsHeur;
Types and data structures
ROPE: PUBLIC TYPE = Rope.ROPE;
VarNb: TYPE = AlpsBool.VarNb;
CompClass: TYPE = AlpsBool.CompClass;
OutputType: TYPE = AlpsBool.OutputType;
Useful TableComparisonProc
ImproveAreaAndDelay: PUBLIC TableComparisonProc = {
oldArea, newArea, oldSize, newSize, oldDeep, newDeep: INT;
[area: oldArea, sigmaSize: oldSize, maxDeep: oldDeep] ← AlpsBool.TableStatistics[oldTable];
[area: newArea, sigmaSize: newSize, maxDeep: newDeep] ← AlpsBool.TableStatistics[newTable];
IF oldArea>newArea THEN RETURN [TRUE];
IF oldArea<newArea THEN RETURN [FALSE];
IF oldSize>newSize THEN RETURN [TRUE];
IF oldSize<newSize THEN RETURN [FALSE];
IF oldDeep>newDeep THEN RETURN [TRUE];
RETURN [FALSE];
};
ImproveSizeAndDelay: PUBLIC TableComparisonProc = {
oldSize, newSize, oldDeep, newDeep: INT;
[sigmaSize: oldSize, maxDeep: oldDeep] ← AlpsBool.TableStatistics[oldTable];
[sigmaSize: newSize, maxDeep: newDeep] ← AlpsBool.TableStatistics[newTable];
newIsBetter ← TRUE;
IF oldSize<newSize OR (oldSize=newSize AND oldDeep<=newDeep) THEN RETURN [FALSE];
IF oldDeep<newDeep OR (oldDeep=newDeep AND oldSize<=newSize) THEN RETURN [FALSE];
};
ImproveSize: PUBLIC TableComparisonProc = {
oldSize: INT ← AlpsBool.TableStatistics[oldTable].sigmaSize;
newSize: INT ← AlpsBool.TableStatistics[newTable].sigmaSize;
oldDeep: INT ← AlpsBool.TableStatistics[oldTable].maxDeep;
newDeep: INT ← AlpsBool.TableStatistics[newTable].maxDeep;
newIsBetter ← TRUE;
IF oldSize<newSize OR (oldSize=newSize AND oldDeep<=newDeep) THEN RETURN [FALSE];
};
ImproveDelay: PUBLIC TableComparisonProc = {
oldSize: INT ← AlpsBool.TableStatistics[oldTable].sigmaSize;
newSize: INT ← AlpsBool.TableStatistics[newTable].sigmaSize;
oldDeep: INT ← AlpsBool.TableStatistics[oldTable].maxDeep;
newDeep: INT ← AlpsBool.TableStatistics[newTable].maxDeep;
newIsBetter ← TRUE;
IF oldDeep<newDeep OR (oldDeep=newDeep AND oldSize<=newSize) THEN RETURN [FALSE];
};
AlwaysBetter: PUBLIC TableComparisonProc = {
newIsBetter ← TRUE;
};
Utilities
Output: PUBLIC PROC [t1, t2, t3, t4, t5: ROPE ← NIL] = AlpsBool.Output;
Alps heart
Example: PUBLIC PROC [] RETURNS [table: AlpsBool.TableOfVariables] =
BEGIN
aVarNb: VarNb = 1;
bVarNb: VarNb = 2;
cVarNb: VarNb = 3;
dVarNb: VarNb = 4;
eVarNb: VarNb = 5;
fVarNb: VarNb = 5;
r1Expr, r2Expr: AlpsBool.Expression;
table ← AlpsBool.InitTableOfVariables[7];
table[aVarNb].name ← "aVarNb";
table[bVarNb].name ← "bVarNb";
table[cVarNb].name ← "cVarNb";
table[dVarNb].name ← "dVarNb";
table[eVarNb].name ← "eVarNb";
table[fVarNb].name ← "fVarNb";
r1Expr ← AlpsBool.Or[table, AlpsBool.And[table, AlpsBool.ExprFromVarNb[aVarNb], AlpsBool.ExprFromVarNb[bVarNb], AlpsBool.ExprFromVarNb[cVarNb], AlpsBool.ExprFromVarNb[dVarNb]], AlpsBool.ExprFromVarNb[eVarNb, FALSE], AlpsBool.Not[AlpsBool.And[table, AlpsBool.ExprFromVarNb[aVarNb], AlpsBool.ExprFromVarNb[fVarNb]]]];
r2Expr ← AlpsBool.Or[table, AlpsBool.ExprFromVarNb[aVarNb], AlpsBool.ExprFromVarNb[cVarNb]];
AlpsBool.AddOutput[table, NEW[AlpsBool.OutputRec ← [name: "r1Expr", expr: r1Expr]]];
AlpsBool.AddOutput[table, NEW[AlpsBool.OutputRec ← [name: "r2Expr", expr: r2Expr]]];
END;
ExampleC1MX07A: PUBLIC PROC [] RETURNS [table: AlpsBool.TableOfVariables] =
BEGIN
I1A, I1B, I2C, I2D, I3E, I3F: VarNb;
result: AlpsBool.Expression;
table ← AlpsBool.InitTableOfVariables[7];
I1A ← 1; table[I1A].name ← "I1A";
I1B ← 2; table[I1B].name ← "I1B";
I2C ← 3; table[I2C].name ← "I2C";
I2D ← 4; table[I2D].name ← "I2D";
I3E ← 5; table[I3E].name ← "I3E";
I3F ← 6; table[I3F].name ← "I3F";
result ← AlpsBool.Nor[table, AlpsBool.And[table, AlpsBool.ExprFromVarNb[I1A], AlpsBool.ExprFromVarNb[I1B]], AlpsBool.And[table, AlpsBool.ExprFromVarNb[I2C], AlpsBool.ExprFromVarNb[I2D]], AlpsBool.And[table, AlpsBool.ExprFromVarNb[I3E], AlpsBool.ExprFromVarNb[I3F]]];
AlpsBool.AddOutput[table, NEW[AlpsBool.OutputRec ← [name: "result", expr: result]]];
END;
MostUsed: PUBLIC PROC [table: AlpsBool.TableOfVariables] RETURNS [exprs: LIST OF AlpsBool.Expression ← NIL] =
BEGIN
Hash: PROC [key: HashTable.Key] RETURNS [CARDINAL] = {
expr: AlpsBool.Expression ← NARROW[key];
RETURN[CARDINAL[expr.varNb]];
};
Equal: PROC [key1, key2: HashTable.Key] RETURNS [BOOL] = {
expr1: AlpsBool.Expression ← NARROW[key1];
expr2: AlpsBool.Expression ← NARROW[key2];
RETURN [AlpsBool.Equal[table, expr1, expr2] OR AlpsBool.Equal[table, expr1, expr2, FALSE]]
};
RegisterExprRec: AlpsBool.EachNodeProc -- [expr: AlpsBool.Expression] RETURNS [quit: BOOL ← FALSE] -- = {
value: HashTable.Value ← HashTable.Fetch[used, expr].value;
nbUsed: REF INT ← IF value=NIL THEN NEW[INT ← 0] ELSE NARROW[value];
nbUsed^ ← nbUsed^ + 1;
[] ← HashTable.Store[used, expr, nbUsed];
};
FindBestPairs: HashTable.EachPairAction = {
[key: HashTable.Key, value: HashTable.Value] RETURNS [quit: BOOLEAN ← FALSE]
nbUsed: REF INT ← NARROW[value];
expr: AlpsBool.Expression ← NARROW[key];
caseXY: INT ← AlpsBool.NbOfCaseXY[table, expr];
quit ← FALSE;
IF nbUsed^<2 THEN RETURN;
IF nbUsed^>bestNbUsed THEN {bestNbUsed ← nbUsed^; bestCaseXY ← caseXY; exprs ← LIST[expr]; RETURN};
IF nbUsed^<bestNbUsed OR caseXY<bestCaseXY THEN RETURN;
IF caseXY>bestCaseXY THEN {bestCaseXY ← caseXY; exprs ← LIST[expr]; RETURN};
same interest, then
exprs ← CONS[expr, exprs];
};
used: HashTable.Table ← HashTable.Create[hash: Hash, equal: Equal, mod: table.size];
bestNbUsed: INT ← FIRST[INT]; bestCaseXY: INT ← FIRST[INT];
We register every expr
FOR outs: LIST OF AlpsBool.OutputRef ← table.outputs, outs.rest WHILE outs#NIL DO
AlpsBool.Enumerate[outs.first.expr, RegisterExprRec];
ENDLOOP;
We select the best ones
[] ← HashTable.Pairs[used, FindBestPairs];
END;
DefaultInterestProc: PUBLIC InterestProc = {
exprIsInteresting ← AlpsBool.NbOfCaseXY[table, expr]>0;
};
EnumerateRestrictions: PUBLIC PROC [table: AlpsBool.TableOfVariables, eachRestriction: EachRestrictionProc, interestProc: InterestProc ← DefaultInterestProc] = {
Hash: PROC [key: HashTable.Key] RETURNS [CARDINAL] = {
expr: AlpsBool.Expression ← NARROW[key];
RETURN[CARDINAL[expr.varNb]];
};
Equal: PROC [key1, key2: HashTable.Key] RETURNS [BOOL] = {
expr1: AlpsBool.Expression ← NARROW[key1];
expr2: AlpsBool.Expression ← NARROW[key2];
RETURN [AlpsBool.Equal[table, expr1, expr2] OR AlpsBool.Equal[table, expr1, expr2, FALSE]]
};
Add: PROC [ref: HashTable.Table, expr: AlpsBool.Expression, nb: INT ← 1] = {
value: HashTable.Value ← HashTable.Fetch[ref, expr].value;
refInt: REF INT ← IF value=NIL THEN NEW[INT ← 0] ELSE NARROW[value];
IF ~interestProc[table, expr] THEN RETURN;
refInt^ ← refInt^ + nb;
[] ← HashTable.Store[ref, expr, refInt];
};
restrictions: HashTable.Table ← HashTable.Create[hash: Hash, equal: Equal, mod: table.size];
FOR outputs: LIST OF AlpsBool.OutputRef ← table.outputs, outputs.rest WHILE outputs#NIL DO Add[restrictions, outputs.first.expr] ENDLOOP;
WHILE HashTable.GetSize[restrictions]#0 DO
newRestrictions: HashTable.Table ← HashTable.Create[hash: Hash, equal: Equal, mod: table.size];
AddExprToNewRestrictions: HashTable.EachPairAction = {
expr: AlpsBool.Expression ← NARROW[key];
refInt: REF INT ← NARROW[value];
exprs: HashTable.Table ← HashTable.Create[hash: Hash, equal: Equal, mod: table.size];
AddExprLow: HashTable.EachPairAction = {
Add[newRestrictions, NARROW[key], refInt^];
};
Process.Yield[]; Process.SetPriority[Process.priorityBackground];
FOR varNb: VarNb IN [1..table.size) DO
[] ← HashTable.Store[exprs, AlpsBool.ExprWhenVarIs[table, expr, varNb, TRUE], NIL];
[] ← HashTable.Store[exprs, AlpsBool.ExprWhenVarIs[table, expr, varNb, FALSE], NIL];
ENDLOOP;
[] ← HashTable.Pairs[exprs, AddExprLow];
};
ApplyToEachInteresting: HashTable.EachPairAction = {
expr: AlpsBool.Expression ← NARROW[key];
refInt: REF INT ← NARROW[value];
IF refInt^>1 THEN quit ← eachRestriction[table, expr, refInt^];
};
[] ← HashTable.Pairs[restrictions, AddExprToNewRestrictions];
IF HashTable.Pairs[newRestrictions, ApplyToEachInteresting] THEN EXIT;
restrictions ← newRestrictions;
ENDLOOP;
};
RenumProc: TYPE = AlpsBool.RenumProc;
FactorizeOutput: PUBLIC PROC [table: AlpsBool.TableOfVariables, auxOutput: AlpsBool.OutputRef] RETURNS [newTable: AlpsBool.TableOfVariables] =
BEGIN
Renum: RenumProc =
{RETURN [IF oldVarNb<auxOutput.fedBackInput THEN oldVarNb ELSE oldVarNb+1]};
newTable ← AlpsBool.InitTableOfVariables[table.size+1];
newTable[auxOutput.fedBackInput].name ← auxOutput.name;
AlpsBool.AddOutput[newTable, auxOutput];
FOR i: VarNb IN [1 .. table.size) DO
newTable[Renum[i]].name ← table[i].name;
ENDLOOP;
FOR outputs: LIST OF AlpsBool.OutputRef ← table.outputs, outputs.rest WHILE outputs#NIL DO
AlpsBool.AddOutput[newTable, NEW[AlpsBool.OutputRec ← [
name: outputs.first.name, type: outputs.first.type,
expr: outputs.first.expr, fedBackInput: Renum[outputs.first.fedBackInput]
]]];
ENDLOOP;
FOR outputs: LIST OF AlpsBool.OutputRef ← table.outputs, outputs.rest WHILE outputs#NIL DO
IF outputs.first#auxOutput THEN outputs.first.expr ← AlpsBool.Factorize[newTable, outputs.first.expr, auxOutput.expr, auxOutput.fedBackInput];
ENDLOOP;
END;
FactorizeBest: PUBLIC PROC [table: AlpsBool.TableOfVariables, better: TableComparisonProc, printLevel: INT ← 2] RETURNS [newTable: AlpsBool.TableOfVariables, ok: BOOL] =
BEGIN
ok ← FALSE;
FOR exprs: LIST OF AlpsBool.Expression ← MostUsed[table], exprs.rest WHILE exprs#NIL DO
auxOutput: AlpsBool.OutputRef ← NEW[AlpsBool.OutputRec ← [
name: AlpsBool.NewName["AlpsAux"], expr: exprs.first, type: aux, fedBackInput: exprs.first.varNb+1
]];
IF table.size>=LAST[VarNb]-1 THEN {Output["No more variable\n"]; RETURN};
newTable ← FactorizeOutput[table, auxOutput];
We try to permute, now
FOR j: VarNb DECREASING IN [1..table.size) DO
newNewTable: AlpsBool.TableOfVariables ← AlpsBool.Permute2Vars[newTable, 1, j];
Output["."];
IF better[newTable, newNewTable] THEN newTable ← newNewTable;
ENDLOOP;
newTable is the best we can do by permutations now
IF ~better[table, newTable] THEN LOOP;
Output["\nFactorized: "];
[] ← AlpsBool.PrintExpression[table, auxOutput, printLevel];
Output["\n"];
table ← newTable; ok ← TRUE;
ENDLOOP;
table ← newTable;
END;
FactorizeBest: PUBLIC PROC [table: AlpsBool.TableOfVariables, better: TableComparisonProc, printLevel: INT ← 2] RETURNS [newTable: AlpsBool.TableOfVariables, ok: BOOL] =
BEGIN
Triplet: TYPE = REF TripletRec;
TripletRec: TYPE = RECORD [expr: AlpsBool.Expression, caseXY: INT, nb: INT];
goodOnes: HashTable.Ref ← HashTable.Create[Hash, Equal, table.size];
RecordEach: EachRestrictionProc = {
caseXY: INT ← AlpsBool.NbOfCaseXY[table, expr];
newGoodOnes: HashTable.Ref ← HashTable.Create[Hash, Equal, table.size];
IzNoGood: HashTable.EachPairAction = {
thisExpr: AlpsBool.Expression ← NARROW[key];
refInt: REF INT ← NARROW[val];
thisNb: INT ← refInt^;
thisCaseXY: INT ← AlpsBool.NbOfCaseXY[table, thisExpr];
IF (thisCaseXY>caseXY AND thisNb>=nb) OR (thisCaseXY>=caseXY AND thisNb>nb) THEN quit ← TRUE;
};
MakeNewVizir: HashTable.EachPairAction = {
thisExpr: AlpsBool.Expression ← NARROW[key];
refInt: REF INT ← NARROW[val];
thisNb: INT ← refInt^;
thisCaseXY: INT ← AlpsBool.NbOfCaseXY[table, thisExpr];
IF ~((thisCaseXY<caseXY AND thisNb<=nb) OR (thisCaseXY<=caseXY AND thisNb<nb)) THEN [] ← HashTable.Store[newGoodOnes, key, val] ELSE Output["-"];
};
Output["."];
IF HashTable.Pairs[goodOnes, IzNoGood] THEN RETURN;
Output["!"];
[] ← HashTable.Store[newGoodOnes, expr, NEW[INT ← nb]];
[] ← HashTable.Pairs[goodOnes, MakeNewVizir];
goodOnes ← newGoodOnes;
};
ThisTimePrint: HashTable.EachPairAction = {
expr: AlpsBool.Expression ← NARROW[key];
nb: INT ← NARROW[val, REF INT]^;
caseXY: INT ← AlpsBool.NbOfCaseXY[table, expr];
AlpsBool.Output[
"Expr: ", AlpsBool.RopeFromExpression[table, expr, TRUE, printLevel],
"  NbCaseXY: ", Convert.RopeFromInt[caseXY],
Rope.Cat["  nb: ", Convert.RopeFromInt[nb], "\n"]];
};
EnumerateRestrictions[table, RecordEach];
[] ← HashTable.Pairs[goodOnes, ThisTimePrint];
RETURN [table, FALSE];
END;
FastPermute: PUBLIC PROC [table: AlpsBool.TableOfVariables, better: TableComparisonProc] RETURNS [newTable: AlpsBool.TableOfVariables, ok: BOOL ← FALSE] = {
FOR i: VarNb DECREASING IN (1 .. table.size) DO
Output["."];
newTable ← AlpsBool.Permute2Vars[table, i, i-1];
IF better[table, newTable] THEN {
Output["Permuting variable ", table[i].name, " (#", Convert.RopeFromInt[i], ") and variable "];
Output[table[i-1].name, " (#", Convert.RopeFromInt[i-1], ")\n"];
ok ← TRUE; table ← newTable;
};
ENDLOOP;
};
AllPermute: PUBLIC PROC [table: AlpsBool.TableOfVariables, better: TableComparisonProc, permutLimit: INT ← 99] RETURNS [newTable: AlpsBool.TableOfVariables] = {
minNbCaseXY: INT ← LAST[INT];
SigmaNbCaseXY: PROC [table: AlpsBool.TableOfVariables] RETURNS [nb: INT ← 0] = {
FOR outs: LIST OF AlpsBool.OutputRef ← table.outputs, outs.rest WHILE outs#NIL DO
nb ← nb + AlpsBool.NbOfCaseXY[table, outs.first.expr];
ENDLOOP;
};
AlreadyNbCaseXY: PROC [table: AlpsBool.TableOfVariables, varNb: VarNb] RETURNS [nb: INT ← 0] = {
AddCaseXY: AlpsBool.EachNodeProc = {quit ← expr.varNb<=varNb; IF expr.varNb>=varNb AND expr.case=caseXY THEN nb ← nb+1};
FOR outs: LIST OF AlpsBool.OutputRef ← table.outputs, outs.rest WHILE outs#NIL DO
AlpsBool.Enumerate[outs.first.expr, AddCaseXY];
ENDLOOP;
};
NbCaseXYOnVar: PROC [table: AlpsBool.TableOfVariables, varNb: VarNb] RETURNS [nb: INT ← 0] = {
AddCaseXY: AlpsBool.EachNodeProc = {quit ← expr.varNb<=varNb; IF expr.varNb=varNb AND expr.case=caseXY THEN nb ← nb+1};
FOR outs: LIST OF AlpsBool.OutputRef ← table.outputs, outs.rest WHILE outs#NIL DO
AlpsBool.Enumerate[outs.first.expr, AddCaseXY];
ENDLOOP;
};
AllPermuteRec: PROC [table: AlpsBool.TableOfVariables, varNb: VarNb] RETURNS [newTable: AlpsBool.TableOfVariables] = {
IF varNb=0 THEN RETURN[table];
IF AlreadyNbCaseXY[table, varNb]>minNbCaseXY THEN RETURN[table]; -- no good
IF NbCaseXYOnVar[table, varNb]=0 THEN RETURN[AllPermuteRec[table, varNb-1]];
Try first to get a NbCaseXYOnVar=0
FOR other: VarNb DECREASING IN [1..varNb) DO
Output["."];
newTable ← AlpsBool.Permute2Vars[table, varNb, other];
IF NbCaseXYOnVar[newTable, varNb]=0 THEN {
Output["!"]; RETURN[AllPermuteRec[newTable, varNb-1]];
};
IF better[table, newTable] THEN table ← newTable;
ENDLOOP;
Now the full recursive try
table ← AllPermuteRec[table, varNb-1];
minNbCaseXY ← MIN [minNbCaseXY, SigmaNbCaseXY[table]];
IF permutLimit=0 THEN {Output["\nAborted\n"]; RETURN[table]};
permutLimit ← permutLimit - 1;
FOR other: VarNb DECREASING IN [1..varNb) DO
Output["'"];
newTable ← AlpsBool.Permute2Vars[table, varNb, other];
newTable ← AllPermuteRec[newTable, varNb-1];
IF better[table, newTable] THEN {
Output["Permuting variable ", table[varNb].name, " (#", Convert.RopeFromInt[varNb], ") and variable ", Rope.Cat[table[other].name, " (#", Convert.RopeFromInt[other], ")\n"]];
table ← newTable;
};
ENDLOOP;
newTable ← table;
};
newTable ← AllPermuteRec[table, table.size-1];
};
BestPermute: PUBLIC PROC [table: AlpsBool.TableOfVariables, better: TableComparisonProc] RETURNS [newTable: AlpsBool.TableOfVariables, ok: BOOL ← FALSE] = {
FOR i: VarNb DECREASING IN [1 .. table.size) DO
bestTable: AlpsBool.TableOfVariables ← table;
bestJ: INT ← i;
FOR j: VarNb DECREASING IN [1..i) DO
Output["."];
newTable ← AlpsBool.Permute2Vars[table, i, j];
IF better[bestTable, newTable] THEN {
bestTable ← newTable; bestJ ← j;
};
ENDLOOP;
IF bestJ#i THEN {
It works!
Output["Permuting variable ", table[i].name, " (#", Convert.RopeFromInt[i], ") and variable "];
Output[table[bestJ].name, " (#", Convert.RopeFromInt[bestJ], ")\n"];
ok ← TRUE; table ← bestTable;
};
ENDLOOP;
newTable ← table;
};
BestPermuteInfinitely: PUBLIC PROC [table: AlpsBool.TableOfVariables, better: TableComparisonProc] RETURNS [newTable: AlpsBool.TableOfVariables] = {
ok: BOOL ← TRUE;
Output["Starting permutations\n"];
WHILE ok DO
newTable: AlpsBool.TableOfVariables;
Output["Permuting ...\n"];
[newTable, ok] ← BestPermute[table, better];
IF ok THEN table ← newTable;
ENDLOOP;
Output["Permutations finished\n"];
newTable ← table;
};
NbOfUseOfVarInTable: PUBLIC PROC [table: AlpsBool.TableOfVariables, varNb: VarNb] RETURNS [sigma: INT ← 0] =
BEGIN
FOR outs: LIST OF AlpsBool.OutputRef ← table.outputs, outs.rest WHILE outs#NIL DO
sigma ← sigma + AlpsBool.NbUsedVar[outs.first.expr, varNb];
ENDLOOP;
END;
RemoveAuxVar: PUBLIC PROC [table: AlpsBool.TableOfVariables, better: TableComparisonProc, printLevel: INT ← 2] RETURNS [newTable: AlpsBool.TableOfVariables, ok: BOOL] =
BEGIN
renum: REF RenumSeq ← NEW[RenumSeq[table.size]];
RenumSeq: TYPE = RECORD [contents: SEQUENCE size: VarNb OF VarNb];
Renum: RenumProc = {RETURN[renum[oldVarNb]]};
auxOutputs: LIST OF AlpsBool.OutputRef ← NIL;
min: INT ← LAST [INT];
minCaseXY: INT ← LAST [INT];
nb: INT 𡤀
IsGoingToBeDeleted: PROC [aux: AlpsBool.VarNb] RETURNS [BOOL ← FALSE] = {
FOR list: LIST OF AlpsBool.OutputRef ← auxOutputs, list.rest WHILE list#NIL DO
IF list.first.fedBackInput=aux THEN RETURN [TRUE];
ENDLOOP;
};
Find one of the less used auxiliary variable
FOR outs: LIST OF AlpsBool.OutputRef ← table.outputs, outs.rest WHILE outs#NIL DO
IF outs.first.type=aux THEN
BEGIN
use: INT ← NbOfUseOfVarInTable[table, outs.first.fedBackInput];
caseXY: INT ← AlpsBool.NbOfCaseXY[table, outs.first.expr];
IF caseXY=minCaseXY AND use=min THEN auxOutputs ← CONS [outs.first, auxOutputs];
IF caseXY<minCaseXY OR (caseXY=minCaseXY AND use<min) THEN {
minCaseXY ← caseXY; min ← use; auxOutputs ← LIST [outs.first];
};
END;
ENDLOOP;
IF auxOutputs=NIL THEN RETURN [table, FALSE];
-- prepares renum
nb ← 0; FOR i: VarNb IN (0 .. table.size) DO
IF ~IsGoingToBeDeleted[i] THEN {nb ← nb+1; renum[i] ← nb} ELSE renum[i] ← 0;
ENDLOOP;
nb ← 0; FOR list: LIST OF AlpsBool.OutputRef ← auxOutputs, list.rest WHILE list#NIL DO
nb ← nb+1;
ENDLOOP;
newTable ← AlpsBool.InitTableOfVariables[table.size-nb];
FOR i: VarNb IN (0 .. table.size) DO
IF Renum[i]#0 THEN newTable[Renum[i]].name ← table[i].name;
ENDLOOP;
FOR outs: LIST OF AlpsBool.OutputRef ← table.outputs, outs.rest WHILE outs#NIL DO
IF ~IsGoingToBeDeleted[outs.first.fedBackInput] THEN {
expr: AlpsBool.Expression ← outs.first.expr;
FOR list: LIST OF AlpsBool.OutputRef ← auxOutputs, list.rest WHILE list#NIL DO
expr ← AlpsBool.ExpanseAux[table, expr, list.first.expr, list.first.fedBackInput];
ENDLOOP;
expr ← AlpsBool.ChangeVars[newTable, expr, Renum];
AlpsBool.AddOutput[newTable, NEW[AlpsBool.OutputRec ← [name: outs.first.name, type: outs.first.type, expr: expr, fedBackInput: Renum[outs.first.fedBackInput]]]];
};
ENDLOOP;
-- is it better?
IF ~better[table, newTable] THEN RETURN [table, FALSE];
FOR list: LIST OF AlpsBool.OutputRef ← auxOutputs, list.rest WHILE list#NIL DO
Output["Deleted auxiliary variable: "];
[] ← AlpsBool.PrintExpression[table, list.first, printLevel];
Output[" Used ", Convert.RopeFromInt[min], " times\n"];
ENDLOOP;
RETURN [newTable, TRUE];
END;
Reverse: PUBLIC PROC [table: AlpsBool.TableOfVariables] RETURNS [newTable: AlpsBool.TableOfVariables] = {
Renum: RenumProc = {RETURN [IF oldVarNb=0 THEN 0 ELSE table.size-oldVarNb]};
newTable ← AlpsBool.InitTableOfVariables[table.size];
FOR i: VarNb IN [1 .. table.size) DO
newTable[Renum[i]].name ← table[i].name;
ENDLOOP;
FOR outs: LIST OF AlpsBool.OutputRef ← table.outputs, outs.rest WHILE outs#NIL DO
output: AlpsBool.OutputRef ← outs.first;
AlpsBool.AddOutput[newTable, NEW[AlpsBool.OutputRec ← [name: output.name, type: output.type, expr: AlpsBool.ChangeVars[newTable, output.expr, Renum], fedBackInput: Renum[output.fedBackInput]]]];
ENDLOOP;
};
END.