-- beadsclean.mesa
-- change name to Shrink

DIRECTORY IODefs:FROM"IODefs",
BeadsInlines:FROM"BeadsInlines",
InlineDefs:FROM"InlineDefs",
BeadsDefs:FROM"BeadsDefs";
BeadsClean:PROGRAM IMPORTS BeadsInlines, InlineDefs, IODefs, BeadsDefs
EXPORTS BeadsDefs=
BEGIN OPEN BeadsDefs, BeadsInlines;

Error:SIGNAL=CODE;

KeepMesaHappy:PROCEDURE =BEGIN IODefs.WriteChar[’*]; END;
FarAndGood:TYPE=RECORD[amt,win:INTEGER];
noGood:FarAndGood=[0,0];
justFine:FarAndGood=[32000,0];
drop:INTEGER;
iKnow:BOOLEAN;
processNo:CARDINAL;
maxProcessNo:INTEGER=32000;

--////// FALL //////

Clean:PUBLIC PROCEDURE= BEGIN
iKnow←FALSE;
processNo←maxProcessNo;
EnumerateSortedBottomUp[LocalAreaReduction];
EnumerateSortedBottomUp[LocalAreaReduction];
EnumerateSortedBottomUp[LocalAreaReduction];
FixWires[];
END;

LocalAreaReduction:PROCEDURE[i:Desc]= BEGIN
IF ~NoBeadL[i] OR i.p.wire THEN RETURN;
DO a:FarAndGood;
Dropit:PROCEDURE[i:Desc] = BEGIN
IF ~Uninteresting[i] THEN
{IncrementY[i,-a.amt]; Dropit[DescR[i]]; Dropit[DescT[i]];}
END;
IncrementProcessNo[]; a←HowFarAndHowGoodIsDrop[i];
IF WorthWhile[a] THEN {IncrementProcessNo[]; Dropit[i]} ELSE RETURN;
ENDLOOP;
END;

WorthWhile:PROCEDURE[a:FarAndGood] RETURNS[BOOLEAN]=INLINE
BEGIN IF a.amt<0 THEN Error; RETURN[a.amt#0 AND a.win>=0]; END;

IncrementProcessNo:PROCEDURE=INLINE BEGIN
IF processNo=maxProcessNo THEN {EnumerateBeads[ClearProcessed]; processNo←1}
ELSE processNo←processNo+1;
END;

ClearProcessed:PROCEDURE[i:Desc]=BEGIN Getw[i].processNo←0; END;

HowFarAndHowGoodIsDrop:PROCEDURE[i:Desc] RETURNS[ans:FarAndGood]= BEGIN
Worse:PROCEDURE[b:FarAndGood]=INLINE
BEGIN ans←[MIN[ans.amt,b.amt],ans.win+b.win]; END;
IF Uninteresting[i] THEN RETURN[justFine];
IF ~Uninteresting[DescL[i]] THEN RETURN[noGood];
ans←[MaxDrop[i],(IF NoBeadD[i] THEN 0 ELSE 1)
- (IF NoBeadU[i] THEN 0 ELSE 1)];
Worse[HowFarAndHowGoodIsDrop[DescR[i]]];
Worse[HowFarAndHowGoodIsDrop[DescT[i]]];
IF ans.amt=0 THEN ans←noGood;
END;

Uninteresting:PROCEDURE[i:Desc] RETURNS[BOOLEAN]=INLINE BEGIN
RETURN[NoBead[i] OR Processed[i]]; END;

Processed:PROCEDURE[i:Desc] RETURNS[b:BOOLEAN]=INLINE BEGIN
wpi:WorkPtr←Getw[i]; b←wpi.processNo=processNo; wpi.processNo←processNo;
END;

MaxDrop:PROCEDURE[i:Desc] RETURNS[INTEGER]=BEGIN
endOnTop:BOOLEAN←End[i] AND ~NoBeadD[i];
IF endOnTop THEN RETURN[0];
drop←Bot[i];
[]←TryAllBelow[i.z,MaxDropEach];
RETURN[MAX[drop,0]];
END;

MaxDropEach:PROCEDURE[ii,jj:CARDINAL] RETURNS[BOOLEAN] =BEGIN
i:Desc←GetDesc[ii];
j:Desc←GetDesc[jj];
delta:Coord←Delta[i,j];
delta.x←MAX[0,delta.x];
IF TiedBeads[i,j]
OR Unrelated[i,j]
OR LeftOf[j,i]
OR LeftOf[i,j]
OR NoWidths[i,j]
OR ~InteractH[i,j,delta.x]
THEN RETURN[TRUE];
drop←MIN[drop,Bot[i]-Top[j]-delta.y];
IF ~iKnow AND drop<0 THEN BEGIN Error; iKnow←TRUE; END;
RETURN[drop>0];
END;


END..

Clean: The function of Clean is to examine all beads to discover whether they can drop somewhat, and whether it is a net win to do so. Any advantageous drops are promptly made. Clean does not operate on bent wires. Clean uses LocalAreaReduction[i] to do its thing for bead i.
It is important to somehow handle a horizontal wire with a vertical zero height jog in it.

HowFarAndHowGoodIsDrop[i]: The function of HowFarAndHowGoodIsDrop is to discover how far bead i can drop, and whether it is a net win to do so, but not to actually make the drop. HowFarAndHowGoodIsDrop assumes that everything to the left has been taken care of, so that all it must check is the current bead, the bead to its right, and tied beads. HowFarAndHowGoodIsDrop is one of those recursive control things, and needs a processd number to help curb infinite recursion. The definition of net win is plus one for every wire leading down (which will be shortened) and minus one for every wire leading up (lengthened), applied over all the beads the recursion can reach. How far to drop is simply the minimum legal drop over the whole recursion.

Dropit[i,a]: The function of Dropit is to drop bead i and all its friends by the amount a, following the same recursion path of HowFarAndHowGoodIsDrop.

MaxDrop[i]: The function of MaxDrop is to compute how far bead i could drop. It uses TryAllBelow to find the guy limiting the fall. It also checks to see that end beads don’t drop away from their edge.

*Clean:
EnumerateSortedBottomUp(3)
LocalAreaReduction(3)
FixWires
LocalAreaReduction:
Dropit:
Uninteresting
IncrementY
Dropit(2)
IncrementProcessNo(2)
HowFarAndHowGoodIsDrop
WorthWhile
Dropit
WorthWhile:
IncrementProcessNo:
EnumerateBeads
ClearProcessed
ClearProcessed:
HowFarAndHowGoodIsDrop:
Worse:
Uninteresting(2)
MaxDrop
Worse(2)
Uninteresting:
Processed
Processed:
MaxDrop:
TryAllBelow
MaxDropEach
MaxDropEach
Delta
InteractH