--routeInter.mesa

DIRECTORY  RouteDefs;

RouteInter:PROGRAM IMPORTS RouteDefs EXPORTS RouteDefs=BEGIN
OPEN RouteDefs;

--RouteIntersections figures out the intersection
--InterSilicon turns the internal representation into rectangles
--WhereIs takes a path and a side and returns the runNo of that wire
--   WhereIs returns the first matching path among equals 
--the circuit in IWire is the current assignment. -1 means unassigned

Error:SIGNAL=CODE;
spaceB:Lambda←0;

RouteIntersections:PUBLIC CtlProc=BEGIN
ShowLabel["INTERSECTIONS"];
EnumerateRectangles[SetSizeC];
EnumerateInters[MakeIWires]; --sets type,h,wire,path
EnumerateInters[AssignIWires]; --sets nx,sx,ey,wy
EnumerateAllIWire[CheckInter];
EnumerateInters[ShowInter];
EnumerateInters[ShowIWire];
RETURN[-1];
END;

EnumerateAllPaths:PROCEDURE[c:PROCEDURE[PathPtr]]=BEGIN
FOR wl:PathwayListPtr←paths, wl.t UNTIL wl=NIL DO
  FOR pl:PathListPtr←wl.h.path, pl.t UNTIL pl=NIL
  DO c[pl.h]; ENDLOOP; ENDLOOP;
END;

EnumerateIWire:PROCEDURE[r:RectanglePtr, c:PROCEDURE[RectanglePtr,IWirePtr]]=
  {FOR l:IWireListPtr←r.junction.iwires,l.t UNTIL l=NIL DO c[r,l.h]; ENDLOOP};

EnumerateAllIWire:PROCEDURE[c:PROCEDURE[RectanglePtr,IWirePtr]]=BEGIN
Sub:PROCEDURE[rect:RectanglePtr]={EnumerateIWire[rect,c]};
EnumerateInters[Sub];
END;

SetSizeC:PROCEDURE[rect:RectanglePtr]=BEGIN
ew:INTEGER=(East[rect]-West[rect]+4)/7;
ns:INTEGER=(North[rect]-South[rect]+4)/7;
IF rect.orient=inter
THEN {rect.sizeC.x←ew; rect.sizeC.y←ns}
ELSE rect.sizeC.y←IF rect.orient=hor THEN ns ELSE ew;
END;

MakeIWires:PROCEDURE[inter:RectanglePtr]=BEGIN
AddIWire:PROCEDURE[path:PathPtr]=BEGIN
IF path.inter#inter THEN RETURN ELSE BEGIN 
h:Huggers=path.huggers;
type:InterType=MakeType[n:path.n#NIL,e:path.e#NIL,s:path.s#NIL,w:path.w#NIL];
list:IWireListPtr←AllocateList[];
wire:IWirePtr←AllocateIWire[];
wire.type←type;
wire.h←h;
wire.path←path;
path.wire←wire;
list↑←[wire,inter.junction.iwires];
inter.junction.iwires←list;
wire.be1←wire.h.n#w OR  wire.h.s#w;
wire.be2←wire.h.n#w AND wire.h.s#w;
wire.bn1←wire.h.e=n OR  wire.h.w=n;
wire.bn2←wire.h.e=n AND wire.h.w=n;
wire.nx←wire.sx←wire.ey←wire.wy←-1;
END; END;
EnumerateAllPaths[AddIWire];
END;

RR:TYPE=PROCEDURE[r:RectanglePtr] RETURNS[x:Lambda];
South:RR={x←r.pos.y+r.levelers.s+r.margins.s};
West:RR ={x←r.pos.x+r.levelers.w+r.margins.w};
North:RR={x←r.pos.y+r.sizeL.y-r.levelers.n-r.margins.n};
East:RR ={x←r.pos.x+r.sizeL.x-r.levelers.e-r.margins.e};

AlreadyUsed:PROCEDURE[s:Side,junct:JunctionPtr,x:RunNo] RETURNS[BOOLEAN]=
BEGIN
t:BOOLEAN←FALSE;
FOR iwl:IWireListPtr←junct.iwires,iwl.t UNTIL iwl=NIL DO
  w:IWirePtr=iwl.h;
  y:RunNo=SELECT s FROM n=>w.nx, s=>w.sx, e=>w.ey, ENDCASE=>w.wy;
  IF y=x THEN {IF t THEN RETURN[TRUE]; t←TRUE};
  ENDLOOP;
RETURN[FALSE];
END;

AssignIWires:PROCEDURE[rect:RectanglePtr]=BEGIN
junct:JunctionPtr=rect.junction;
rw:RectanglePtr=IF rect.w=NIL THEN rect ELSE rect.w;
re:RectanglePtr=IF rect.e=NIL THEN rect ELSE rect.e;
rn:RectanglePtr=IF rect.n=NIL THEN rect ELSE rect.n;
rs:RectanglePtr=IF rect.s=NIL THEN rect ELSE rect.s;
ssw:RunNo←MAX[0,(West[rs]-West[rect]+6)/7];
sse:RunNo←MAX[0,(East[rect]-East[rs]+6)/7];
nnw:RunNo←MAX[0,(West[rn]-West[rect]+6)/7];
nne:RunNo←MAX[0,(East[rect]-East[rn]+6)/7];
wsw:RunNo←MAX[0,(South[rw]-South[rect]+6)/7];
ese:RunNo←MAX[0,(South[re]-South[rect]+6)/7];
wnw:RunNo←MAX[0,(North[rect]-North[rw]+6)/7];
ene:RunNo←MAX[0,(North[rect]-North[re]+6)/7];
Setnx:PROCEDURE[b:BOOLEAN]=BEGIN
  IF w.nx#-1 THEN RETURN;
  IF nne+nnw=topx+1 THEN Error ELSE
   IF b THEN {w.nx←topx-nne; nne←nne+1} ELSE {w.nx←nnw; nnw←nnw+1};
  IF rect.n.orient=inter AND AlreadyUsed[n,junct,w.nx] THEN {w.nx←-1; Setnx[b]};
  END;
Setsx:PROCEDURE[b:BOOLEAN]=BEGIN
  IF w.sx#-1 THEN RETURN;
  IF sse+ssw=topx+1 THEN Error ELSE
   IF b THEN {w.sx←topx-sse; sse←sse+1} ELSE {w.sx←ssw; ssw←ssw+1};
  IF rect.s.orient=inter AND AlreadyUsed[s,junct,w.sx] THEN {w.sx←-1; Setsx[b]};
  END;
Setey:PROCEDURE[b:BOOLEAN]=BEGIN
  IF w.ey#-1 THEN RETURN;
  IF ene+ese=topy+1 THEN Error ELSE
   IF b THEN {w.ey←topy-ene; ene←ene+1} ELSE {w.ey←ese; ese←ese+1};
  IF rect.e.orient=inter AND AlreadyUsed[e,junct,w.ey] THEN {w.ey←-1; Setey[b]};
  END;
Setwy:PROCEDURE[b:BOOLEAN]=BEGIN
  IF w.wy#-1 THEN RETURN;
  IF wnw+wsw=topy+1 THEN Error ELSE
   IF b THEN {w.wy←topy-wnw; wnw←wnw+1} ELSE {w.wy←wsw; wsw←wsw+1};
  IF rect.w.orient=inter AND AlreadyUsed[w,junct,w.wy] THEN {w.wy←-1; Setwy[b]};
  END;
ThruNS:PROCEDURE[z:BOOLEAN]={Setnx[z]; Setsx[z]};
ThruEW:PROCEDURE[z:BOOLEAN]={Setwy[z]; Setey[z]};
topx:RunNo←rect.sizeC.x-1;
topy:RunNo←rect.sizeC.y-1;
w:IWirePtr←NIL;
FOR iwl:IWireListPtr←junct.iwires,iwl.t UNTIL iwl=NIL DO
  w←iwl.h;
  SELECT w.type FROM
    05=>{Setnx[TRUE]; Setey[TRUE]};
    06=>{Setsx[TRUE]; Setey[FALSE]};
    09=>{Setnx[FALSE]; Setwy[TRUE]};
    10=>{Setsx[FALSE]; Setwy[FALSE]};
    ENDCASE;
  ENDLOOP;
FOR iwl:IWireListPtr←junct.iwires,iwl.t UNTIL iwl=NIL DO
  w←iwl.h;
  SELECT w.type FROM
    07=>Setey[w.h.e=n]; 11=>Setwy[w.h.w=n];
    13=>Setnx[w.h.n#w]; 14=>Setsx[w.h.s#w];
    ENDCASE;
  ENDLOOP;
nne←sse←MAX[nne,sse]; nnw←ssw←MAX[nnw,ssw];
ese←wsw←MAX[ese,wsw]; ene←wnw←MAX[ene,wnw];
FOR iwl:IWireListPtr←junct.iwires,iwl.t UNTIL iwl=NIL DO
  w←iwl.h;
  SELECT w.type FROM
    07=>ThruNS[w.be1]; 11=>ThruNS[w.be2];
    13=>ThruEW[w.bn1]; 14=>ThruEW[w.bn2];
    ENDCASE;
  ENDLOOP;
FOR iwl:IWireListPtr←junct.iwires,iwl.t UNTIL iwl=NIL DO
  w←iwl.h;
  IF w.type=15 THEN {ThruNS[w.be1]; ThruEW[w.bn1]};
  ENDLOOP;
FOR iwl:IWireListPtr←junct.iwires,iwl.t UNTIL iwl=NIL DO
  w←iwl.h;
  IF w.type=03 THEN ThruNS[w.be1]; IF w.type=12 THEN ThruEW[w.bn1];
  ENDLOOP;
junct.bridgeNS←nne;
junct.bridgeEW←ese;
FixNeighbor[rect];
END;

FixNeighbor:PROCEDURE[rect:RectanglePtr]=BEGIN
rw:RectanglePtr=IF rect.w=NIL THEN rect ELSE rect.w;
re:RectanglePtr=IF rect.e=NIL THEN rect ELSE rect.e;
rn:RectanglePtr=IF rect.n=NIL THEN rect ELSE rect.n;
rs:RectanglePtr=IF rect.s=NIL THEN rect ELSE rect.s;
deltxN:RunNo=West[rn]-West[rect];
deltxS:RunNo=West[rs]-West[rect];
deltxE:RunNo=South[re]-South[rect];
deltxW:RunNo=South[rw]-South[rect];
deltaN:RunNo=IF deltxN>=0 THEN (deltxN+6)/7 ELSE (deltxN-6)/7;
deltaS:RunNo=IF deltxS>=0 THEN (deltxS+6)/7 ELSE (deltxS-6)/7;
deltaE:RunNo=IF deltxE>=0 THEN (deltxE+6)/7 ELSE (deltxE-6)/7;
deltaW:RunNo=IF deltxW>=0 THEN (deltxW+6)/7 ELSE (deltxW-6)/7;
Sub:PROCEDURE[rect:RectanglePtr,w:IWirePtr]=BEGIN
  IF w.path.n#NIL AND w.path.n.wire#NIL AND w.path.n.wire.sx=-1
     THEN w.path.n.wire.sx←w.nx-deltaN;
  IF w.path.s#NIL AND w.path.s.wire#NIL AND w.path.s.wire.nx=-1
     THEN w.path.s.wire.nx←w.sx-deltaS;
  IF w.path.e#NIL AND w.path.e.wire#NIL AND w.path.e.wire.wy=-1
     THEN w.path.e.wire.wy←w.ey-deltaE;
  IF w.path.w#NIL AND w.path.w.wire#NIL AND w.path.w.wire.ey=-1
     THEN w.path.w.wire.ey←w.wy-deltaW;
  END;
EnumerateIWire[rect,Sub];
END;

CheckInter:PROCEDURE[rect:RectanglePtr,w:IWirePtr]=BEGIN
lastx:INTEGER=rect.sizeC.x-1;
realType:InterType=MakeType[n:w.nx#-1,e:w.ey#-1,s:w.sx#-1,w:w.wy#-1];
IF w.type#realType THEN Error;
IF w.sx NOT IN [-1..rect.sizeC.x) THEN Error;
IF w.nx NOT IN [-1..rect.sizeC.x) THEN Error;
IF w.ey NOT IN [-1..rect.sizeC.y) THEN Error;
IF w.wy NOT IN [-1..rect.sizeC.y) THEN Error;
IF w.sx#-1 AND w.nx#-1 AND w.sx#w.nx THEN Error;
IF w.ey#-1 AND w.wy#-1 AND w.ey#w.wy THEN Error;
FOR iwl2:IWireListPtr←rect.junction.iwires,iwl2.t UNTIL iwl2=NIL DO
    w2:IWirePtr=iwl2.h;
    IF w2=w THEN EXIT;
    IF w.nx=w2.nx AND w.nx#-1 THEN Error;
    IF w.sx=w2.sx AND w.sx#-1 THEN Error;
    IF w.ey=w2.ey AND w.ey#-1 THEN Error;
    IF w.wy=w2.wy AND w.wy#-1 THEN Error;
    ENDLOOP;
END;


ShowInter:PROCEDURE[rect:RectanglePtr]=BEGIN
junct:JunctionPtr=rect.junction;
LineHor:PROCEDURE[lev,st,end:INTEGER]=BEGIN
  IF end=-1 THEN end←lasty;
  lev←2*lev+2; st←2*st+2; end←2*end+2;
  FOR j:INTEGER IN [st..end] DO Store[lev,j]; ENDLOOP;
  END;
LineVer:PROCEDURE[lev,st,end:INTEGER]=BEGIN
  IF end=-1 THEN end←lastx;
  lev←2*lev+2; st←2*st+2; end←2*end+2;
  FOR j:INTEGER IN [st..end] DO Store[j,lev]; ENDLOOP;
  END;
Store:PROCEDURE[x,y:INTEGER]=BEGIN
  IF x NOT IN [0..size/2) THEN
    {x←x-2*lastx-2+size-1; IF x NOT IN [size/2..size) THEN RETURN};
  IF y NOT IN [0..size/2) THEN
    {y←y-2*lasty-2+size-1; IF y NOT IN [size/2..size) THEN RETURN};
  copout[x][y]←TRUE;
  END;
size:INTEGER=28;
copout:ARRAY [0..size) OF ARRAY [0..size) OF BOOLEAN←ALL[ALL[FALSE]];
topY:INTEGER←0;
lastx:INTEGER=rect.sizeC.x-1;
lasty:INTEGER=rect.sizeC.y-1;
Return[];
ShowDecimal[rect.channelNo,"Int "L];
Return[];
FOR iwl:IWireListPtr←junct.iwires,iwl.t UNTIL iwl=NIL DO
  w:IWirePtr=iwl.h;
  SELECT w.type FROM
    03=> LineVer[w.sx,-1,-1];
    05=>{LineHor[w.ey,w.nx,-1]; LineVer[w.nx,w.ey,-1]};
    06=>{LineHor[w.ey,w.sx,-1]; LineVer[w.sx,-1,w.ey]};
    07=>{LineHor[w.ey,w.sx,-1]; LineVer[w.nx,-1,-1]};
    09=>{LineHor[w.wy,-1,w.nx]; LineVer[w.nx,w.wy,-1]};
    10=>{LineHor[w.wy,-1,w.sx]; LineVer[w.sx,-1,w.wy]};
    11=>{LineHor[w.wy,-1,w.sx]; LineVer[w.sx,-1,-1]};
    12=> LineHor[w.wy,-1,-1];
    13=>{LineHor[w.wy,-1,-1]; LineVer[w.nx,w.wy,-1]};
    14=>{LineHor[w.wy,-1,-1]; LineVer[w.sx,-1,w.wy]};
    15=>{LineHor[w.wy,-1,-1]; LineVer[w.sx,-1,-1]};
    ENDCASE=>Error;
  ENDLOOP;
Return[];
FOR i:INTEGER DECREASING IN [0..size) DO
  found:BOOLEAN←FALSE;
  FOR j:INTEGER IN [0..size)
      DO IF copout[i][j] THEN found←TRUE; EXIT;  ENDLOOP;
  IF found THEN {topY←i+1; EXIT};
  ENDLOOP;
FOR i:INTEGER DECREASING IN [0..topY) DO
  y:INTEGER=i;
    --y:INTEGER=SELECT i FROM 0=>0, 2*lasty+2=>i-2, ENDCASE=>i-1;
  Return[];
  FOR j:INTEGER IN [0..size) DO
      --z:INTEGER=SELECT j FROM 0=>0, 2*lastx+2=>j-2, ENDCASE=>j-1;
    z:INTEGER=j;
    ShowChar[IF copout[y][z] THEN 'b ELSE ' ];
    ENDLOOP;
  ENDLOOP;
END;

ShowIWire:PROCEDURE[inter:RectanglePtr]=BEGIN
Return[];
FOR wl:IWireListPtr←inter.junction.iwires,wl.t UNTIL wl=NIL DO
  wire:IWirePtr=wl.h;
  Return[];
  ShowDecimal[wire.type, "   type: "];
  ShowDecimal[wire.nx, " nx: "];
  ShowDecimal[wire.sx, " sx "];
  ShowDecimal[wire.ey, " ey: "];
  ShowDecimal[wire.wy, " wy: "];
  ENDLOOP;
END;

InterSilicon:PUBLIC PROCEDURE[rect:RectanglePtr]=BEGIN
junct:JunctionPtr=rect.junction;
sB:Lambda←spaceB←rect.margins.s+rect.levelers.s;
x:Lambda=rect.pos.x;
width:Lambda=rect.sizeL.x;
lastx:INTEGER=rect.sizeC.x-1;
edge:Lambda=East[rect]-Across[lastx]-3;
y:Lambda=rect.pos.y;
LineHor:PROCEDURE[lev,st,end:INTEGER]=BEGIN
  yy:Lambda=y+AcrossS[lev];
  xBot:Lambda=IF st=-1 THEN x ELSE edge+Across[st];
  xTop:Lambda=IF end=-1 THEN x+rect.sizeL.x ELSE edge+Across[end]+3;
  MakeBlue[TRUE,xBot,yy,xTop-xBot];
  END;
LineVer:PROCEDURE[lev,st,end:INTEGER]=BEGIN
  xx:Lambda=edge+Across[lev];
  yBot:Lambda=IF st=-1 THEN 0 ELSE AcrossS[st];
  yTop:INTEGER=IF end=-1 THEN rect.sizeL.y ELSE AcrossS[end]+3;
  MakeBlue[FALSE,xx,y+yBot,yTop-yBot];
  END;
MakeBridge[rect];
FOR iwl:IWireListPtr←junct.iwires,iwl.t UNTIL iwl=NIL DO
  w:IWirePtr=iwl.h;
  SELECT w.type FROM
    03=> LineVer[w.sx,-1,-1];
    05=>{LineHor[w.ey,w.nx,-1]; LineVer[w.nx,w.ey,-1]};
    06=>{LineHor[w.ey,w.sx,-1]; LineVer[w.sx,-1,w.ey]};
    07=>{LineHor[w.ey,w.sx,-1]; LineVer[w.nx,-1,-1]};
    09=>{LineHor[w.wy,-1,w.nx]; LineVer[w.nx,w.wy,-1]};
    10=>{LineHor[w.wy,-1,w.sx]; LineVer[w.sx,-1,w.wy]};
    11=>{LineHor[w.wy,-1,w.sx]; LineVer[w.sx,-1,-1]};
    12=> LineHor[w.wy,-1,-1];
    13=>{LineHor[w.wy,-1,-1]; LineVer[w.nx,w.wy,-1]};
    14=>{LineHor[w.wy,-1,-1]; LineVer[w.sx,-1,w.wy]};
    15=>{LineHor[w.wy,-1,-1]; LineVer[w.sx,-1,w.wy]; LineVer[w.sx,w.wy,-1];};
    ENDCASE=>Error;
  ENDLOOP;
END;

Bridge:TYPE=ARRAY[0..4) OF Span←ALL[[]];
Span:TYPE=RECORD[none,hRed:BOOLEAN←TRUE,n,e:Lambda←-1,s,w:Lambda←bigRun];
SpanPtr:TYPE=POINTER TO Span;

MakeBridge:PUBLIC PROCEDURE[rect:RectanglePtr]=BEGIN
j:JunctionPtr=rect.junction;
x:Lambda=rect.pos.x;
y:Lambda=rect.pos.y;
l:INTEGER;
lastx:INTEGER=rect.sizeC.x-1;
edge:Lambda=x+rect.sizeL.x-Across[lastx]-rect.margins.e-rect.levelers.e-3;
bridge←ALL[[]];
FOR iwl:IWireListPtr←j.iwires,iwl.t UNTIL iwl=NIL DO
  w:IWirePtr=iwl.h;
  a,b,c,d:INTEGER←-1;
  SELECT w.type FROM
    03=>{a←IF w.be1 THEN 2 ELSE 0; b←a+1};
    05=>IF w.nx>=j.bridgeNS THEN
          {IF w.ey<j.bridgeEW THEN {a←c←2; b←3}}
        ELSE IF w.ey<j.bridgeEW THEN {b←d←0; a←1; c←2}
           ELSE {d←3; a←c←1};
    06=>IF w.sx>=j.bridgeNS THEN
          {IF w.ey>=j.bridgeEW THEN {a←c←3; b←2}}
        ELSE IF w.ey>=j.bridgeEW THEN {b←d←1; a←0; c←3}
           ELSE {d←2; a←c←0};
    07=>{a←IF w.be1 THEN 2 ELSE 0; b←a+1;
         c←IF w.h.e=n THEN 3 ELSE 2; IF a=0 THEN d←c-2};
    09=>IF w.nx<j.bridgeNS THEN
          {IF w.wy<j.bridgeEW THEN {a←c←0; b←1}}
        ELSE IF w.wy<j.bridgeEW THEN {b←d←2; a←3; c←0}
           ELSE {d←1; a←c←3};
    10=>IF w.sx<j.bridgeNS THEN
          {IF w.wy>=j.bridgeEW THEN {a←c←1; b←0}}
        ELSE IF w.wy>=j.bridgeEW THEN {b←d←3; a←2; c←1}
           ELSE {d←0; a←c←2};
    11=>{a←IF w.be2 THEN 2 ELSE 0; b←a+1;
         d←IF w.h.w=n THEN 1 ELSE 0; IF a=2 THEN d←c+2};
    12=>{c←IF w.bn1 THEN 1 ELSE 0; d←c+2};
    13=>{c←IF w.bn1 THEN 1 ELSE 0; d←c+2;
         b←IF w.h.n#w THEN 3 ELSE 1; IF c=1 THEN a←b-1};
    14=>{c←IF w.bn2 THEN 1 ELSE 0; d←c+2;
         a←IF w.h.s#w THEN 2 ELSE 0; IF c=0 THEN a←b+1};
    15=>{a←IF w.be1 THEN 2 ELSE 0; b←a+1;
         c←IF w.bn1 THEN 1 ELSE 0; d←c+2};
    ENDCASE=>LOOP;
  IF a#-1 THEN {l←w.sx; IF l=-1 OR l=bigRun THEN l←w.nx;
                bridge[a].e←MAX[bridge[a].e,l];
                bridge[a].w←MIN[bridge[a].w,l]};
  IF b#-1 THEN {l←w.sx; IF l=-1 OR l=bigRun THEN l←w.nx;
                bridge[b].e←MAX[bridge[b].e,l];
                bridge[b].w←MIN[bridge[b].w,l]};
  IF c#-1 THEN {l←w.ey; IF l=-1 OR l=bigRun THEN l←w.wy;
                bridge[c].s←MIN[bridge[c].s,l];
                bridge[c].n←MAX[bridge[c].n,l]};
  IF d#-1 THEN {l←w.ey; IF l=-1 OR l=bigRun THEN l←w.wy;
                bridge[d].s←MIN[bridge[d].s,l];
                bridge[d].n←MAX[bridge[d].n,l]};
  ENDLOOP;
FOR i:INTEGER IN [0..4) DO
  span:SpanPtr←@bridge[i];
  IF span.e=-1 OR span.n=-1 OR span.w=bigRun OR span.s=bigRun THEN LOOP;
  span.w←MAX[edge+Across[span.w]-3,x-4];
  span.e←MIN[edge+Across[span.e]+7,x+rect.sizeL.x];
  span.s←MAX[y+AcrossS[span.s]-3,y-4];
  span.n←MIN[y+AcrossS[span.n]+7,y+rect.sizeL.y];
  span.none←FALSE;
  ENDLOOP;
Return[];
ShowDecimal[rect.channelNo, "bridge "];
FOR i:INTEGER IN [0..4) DO
  span:SpanPtr←@bridge[i];
  Return[];
  ShowString[IF span.none THEN "  off  " ELSE
          IF span.hRed THEN "  hor  " ELSE "  vert "];
  ShowDecimal[span.w, " w "];
  ShowDecimal[span.e, " e "];
  ShowDecimal[span.n, " n "];
  ShowDecimal[span.s, " s "];
  ENDLOOP;
END;

MakeBlue:PROCEDURE[hor:BOOLEAN,x,y,l:Lambda]=BEGIN
IF l<0 THEN {IF hor THEN x←x+l ELSE y←y+l; l←-l};
IF hor THEN FOR i:INTEGER IN [0..4) DO
  s:SpanPtr←@bridge[i];
  x1,x2:Lambda;
  IF s.none OR ~s.hRed THEN LOOP;
  IF y NOT IN [s.s..s.n) THEN LOOP;
  IF x NOT IN (s.w-l..s.e] THEN LOOP;
  IF ~s.hRed THEN BEGIN
    IF x IN (s.w..s.e] THEN MakeContact[x,y];
    IF x+l IN (s.w..s.e] THEN MakeContact[x+l-3,y];
    LOOP;
    END;
  x1←IF x<s.w+3 THEN s.w-4 ELSE x;
  x2←IF x+l>s.e-3 THEN s.e ELSE x+l-4;
  IF x<s.w THEN MakeBlueWire[TRUE,x,y,s.w-x];
  MakeContact[x1,y];
  MakeContact[x2,y];
  MakeRedWire[TRUE,x1,y,x2-x1];
  IF x+l<=s.e-3 THEN RETURN;
  l←x+l-s.e;
  x←s.e;
  ENDLOOP
ELSE FOR i:INTEGER IN [0..4) DO
  s:SpanPtr←@bridge[i];
  y1,y2:Lambda;
  IF s.none THEN LOOP;
  IF x NOT IN [s.w..s.e) THEN LOOP;
  IF s.hRed THEN BEGIN
    IF y IN (s.s..s.n] THEN MakeContact[x,y];
    IF y+l IN (s.s..s.n] THEN MakeContact[x,y+l-3];
    LOOP;
    END;
  IF y NOT IN (s.s-l..s.n] THEN LOOP;
  y1←IF y<s.s+3 THEN s.s-4 ELSE x;
  y2←IF y+l>s.n-3 THEN s.n ELSE y+l-4;
  IF y<s.s THEN MakeBlueWire[FALSE,x,y,s.s-y];
  MakeContact[x,y1];
  MakeContact[x,y2];
  MakeRedWire[FALSE,x,y1,y2-y1];
  IF y+l<=s.n-3 THEN RETURN;
  l←y+l-s.n;
  y←s.n;
  ENDLOOP;
MakeBlueWire[hor,x,y,l];
END;

bridge:Bridge;

WhereIs:PUBLIC PROCEDURE[p:PathPtr,ss:Side,desired:RunNo] RETURNS[RunNo]=BEGIN
i:RectanglePtr=p.inter;
top:RunNo=i.sizeC.x-1;
j:RectanglePtr=SELECT ss FROM  n=>i.n,  s=>i.s,  e=>i.e,  ENDCASE=>i.w;
excessL:Lambda=SELECT ss FROM
    n,s=>East[i]-East[j], ENDCASE=>South[j]-South[i];
excessC:RunNo=excessL/7;
desNo:RunNo=SELECT ss FROM n,s=>top-desired-excessC, ENDCASE=>excessC+desired;
w:IWirePtr←FindOne[p,ss,desNo];
IF w=NIL OR j=NIL THEN {Error; RETURN[0]};
w.circuit←p.circuit;
BEGIN
myNo:RunNo=SELECT ss FROM n=>top-w.nx, s=>top-w.sx, e=>w.ey, ENDCASE=>w.wy;
IF excessC>myNo THEN Error;
RETURN[myNo-excessC];
END; END;

FindOne:PUBLIC PROCEDURE[p:PathPtr,ss:Side,desired:RunNo]
  RETURNS[w:IWirePtr]=BEGIN
best:INTEGER←10000;
i:RectanglePtr=p.inter;
ns:BOOLEAN=ss=n OR ss=s;
type:InterType=MakeType[n:p.n#NIL,e:p.e#NIL,s:p.s#NIL,w:p.w#NIL];
FOR iwl:IWireListPtr←i.junction.iwires,iwl.t UNTIL iwl=NIL DO
  ww:IWirePtr←iwl.h;
  IF ww.type=type AND ww.circuit=p.circuit THEN RETURN[ww];
  ENDLOOP;
w←NIL;
FOR iwl:IWireListPtr←i.junction.iwires,iwl.t UNTIL iwl=NIL DO
  ww:IWirePtr←iwl.h;
  IF ww.type=type AND ww.circuit=-1 -- AND EquivalentHugs[p.huggers,ww.h]
    THEN BEGIN
    this:RunNo=SELECT ss FROM e=>ww.ey, w=>ww.wy, n=>ww.nx, ENDCASE=>ww.sx;
    IF this=desired THEN RETURN[ww];
    SELECT ABS[this-desired]-best FROM
      <0 => {w←ww; best←ABS[this-desired]};
    --  0  =>IF (SELECT type FROM
     --     03=>ww.be1, 05=>ns, 06=>TRUE, 10=>~ns, 12=>~ww.bn1,
    --      07=>IF  ns THEN  ww.be1 ELSE ww.h.e#n,
    --      11=>IF  ns THEN  ww.be2 ELSE ww.h.w#n,
    --      13=>IF ~ns THEN ~ww.bn1 ELSE ww.h.n#w,
    --      14=>IF ~ns THEN ~ww.bn2 ELSE ww.h.s#w,
    --      15=>IF ~ns THEN ~ww.bn1 ELSE ww.be1,
    --      ENDCASE=>FALSE)=(this<desired) THEN {w←ww; best←ABS[this-desired]};
      ENDCASE;
    END;
  ENDLOOP;
IF w=NIL THEN {Error; RETURN[NIL]};
END;

EquivalentHugs:PROCEDURE[a,b:Huggers] RETURNS[BOOLEAN]=BEGIN
RETURN[a.ch=b.ch AND (a.n#w)=(b.n#w) AND (a.s#w)=(b.s#w)
                 AND (a.e#n)=(b.e#n) AND (a.w#n)=(b.w#n)];
END;

Across:PROCEDURE[run:RunNo] RETURNS[Lambda]=BEGIN
IF run=bigRun THEN Error;
RETURN[7*run];
END;

AcrossS:PROCEDURE[run:RunNo] RETURNS[Lambda]=BEGIN
IF run=bigRun THEN Error;
RETURN[7*run+spaceB];
END;

END.

Timing:
  Make - Inter*All PAths + AllIWires
  Silicon - Inter x 4 x IWires
  Where - IWire