--beadsmove.mesa DIRECTORY IODefs:FROM"IODefs", BeadsInlines:FROM"BeadsInlines", InlineDefs:FROM"InlineDefs", BeadsDefs:FROM"BeadsDefs"; BeadsMove:PROGRAM IMPORTS BeadsInlines, InlineDefs,IODefs,BeadsDefs EXPORTS BeadsDefs = BEGIN OPEN BeadsDefs, BeadsInlines; Error:SIGNAL=CODE; oldtopBead:CARDINAL; maxCache:INTEGER=100; index:CARDINAL_ 0; cache:ARRAY [0..maxCache] OF Bead; --saves state until after transformation address:ARRAY [0..maxCache] OF CARDINAL; abort:ARRAY [0..maxCache] OF BOOLEAN; --this bead is abortable shift:ARRAY [0..maxCache] OF BOOLEAN; --this bead is shiftable noMoves:INTEGER_0; maxMoves:INTEGER=20; ShiftLeft,ShiftRight,ShiftUp,ShiftDown:BOOLEAN; shortLegalOK:BOOLEAN_FALSE; maxPathLength:INTEGER= 20; step:INTEGER[0..maxPathLength]; path:ARRAY [0..maxPathLength] OF Step; --contains the current path Step:TYPE= RECORD[bead:CARDINAL,v:Variant]; deleteindex:CARDINAL[0..20]_ 0; delete:ARRAY [0..20] OF CARDINAL; --cache of beads to be deleted KeepMesaHappy:PROCEDURE =BEGIN IODefs.WriteChar['*]; END; --************************************************************************ Process:PUBLIC PROCEDURE= BEGIN FOR i:CARDINAL IN [0..index) DO IF shift[i] AND ~RoomFor[address[i]] THEN {Abort[]; EXIT}; ENDLOOP; FOR i:CARDINAL IN [0..index) DO IF shift[i] AND ~Move[address[i],Zero] THEN {Restore[]; RETURN}; ENDLOOP; Commit[]; END; --************************************************************************ --path detection and removal Find:PUBLIC PROCEDURE[b:BeadType,i:CARDINAL] RETURNS[CARDINAL]=BEGIN t:Desc_DescT[GetDesc[i]]; RETURN[IF t.p.t=b THEN t.z ELSE t.p.beadT]; END; FindPath:PUBLIC PROCEDURE[i,j:CARDINAL,v:Variant] RETURNS[BOOLEAN]= BEGIN FindOut:PROCEDURE[v:Variant,bpi:BeadPtr] RETURNS[BOOLEAN]= BEGIN RecursiveFindPath:PROCEDURE[mm:CARDINAL,v:Variant] RETURNS[BOOLEAN]= BEGIN IF mm=noBead THEN RETURN[FALSE]; IF mm=j THEN RETURN[TRUE]; IF i=mm OR step> maxPathLength THEN RETURN[FALSE]; BEGIN m:Desc_GetDesc[mm]; IF Trans[m] THEN RETURN[FALSE]; path[step]_[m.z,v]; step_step+1; RETURN[FindOut[v,m.p]]; END; END; IF v#left AND RecursiveFindPath[bpi.beadR,right] THEN RETURN[TRUE]; IF v#right AND RecursiveFindPath[bpi.beadL,left ] THEN RETURN[TRUE]; IF v#up AND RecursiveFindPath[bpi.beadD,down ] THEN RETURN[TRUE]; IF v#down AND RecursiveFindPath[bpi.beadU,up ] THEN RETURN[TRUE]; IF v#tied AND RecursiveFindPath[bpi.beadT,tied ] THEN RETURN[TRUE]; step_step-1; RETURN[FALSE]; END; step_ 0; RETURN[FindOut[v,Get[i]]]; END; RemovePaths:PUBLIC PROCEDURE[i,j:CARDINAL,v:Variant]=BEGIN IF i=noBead OR j=noBead THEN RETURN; WHILE FindPath[i,j,v] DO Remove[path[0].bead]; FOR k:INTEGER IN [1..step) WHILE NumRelatives[path[k].bead]< 2 DO Remove[path[k].bead]; ENDLOOP; ENDLOOP; END; --************************************************************************ --queries about the beads NumRelatives:PUBLIC PROCEDURE[ii:CARDINAL] RETURNS[num:CARDINAL]= BEGIN i:Desc_GetDesc[ii]; num_(IF NoBeadR[i] THEN 0 ELSE 1) +(IF NoBeadL[i] THEN 0 ELSE 1) +(IF NoBeadU[i] THEN 0 ELSE 1) +(IF NoBeadD[i] THEN 0 ELSE 1) +(IF NoBeadT[i] THEN 0 ELSE 1); END; Overlap:PUBLIC PROCEDURE[i,j:CARDINAL] RETURNS[BOOLEAN]= BEGIN s:Desc_GetDesc[i]; t:Desc_GetDesc[j]; RETURN[InteractH[s,t,0] AND InteractV[s,t,0]] END; SlackH:PROCEDURE[i,v:Desc] RETURNS[INTEGER]=BEGIN t1:INTEGER_Bot[v]-Bot[i]; t2:INTEGER_Top[v]-Top[i]; RETURN[IF t1>0 THEN MAX[0,MIN[t1,t2]] ELSE MIN[0,MAX[t1,t2]]]; END; SlackV:PROCEDURE[i,v:Desc] RETURNS[INTEGER]=BEGIN t1:INTEGER_Lfm[v]-Lfm[i]; t2:INTEGER_Rtm[v]-Rtm[i]; RETURN[IF t1>0 THEN MAX[0,MIN[t1,t2]] ELSE MIN[0,MAX[t1,t2]]]; END; Push:PROCEDURE[i,j:Desc] RETURNS[d:Coord]= BEGIN --i pushes on j. How far must j move? delta:Coord_Delta[i,j]; w:INTEGER_ IF Lfm[i] IF x> y THEN d.y_ 0 ELSE d.x_ 0; ~NoBeadL[j] => d.x_0; ~NoBeadU[j] => d.y_0; ENDCASE; RETURN[d]; END; RETURN[Zero]; END; --************************************************************************ --procedures that modify the beads structure Initialize:PUBLIC PROCEDURE= BEGIN -- cache_ LOOPHOLE[work]; --address_ LOOPHOLE[work+ 16*maxCache]; -- abort_ LOOPHOLE[work+ 17*maxCache]; -- shift_ LOOPHOLE[work+ 18*maxCache]; oldtopBead_ topBead; Clear[Get[noBead]]; END; SaveBoth:PROCEDURE[i,j:Desc]={Save[i.z,FALSE,FALSE]; Save[j.z,FALSE,FALSE]}; Clear:PROCEDURE[bpi:BeadPtr]= BEGIN bpi.beadL_bpi.beadR_bpi.beadU_bpi.beadD_bpi.beadT_ noBead; END; Attach:PUBLIC PROCEDURE[i:Desc,variant:Variant,j:Desc]= BEGIN --Attach i to the variant of j m,n:Desc; SaveBoth[i,j]; SELECT variant FROM left => BEGIN SaveBoth[m_DescR[i],n_DescL[j]]; m.p.beadL_ noBead; n.p.beadR_noBead; HookLR[i,j]; END; right => BEGIN SaveBoth[m_DescR[j],n_DescL[i]]; m.p.beadL_noBead; n.p.beadR_noBead; HookLR[j,i]; END; up => BEGIN SaveBoth[m_DescU[j],n_DescD[i]]; m.p.beadD_noBead; n.p.beadU_noBead; HookUD[j,i]; END; down => BEGIN SaveBoth[m_DescU[i],n_DescD[j]]; m.p.beadD_noBead; n.p.beadU_noBead; HookUD[i,j]; END; tied => BEGIN IncrementX[i,Lfm[j]-Lfm[i]+(Width[j]- Width[i])/2]; IncrementY[i,Bot[j]-Bot[i]+(Height[j]- Height[i])/2]; SaveBoth[m_DescT[i],n_DescT[j]]; m.p.beadT_noBead; n.p.beadT_noBead; IF ~NoBead[i] THEN i.p.beadT_j.z; j.p.beadT_i.z; END; ENDCASE; END; AttachAll:PUBLIC PROCEDURE[i,j:CARDINAL]= BEGIN AttachOne:PROCEDURE[i:Desc,v:Variant]= INLINE BEGIN IF ~NoBead[i] THEN Attach[i,v,GetDesc[j]]; END; k:Desc_GetDesc[i]; AttachOne[DescL[k],left ]; AttachOne[DescR[k],right]; AttachOne[DescU[k],up ]; AttachOne[DescD[k],down ]; AttachOne[DescT[k],tied ]; END; Move:PUBLIC PROCEDURE[i:Desc,a:Coord]] RETURNS[BOOLEAN] = BEGIN IF noBead[i] THEN RETURN[TRUE] ELSE BEGIN d:Desc_DescD[i]; l:Desc_DescL[i]; u:Desc_DescU[i]; r:Desc_DescR[i]; t:Desc_DescT[i]; w:INTEGER_ Width[i]; h:INTEGER_ Height[i]; k:Desc_IF NoBead[t] THEN i ELSE DescT[t]; IF Lfm[i]+ a.x ~IN [0..maxX-w] OR Bot[i]+ a.y ~IN [0..maxY-h] OR (noMoves_ noMoves+1)>maxMoves THEN RETURN[FALSE]; noMoves_ noMoves+1; Save[i,TRUE,FALSE]; IncrementX[i,a.x]; IncrementY[i,a.y]; SetW[i,w]; SetH[i,h]; IF ~Movex[down ,u, Zero] OR ~Movex[left ,r, Zero] OR ~Movex[up ,d, Zero] OR ~Movex[right,l, Zero] OR ~Movex[tied ,t,a] OR k#m AND ~Movex[tied ,k,a] THEN RETURN[FALSE]; RETURN[Legal[i]]; END; END; Movex:PUBLIC PROCEDURE[variant:Variant,i:Desc,a:Coord]] RETURNS[BOOLEAN] = BEGIN IF noBead[i] THEN RETURN[TRUE] ELSE BEGIN d:Desc_DescD[i]; l:Desc_DescL[i]; u:Desc_DescU[i]; r:Desc_DescR[i]; t:Desc_DescT[i]; w:INTEGER_ Width[i]; h:INTEGER_ Height[i]; IF Wir[i] THEN BEGIN d5:INTEGER_Des5[desP[Type[u]].short][desP[Type[d]].short]; d7:INTEGER_Des7[desP[Type[l]].short][desP[Type[r]].short]; SELECT variant FROM left =>{w_MAX[d7,Lfm[r]-Rtm[l]]; a_[Rtm[l]-Lfm[i],SlackH[i,l]]}; down =>{h_MAX[d5,Bot[u]-Top[d]]; a_[SlackV[i,d],Top[d]-Bot[i]]}; right=>{w_MAX[d7,Lfm[r]-Rtm[l]]; a_[Lfm[r]-(Lfm[i]+w),SlackH[i,r]]}; up =>{h_MAX[d5,Bot[u]-Top[d]]; a_[SlackV[i,u],Bot[u]-(Bot[i]+h)]}; ENDCASE; IF a=Zero AND Width[i]=w AND Height[i]=h THEN RETURN[TRUE]; END; IF a=Zero THEN RETURN[TRUE]; BEGIN k:Desc_IF NoBead[t] THEN i ELSE DescT[t]; IF Lfm[i]+ a.x ~IN [0..maxX-w] OR Bot[i]+ a.y ~IN [0..maxY-h] OR (noMoves_ noMoves+1)>maxMoves THEN RETURN[FALSE]; Save[i,TRUE,FALSE]; IncrementX[i,a.x]; IncrementY[i,a.y]; SetW[i,w]; SetH[i,h]; IF variant#up AND ~Movex[down ,u, Zero] OR variant#right AND ~Movex[left ,r, Zero] OR variant#down AND ~Movex[up ,d, Zero] OR variant#left AND ~Movex[right,l, Zero] OR variant#tied AND ~Movex[tied ,t,a] OR variant#tied AND k#m AND ~Movex[tied ,k,a] THEN RETURN[FALSE]; RETURN[Legal[i]]; END; END; END; Zero:Coord=[0,0]; Legal:PROCEDURE[i:Desc] RETURNS[r:BOOLEAN]= BEGIN RETURN[IF shortLegalOK THEN LegalShort[i] ELSE LegalLong[i]]; END; LegalLong:PROCEDURE[i:Desc] RETURNS[BOOLEAN]= BEGIN --make the rest of the world legal with respect to i NoName:PROCEDURE[j:Desc] RETURNS[abort:BOOLEAN]=BEGIN d:Coord_ Push[i,j]; SELECT TRUE FROM d=Zero OR TouchingBeads[i,j] OR TiedBeads[i,j] =>NULL; ~Move[j,d] =>RETURN[TRUE]; ENDCASE; RETURN[FALSE]; END; RETURN[~EnumerateBeadsWithAbort[NoName]]; END; Zero:Coord_[0,0]; LegalShort:PROCEDURE[i:Desc] RETURNS[r:BOOLEAN]= BEGIN Error; RETURN[TRUE]; END; Put:PUBLIC PROCEDURE[i:Desc,dx,dy,h,w:INTEGER]= BEGIN Save[i,FALSE,TRUE]; IncrementX[i,dx]; IncrementY[i,dy]; IF h#0 THEN SetH[i,h]; IF w#0 THEN SetW[i,w]; END; Create:PROCEDURE[ty:BeadType,x,y,h,w,circuit:INTEGER] RETURNS[Desc]= BEGIN t:Desc_GetFreeBead[]; Save[t]; t.p.x_ x; t.p.y_ y; t.p.circuit_ circuit; t.p.w_ IF w=0 THEN desP[ty].w ELSE w; t.p.h_ IF h=0 THEN desP[ty].h ELSE h; t.p.t_ ty; t.p.wire_ ty=wireG OR ty=wireB OR ty=wireR; InitBeadWork[t]; RETURN[t]; END; InsertJogs:PUBLIC PROCEDURE[i:Desc,horizontal,vertical:Variant]= BEGIN InsertJog[i,left,horizontal]; InsertJog[i,right,horizontal]; InsertJog[i,down,vertical]; InsertJog[i,up,vertical]; END; InsertJog:PROCEDURE[i:Desc,whichEnd,bend:Variant]= BEGIN wire:Desc_SELECT whichEnd FROM left=>DescR[i], right=>DescL[i], up=>DescD[i], ENDCASE=>DescU[i]; IF NoBead[wire] THEN RETURN ELSE BEGIN wt:BeadType_ Type[wire]; vert:BOOLEAN_ whichEnd=up OR whichEnd=down; s:INTEGER_IF wt=wireB THEN 6 ELSE 4; x:INTEGER_Lfm[i]; y:INTEGER_Bot[i]; jt:BeadType_ SELECT wt FROM wireR => jctnR,wireB => jctnB, ENDCASE => jctnG; j1:Desc_ Create[jt,x,y,s,s,i.p.circuit]; j2:Desc_ Create[jt,x,y,s,s,i.p.circuit]; w1:Desc_ IF vert THEN Create[wt,x,y+s,-s,s,i.p.circuit] ELSE Create[wt,x+s,y,s,-s,i.p.circuit]; w2:Desc_ IF vert THEN Create[wt,x+s,y,s,-s,i.p.circuit] ELSE Create[wt,x,y+s,-s,s,i.p.circuit]; Attach[i,whichEnd,w1]; Attach[j2,whichEnd,wire]; Attach[w1,whichEnd,j1]; Attach[j2,bend,w2]; Attach[w2,bend,j1]; END; END; --************************************************************************ --find room for a group of beads RoomFor:PUBLIC PROCEDURE[ii:CARDINAL] RETURNS[r:BOOLEAN]= BEGIN --make i legal with respect to the rest of the world i:Desc_GetDesc[ii]; quit:BOOLEAN_FALSE; NoName:PROCEDURE[j:Desc]=BEGIN IF quit THEN RETURN ELSE BEGIN d:Coord_ Push[i,j]; quit_d#Zero AND ~TouchingBeads[i,j] AND ~TiedBeads[i,j] AND Shift[-d.x,-d.y]; END; END; EnumerateBeads[NoName]; RETURN[~quit]; END; ClearShift:PUBLIC PROCEDURE= BEGIN ShiftLeft_ ShiftRight_ ShiftUp_ ShiftDown_ FALSE; END; Shift:PUBLIC PROCEDURE[dx,dy:INTEGER] RETURNS[BOOLEAN]= BEGIN IF dx<0 AND ShiftLeft THEN RETURN[FALSE] ELSE ShiftLeft_ TRUE; IF dx>0 AND ShiftRight THEN RETURN[FALSE] ELSE ShiftRight_ TRUE; IF dy<0 AND ShiftDown THEN RETURN[FALSE] ELSE ShiftDown_ TRUE; IF dy>0 AND ShiftUp THEN RETURN[FALSE] ELSE ShiftUp_ TRUE; FOR i:CARDINAL IN [0..index) DO IF shift[i] THEN BEGIN a:Desc_GetDesc[address[i]]; IncrementX[a,dx]; IncrementY[a,dy]; END; ENDLOOP; RETURN[TRUE]; END; --************************************************************************ --procedures that save state until a transformation is complete Save:PUBLIC PROCEDURE[a:CARDINAL,abortable,shiftable:BOOLEAN]= BEGIN IF a= noBead THEN RETURN; IF a> oldtopBead THEN RETURN; IF index> maxCache THEN Error; --you should increase maxCache cache[index]_ Get[a]^; address[index]_ a; abort[index]_ abortable; shift[index]_ shiftable; index_ index+ 1; END; Remove:PUBLIC PROCEDURE[i:CARDINAL]=BEGIN --get the bead out of the way bpi:BeadPtr_Get[i]; Save[i,FALSE,FALSE]; delete[deleteindex]_ i; deleteindex_ deleteindex+ 1; SaveAndClear[bpi,right]; SaveAndClear[bpi,left]; SaveAndClear[bpi,up]; SaveAndClear[bpi,down]; SaveAndClear[bpi,tied]; bpi.x_ 2*maxX; bpi.y_ 2*maxY; Clear[bpi]; END; --NONSENSE SaveAndClear:PROCEDURE[bpi:BeadPtr,v:Variant]=BEGIN t:CARDINAL_SELECT v FROM right=>bpi.beadR,left=>bpi.beadL, up=>bpi.beadU, down=>bpi.beadD, tied=>bpi.beadT, ENDCASE=>ERROR; IF t=noBead THEN RETURN; Save[t,FALSE,FALSE]; SELECT v FROM right=>bpi.beadL_noBead; left =>bpi.beadR_noBead; up =>bpi.beadD_noBead; down =>bpi.beadU_noBead; tied =>bpi.beadT_noBead; ENDCASE=>ERROR; END; Restore:PUBLIC PROCEDURE= BEGIN FOR i:CARDINAL DECREASING IN [0..index) DO this:Desc_GetDesc[address[i]]; this.p^_cache[i]; IF Type[this]=none THEN ReleaseBead[this]; ENDLOOP; noMoves_ deleteindex_ index_ 0; END; Abort:PUBLIC PROCEDURE=BEGIN noMoves_0; FOR i:CARDINAL DECREASING IN [0..index) DO IF abort[i]=TRUE THEN Get[address[i]]^_ cache[index_ i]; ENDLOOP; END; Commit:PUBLIC PROCEDURE=BEGIN FOR i:INTEGER IN [0..deleteindex) DO IF delete[i]=noBead THEN Error; ReleaseBead[GetDesc[delete[i]]]; ENDLOOP; noMoves_ index_ deleteindex_0; oldtopBead_ topBead; END; --************************************************************************ Rotate:PUBLIC PROCEDURE= BEGIN FindBoundingBox[]; EnumerateBeads[RotateOne]; END; Reflect:PUBLIC PROCEDURE= BEGIN FindBoundingBox[]; EnumerateBeads[ReflectOne]; END; RotateBack:PUBLIC PROCEDURE= BEGIN FindBoundingBox[]; EnumerateBeads[RotateBackOne]; END; RotateOne:PROCEDURE[i:Desc]=BEGIN s:CARDINAL; t:INTEGER; t_Bot[i]; i.p.y_maxX-Rtm[i]; i.p.x_t; t_i.p.w; i.p.w_i.p.h; i.p.h_t; s_i.p.beadL; i.p.beadL_i.p.beadD; i.p.beadD_i.p.beadR; i.p.beadR_i.p.beadU; i.p.beadU_s; i.p.t_desP[i.p.t].rotate; END; ReflectOne:PUBLIC PROCEDURE[i:Desc]=BEGIN s:CARDINAL; t:INTEGER; t_Bot[i]; i.p.y_Lfm[i]; i.p.x_t; t_i.p.w; i.p.w_i.p.h; i.p.h_t; s_i.p.beadL; i.p.beadL_i.p.beadD; i.p.beadD_s; s_i.p.beadR; i.p.beadR_i.p.beadU; i.p.beadU_s; i.p.t_desP[i.p.t].rotate; END; RotateBackOne:PUBLIC PROCEDURE[i:Desc]=BEGIN s:CARDINAL; t:INTEGER; t_Bot[i]; i.p.x_maxY-Top[i]; i.p.y_t; t_i.p.w; i.p.w_i.p.h; i.p.h_t; s_i.p.beadL; i.p.beadL_i.p.beadU; i.p.beadU_i.p.beadR; i.p.beadR_i.p.beadD; i.p.beadD_s; i.p.t_desP[i.p.t].rotate; END; END.. AndOfRelatives:PUBLIC PROCEDURE[ii,jj:CARDINAL] RETURNS[BOOLEAN]= BEGIN i:Desc_GetDesc[ii]; j:Desc_GetDesc[jj]; RETURN[~NoBeadL[i] AND ~NoBeadL[j] OR ~NoBeadR[i] AND ~NoBeadR[j] OR ~NoBeadU[i] AND ~NoBeadU[j] OR ~NoBeadD[i] AND ~NoBeadD[j]]; END; DeleteBead:PUBLIC PROCEDURE[i:CARDINAL]=BEGIN j:CARDINAL; bpi:BeadPtr_Get[i]; bpt:BeadPtr_Get[topBead]; --switch the bead with the topBead Error; IF i=topBead THEN BEGIN topBead_topBead-1; RETURN; END; IF (j_bpt.beadU)#noBead THEN Get[j].beadD_i; IF (j_bpt.beadD)#noBead THEN Get[j].beadU_i; IF (j_bpt.beadR)#noBead THEN Get[j].beadL_i; IF (j_bpt.beadL)#noBead THEN Get[j].beadR_i; IF (j_bpt.beadT)#noBead THEN FOR j_topBead, Get[j].beadT DO IF Get[j].beadT=topBead THEN BEGIN Get[j].beadT_i; EXIT; END; ENDLOOP; bpi^_bpt^; topBead_topBead-1; END; (1792)\418i38I83i22I42i22I220i25I115i28I136b7B345b2Bi27bI4B143b8B931b11B346b2Bi24bI12B272b7B154b6B173b6B173b4B49i37I589i43bI10B225b8B70b5B98b6B60i28I1i1I10i1I16i1I24i4I117i5I115i2I118i4I116i4I297b9B320b4B730b5B1450b5B112b11B47i50I309b12B72b5B171b6B329b10B193b9B940i31bI7B61i50I296b10B83b5B583i62bI4B161i28I128b6B38i27I22i3I207i2I62b12B429b7B234b5B160b6B289b6B78b7B79b10B83b9B255b10B257b13B269b14B260b10B69i1I27i1I4i32I