-- beadsclean1.mesa  October 12, 1979  9:36 AM
-- change name to Local Area Reduction

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

Error:SIGNAL=CODE;

KeepMesaHappy:PROCEDURE =BEGIN IODefs.WriteChar['*]; END;
FarAndGood:TYPE=RECORD[amt,win:INTEGER];
noGood:FarAndGood=[0,0];
drop:INTEGER;

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

Clean:PUBLIC PROCEDURE= BEGIN
  iKnow_FALSE;
  EnumerateSortedBottomUp[LocalAreaReduction];
  EnumerateSortedBottomUp[LocalAreaReduction];
  EnumerateSortedBottomUp[LocalAreaReduction];
  FixWires[];
  END;

LocalAreaReduction:PROCEDURE[i:CARDINAL, bpi:BeadPtr]= BEGIN
  a:FarAndGood;
  IF bpi.beadL#noBead OR bpi.wire THEN RETURN;
  DO
 --   IF i=64 THEN Error;
    a_HowFarAndHowGoodIsDrop[i,noBead];
    IF a.amt<0 THEN Error;
    IF a.amt#0 AND a.win>=0 THEN Dropit[i,a.amt,noBead] ELSE RETURN;
    ENDLOOP;
  END;

HowFarAndHowGoodIsDrop:PROCEDURE[i,tieStop:CARDINAL] RETURNS[ans:FarAndGood]= BEGIN
  fag:FarAndGood;
  bpi:BeadPtr_Get[i];
  right:CARDINAL_bpi.beadR;
  tied:CARDINAL_bpi.beadT;
  ans_[MaxDrop[i,bpi],(IF bpi.beadD#noBead THEN 1 ELSE 0)
                    - (IF bpi.beadU#noBead THEN 1 ELSE 0)];
--  IF i=68 THEN Error;
  IF ans.amt=0 THEN RETURN[noGood];
  IF bpi.beadL#noBead AND tieStop#noBead THEN RETURN[noGood];
  IF right#noBead THEN BEGIN
    fag_HowFarAndHowGoodIsDrop[right,noBead];
    IF fag=noGood THEN RETURN[noGood];
    ans_[MIN[ans.amt,fag.amt],ans.win+fag.win];
    END;
  IF tied#tieStop THEN BEGIN
    fag_HowFarAndHowGoodIsDrop[tied,IF tieStop=noBead THEN i ELSE tieStop];
    IF fag=noGood THEN RETURN[noGood];
    ans_[MIN[ans.amt,fag.amt],ans.win+fag.win];
    END;
  END;

Dropit:PROCEDURE[i:CARDINAL,a:INTEGER,tieStop:CARDINAL] = BEGIN
  bpi:BeadPtr_Get[i];
  right:CARDINAL_bpi.beadR;
  tied:CARDINAL_bpi.beadT;
  bpi.y_bpi.y-a;
  IF right#noBead THEN Dropit[right,a,noBead];
  IF tied#tieStop THEN Dropit[tied,a,IF tieStop=noBead THEN i ELSE tieStop];
  END;

MaxDrop:PROCEDURE[i:CARDINAL, bpi:BeadPtr] RETURNS[INTEGER]= BEGIN
  endOnTop:BOOLEAN_(SELECT bpi.t FROM endR,endG,endB=>TRUE, ENDCASE=>FALSE)
                   AND bpi.beadD#noBead;
  IF endOnTop THEN RETURN[0];
  drop_bpi.y;
  []_TryAllBelow[i,MaxDropEach];
  RETURN[MAX[drop,0]];
  END;

MaxDropEach:PROCEDURE[i,j:CARDINAL] RETURNS[BOOLEAN] =BEGIN
  deltaX,deltaY:INTEGER;
  bpi:BeadPtr_Get[i]; ti:BeadType_bpi.t;
  bpj:BeadPtr_Get[j]; tj:BeadType_bpj.t;
  [deltaX,deltaY]_Deltas[i,j];
  deltaX_MAX[0,deltaX];
  IF   i=bpj.beadT
    OR j=bpi.beadT
    OR bpi.beadL=bpj.beadR AND bpi.beadL#noBead
    OR bpi.beadR=bpj.beadL AND bpi.beadR#noBead
    OR j=bpi.beadR
    OR j=bpi.beadL
    OR bpj.w<0
    OR bpi.w<0
    OR bpj.x-bpi.x NOT IN (-bpj.w-deltaX..bpi.w+deltaX)
       THEN RETURN[TRUE];
  drop_MIN[drop,bpi.y-bpj.y-bpj.h-deltaY];
  IF ~iKnow AND drop<0 THEN BEGIN Error; iKnow_TRUE; END;
  RETURN[drop>0];
  END;

iKnow:BOOLEAN;


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 passes along a tie stop parameter to help curb the recursion on tied beads. 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.

(1792)