DIRECTORY
AlpsBool, AlpsHeur, Commander, Convert, GeneralRefTab, Process, Rope;

AlpsHeurImpl: CEDAR PROGRAM
IMPORTS AlpsBool, Convert, GeneralRefTab, Process, Rope

EXPORTS AlpsHeur = 

BEGIN
OPEN AlpsHeur;


ROPE: PUBLIC TYPE = Rope.ROPE;
VarNb: TYPE = AlpsBool.VarNb;
CompClass: TYPE = AlpsBool.CompClass;

OutputType: TYPE = AlpsBool.OutputType;


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;
};

Output: PUBLIC PROC [t1, t2, t3, t4, t5, t6: ROPE _ NIL] = AlpsBool.Output;


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};
exprs _ CONS[expr, exprs];
};
used: GeneralRefTab.Ref _ GeneralRefTab.Create[Hash, Equal, table.size];
bestNbUsed: INT _ FIRST[INT]; bestCaseXY: INT _ FIRST[INT];
FOR outs: LIST OF AlpsBool.OutputRef _ table.outputs, outs.rest WHILE outs#NIL DO
AlpsBool.Enumerate[outs.first.expr, RegisterExprRec];
ENDLOOP;
[] _ 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];
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;
IF ~better[table, newTable] THEN LOOP;
Output["\nFactorized: "]; 
[] _ AlpsBool.PrintExpression[table, auxOutput, printLevel];
Output["\n"];
table _ newTable; ok _ TRUE;
ENDLOOP;
table _ newTable; 
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]];
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;
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 {
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 {
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 _0;
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;
};
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.

üAlpsHeurImpl.mesa
Created by Bertrand Serlet, February 27, 1985 11:42:42 am PST
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. 

Types and data structures

Useful TableComparisonProc


Utilities

Alps heart
same interest, then
We register every expr
We select the best ones
We try to permute, now
newTable is the best we can do by permutations now
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;
Try first to get a NbCaseXYOnVar=0
Now the full recursive try
Output["Permuting variable ", table[varNb].name, " (#", Convert.RopeFromInt[varNb], ") and variable ", Rope.Cat[table[other].name, " (#", Convert.RopeFromInt[other], ")\n"]];
It works! 

Find one of the less used auxiliary variable 
�Ê#˜š
œ™J™=J™2—J™J™QJ™š
Ïk	˜	Jš
œE˜E—J˜•StartOfExpansion[]šÏbœ�œ
�˜Jš�œ0˜7J˜Jš�œ˜J˜Jš
�˜Jš�œ
˜J˜™J˜Jš�œ�œ
�œ�œ
˜Jšœ�œ˜J™Jšž	œ�œ˜%J˜Jšž
œ�œ˜'—J˜š
œ™J˜šžœ�œ˜3Jšœ6�œ
˜:Jš
œ[˜[Jš
œ[˜[Jš�œ�œ
�œ�œ˜&Jš�œ�œ
�œ�œ˜'Jš�œ�œ
�œ�œ˜&Jš�œ�œ
�œ�œ˜'Jš�œ�œ
�œ�œ˜&Jš�œ�œ˜J˜—J˜šžœ�œ˜3Jšœ$�œ
˜(Jš
œL˜LJš
œL˜LJšœ�œ
˜Jš�œ�œ�œ�œ
�œ�œ˜QJš�œ�œ�œ�œ
�œ�œ˜QJ˜—J˜šžœ�œ˜+Jšœ	�œ0˜<Jšœ	�œ0˜<Jšœ	�œ.˜:Jšœ	�œ.˜:Jšœ�œ
˜Jš�œ�œ�œ�œ
�œ�œ˜QJ˜—J™šžœ�œ˜,Jšœ	�œ0˜<Jšœ	�œ0˜<Jšœ	�œ.˜:Jšœ	�œ.˜:Jšœ�œ
˜Jš�œ�œ�œ�œ
�œ�œ˜QJ˜—J™šžœ�œ˜,Jšœ�œ
˜J˜——J˜™	J™Jš
Ïnœ�œ
�œ�œ�œ˜K—J˜™
J˜šŸœ�œ
�œ�œ&˜EJš
�˜Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ$˜$J˜Jš
œ)˜)Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜JšœÐ
�œf˜»Jš
œ\˜\Jšœ�œ7˜TJšœ�œ7˜TJš�œ
˜—J˜šÐbnœ�œ
�œ�œ&˜LJš
�˜Jš
œ$˜$Jš
œ˜Jš
œ)˜)Jš
œ"˜"Jš
œ"˜"Jš
œ"˜"Jš
œ"˜"Jš
œ"˜"Jš
œ"˜"Jš
œŠ˜ŠJšœ�œ7˜TJš�œ
˜—J˜šŸœ�œ
�œ$�œ	�œ
�œ�œ˜mJš
�˜–> -- [key: GeneralRefTab.Key] RETURNS [hashIndex: CARDINAL] -- šžœÐck=œ˜^Jšœ�œ˜(Jš�œ
�œ˜J˜—–I -- [val1: GeneralRefTab.Val, val2: GeneralRefTab.Val] RETURNS [BOOL] -- šžœ¡Hœ˜kJšœ�œ˜*Jšœ�œ˜*Jš�œ&�œ%�œ˜ZJ˜—šŸœ
�
œ¡?œ˜jJš
œ=˜=Jšœ�œ
�œ�œ�œ
�œ
�œ
�œ�œ
�œ˜@J˜Jš
œ-˜-Jš
œ˜—–P -- [key: GeneralRefTab.Key, val: GeneralRefTab.Val] RETURNS [quit: BOOLEAN] -- šž
œ¡Oœ˜Jšœ�œ
�œ�œ˜Jšœ�œ˜(Jšœ�œ$˜/Jšœ�œ
˜
Jš�œ�œ
�œ
˜Jš�œ�œ5�œ�œ˜cJš�œ�œ�œ
�œ
˜7Jš�œ�œ�œ�œ˜LJš
œ™Jšœ�œ˜J˜—Jš
œH˜HJš
œ�œ�œ
�œ�œ�œ
�œ˜;Jš
œ™š�œ�œ
�œ/�œ�œ
�˜QJš
œ5˜5Jš�œ
˜—Jš
œ™Jš
œ.˜.Jš�œ
˜—J˜šžœ�œ˜,Jš
œ7˜7J˜J˜—šŸœ�œ
�œ˜¡
–> -- [key: GeneralRefTab.Key] RETURNS [hashIndex: CARDINAL] -- šžœ¡=œ˜^Jšœ�œ˜(Jš�œ
�œ˜J˜—–I -- [val1: GeneralRefTab.Val, val2: GeneralRefTab.Val] RETURNS [BOOL] -- šžœ¡Hœ˜kJšœ�œ˜*Jšœ�œ˜*Jš�œ&�œ%�œ˜ZJ˜—šŸœ�œ9�œ	˜NJš
œ<˜<Jšœ�œ
�œ�œ�œ
�œ
�œ
�œ�œ
�œ˜@Jš�œ�œ
�œ
˜*Jš
œ˜Jš
œ,˜,J˜—J˜Jš
œP˜PJš�œ
�œ
�œ2�œ	�œ
�œ'�œ
˜‰
š�œ'�˜.Jš
œS˜S–[]šžœ"˜:Jšœ�œ˜(Jšœ�œ
�œ�œ˜Jš
œI˜Išž
œ"˜,Jšœ�œ˜+J˜—Jš
œA˜Aš�œ�œ�˜&JšœK�œ�œ˜WJšœK�œ�œ˜XJš�œ
˜—Jš
œ-˜-J˜—–[]šžœ"˜8Jšœ�œ˜(Jšœ�œ
�œ�œ˜Jš�œ�œ.˜?J˜—J˜Jš
œA˜AJš�œ>�œ
�œ
˜JJš
œ˜Jš�œ
˜—J˜—J˜J˜Jšœ�œ˜%J˜š	 	žœ�œ
�œC�œ(˜Ž
Jš
�˜šžœ˜Jš	œ
�œ�œ!�œ
�œ˜L—Jš
œ7˜7Jš
œ7˜7Jš
œ(˜(š�œ
�œ�˜$Jš
œ(˜(Jš�œ
˜—š�œ
�œ
�œ2�œ	�œ
�˜Zšœ�œ˜7Jš
œ4˜4Jš
œI˜IJš
œ˜—Jš�œ
˜—š�œ
�œ
�œ2�œ	�œ
�˜ZJš�œ�œo˜Ž
Jš�œ
˜—Jš�œ
˜—J˜šŸ
œ�œ
�œM�œ�œ+�œ˜©
Jš
�˜Jšœ�œ
˜š�œ�œ
�œ3�œ�œ
�œ
˜Xšœ �œ˜:Jš
œb˜bJš
œ˜—Jš�œ
�œ
�œ �œ˜IJš
œ-˜-Jš
œ™š�œ
�
œ
�œ�˜-Jš
œO˜OJš
œ˜Jš�œ�œ˜=Jš�œ
˜—Jš
œ2™2Jš�œ�œ
�œ
˜&Jš
œ˜Jš
œ<˜<Jš
œ
˜
Jšœ�œ
˜Jš�œ
˜—Jš
œ˜Jš�œ
˜—J˜šŸ
œ�œ
�œM�œ�œ+�œ™©
Jš
�™Jšœ	�œ�œ™Jš	œ�œ�œ%�œ�œ™LJš
œL™L–> -- [key: GeneralRefTab.Key] RETURNS [hashIndex: CARDINAL] -- šžœ¡=œ™^Jšœ�œ™(Jš�œ
�œ™J™—–I -- [val1: GeneralRefTab.Val, val2: GeneralRefTab.Val] RETURNS [BOOL] -- šžœ¡Hœ™kJšœ�œ™*Jšœ�œ™*Jš�œ&�œ%�œ™ZJ™—šž
œ™#Jšœ�œ$™/Jš
œO™Ošžœ"™*Jšœ �œ™,Jšœ�œ
�œ�œ™Jšœ�œ™Jšœ�œ(™7Jš�œ�œ
�œ�œ�œ�œ
™]J™—šžœ"™.Jšœ �œ™,Jšœ�œ
�œ�œ™Jšœ�œ™Jšœ�œ(™7Jš�œ�œ
�œ�œ
�œ1�œ
™•
J™—J™Jš�œ)�œ
�œ
™7J™Jšœ,�œ
�œ™;Jš
œ1™1Jš
œ™J™—šž
œ"™/Jšœ�œ™(Jš	œ�œ�œ�œ
�œ™ Jšœ�œ$™/š
œ™Jšœ3�œ™FJš
œ-™-Jš
œ3™3—J™—Jš
œ)™)Jš
œ2™2Jš�œ	�œ™Jš�œ
™—J˜šŸœ�œ
�œA�œ+�œ�œ˜œ
š�œ
�
œ
�œ�˜/Jš
œ˜Jš
œ0˜0š�œ�œ˜!Jš
ϣ
˜£
Jšœ�œ˜Jš
œ˜—Jš�œ
˜—J˜—J˜š
Ÿ
œ�œ
�œN�œ�œ*˜ 
Jšœ
�œ�œ
�œ˜šŸ
œ�œ$�œ�œ	˜Pš�œ�œ
�œ/�œ�œ
�˜QJš
œ6˜6Jš�œ
˜—J˜—šŸœ�œ2�œ�œ	˜`Jšž	œ5�œ�œ�œ˜xš�œ�œ
�œ/�œ�œ
�˜QJš
œ/˜/Jš�œ
˜—J˜—šŸ
œ�œ2�œ�œ	˜^Jšž	œ5�œ�œ�œ˜wš�œ�œ
�œ/�œ�œ
�˜QJš
œ/˜/Jš�œ
˜—J˜—šŸ
œ�œ2�œ*˜vJš�œ	�œ
�œ˜Jš�œ+�œ
�œ	Ïc
˜KJš�œ�œ
�œ ˜LJš
œ"™"š�œ�
œ
�œ�˜,Jš
œ˜Jš
œ6˜6š�œ"�œ
�
˜*Jšœ
�œ#˜6J˜—Jš�œ�œ˜1Jš�œ
˜—Jš
œ™Jš
œ&˜&Jšœ�œ%˜6Jš�œ�œ�œ	˜=Jš
œ˜š�œ�
œ
�œ�˜,Jš
œ˜Jš
œ6˜6Jš
œ,˜,š�œ�œ˜!Jš
Ϩ
™®
Jš
œ˜J˜—Jš�œ
˜—Jš
œ˜J˜—Jš
œ.˜.J˜—J˜šŸœ�œ
�œA�œ+�œ�œ˜œ
š�œ
�
œ
�œ�˜/Jš
œ-˜-Jšœ�œ˜š�œ
�
œ
�œ�˜$Jš
œ˜Jš
œ.˜.š�œ�œ˜%Jš
œ ˜ J˜—Jš�œ
˜—š�œ	�œ˜Jš
œ
™
Jš
œ¦
˜¦
Jšœ�œ˜J˜—Jš�œ
˜—Jš
œ˜J˜—J˜šŸœ�œ
�œA�œ*˜”
Jšœ�œ�œ
˜J˜"š�œ�œ
˜Jš
œ$˜$J˜Jš
œ,˜,Jš�œ�œ˜Jš�œ
˜—J˜"Jš
œ˜J˜—J™š
Ÿœ�œ
�œ2�œ	�œ˜lJš
�˜š�œ�œ
�œ/�œ�œ
�˜QJš
œ;˜;Jš�œ
˜—Jš�œ
˜—J˜šŸœ�œ
�œM�œ�œ+�œ˜¨
Jš
�˜J–[]šœ�œ�œ˜0Jš
žœ�œ�œ�œ
�œ˜BJšžœ�œ˜-Jšœ�œ
�œ�œ˜.Jšœ�œ�œ�œ˜Jšœ�œ�œ�œ˜Jšœ�œ˜š
Ÿœ�œ�œ�œ�œ˜Iš�œ�œ
�œ,�œ�œ
�˜NJš�œ�œ
�œ�œ˜2Jš�œ
˜—J˜—Jš
œ-™-š�œ�œ
�œ/�œ�œ
�˜Qš�œ�œ
˜Jš
�˜Jšœ�œ7˜?Jšœ�œ/˜:Jš�œ�œ	�œ�œ˜Pš�œ�œ�œ
�œ˜<Jšœ,�œ˜>Jš
œ˜—Jš�œ
˜—Jš�œ
˜—Jš
�œ�œ
�œ
�œ	�œ˜-J˜šœ�œ
�œ�˜,Jš�œ�œ�œ˜LJš�œ
˜—šœ�œ�œ
�œ,�œ�œ
�˜VJš
œ
˜
Jš�œ
˜—Jš
œ8˜8š�œ
�œ�˜$Jš�œ�œ)˜;Jš�œ
˜—š�œ�œ
�œ/�œ�œ
�˜Qš�œ.�œ˜6Jš
œ,˜,š�œ�œ
�œ,�œ�œ
�˜NJš
œR˜RJš�œ
˜—Jš
œ3˜3Jšœ�œ�
˜¡
J˜—Jš�œ
˜—J˜Jš�œ�œ
�œ	�œ˜7š�œ�œ
�œ,�œ�œ
�˜NJš
œ(˜(Jš
œ=˜=Jš
œ7˜7Jš�œ
˜—Jš�œ�œ˜Jš�œ
˜—J˜š œ�œ
�œ$�œ*˜iJ–[]š
žœ�œ�œ�œ�œ˜LJš
œ5˜5š�œ
�œ�œ
˜%Jš
œ(˜(Jš�œ
˜—š�œ�œ
�œ/�œ�œ
�˜QJš
œ(˜(Jšœ�œ¢
˜Â
Jš�œ
˜—Jš
œ˜——J˜Jš�œ
˜—J˜—…—Dlg‹