<> <> <> <<>> <> <<>> 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 oldAreanewSize THEN RETURN [TRUE]; IF oldSizenewDeep 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> 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> 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 = { <<[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^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=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; <> <> <> <> <> <> <> <> <> <> <> <> <> <caseXY AND thisNb>=nb) OR (thisCaseXY>=caseXY AND thisNb>nb) THEN quit _ TRUE;>> <<};>> <> <> <> <> <> <> <<};>> <> <> <> <<[] _ HashTable.Store[newGoodOnes, expr, NEW[INT _ nb]];>> <<[] _ HashTable.Pairs[goodOnes, MakeNewVizir];>> <> <<};>> <> <> <> <> <> <<"Expr: ", AlpsBool.RopeFromExpression[table, expr, TRUE, printLevel], >> <<" NbCaseXY: ", Convert.RopeFromInt[caseXY], >> <> <<};>> <> <<[] _ HashTable.Pairs[goodOnes, ThisTimePrint];>> <> <> 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