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;
};
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: GeneralRefTab.HashProc
-- [key: GeneralRefTab.Key] RETURNS [hashIndex: CARDINAL] -- = {
expr: AlpsBool.Expression ← NARROW[key];
RETURN[CARDINAL[expr.varNb]];
};
Equal: GeneralRefTab.EqualProc
-- [val1: GeneralRefTab.Val, val2: GeneralRefTab.Val] 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] -- = {
val: GeneralRefTab.Val ← GeneralRefTab.Fetch[used, expr].val;
nbUsed: REF INT ← IF val=NIL THEN NEW[INT ← 0] ELSE NARROW[val];
nbUsed^ ← nbUsed^ + 1;
[] ← GeneralRefTab.Store[used, expr, nbUsed];
};
FindBestPairs: GeneralRefTab.EachPairAction
-- [key: GeneralRefTab.Key, val: GeneralRefTab.Val] RETURNS [quit: BOOLEAN] -- = {
nbUsed: REF INT ← NARROW[val];
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: GeneralRefTab.Ref ← GeneralRefTab.Create[Hash, Equal, 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
[] ← GeneralRefTab.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: GeneralRefTab.HashProc
-- [key: GeneralRefTab.Key] RETURNS [hashIndex: CARDINAL] -- = {
expr: AlpsBool.Expression ← NARROW[key];
RETURN[CARDINAL[expr.varNb]];
};
Equal: GeneralRefTab.EqualProc
-- [val1: GeneralRefTab.Val, val2: GeneralRefTab.Val] 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: GeneralRefTab.Ref, expr: AlpsBool.Expression, nb:
INT ← 1] = {
val: GeneralRefTab.Val ← GeneralRefTab.Fetch[ref, expr].val;
refInt: REF INT ← IF val=NIL THEN NEW[INT ← 0] ELSE NARROW[val];
IF ~interestProc[table, expr] THEN RETURN;
refInt^ ← refInt^ + nb;
[] ← GeneralRefTab.Store[ref, expr, refInt];
};
restrictions: GeneralRefTab.Ref ← GeneralRefTab.Create[Hash, Equal, table.size];
FOR outputs: LIST OF AlpsBool.OutputRef ← table.outputs, outputs.rest WHILE outputs#NIL DO Add[restrictions, outputs.first.expr] ENDLOOP;
WHILE GeneralRefTab.GetSize[restrictions]#0
DO
newRestrictions: GeneralRefTab.Ref ← GeneralRefTab.Create[Hash, Equal, table.size];
AddExprToNewRestrictions: GeneralRefTab.EachPairAction = {
expr: AlpsBool.Expression ← NARROW[key];
refInt: REF INT ← NARROW[val];
exprs: GeneralRefTab.Ref ← GeneralRefTab.Create[Hash, Equal, table.size];
AddExprLow: GeneralRefTab.EachPairAction = {
Add[newRestrictions, NARROW[key], refInt^];
};
Process.Yield[]; Process.SetPriority[Process.priorityBackground];
FOR varNb: VarNb
IN [1..table.size)
DO
[] ← GeneralRefTab.Store[exprs, AlpsBool.ExprWhenVarIs[table, expr, varNb, TRUE], NIL];
[] ← GeneralRefTab.Store[exprs, AlpsBool.ExprWhenVarIs[table, expr, varNb, FALSE], NIL];
ENDLOOP;
[] ← GeneralRefTab.Pairs[exprs, AddExprLow];
};
ApplyToEachInteresting: GeneralRefTab.EachPairAction = {
expr: AlpsBool.Expression ← NARROW[key];
refInt: REF INT ← NARROW[val];
IF refInt^>1 THEN quit ← eachRestriction[table, expr, refInt^];
};
[] ← GeneralRefTab.Pairs[restrictions, AddExprToNewRestrictions];
IF GeneralRefTab.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: GeneralRefTab.Ref ← GeneralRefTab.Create[Hash, Equal, table.size];
Hash: GeneralRefTab.HashProc -- [key: GeneralRefTab.Key] RETURNS [hashIndex: CARDINAL] -- = {
expr: AlpsBool.Expression ← NARROW[key];
RETURN[CARDINAL[expr.varNb]];
};
Equal: GeneralRefTab.EqualProc -- [val1: GeneralRefTab.Val, val2: GeneralRefTab.Val] 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]]
};
RecordEach: EachRestrictionProc = {
caseXY: INT ← AlpsBool.NbOfCaseXY[table, expr];
newGoodOnes: GeneralRefTab.Ref ← GeneralRefTab.Create[Hash, Equal, table.size];
IzNoGood: GeneralRefTab.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: GeneralRefTab.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 [] ← GeneralRefTab.Store[newGoodOnes, key, val] ELSE Output["-"];
};
Output["."];
IF GeneralRefTab.Pairs[goodOnes, IzNoGood] THEN RETURN;
Output["!"];
[] ← GeneralRefTab.Store[newGoodOnes, expr, NEW[INT ← nb]];
[] ← GeneralRefTab.Pairs[goodOnes, MakeNewVizir];
goodOnes ← newGoodOnes;
};
ThisTimePrint: GeneralRefTab.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];
[] ← GeneralRefTab.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 ", Rope.Cat[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 ", Rope.Cat[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;
};