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

AlpsHeurImpl: CEDAR PROGRAM
IMPORTS AlpsBool, Convert, HashTable, Process

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: 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: 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 = {
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};
exprs _ CONS[expr, exprs];
};
used: HashTable.Table _ HashTable.Create[hash: Hash, equal: Equal, mod: 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;
[] _ 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];
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 "];
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]];
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 "];
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 _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.


LAlpsHeurImpl.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. 

Types and data structures

Useful TableComparisonProc


Utilities

Alps heart
[key: HashTable.Key, value: HashTable.Value] RETURNS [quit: BOOLEAN _ FALSE]
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: 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;
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š
œA˜A—J˜•StartOfExpansion[]šÏbœ�œ
�˜Jš�œ&˜-J˜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œ�œ
�œ�œ�œ˜G—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: HashTable.Key] RETURNS [CARDINAL]š œ�œ�œ�œ˜6Jšœ�œ˜(Jš�œ
�œ˜J˜—–= -- [key1: HashTable.Key, key2: HashTable.Key] RETURNS [BOOL]š œ�œ�œ�œ˜:Jšœ�œ˜*Jšœ�œ˜*Jš�œ&�œ%�œ˜ZJ˜—šŸœ
�
œÐck?œ˜jJš
œ;˜;Jšœ�œ
�œ�œ�œ
�œ
�œ
�œ�œ
�œ˜DJ˜Jš
œ)˜)Jš
œ˜—–P -- [key: HashTable.Key, value: HashTable.Value] RETURNS [quit: BOOLEAN _ FALSE]šž
œ˜+Jš
¡L™LJšœ�œ
�œ�œ˜ Jšœ�œ˜(Jšœ�œ$˜/Jšœ�œ
˜
Jš�œ�œ
�œ
˜Jš�œ�œ5�œ�œ˜cJš�œ�œ�œ
�œ
˜7Jš�œ�œ�œ�œ˜LJš
œ™Jšœ�œ˜J˜—Jš
œT˜TJš
œ�œ�œ
�œ�œ�œ
�œ˜;Jš
œ™š�œ�œ
�œ/�œ�œ
�˜QJš
œ5˜5Jš�œ
˜—Jš
œ™Jš
œ*˜*Jš�œ
˜—J˜šžœ�œ˜,Jš
œ7˜7J˜J˜—šŸœ�œ
�œ˜¡
–+ -- [key: HashTable.Key] RETURNS [CARDINAL]š œ�œ�œ�œ˜6Jšœ�œ˜(Jš�œ
�œ˜J˜—–= -- [key1: HashTable.Key, key2: HashTable.Key] RETURNS [BOOL]š œ�œ�œ�œ˜:Jšœ�œ˜*Jšœ�œ˜*Jš�œ&�œ%�œ˜ZJ˜—šŸœ�œ7�œ	˜LJš
œ:˜:Jšœ�œ
�œ�œ�œ
�œ
�œ
�œ�œ
�œ˜DJš�œ�œ
�œ
˜*Jš
œ˜Jš
œ(˜(J˜—J˜Jš
œ\˜\Jš�œ
�œ
�œ2�œ	�œ
�œ'�œ
˜‰
š�œ#�˜*Jš
œ_˜_–[]šžœ˜6Jšœ�œ˜(Jšœ�œ
�œ�œ˜ Jš
œU˜Ušž
œ˜(Jšœ�œ˜+J˜—Jš
œA˜Aš�œ�œ�˜&JšœG�œ�œ˜SJšœG�œ�œ˜TJš�œ
˜—Jš
œ)˜)J˜—–[]šžœ˜4Jšœ�œ˜(Jšœ�œ
�œ�œ˜ Jš�œ�œ.˜?J˜—J˜Jš
œ=˜=Jš�œ:�œ
�œ
˜FJš
œ˜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š
œD™Dšž
œ™#Jšœ�œ$™/Jš
œG™Gšžœ™&Jšœ �œ™,Jšœ�œ
�œ�œ™Jšœ�œ™Jšœ�œ(™7Jš�œ�œ
�œ�œ�œ�œ
™]J™—šžœ™*Jšœ �œ™,Jšœ�œ
�œ�œ™Jšœ�œ™Jšœ�œ(™7Jš�œ�œ
�œ�œ
�œ-�œ
™‘
J™—J™Jš�œ%�œ
�œ
™3J™Jšœ(�œ
�œ™7Jš
œ-™-Jš
œ™J™—šž
œ™+Jšœ�œ™(Jš	œ�œ�œ�œ
�œ™ Jšœ�œ$™/š
œ™Jšœ3�œ™FJš
œ-™-Jš
œ3™3—J™—Jš
œ)™)Jš
œ.™.Jš�œ	�œ™Jš�œ
™—J˜šŸœ�œ
�œA�œ+�œ�œ˜œ
š�œ
�
œ
�œ�˜/Jš
œ˜Jš
œ0˜0š�œ�œ˜!Jš
œ_˜_Jš
œA˜AJšœ�œ˜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š
œD˜DJšœ�œ˜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˜—…—CXcÈ