Documentation:

The modules which implement Beads are:
BeadsDefs - The Types and Procedures
BeadsInlines- common simple operations on the beads
BeadsCtl - which does very little except decide what should be done
BeadsUser - which talks to the keyboard and the file system
BeadsCreate - which makes beads out of Sticks
BeadsPrint - which makes the pretty pictures on the screen
- and formats major data structures for printing
- and holds global data and utility routines
BeadsBelow - whose job is to enumerate every bead "below" a bead
BeadsPut - places the beads in the compression logic
BeadsFall - straightens out bent wires
- lowers beads placed unnecessarily high
- combines overlapping beads
- Other micsellaneous wire related stuff
BeadsClean - Tries to reduce Capacitance by moving several beads
BeadsLocal - Makes Local transformations
- makes "free" transformations each pass
BeadsMove - Utility subroutines for BeadsLocal
BeadsTest - checks a bead figure for design rule violation
BeadsNoodles-handles the bent wire data structures

Start your study of Beads by glancing at Beadsdefs and Beadsinlines. Then begin with the module called beadsCtl.
Then Glance at the start of beadsPrint to see what Deltas does.
Then leap into beadsPut.

BEADSPUT DOCUMENTATION 1
PositionBeads and Push:
Position Beads implements the heart of the whole algorithm. All of the other modules can be considered as initialization, cleanup, efficiency hacks, or utility routines (Local Transformations excepted). Position is called with a loose diagram, and compresses it in the y dimension. To get compression in x, the whole diagram is rotated 90 degrees and Position is called again. Position accepts several minor parameters (like whether or not to bend wires).
The algorithm of position beads is to first place all the beads at the top of the figure, then to enumerate through all pairs of beads i and j and call Shoot to adjust down the position of j so that it is legal with respect to i. Whenever Shoot repositions a bead j , it calls Push[j] to tell Position that j has moved. Position continues to run until every pair has been processed with the i of the pair in its final position.
Position owns three data structures: a boolean per bead called "processed", a backpointer per bead to hold the inverse of the (constant) sort table, and the global "pushingY" which says how far through the processing we are. Position itself, as opposed to its friend Shoot, knows almost nothing about the details of beads, although it does know enough not to bother processing vertical wires.
For efficiency, position processes the higher beads first, based on the last iteration through the processing, hoping to not have to reprocess many beads - actually it should never reprocess beads except when they are connected as neighbors (rather than interacting by closeness). Also, Position does not try all of the possible j, but only those recommended by TryAllBelow, which is cleverly constructed to be able to find the few beads which might possibly interact with i without looking at those which cannot interact. The result of these two efficiencies is to change a potential n cubed algorithm to an n log n algorithm (TryAllBelow returns log n candidates for j - actually it returns something like 6 plus 1/8 log n, which means that one doesn’t see the log n until n = 2 to the 50 -but these numbers are shakey).

Shoot[i,j]: The function of Shoot is to make j legal with respect to i by moving j down, if necessary. Shoot uses Deltas to find the minumum x and y separation for interaction between i and j - all the design rule information is imbedded in Deltas (almost). Actually, Shoot is nothing but a big dispatch routine, determining which of several cases apply and then calling the appropiate routine labeled "try" to actually do the work. The cases recognized by Shoot are:
j is above i - assumed not to occur
i is vertical wire - assumed not to occur
j is vertical wire - do nothing (should not occur?)
i and j are tied - call tryT
i and j are different levels - do nothing (should not occur?)
i and j are across a TT - do nothing (should go in Deltas?)
i and j are neighbors - call tryR or tryL
i or j has negative length - do nothing
i and j are stiff - call try1
i is stiff - call try2
j is stiff - call try3
no stiff - call try4
A bead is stiff if it cannot bend. Only long wires can bend, ans those only when bending is asked for.

BEADSPUT DOCUMENTATION 2

Position Beads is a control procedure. It contains all of the enumerations by beads (there are four). The first is a simple initializatin. The second is the main processing pass to position the beads. The third finds the lowest value of Y, and the fourth normalizes the diagram using that value, to keep the lower left corner at (0,0). The third pass must track out along bent wires, and so is time n Log nwhen bending (but time n otherwise). The second pass is more complex. First, the main enumeration allows for backing up when there is an error i the dependency graph. That happens only when beads are directly connected, and in the worse case causes a slowdown proportional to the square of the number of horizontally connected beads. I don’t really know the statistics of connection, but I estimate lon n for that. Then when bending wires, one must run out along the wire (actually, several times). Clean needle right now actually runs out in a way which could go as the square of the number of jogs in the wire, making a factor of log2 n. Fortunately, when one is bending a wire of any length, the dependency between adjacent beads disappears, so one should see a factor of log2 n in either of two ways, but not a factor of log4n. Unfortunately, I do things in somewhat the wrong order, so the log4 can appear. Fortunately, this is not the slowest thing in the processing because of constant factors. When examining a bead, one must also examine all the beads below that bead. This adds yet one more factor of log n, for a total of five such factors.

The structure of BeadsPut is a simple tree of procedure calls, with the four loops explicitely spelled out in the top level procedure. The routine called Push, which is one of the leaves of the tree, has the ability to back up the loop variable for the second loop. Program bugs here can cause infinite looping. The routine called Shoot decides which of seven cases we have here, and calls the seven routines whose names begin with Try to handle them.

There are several places where a routine will enumerate its way through the bent segments of a wire (the noodles). Usually this is a simple enumeration, but the routine called CleanNoodle, whose function is to put the wire into a standard form(no zero height bends, for example), starts over when it finds and corrects a non-standard form. If the fix doesn’t really fix whatever the test found, CleanNoodle can loop. This is bad design.

There is also an enumeration through all of the beads below this bead, using the BeadsBelow logic.

There are two things which might sometimes be done to beads put to make it better. The first is to make cleanNoodle continue rather than restarting. This is in principle easy, but there are a lot of temporary values to recompute. The second is conceptually more difficult. Right now, BeadsPut selects a bead to process and makes all the beads below it legal. The bead itself is assumed to be legal because preceeding beads have followed the same discipline. To do this we must be able to find all the beads below this one. An alternate, and better strategy, is to select a bead and make it legal with respect to all the beads above it. This has no conceptual difference, but does help a bit with the adjacent bead/bending bead problem. It also means that one will need to separately conpute the beads Above and the beads below tables, because both are needed (one for Put, one for Fall) with this approach.


BEADS FALL DOCUMENTATION

Fall: The intent of Fall is to try to let each bead move down in such a way that horizontal wires get straightened out and vertical wires get shortened ( if that is convenient and legal) There are several reasons to implement fall:
1) a bent wire uses up more computer storage than a straight(er) one
2) some cases of fall produce less colored area locally, which is electrically better.
3) unnecessarily bent wires tend to inhibit further progress in compressing the diagram in the other dimension.

WireFall[i]: The intent of wire fall is to examine a horizontal wire for bends, and to straighten out the bends by dropping the higher wire segment if that is possible. There are three cases - a bend up, a bend down, and a bend of height 0 (not fundamental, but this is a good place to get rid of them). The details are complicated at each end by several constraints: a segment anchored to a transistor cannot drop, a segment anchored to a bead of larger width may slide along that bead, and should do so according to rules which depend on the next segment over, and one must watch out for zero width segments at the ends. WireFall mainpulates noodles directly.


ScourBead:PROCEDURE[i:CARDINAL,bpi:BeadPtr]=BEGIN
conu,cond:BOOLEAN;
up:CARDINAL←bpi.beadU;
down:CARDINAL←bpi.beadD;
bpu:BeadPtr←Get[up];
bpd:BeadPtr←Get[down];
room:BOOLEAN←(NoBeadL[bpu] OR NoBeadL[bpd])
AND (NoBeadR[bpu] OR NoBeadR[bpd]);
IF ~VerticalWire[bpi] OR bpu.y>=Top[bpd]+8 OR ~room THEN RETURN;
SELECT bpu.t FROM
jctnG,jctnR,jctnB=>conu←FALSE; bg,rb,bf=>conu←TRUE; ENDCASE=>RETURN;
SELECT bpd.t FROM
jctnG,jctnR,jctnB=>cond←FALSE; bg,rb,bf=>cond←TRUE; ENDCASE=>RETURN;
SELECT TRUE FROM
Top[bpu]<=Top[bpd] AND ~conu=>
{FixLR[up,down]; RemoveUpAndI[i,bpi];};
bpu.y<=bpd.y AND ~cond =>{ FixLR[down,up]; RemoveRtAndI[i,bpi];};
conu AND cond AND bpu.x=bpd.x AND bpu.y=bpd.y
AND bpu.h=bpd.h AND bpu.w=bpd.w => BEGIN
s:CARDINAL←bpu.beadT; bps:BeadPtr←Get[s];
t:CARDINAL←bpd.beadT; bpt:BeadPtr←Get[t];
hooked:BOOLEAN←bps.beadD=bpt.beadU AND ~NoBeadD[bps];
IF bps.beadT=up AND bpt.beadT=down
AND (NoBeadL[bps] OR NoBeadL[bpt])
AND (NoBeadR[bps] OR NoBeadR[bpt])
AND (hooked OR (NoBeadU[bps] OR NoBeadU[bpt])
AND (NoBeadD[bps] OR NoBeadD[bpt]))
AND (NoBeadD[bps] OR NoBeadU[bpt] OR bps.beadD=bpt.beadU)
THEN BEGIN
FixLR[down,up];
RemoveDownAndI[i,bpi];
FixLR[t,s];
IF hooked THEN Get[bps.beadD←bpt.beadD].beadU←s ELSE FixUD[t,s];
IF hooked THEN ReleaseBead[bpt.beadU];
ReleaseBead[t];
END;
END;
ENDCASE;
END;


Structure Things

BeadsCtl:PROGRAM

Top Level Names
Error:SIGNAL=CODE
cleanup:BOOLEAN
doWires:BOOLEAN
scour:BOOLEAN
drop:BOOLEAN
bothWays:BOOLEAN
disp:BOOLEAN
lookAtBelow:BOOLEAN
Main:PROCEDURE
Push:PROCEDURE[i:INTEGER]
rot:BOOLEAN
Squeeze:PROCEDURE[rotate:BOOLEAN]
FallOne:PROCEDURE[i:Desc]
NewYGetsY:PROCEDURE[i:Desc]
InitSqueeze:PROCEDURE
FinalSqueeze:PROCEDURE[s:STRING,xx:INTEGER]
PrintSomeBelowStuff:PROCEDURE
SortOnY:PROCEDURE
FastSort:PROCEDURE[low,high,bit:CARDINAL]
ShowTime:PROCEDURE[c:CARDINAL]
Finish:PROCEDURE

findings
has two unreachable routines(FastSort,Finish)
contains no recursion(except unreachable FastSort)
hands off two routines(NewYGetsY,FallOne)
exports nothing
has four loops

Call Structure(internal only)
Main=>Push=>Squeeze(2)=>NewYGetsY
=>FallOne
=>InitSqueeze(2)=>PrintSomeBelowStuff
=>SortOnY
=>ShowTime
=>FinalSqueeze(2)=>ShowTime(2)
=>ShowTime(2)
=>ShowTime
FastSort=>FastSort(2)

External Calls and Variables
Main:bendingWires,SetUpForRun,Local,CheckBeads,FullTest,Finalize
Push:howMuch
Squeeze:bendingWires,InitPut,FixWires(3),PositionBeads,AdjustTheBottom,
EnumerateBeads,ResetBelow,EnumerateSortedBottomUp,PrintCounts,ScourBeads,
Cleanup,WriteOneNumber,Clean
FallOne:VerticalWire,WireFall,BeadFall
NewYGetsY:Getw,Bot
InitSqueeze:timeV5,timeV6,time,Reflect,FindBoundingBox,EnumerateBeads,
InitBeadWork,MakeBelow
FinalSqueeze:maxX,maxY,TurnWiresToBeads,ScavageBeads,Reflect,
FindBoundingBox,Display,WriteOneNumber(3)
PrintSomeBelowStuff:timeV5,timeV6,ShowBelow,WriteString,WriteChar
SortOnY:topBead,GetW,GetDesc
FastSort:GetW,Get,BITAND
ShowTime:time,CurrentTime,WriteOneNumber,LowHalf
Finish:AdjustTheBottom,FixWires,ManipulateDisplay

CALL STRUCTURE OF BEADSPUT

StartIncrementalDisplay:
IncrementalDisplay:
EndIncrementalDisplay:
*PositionBeads: EnumerateBeads(3) InitNoodle, ClearCounts
InitBackSortAndProcessed StartIncrementalDisplay
PlaceABead EndIncrementalDisplay FindGain MoveDown PrintCounts
PlaceABead:TryAllBelow, Shoot IncrementalDisplay
ClearCounts:
InitBackSortAndProcessed:
Shoot: Delta TryT TryR TryL Try1 Try3 Try2 Try4 ShowTracked
TryT:UpdateY
TryL:UpdateY DoSegment
TryR:UpdateY LowestPoint
Try1:UpdateY
Try2:DoSegment
Try3:FollowShortNoodle Lowest(2) UpdateY
Lowest:
Try4:FollowNoodle NoName DoSegment
NoName:DoSegment
UpdateY:MakeNewNoodle DoSegment Push[bj];
DoSegment:FollowNoodle SegSeg(2) CleanNoodle
Append:IncrementNoodle MakeNewNoodle
SegSeg:InsertNewNoodle SetNoodle Append(3) Push[bj]
CleanNoodle:FollowNoodle(2) CheckWire(2) NoName StillNoName
NoName:MergeL
StillNoName:MergeR(2) MergeL MergeLPlus(4) MoveJog(3)
IncrementNoodle(3) ReleaseNoodle NearRight(2) Wicket Push(3)
NearRight:
Wicket:
Seen1:
CheckWire:FollowShortNoodle NoName(2)
NoName:
Push:
FindGain:LowestPoint
MoveDown:
LowestPoint:FollowShortNoodle NoName
NoName:
PrintCounts:WriteChar PrintLong(4)
ShowTracked:WriteChar WriteNumber(3) WriteString(2)


Call Structure of Bedsfall

*FallTwo: FallOne BeadFall
*FallOne: WireFall BeadFall
*WireFall: StartBentWire FollowNoodle NoName ReleaseLink(2)
DropSeg(3) IncrementNoodle(4) BeadFall
NoName: DropSeg(2) MergeLeft MergeRight
*BeadFall: Delta StartBentWire DropSeg DropBead(2)
MakeNewY(4) IncrementNoodle(2) ReleaseNoodle MakeNewNoodle
MakeNewY: IncrementY Seen2 Track
Seen2:
Track:
DropBead: DropSeg
DropSeg: TryAllBelow FallOk
FallOk: TestWireSegment Delta Track
TestWireSegment: Delta StartBentWire FollowNoodle NoName(2)
NoName:
*FixWires: EnumerateBeads FixWire
*FixWire:
*TurnWiresToBeads: EnumerateBeads TurnWire
*TurnWire: GetNoodle Jig(2) MakeBead(4) FixWire(3) IncrementY
Jig: IncrementNoodle IncrementY
MakeBead: GetFreeBead
*GetFreeBead: