TableConstraintsImpl.Mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Rick Beach, June 6, 1985 2:08:46 pm PDT
DIRECTORY
Convert,
LinearSolver,
SymTab,
Rope,
TableBase,
TableConstraints,
TableLayout,
TSTypes;
TableConstraintsImpl: CEDAR PROGRAM
IMPORTS Convert, LinearSolver, SymTab, Rope, TableBase, TableLayout, TSTypes
EXPORTS TableConstraints
= BEGIN
ROPE: TYPE = Rope.ROPE;
constraintSymTab: SymTab.Ref;
SolveConstraints: PUBLIC PROCEDURE [table: TableBase.RefTable] = {
Solve row constraints first
constraintSymTab ← SymTab.Create[101];
table.tableau ← LinearSolver.Init[];
IF table.rowConstraints # NIL THEN
EstablishConstraints[table, table.rowConstraints];
TableBase.EnumerateByRows[table, GenerateRowConstraints];
IF NOT LinearSolver.Satisfiable[table.tableau] THEN
ERROR TableBase.ImplementationError["Unsatisifiable row constraints"];
table.rowGridPositions ← NEW[TableBase.GridVector[table.rowGrids+1]];
FOR i: TableBase.GridNumber IN [0..table.rowGrids] DO
table.rowGridPositions.grid[i] ← TSTypes.Pt[LinearSolver.Solution[table.tableau, LookUpUnknown[table.tableau, Rope.Concat["gy", Convert.RopeFromInt[i]]]]];
ENDLOOP;
Determine the box positions
{
SetBoxY: TableBase.EnumeratedEntryProc ~ {
WITH entry SELECT FROM
box: TableBase.RefTableBox => {
boxNumber: ROPE ~ Convert.RopeFromInt[box.left*1000 + box.top];
box.y ← TSTypes.Pt[LinearSolver.Solution[table.tableau, LookUpUnknown[table.tableau, Rope.Concat["y", boxNumber]]]];
box.y ← box.y.SubDimn[box.yOffset];
};
ENDCASE;
};
TableBase.EnumerateByRows[table, SetBoxY];
};
Solve column constraints next
constraintSymTab ← SymTab.Create[101];
table.tableau ← LinearSolver.Init[];
IF table.colConstraints # NIL THEN
EstablishConstraints[table, table.colConstraints];
TableBase.EnumerateByRows[table, GenerateColumnConstraints];
IF NOT LinearSolver.Satisfiable[table.tableau] THEN
ERROR TableBase.ImplementationError["Unsatisifiable column constraints"];
table.colGridPositions ← NEW[TableBase.GridVector[table.columnGrids+1]];
FOR i: TableBase.GridNumber IN [0..table.columnGrids] DO
table.colGridPositions.grid[i] ← TSTypes.Pt[LinearSolver.Solution[table.tableau, LookUpUnknown[table.tableau, Rope.Concat["gx", Convert.RopeFromInt[i]]]]];
ENDLOOP;
Determine the box positions
{
SetBoxX: TableBase.EnumeratedEntryProc ~ {
WITH entry SELECT FROM
box: TableBase.RefTableBox => {
boxNumber: ROPE ~ Convert.RopeFromInt[box.left*1000 + box.top];
box.x ← TSTypes.Pt[LinearSolver.Solution[table.tableau, LookUpUnknown[table.tableau, Rope.Concat["x", boxNumber]]]];
box.x ← box.x.AddDimn[box.xOffset];
};
ENDCASE;
};
TableBase.EnumerateByRows[table, SetBoxX];
};
};
EstablishConstraints: PROC [table: TableBase.RefTable, constraintList: LIST OF TableBase.RefConstraint] ~ {
FOR c: LIST OF TableBase.RefConstraint ← constraintList, c.rest WHILE c # NIL DO
lsConstraint: LinearSolver.Constraint;
FOR l: LIST OF TableBase.Coefficient ← c.first.coefficients, l.rest WHILE l # NIL DO
unknown: LinearSolver.Unknown ~ IF l.first.unknown.IsEmpty THEN table.tableau.unity ELSE LookUpUnknown[table.tableau, l.first.unknown];
lsConstraint ← CONS[NEW[LinearSolver.LinearMonomial ← [l.first.coefficient, unknown]], lsConstraint];
ENDLOOP;
IF lsConstraint = NIL THEN LOOP;
IF c.first.equality THEN
LinearSolver.AssertZero[table.tableau, lsConstraint]
ELSE
LinearSolver.AssertGEZero[table.tableau, lsConstraint];
ENDLOOP;
};
GenerateRowConstraints: TableBase.EnumeratedEntryProc = {
WITH entry SELECT FROM
box: TableBase.RefTableBox =>{
boxNumber: ROPE ~ Convert.RopeFromInt[box.left*1000 + box.top];
boxY: LinearSolver.Unknown ~ LookUpUnknown[table.tableau, Rope.Concat["y", boxNumber]];
gridTop: LinearSolver.Unknown ~ LookUpUnknown[table.tableau, Rope.Concat["gy", Convert.RopeFromInt[box.top]]];
gridBottom: LinearSolver.Unknown ~ LookUpUnknown[table.tableau, Rope.Concat["gy", Convert.RopeFromInt[box.bottom]]];
extents: TSTypes.Dimensions ← TableLayout.AlignExtents[table, box];
SELECT box.rowAlignment FROM
flushTop => {
LinearSolver.AssertZero3[table.tableau, 1,boxY, extents[up].texPts,table.tableau.unity, -1,gridTop];
LinearSolver.AssertGEZero3[table.tableau, 1,boxY, -(extents[down].texPts),table.tableau.unity, -1,gridBottom];
};
flushBottom => {
LinearSolver.AssertZero3[table.tableau, 1,gridBottom, extents[down].texPts,table.tableau.unity, -1,boxY];
LinearSolver.AssertGEZero3[table.tableau, 1,gridTop, -(extents[up].texPts),table.tableau.unity, -1,boxY];
};
center => {
LinearSolver.AssertGEZero3[table.tableau, 1,gridTop, -(extents[down].texPts+extents[up].texPts),table.tableau.unity, -1,gridBottom];
LinearSolver.AssertZero[table.tableau, LIST[
LinearSolver.C[[1.0, gridBottom]],
LinearSolver.C[[extents[down].texPts-extents[up].texPts, table.tableau.unity]],
LinearSolver.C[[1.0, gridTop]],
LinearSolver.C[[-2.0, boxY]]]];
};
topBaseline,
bottomBaseline,
centerOnTopBaseline,
centerOnBottomBaseline => {
rowNumber: ROPE ~ Convert.RopeFromInt[box.top*1000 + box.bottom];
rowY: LinearSolver.Unknown ~ LookUpUnknown[table.tableau, Rope.Concat["r", rowNumber]];
LinearSolver.AssertZero2[table.tableau, 1,rowY, -1,boxY];
LinearSolver.AssertGEZero2[table.tableau, 1,rowY, -1,gridBottom];
LinearSolver.AssertGEZero3[table.tableau, 1,rowY, -(extents[down].texPts),table.tableau.unity, -1,gridBottom];
LinearSolver.AssertGEZero3[table.tableau, 1,gridTop, -(extents[up].texPts),table.tableau.unity, -1,rowY];
};
ENDCASE => ERROR TableBase.UnimplementedCase;
IF NOT LinearSolver.Satisfiable[table.tableau] THEN
ERROR TableBase.ImplementationError["Unsatisifiable constraints"]
};
rule: TableBase.RefTableRule => NULL;
background: TableBase.RefTableBackground => NULL;
ENDCASE => ERROR;
};
GenerateColumnConstraints: TableBase.EnumeratedEntryProc = {
WITH entry SELECT FROM
box: TableBase.RefTableBox =>{
boxNumber: ROPE ~ Convert.RopeFromInt[box.left*1000 + box.top];
boxX: LinearSolver.Unknown ~ LookUpUnknown[table.tableau, Rope.Concat["x", boxNumber]];
gridLeft: LinearSolver.Unknown ~ LookUpUnknown[table.tableau, Rope.Concat["gx", Convert.RopeFromInt[box.left]]];
gridRight: LinearSolver.Unknown ~ LookUpUnknown[table.tableau, Rope.Concat["gx", Convert.RopeFromInt[box.right]]];
extents: TSTypes.Dimensions ← TableLayout.AlignExtents[table, box];
IF box.alignOnChar THEN { -- oh, what a crock
colNumber: ROPE ~ Convert.RopeFromInt[box.left*1000 + box.right];
colX: LinearSolver.Unknown ~ LookUpUnknown[table.tableau, Rope.Concat["c", colNumber]];
LinearSolver.AssertZero2[table.tableau, 1,colX, -1,boxX];
LinearSolver.AssertGEZero2[table.tableau, 1,colX, -1,gridLeft];
LinearSolver.AssertGEZero3[table.tableau, 1,colX, -(extents[left].texPts),table.tableau.unity, -1,gridLeft];
LinearSolver.AssertGEZero2[table.tableau, 1,gridRight, -1,colX];
LinearSolver.AssertGEZero3[table.tableau, 1,gridRight, -(extents[right].texPts),table.tableau.unity, -1,colX];
}
ELSE SELECT box.colAlignment FROM
flushLeft => {
LinearSolver.AssertZero3[table.tableau, 1,gridLeft, extents[left].texPts,table.tableau.unity, -1,boxX];
LinearSolver.AssertGEZero3[table.tableau, 1,gridRight, -(extents[right].texPts),table.tableau.unity, -1,boxX];
};
flushRight => {
LinearSolver.AssertZero3[table.tableau, 1,boxX, extents[right].texPts,table.tableau.unity, -1,gridRight];
LinearSolver.AssertGEZero3[table.tableau, 1,boxX, -(extents[left].texPts),table.tableau.unity, -1,gridLeft];
};
center => {
LinearSolver.AssertGEZero3[table.tableau, 1,gridRight, -(extents[left].texPts+extents[right].texPts),table.tableau.unity, -1,gridLeft];
LinearSolver.AssertZero[table.tableau, LIST[
LinearSolver.C[[1.0, gridLeft]],
LinearSolver.C[[extents[left].texPts-extents[right].texPts, table.tableau.unity]],
LinearSolver.C[[1.0, gridRight]],
LinearSolver.C[[-2.0, boxX]]]];
};
ENDCASE => ERROR TableBase.UnimplementedCase;
IF NOT LinearSolver.Satisfiable[table.tableau] THEN
ERROR TableBase.ImplementationError["Unsatisifiable constraints"]
};
rule: TableBase.RefTableRule => NULL;
background: TableBase.RefTableBackground => NULL;
ENDCASE => ERROR;
};
LookUpUnknown: PROCEDURE [tableau: LinearSolver.Tableau, name: ROPE] RETURNS [v: LinearSolver.Unknown] = {
found: BOOLEAN;
val: REF;
[found, val] ← SymTab.Fetch[constraintSymTab, name];
IF found THEN
v ← NARROW[val, LinearSolver.Unknown]
ELSE {
v ← LinearSolver.NewUnknown[tableau, name];
LinearSolver.Restrict[tableau, v];
[] ← SymTab.Insert[constraintSymTab, name, v]
};
};
END.
GenerateRowConstraints: PROC [table: TableBase.RefTable] ~ {
GenerateRowConstraint: TableBase.EnumeratedEntryProc = {
WITH entry SELECT FROM
box: TableBase.RefTableBox =>{
boxNumber: ROPE ~ Convert.RopeFromInt[box.left*1000 + box.top];
boxY: LinearSolver.Unknown ~ LookUpUnknown[table.tableau, Rope.Concat["y", boxNumber]];
gridTop: LinearSolver.Unknown ~ LookUpUnknown[table.tableau, Rope.Concat["gy", Convert.RopeFromInt[box.top]]];
gridBottom: LinearSolver.Unknown ~ LookUpUnknown[table.tableau, Rope.Concat["gy", Convert.RopeFromInt[box.bottom]]];
extents: TSTypes.Dimensions ← TableLayout.AlignExtents[table, box];
SELECT box.rowAlignment FROM
flushTop => {
LinearSolver.AssertZero3[table.tableau, 1,boxY, extents[up].texPts,table.tableau.unity, -1,gridTop];
LinearSolver.AssertGEZero3[table.tableau, 1,boxY, -(extents[down].texPts),table.tableau.unity, -1,gridBottom];
};
flushBottom => {
LinearSolver.AssertZero3[table.tableau, 1,gridBottom, extents[down].texPts,table.tableau.unity, -1,boxY];
LinearSolver.AssertGEZero3[table.tableau, 1,gridTop, -(extents[up].texPts),table.tableau.unity, -1,boxY];
};
center => {
LinearSolver.AssertGEZero3[table.tableau, 1,gridTop, -(extents[down].texPts+extents[up].texPts),table.tableau.unity, -1,gridBottom];
LinearSolver.AssertZero[table.tableau, LIST[
LinearSolver.C[[0.5, gridBottom]],
LinearSolver.C[[0.5*(extents[down].texPts-extents[up].texPts), table.tableau.unity]],
LinearSolver.C[[0.5, gridTop]],
LinearSolver.C[[-1, boxY]]]];
};
topBaseline,
bottomBaseline,
centerOnTopBaseline,
centerOnBottomBaseline => {
rowNumber: ROPE ~ Convert.RopeFromInt[box.top*1000 + box.bottom];
rowY: LinearSolver.Unknown ~ LookUpUnknown[table.tableau, Rope.Concat["r", rowNumber]];
LinearSolver.AssertZero2[table.tableau, 1,rowY, -1,boxY];
LinearSolver.AssertGEZero2[table.tableau, 1,rowY, -1,gridBottom];
LinearSolver.AssertGEZero3[table.tableau, 1,rowY, -(extents[down].texPts),table.tableau.unity, -1,gridBottom];
LinearSolver.AssertGEZero3[table.tableau, 1,gridTop, -(extents[up].texPts),table.tableau.unity, -1,rowY];
};
ENDCASE => ERROR TableBase.UnimplementedCase;
IF NOT LinearSolver.Satisfiable[table.tableau] THEN
ERROR TableBase.ImplementationError["Unsatisifiable constraints"]
};
rule: TableBase.RefTableRule => NULL;
background: TableBase.RefTableBackground => NULL;
ENDCASE => ERROR;
};
IF doItTheLongWay THEN TableBase.EnumerateByRows[table, GenerateRowConstraint]
ELSE {
DetermineTheMaxs;
Enumerate the grid equations...
};
};
GenerateColumnConstraints: PROC [table: TableBase.RefTable] ~ {
GenerateColumnConstraint: TableBase.EnumeratedEntryProc = {
WITH entry SELECT FROM
box: TableBase.RefTableBox =>{
boxNumber: ROPE ~ Convert.RopeFromInt[box.left*1000 + box.top];
boxX: LinearSolver.Unknown ~ LookUpUnknown[table.tableau, Rope.Concat["x", boxNumber]];
colNumber: ROPE ~ Convert.RopeFromInt[box.left*1000 + box.right];
colX: LinearSolver.Unknown ~ LookUpUnknown[table.tableau, Rope.Concat["c", colNumber]];
gridLeft: LinearSolver.Unknown ~ LookUpUnknown[table.tableau, Rope.Concat["gx", Convert.RopeFromInt[box.left]]];
gridRight: LinearSolver.Unknown ~ LookUpUnknown[table.tableau, Rope.Concat["gx", Convert.RopeFromInt[box.right]]];
extents: TSTypes.Dimensions ← TableLayout.AlignExtents[table, box];
SELECT box.colAlignment FROM
flushLeft => {
LinearSolver.AssertZero3[table.tableau, 1,gridLeft, extents[left].texPts,table.tableau.unity, -1,colX];
LinearSolver.AssertGEZero3[table.tableau, 1,gridRight, -(extents[right].texPts),table.tableau.unity, -1,colX];
};
flushRight => {
LinearSolver.AssertZero3[table.tableau, 1,colX, extents[right].texPts,table.tableau.unity, -1,gridRight];
LinearSolver.AssertGEZero3[table.tableau, 1,colX, -(extents[left].texPts),table.tableau.unity, -1,gridLeft];
};
center => {
LinearSolver.AssertGEZero3[table.tableau, 1,colX, -(extents[left].texPts),table.tableau.unity, -1,gridLeft];
LinearSolver.AssertGEZero3[table.tableau, 1,gridRight, -(extents[right].texPts),table.tableau.unity, -1,colX];
LinearSolver.AssertZero3[table.tableau, 1.0,gridLeft, 1.0,gridRight, -2,colX];
};
charAlign => {
colNumber: ROPE ~ Convert.RopeFromInt[box.left*1000 + box.right];
colX: LinearSolver.Unknown ~ LookUpUnknown[table.tableau, Rope.Concat["c", colNumber]];
LinearSolver.AssertZero2[table.tableau, 1,colX, -1,boxX];
LinearSolver.AssertGEZero2[table.tableau, 1,colX, -1,gridLeft];
LinearSolver.AssertGEZero3[table.tableau, 1,colX, -(extents[left].texPts),table.tableau.unity, -1,gridLeft];
LinearSolver.AssertGEZero2[table.tableau, 1,gridRight, -1,colX];
LinearSolver.AssertGEZero3[table.tableau, 1,gridRight, -(extents[right].texPts),table.tableau.unity, -1,colX];
};
ENDCASE => ERROR TableBase.UnimplementedCase;
IF NOT LinearSolver.Satisfiable[table.tableau] THEN
ERROR TableBase.ImplementationError["Unsatisifiable constraints"]
};
rule: TableBase.RefTableRule => NULL;
background: TableBase.RefTableBackground => NULL;
ENDCASE => ERROR;
};
IF doItTheLongWay THEN TableBase.EnumerateByRows[table, GenerateColumnConstraint]
ELSE {
LeftRight: TYPE ~ RECORD[left, right: TableBase.GridNumber, alignment: TableBase.HorizontalAlignment, leftExtent, rightExtent: TSTypes.Dimn];
MaxLeftRight: TableBase.EnumeratedEntryProc ~ {
WITH entry SELECT FROM
box: TableBase.RefTableBox => {
column: ROPE ~ Rope.Concat[SELECT box.colAlignment FROM
flushLeft => "L", flushRight => "R", center => "C", ENDCASE => "C", Convert.RopeFromInt[box.left*1000 + box.right]];
extents: TSTypes.Dimensions ← TableLayout.AlignExtents[table, box];
val: SymTab.Val;
max: REF LeftRight;
found: BOOLEAN;
[found, val] ← SymTab.Fetch[leftRightSymTab, column];
IF found THEN {
max ← NARROW[val];
max.leftExtent ← max.leftExtent.MaxDimn[extents[left]];
max.rightExtent ← max.rightExtent.MaxDimn[extents[right]];
}
ELSE
[] ← SymTab.Insert[leftRightSymTab, column, NEW[LeftRight ← [box.left, box.right, box.colAlignment, extents[left], extents[right]]]];
};
ENDCASE => NULL;
};
GenerateNewColumnConstraint: SymTab.EachPairAction ~ {
PROC [key: SymTab.Key, val: SymTab.Val] RETURNS [quit: BOOL];
max: REF LeftRight ~ NARROW[val];
gridColumn: LinearSolver.Unknown ~ LookUpUnknown[table.tableau, Rope.Concat["c", Convert.RopeFromInt[max.left*1000 + max.right]]];
gridLeft: LinearSolver.Unknown ~ LookUpUnknown[table.tableau, Rope.Concat["gx", Convert.RopeFromInt[max.left]]];
gridRight: LinearSolver.Unknown ~ LookUpUnknown[table.tableau, Rope.Concat["gx", Convert.RopeFromInt[max.right]]];
SELECT max.alignment FROM
flushLeft => {
LinearSolver.AssertZero3[table.tableau, 1,gridLeft, max.leftExtent.texPts,table.tableau.unity, -1,gridColumn];
LinearSolver.AssertGEZero3[table.tableau, 1,gridRight, -(max.rightExtent.texPts),table.tableau.unity, -1,gridColumn];
};
flushRight => {
LinearSolver.AssertZero3[table.tableau, 1,gridColumn, max.rightExtent.texPts,table.tableau.unity, -1,gridRight];
LinearSolver.AssertGEZero3[table.tableau, 1,gridColumn, -(max.leftExtent.texPts),table.tableau.unity, -1,gridLeft];
};
center => {
LinearSolver.AssertGEZero3[table.tableau, 1,gridRight, -(max.leftExtent.texPts+max.rightExtent.texPts),table.tableau.unity, -1,gridLeft];
LinearSolver.AssertZero[table.tableau, LIST[
LinearSolver.C[[1, gridLeft]],
LinearSolver.C[[max.leftExtent.texPts-max.rightExtent.texPts, table.tableau.unity]],
LinearSolver.C[[1, gridRight]],
LinearSolver.C[[-2, gridColumn]]]];
};
ENDCASE => ERROR TableBase.UnimplementedCase;
};
leftRightSymTab: SymTab.Ref ← SymTab.Create[101];
TableBase.EnumerateByRows[table, MaxLeftRight];
[] ← SymTab.Pairs[leftRightSymTab, GenerateNewColumnConstraint]
};
};
doItTheLongWay: BOOLEAN ← TRUE;