DIRECTORY Asserting, Basics, CardHashTableThreaded, IntHashTable, Collections, IntFunctions, PairCollections, RefTab, Rope;

LichenDataStructure: CEDAR DEFINITIONS
IMPORTS RefTab, IntHashTable, Collections, IntFunctions
=

BEGIN OPEN Colls:Collections, PairColls:PairCollections, IntFns:IntFunctions;

nyet: ERROR --not yet implemented--;

Warning: SIGNAL [msg: ROPE, v1, v2, v3, v4, v5: REF ANY _ NIL];

Error: ERROR [msg: ROPE, v1, v2, v3, v4, v5: REF ANY _ NIL];

LNAT: TYPE ~ INT--[0 .. INT.LAST]--;
LORA: TYPE = LIST OF REF ANY;
LOLORA: TYPE = LIST OF LORA;
ROPE: TYPE = Rope.ROPE;
RopeList: TYPE = LIST OF ROPE;
LOR: TYPE ~ LIST OF ROPE;
LOLOR: TYPE ~ LIST OF LOR;
Assertions: TYPE = Asserting.Assertions;
Assertion: TYPE = Asserting.Assertion;
ColorTable: TYPE = CardHashTableThreaded.Table;

Set: TYPE ~ Colls.Set;
VarSet: TYPE ~ Colls.VarSet;
ConstSet: TYPE ~ Colls.ConstSet;
ConstFilter: TYPE ~ Colls.ConstFilter;
Function: TYPE ~ PairColls.Function;
VarFunction: TYPE ~ PairColls.VarFunction;
UWFunction: TYPE ~ PairColls.UWFunction;
ConstFunction: TYPE ~ PairColls.ConstFunction;
Relation: TYPE ~ PairColls.Relation;
VarRelation: TYPE ~ PairColls.VarRelation;
ConstRelation: TYPE ~ PairColls.ConstRelation;
OneToOne: TYPE ~ PairColls.OneToOne;
VarOneToOne: TYPE ~ PairColls.VarOneToOne;
ConstOneToOne: TYPE ~ PairColls.ConstOneToOne;
IntFn: TYPE ~ IntFns.IntFn;
Permutation: TYPE ~ IntFns.Permutation;

RefTable: TYPE = RefTab.Ref;
CreateRefTable: PROC RETURNS [rt: RefTable]
= INLINE {rt _ RefTab.Create[]};

IntTable: TYPE = IntHashTable.Table;
CreateIntTable: PROC RETURNS [it: IntTable]
= INLINE {it _ IntHashTable.Create[]};

GraphID: TYPE = {A, B, Unspecified};
RealGraphID: TYPE = GraphID[A .. B];
OtherGraph: ARRAY RealGraphID OF RealGraphID = [A: B, B: A];
graphIDToRope: GraphDescriptions;
GraphDescriptions: TYPE ~ ARRAY GraphID OF ROPE;
RealGraphDescriptions: TYPE ~ ARRAY RealGraphID OF ROPE;

Color: TYPE = INT;
noColor: Color = LAST[Color];
someColor: Color = 87654321H;
FilterColor: PROC [color: Color] RETURNS [filtered: Color] = INLINE {
filtered _ IF color # noColor THEN color ELSE someColor};

Design: TYPE = REF DesignPrivate;
DesignPrivate: TYPE = RECORD [
cellTypes: VarSet--of CellType--,
other: Assertions _ NIL,
allKnown: BOOL _ FALSE];

nameReln: ATOM;	--relative to narrowest enclosing scope
Describe: PROC [subject: REF ANY, relativeTo: REF ANY _ NIL, nameGen: NameGenerator _ NIL] RETURNS [ROPE];

SteppyDescribe: PROC [subject: REF ANY, relativeTo: REF ANY _ NIL, nameGen: NameGenerator _ NIL] RETURNS [SteppyName];

NameGenerator: TYPE = REF NameGeneratorPrivate;
NameGeneratorPrivate: TYPE = RECORD [
GenerateName: PROC [data, subject: REF ANY] RETURNS [ROPE],
data: REF ANY _ NIL
];

EnumerateCellTypes: PROC [design: Design, Consume: PROC [CellType]];

CellClass: TYPE = REF CellClassPrivate;
CellClassPrivate: TYPE = RECORD [
DefinePrivates: PROC [CellType]
];

CellType: TYPE = REF CellTypePrivate;
CellTypePrivate: TYPE = RECORD [
class: CellClass,
designs: VarSet--of Design--,
publicKnown, privateKnown: BOOL _ FALSE,
wasntNormalized: BOOL _ FALSE,
port: Port _ NIL,
asUnorganized: Unorganized _ NIL,
asArray: Array _ NIL,
firstInstance, lastInstance: CellInstance _ NIL,
firstArray, lastArray: CellType _ NIL,
useCount: INT _ 0 --#instances + #arrays--,
otherPublic, otherPrivate: Assertions _ NIL,
color: Color _ noColor];

EnumeratePorts: PROC [cellType: CellType, Consume: PROC [Port]];
ScanPorts: PROC [cellType: CellType, Consume: PROC [Port] RETURNS [subs, sibs: BOOL _ TRUE]];
EnumerateInstances: PROC [cellType: CellType, Consume: PROC [CellInstance], mirror: BOOL];
EnumerateArrays: PROC [cellType: CellType, Consume: PROC [CellType]];

partsByNameKey: ATOM;

PortList: TYPE = LIST OF Port;
Port: TYPE = REF PortPrivate;
PortPrivate: TYPE = RECORD [
next, prev: Port,
firstChild, lastChild: Port,
parent: REF ANY--UNION [Port, CellType]--,
wire: Wire _ NIL,
names: ListData,
other: Assertions _ NIL,
color: Color _ noColor];

PortCCT: PROC [port: Port] RETURNS [containingCT: CellType];
FirstChildPort: PROC [port: Port] RETURNS [child: Port]
= INLINE {child _ port.firstChild};
NextChildPort: PROC [child: Port] RETURNS [sibling: Port]
= INLINE {sibling _ child.next};
EnumeratePort: PROC [port: Port, Consume: PROC [Port] RETURNS [doKids, moreSibs: BOOL _ TRUE]] RETURNS [didKids, moreSibs: BOOL];

PortIndex: PROC [parent, child: Port] RETURNS [index: INT];
SubPort: PROC [parent: Port, index: INT] RETURNS [child: Port];

PortNames: PROC [port: Port] RETURNS [Set]
~ INLINE {RETURN [[listClass, port.names]]};

SteppyNameList: TYPE ~ LIST OF SteppyName;
SteppyName: TYPE ~ LIST OF NameStep --most significant first--;
NameStep: TYPE ~ REF ANY --actually UNION [ROPE, REF INT]--;

nameStepSpace, steppyNameSpace: Colls.Space;
SteppyNameEqual: PROC [n1, n2: SteppyName, clip1, clip2: SteppyName _ NIL] RETURNS [BOOL];

portToInternalWire: READONLY UWFunction--port of an Unorganized CellType _ its internal wire--;

Unorganized: TYPE = REF UnorganizedPrivate;
UnorganizedPrivate: TYPE = RECORD [
internalWire: Wire _ NIL,
containedInstances: VarSet--of CellInstance--,
mirror: CellInstance _ NIL --the outside world, as seen from the inside
];

Vertex: TYPE = REF VertexPrivate;
VertexPrivate: TYPE = RECORD [
containingCT: CellType,
QNext: Vertex _ notInQ,
colorNext, equiv: Vertex _ NIL,
firstEdge, lastEdge: Edge _ NIL,
names: ListData,
other: Assertions _ NIL,
oldColor, curColor: Color _ noColor,
graph: GraphID _ Unspecified,
unique, suspect: BOOL _ FALSE,
variant: SELECT class: VertexClass FROM
cell => [
type: CellType _ NIL,
nextInstance, prevInstance: CellInstance _ NIL
],
intermediate => [
port: Port
],
wire => [
containingWire: Wire _ NIL,
next, prev: Wire _ NIL, --Siblings
firstChild, lastChild: Wire _ NIL
],
ENDCASE];

VertexClass: TYPE = {cell, intermediate, wire};

CellInstance: TYPE = REF cell VertexPrivate;
Intermediary: TYPE = REF intermediate VertexPrivate;
Wire: TYPE = REF wire VertexPrivate;

VertexNames: PROC [v: Vertex] RETURNS [Set]
~ INLINE {RETURN [[listClass, v.names]]};

WireIndex: PROC [parent, child: Wire] RETURNS [index: INT];
SubWire: PROC [parent: Wire, index: INT] RETURNS [child: Wire];
EnumeratePortAndWire: PROC [port: Port, wire: Wire, Consume: PROC [Port, Wire]];
EnumerateWire: PROC [wire: Wire, Consume: PROC [Wire] RETURNS [doKids, moreSibs: BOOL _ TRUE]] RETURNS [didKids, moreSibs: BOOL];
FirstChildWire: PROC [parent: Wire] RETURNS [child: Wire]
= INLINE {child _ parent.firstChild};
NextChildWire: PROC [child: Wire] RETURNS [sibling: Wire]
= INLINE {sibling _ child.next};

Edge: TYPE = REF EdgePrivate;
EdgePrivate: TYPE = RECORD [
sides: ARRAY GraphDirection OF RECORD [v: Vertex, next, prev: Edge],
port: Port --what the wireward vertex is connected to
];

GraphDirection: TYPE = {cellward, wireward};
OppositeDirection: ARRAY GraphDirection OF GraphDirection = [cellward: wireward, wireward: cellward];

notInQ: Vertex --don't look:-- = NIL --you looked!--;
endOfQ: Vertex;

SideFor: PROC [e: Edge, v: Vertex] RETURNS [side: GraphDirection]
~ INLINE {RETURN [SELECT v FROM e.sides[cellward].v => cellward, e.sides[wireward].v => wireward, ENDCASE => ERROR]};

EnumerateImmediateEdges: PROC [v: Vertex, Consume: PROC [Port, Vertex, Edge], filter: ARRAY GraphDirection OF BOOL _ ALL[TRUE], order: Order _ any];
EnumerateImmediateConnections: PROC [v: Vertex, Consume: PROC [Port, Vertex], filter: ARRAY GraphDirection OF BOOL _ ALL[TRUE], order: Order _ any];
EnumerateTransitiveConnections: PROC [v: Vertex, Consume: PROC [Port, Vertex]];
EnumerateTopEdges: PROC [ci: CellInstance, Consume: PROC [Port, Wire, Edge]];
EnumerateTopConnections: PROC [ci: CellInstance, Consume: PROC [Port, Wire]];
EnumerateNeighboringVertices: PROC [v: Vertex, Consume: PROC [Vertex], filter: ARRAY GraphDirection OF BOOL _ ALL[TRUE]];
FindImmediateConnection: PROC [cellward: Vertex, port: Port, hint: Order _ any] RETURNS [w: Vertex];
FindImmediateEdge: PROC [cellward: Vertex, port: Port, hint: Order _ any] RETURNS [w: Vertex, e: Edge];
FindTransitiveConnection: PROC [cellward: Vertex, port: Port] RETURNS [w: Wire];
FindTopEdge: PROC [ci: CellInstance, port: Port] RETURNS [v: Vertex, e: Edge];
ImParent: PROC [im: Intermediary] RETURNS [v: Vertex];
EnumeratePortsForWire: PROC [w: Wire, Consume: PROC [Port--of container of w--]];

EnumerateParts: PROC [ct: CellType, Consume: PROC [Vertex], mirrorToo: BOOL];

Order: TYPE = {forward, backward, any};

Array: TYPE = REF ArrayPrivate;
ArrayPrivate: TYPE = RECORD [
eltType: CellType _ NIL,
nextArray, prevArray: CellType _ NIL,
size: Size2 _ ALL[1],
jointsPeriod: Nat2 _ ALL[1],
groupingParmses: GroupingParmses,
groupingses: RefSeq--groupings index _ Groupings--,
toRole: ARRAY Dim OF ARRAY End OF RefTable--dim _ side _ port _ SidedPortData-- _ ALL[ALL[NIL]],
roles: ARRAY Dim OF VarRefSeq--dim _ index _ SidedPortData-- _ ALL[NIL],
nextRP: ARRAY Dim OF NATURAL _ ALL[0],
joints: ARRAY Dim--in which we are joining-- OF RefSeq--composite phase _ Joint-- _ ALL[NIL],
<<The wiring is derived from the joints.  Each wire is complete, but some wires might not be derived (yet).>>
toWire: RefTable--group _ IntTable (PackedArrayIndex _ ArrayWire)--,
wires: VarSet--of ArrayWire--,
portWire: RefTable--ap B array.port _ aw: ArrayWire--,
<<Here follows the new wiring stuff>>
wirePats: VarSet--of ArrayWirePattern--,
wirePatCxns: VarSet--of ArrayWirePatternConnection--,
portUses: Function--elt Port _ RefSeq (gi _ ArrayWirePattern)--,
exports: Function--array Port _ [REF Shift, ArrayWirePattern]--
];

Dim--ension--: TYPE = {Foo, Bar};
OtherDim: ARRAY Dim OF Dim = [Foo: Bar, Bar: Foo];

Size2: TYPE = ARRAY Dim OF NATURAL;
Range: TYPE = RECORD [min, maxPlusOne: INT];
Range2: TYPE = ARRAY Dim OF Range;
Int2: TYPE = ARRAY Dim OF INT;
Nat2: TYPE = ARRAY Dim OF NATURAL;
Bool2: TYPE ~ ARRAY Dim OF BOOL;
ArrayIndex: TYPE = ARRAY Dim OF INT;
nullAI: ArrayIndex ~ ALL[INT.FIRST];
PackedArrayIndex: TYPE [SIZE[INT]];

ComposeGI: PROC [a: Array, gi2: Nat2] RETURNS [gi: NATURAL]
~ INLINE {gi _ a.groupingParmses[Bar].sum * gi2[Foo] + gi2[Bar]};

GetBorders: PROC [a: Array] RETURNS [borders: ARRAY Dim OF ARRAY End OF NATURAL]
~ INLINE {RETURN [[
[a.groupingParmses[Foo].middle.min, a.size[Foo]-a.groupingParmses[Foo].middle.maxPlusOne],
[a.groupingParmses[Bar].middle.min, a.size[Bar]-a.groupingParmses[Bar].middle.maxPlusOne]]]};

GroupingParmses: TYPE = ARRAY Dim OF GroupingParms;
GroupingParms: TYPE = RECORD [
middle: Range--or array indices or joint instance indices--,
firstHigh, sum: NATURAL,
d: INT
];

<<Groupings: TYPE = REF GroupingsPrivate;
GroupingsPrivate: TYPE = RECORD [
toGroup: RefTable--port _ Group--,
groups: VarSet--of Group--
];

GroupListPair: TYPE = ARRAY End OF GroupList;
GroupList: TYPE = LIST OF Group;
Group: TYPE = REF GroupPrivate;
GroupPrivate: TYPE = RECORD [
ports: PortList _ NIL,
better: Group _ NIL,
worse: GroupList _ NIL,
stopLooking: ARRAY Dim OF ARRAY End OF BOOL _ ALL[ALL[FALSE]],
gi2: Nat2
];

Joint: TYPE = REF JointPrivate;
JointPrivate: TYPE = RECORD [
size2: Size2--number of instances--,
size: INT--P size2--,
groupingParmses: GroupingParmses,
ties: RefSeq--joint groupings index _ VarSet(of Tie)--,
toTie: ARRAY End OF RefSeq--side of joint _ joint groupings index _ RefTable(Group _ Tie)--
];

ComposeJgi: PROC [j: Joint, jgi2: Nat2] RETURNS [jgi: NATURAL]
~ INLINE {jgi _ j.groupingParmses[Bar].sum * jgi2[Foo] + jgi2[Bar]};

TieList: TYPE = LIST OF Tie;
Tie: TYPE = REF TiePrivate;
TiePrivate: TYPE = RECORD [
groups: ARRAY End OF Group,
completion: Completion _ NIL,
better: Tie _ NIL--when tie gets merged with another, better=that union--
];

SidedPortDataList: TYPE = LIST OF SidedPortData;
SidedPortData: TYPE = REF SidedPortDataPrivate;
SidedPortDataPrivate: TYPE = RECORD [
port: Port,
side: End,
index: NATURAL,
links: Links _ NIL
];

SidedPortList: TYPE = LIST OF SidedPort;
SidedPort: TYPE = RECORD [side: End, port: Port];

Links: TYPE = REF LinksPrivate;
LinksPrivate: TYPE = RECORD [
linkSize: NATURAL,
negLinkSize, negLgLinksPerWord: INTEGER,
lgLinksPerWord: Sublg,
words: SEQUENCE length: NATURAL OF WORD
];

Sublg: TYPE = NATURAL [0 .. Basics.logBitsPerWord];

Completion: TYPE = REF CompletionPrivate;
CompletionPrivate: TYPE = RECORD [
nIncomplete: NATURAL _ 0,
complete: PACKED SEQUENCE length: NATURAL OF BOOL
];

ArrayWire: TYPE = REF ArrayWirePrivate;
ArrayWirePrivate: TYPE = RECORD [
members: VarFunction--Group _ BoolSeq(group instance index _ isMember)--,
ports: VarSet--of array Port--
];

ArrayWireElt: TYPE = RECORD [g: Group, ai: ArrayIndex];>>

ArrayWirePattern: TYPE ~ REF ArrayWirePatternPrivate;
ArrayWirePatternPrivate: TYPE ~ RECORD [
memLocs: Function--elt Port _ Int2Seq (relative gi _ ArrayIndex)--,
part: ArrayPart,
partIndex: PartIndex --IndexOfPart[part]--,
partClass: [0 .. 2] --ClassOfPart[part]--,
gi2Min, ngi2: Nat2 _ ALL[0],
ngi: NATURAL _ 0,
regDim: Dim _ Foo, --when partClass=1, part[regDim]=mid; else unconstrained
order: [0 .. 2] --actually [0 .. partClass]-- _ 0,
periods: ARRAY [0 .. 2)--actually [0 .. order)-- OF Int2 _ ALL[[0, 0]],
cxns: ARRAY PartIndex OF ArrayWirePatternConnection _ ALL[NIL],
ports: Function--array Port _ REF Shift--
];

ArrayPart: TYPE ~ PACKED ARRAY Dim OF Part1;
Part1: TYPE ~ {low, mid, high};
PartIndex: TYPE ~ [0 .. 9);
Shift: TYPE ~ Int2;
KingMove: TYPE ~ Int2--where both components are in [-1 .. 1]--;

ArrayWirePatternConnection: TYPE ~ REF ArrayWirePatternConnectionPrivate;
ArrayWirePatternConnectionPrivate: TYPE ~ RECORD [
pats: ARRAY BOOL OF ArrayWirePattern,
dShift: Shift,
s0r: Range2
];

ClassOfPart: PROC [part: ArrayPart] RETURNS [class: [0 .. 2] _ 0] --||{d | part[d]=mid}||
~ INLINE {
IF part[Foo]=mid THEN class _ class+1;
IF part[Bar]=mid THEN class _ class+1};

IndexOfPart: PROC [part: ArrayPart] RETURNS [PartIndex]
~ INLINE {RETURN [part[Foo].ORD*3 + part[Bar].ORD]};

CompareArrayParts: PROC [part1, part2: ArrayPart] RETURNS [Basics.Comparison];

ComparePartIndices: PROC [pi1, pi2: PartIndex] RETURNS [Basics.Comparison];

ComposeRGI: PROC [awp: ArrayWirePattern, rgi2: Nat2] RETURNS [NATURAL]
~ INLINE {RETURN [awp.ngi2[Bar]*rgi2[Foo]+rgi2[Bar]]};

GIFromRGI: PROC [awp: ArrayWirePattern, rgi2: Nat2] RETURNS [Nat2]
~ INLINE {RETURN Nat2Add[awp.gi2Min, rgi2]};

RelativizeGI: PROC [awp: ArrayWirePattern, gi2: Nat2] RETURNS [rgi2: Nat2, rgi: NATURAL]
~ INLINE {
rgi2 _ Nat2Sub[gi2, awp.gi2Min];
rgi _ awp.ngi2[Bar]*rgi2[Foo]+rgi2[Bar]};

End: TYPE = {low, high};
OtherEnd: ARRAY End OF End = [low: high, high: low];

ListData: TYPE ~ REF ANY;
listClass: Colls.CollectionClass;

CreateSteppyNames: PROC [names: LORA--actually LIST OF SteppyName-- _ NIL] RETURNS [ListData];

Seq: TYPE ~ IntFns.Sequence;

CreateSeq: PROC [len: NATURAL _ 0, oneToOne, dense, domainFixed, invable: BOOL _ FALSE] RETURNS [Seq]
~ INLINE {RETURN [IntFns.CreateSimple[bounds: [0, len-1], val: Colls.noValue, oneToOne: oneToOne, dense: dense, domainFixed: domainFixed, invable: invable]]};

RefSeq: TYPE = REF RefSequence;
RefSequence: TYPE = RECORD [
elts: SEQUENCE length: NATURAL OF REF ANY];

CreateRefSeq: PROC [len: NATURAL] RETURNS [rs: RefSeq]
= INLINE {rs _ NEW [RefSequence[len]]};

VarRefSeq: TYPE = REF VarRefSequence;
VarRefSequence: TYPE = RECORD [
length: NATURAL,
refs: RefSeq];

CreateVarRefSeq: PROC [size: NATURAL _ 12] RETURNS [vrs: VarRefSeq]
= INLINE {vrs _ NEW [VarRefSequence _ [0, CreateRefSeq[size]]]};

VarRefSeqAppend: PROC [vrs: VarRefSeq, value: REF ANY];

Int2Seq: TYPE ~ REF Int2Sequence;
Int2Sequence: TYPE ~ RECORD [elts: SEQUENCE length: NATURAL OF Int2];

CreateInt2Seq: PROC [len: NATURAL, init: Int2] RETURNS [Int2Seq];

BoolSeq: TYPE = REF BoolSequence;
BoolSequence: TYPE = RECORD [elts: PACKED SEQUENCE length: NATURAL OF BOOL];

CreateBoolSeq: PROC [len: NATURAL, b0: BOOL _ FALSE] RETURNS [bs: BoolSeq]
= INLINE {bs _ NEW [BoolSequence[len]]; FOR i: NATURAL IN [0 .. len) DO bs[i] _ b0 ENDLOOP};

NewInt: PROC [i: INT] RETURNS [REF INT];

FloorDiv: PROC [num, den: INT] RETURNS [quot: INT];
CeilDiv: PROC [num, den: INT] RETURNS [quot: INT];

ConsInt2: PROC [d1: Dim, x1, x2: INT] RETURNS [x: Int2]
= INLINE {x[d1] _ x1; x[OtherDim[d1]] _ x2};
Int2Neg: PROC [a: Int2] RETURNS [Int2]
~ INLINE {RETURN [[Foo: -a[Foo], Bar: -a[Bar]]]};
Int2Add: PROC [a, b: Int2] RETURNS [Int2]
= INLINE {RETURN [[Foo: a[Foo]+b[Foo], Bar: a[Bar]+b[Bar]]]};
Int2Sub: PROC [a, b: Int2] RETURNS [Int2]
= INLINE {RETURN [[Foo: a[Foo]-b[Foo], Bar: a[Bar]-b[Bar]]]};
Int2SubN: PROC [a, b: Int2] RETURNS [Nat2]
= INLINE {RETURN [[Foo: a[Foo]-b[Foo], Bar: a[Bar]-b[Bar]]]};
Int2InRange: PROC [i: Int2, r: Range2] RETURNS [in: BOOL]
= INLINE {in _ i[Foo] IN [r[Foo].min .. r[Foo].maxPlusOne) AND i[Bar] IN [r[Bar].min .. r[Bar].maxPlusOne)};
Int2Tweak: PROC [i: Int2, d: Dim, D: INT] RETURNS [j: Int2]
= INLINE {j _ i; j[d] _ j[d] + D};
Int2Scale: PROC [a: Int2, b: INT] RETURNS [Int2]
= INLINE {RETURN [[Foo: a[Foo]*b, Bar: a[Bar]*b]]};
Int2Dot: PROC [a, b: Int2] RETURNS [INT]
~ INLINE {RETURN [a[Foo]*b[Foo]+a[Bar]*b[Bar]]};
Int2Cross: PROC [a, b: Int2] RETURNS [INT]
~ INLINE {RETURN [a[Foo]*b[Bar]-a[Bar]*b[Foo]]};
ConsNat2: PROC [d1: Dim, x1, x2: NATURAL] RETURNS [x: Nat2]
= INLINE {x[d1] _ x1; x[OtherDim[d1]] _ x2};
WidenNat2: PROC [x: Nat2] RETURNS [Int2]
~ INLINE {RETURN [[Foo: x[Foo], Bar: x[Bar]]]};
NarrowInt2: PROC [x: Int2] RETURNS [Nat2]
~ INLINE {RETURN [[Foo: x[Foo], Bar: x[Bar]]]};
Nat2Add: PROC [a, b: Nat2] RETURNS [Nat2]
= INLINE {RETURN [[Foo: a[Foo]+b[Foo], Bar: a[Bar]+b[Bar]]]};
Nat2Sub: PROC [a, b: Nat2] RETURNS [Nat2]
= INLINE {RETURN [[Foo: a[Foo]-b[Foo], Bar: a[Bar]-b[Bar]]]};
Nat2Mul: PROC [a, b: Nat2] RETURNS [Nat2]
= INLINE {RETURN [[Foo: a[Foo]*b[Foo], Bar: a[Bar]*b[Bar]]]};
Nat2Div: PROC [a, b: Nat2] RETURNS [Nat2]
= INLINE {RETURN [[Foo: a[Foo]/b[Foo], Bar: a[Bar]/b[Bar]]]};
Nat2Tweak: PROC [i: Nat2, d: Dim, D: INT] RETURNS [j: Nat2]
= INLINE {j _ i; j[d] _ j[d] + D};
Nat2Area: PROC [x: Nat2] RETURNS [NATURAL]
= INLINE {RETURN [x[Foo] * x[Bar]]};
RangeOff: PROC [r: Range, D: INT] RETURNS [Range]
= INLINE {RETURN[[min: r.min+D, maxPlusOne: r.maxPlusOne+D]]};
RangeOffClip: PROC [r: Range, D: INT] RETURNS [Range]
= INLINE {RETURN[[min: MAX[r.min+D, 0], maxPlusOne: r.maxPlusOne+D]]};
ShaveRange2Top1: PROC [r: Range2, d: Dim] RETURNS [sr: Range2]
= INLINE {sr _ r; sr[d].min _ MIN[sr[d].min, sr[d].maxPlusOne _ sr[d].maxPlusOne - 1]};
ConsRange2: PROC [d1: Dim, x1, x2: Range] RETURNS [x: Range2]
= INLINE {x[d1] _ x1; x[OtherDim[d1]] _ x2};
Range2Empty: PROC [r: Range2] RETURNS [BOOL]
= INLINE {RETURN [r[Foo].maxPlusOne<=r[Foo].min OR r[Bar].maxPlusOne<=r[Bar].min]};
Range2IsSingleton: PROC [r: Range2] RETURNS [BOOL]
= INLINE {RETURN [r[Foo].maxPlusOne=r[Foo].min+1 AND r[Bar].maxPlusOne=r[Bar].min+1]};
Range2Min: PROC [r2: Range2] RETURNS [Int2]
= INLINE {RETURN[[Foo: r2[Foo].min, Bar: r2[Bar].min]]};
Range2MinN: PROC [r2: Range2] RETURNS [Nat2]
= INLINE {RETURN[[Foo: r2[Foo].min, Bar: r2[Bar].min]]};
Range2Off: PROC [r: Range2, D: Int2] RETURNS [Range2]
= INLINE {RETURN[[Foo: RangeOff[r[Foo], D[Foo]], Bar: RangeOff[r[Bar], D[Bar]]]]};
Range2OffClip: PROC [r: Range2, D: Int2] RETURNS [Range2]
= INLINE {RETURN[[Foo: RangeOffClip[r[Foo], D[Foo]], Bar: RangeOffClip[r[Bar], D[Bar]]]]};
Range2Included: PROC [sub, in: Range2] RETURNS [BOOL]
~ INLINE {RETURN [RangeIncluded[sub[Foo], in[Foo]] AND RangeIncluded[sub[Bar], in[Bar]]]};
RangeIncluded: PROC [sub, in: Range] RETURNS [BOOL]
~ INLINE {RETURN [sub.min>=in.min AND sub.maxPlusOne<=in.maxPlusOne]};
Range2Intersection: PROC [a, b: Range2] RETURNS [Range2]
= INLINE {RETURN [[
Foo: [
min: MAX[a[Foo].min, b[Foo].min],
maxPlusOne: MIN[a[Foo].maxPlusOne, b[Foo].maxPlusOne]],
Bar: [
min: MAX[a[Bar].min, b[Bar].min],
maxPlusOne: MIN[a[Bar].maxPlusOne, b[Bar].maxPlusOne]]]]};
RangeArea: PROC [r: Range2] RETURNS [area: NATURAL]
= INLINE {area _ RangeLength[r[Foo]] * RangeLength[r[Bar]]};
RangeShape: PROC [r: Range2] RETURNS [shape: Nat2]
= INLINE {shape _ [RangeLength[r[Foo]], RangeLength[r[Bar]]]};
SizeRange: PROC [size: Nat2] RETURNS [r: Range2]
= INLINE {r _ [[0, size[Foo]], [0, size[Bar]]]};
RangeLength: PROC [r: Range] RETURNS [length: NATURAL]
= INLINE {length _ r.maxPlusOne - r.min};
Range2sIntersect: PROC [r1, r2: Range2] RETURNS [BOOL]
= INLINE {RETURN [RangesIntersect[r1[Foo], r2[Foo]] AND RangesIntersect[r1[Bar], r2[Bar]]]};
RangesIntersect: PROC [r1, r2: Range] RETURNS [BOOL]
= INLINE {RETURN [
(r1.min IN [r2.min .. r2.maxPlusOne) AND r1.maxPlusOne > r1.min) OR
(r2.min IN [r1.min .. r1.maxPlusOne) AND r2.maxPlusOne > r2.min)]};
Range1Mul: PROC [r: Range, t, f: NATURAL] RETURNS [rr: Range];
Range2Mul: PROC [r: Range2, t, f: Nat2] RETURNS [rr: Range2];
Range1Div: PROC [r: Range, t, f: NATURAL] RETURNS [rr: Range];
Range2Div: PROC [r: Range2, t, f: Nat2] RETURNS [rr: Range2];

BeRope: PROC [r: ROPE] RETURNS [r2: ROPE] = INLINE {r2 _ r}--stupid goddam anachronism--;
END.
ΌLichenDataStructure.Mesa
Last tweaked by Mike Spreitzer on September 30, 1987 10:00:06 am PDT
Leftover
private CellType _ VarFunction(ROPE _ Vertex)
AM1: A mirror is not entered in containedInstances.
AM2: A mirror is not counted as an instance of its type.
AM3: mirror.type = mirror.container
The connections to/from cells.
AI1: The edges are in the following order: first, the cellward ones, if any, in any order, then the wireward ones, ordered by port.
the Port is the wireward one.
Indices are not contiguously allocated; some roles[d][i] may _ NIL.
all indices < nextRP[d].
middle is range of (joint | array) indices covered
firstHigh is first grouping index of high range of irregulars
 peculiar = middle.min + size-middle.maxPlusOne
hasMiddle = middle.maxPlusOne > middle.min
sum =  peculiar + hasMiddle*jointsPeriod for arrays
sum =  peculiar + hasMiddle for joints
firstHigh = sum - (size-middle.maxPlusOne)
d = firstHigh - middle.maxPlusOne
tie.completion is redundant with the information in the rpd.links.
tie.completion = NIL iff tie.completion.nIncomplete = 0.
a SidedPortData has links iff needed or array is being created.
words[clai ShiftRight lgLinksPerWord] ShiftRight (linkSize*(clai MaskLast lgLinksPerWord)) MaskLast linkSize gives index of another roledPort connected to this one at ji
where:
clai = <size[Foo], size[Bar]> T <lai[Foo], lai[Bar]>
`T' is APL's `decode'
size is the size of array
lai is the array index of the element on the low side of the joint
complete[instance index] W all connections present at this instance
order=1 => periods[0][Foo]>0 OR periods[0][Foo]=0 & periods[0][Bar]>0.
order=2 =>
periods[0][Foo] IN [0 .. periods[1][Foo]), periods[0][Bar]>0,
periods[1][Foo]>0, periods[1][Bar]=0.
c.pats[b]=awp iff awp.cxns[c.pats[~b].part]=c.
CompareArrayParts[pats[FALSE].part, pats[TRUE].part]=less.
Each shift s0 of pats[FALSE] in s0r is connected to shift s0+dShift of pats[TRUE]; note that this may be a many-to-one, one-to-many, or a one-to-one relation, due to the equivalences among shifts of either pattern.
This is determined first by part.order, then by part[Foo], then by part[Bar].
Equivalent to CompareArrayParts.
Treat the result as a REF READONLY INT, or you'll be sorry!
Κ7–

"cedar" style˜
code™K™D—K˜KšΟk	œr˜{K˜šΠbxœœ
˜&Kšœ0˜7Kš
œ
˜
—K˜Kš
œ
œ
ΟnœŸ	œŸœ˜MK˜KšΠblœœ
Οcœ
˜$K˜Kš œœœœ
œœ˜?K˜Kš œœœœ
œœ˜<K˜Kšœœ‘œ
˜$Kšœœœ
œ
œ
œ
˜Kš
œœœ
œ
œ
˜Kšœœœ
˜Kš	œ
œœ
œ
œ
˜Kš
œœœ
œ
œ
˜Kš
œœœ
œ
œ
˜Kšœœ˜(Kšœœ˜&Kšœœ˜/K˜Kšœœ
˜Kšœœ˜Kšœ
œ˜ Kšœ
œ˜&Kšœ
œ˜$Kšœ
œ˜*Kšœœ˜(Kšœœ˜.Kšœ
œ˜$Kšœ
œ˜*Kšœœ˜.Kšœ
œ˜$Kšœ
œ˜*Kšœœ˜.Kšœœ˜Kšœ
œ˜'K˜Kšœ
œ˜šŸœœ
œ˜+Kšœœ˜ —K˜Kšœ
œ˜$šŸœœ
œ˜+Kšœœ˜&—K˜Kšœ	œ˜$Kšœ
œ˜$Kšœœ
œ˜<Kš
œ!˜!Kš	œœœ	œ
œ
˜0Kš	œœœ
œ
œ
˜8K˜Kšœœœ
˜Kšœœ˜K˜šŸœœœœ˜EKšœœœœ˜9—K˜Kšœœœ˜!šœœœ˜Kšœ‘œ
˜!Kšœœ
˜Kšœ
œœ˜—K˜Kšœ
œ‘'˜7KšŸœœœ
œœ
œœœœœ˜jK˜KšŸœœœ
œœ
œœœœ˜vK˜Kšœœœ˜/šœœœ˜%KšŸœœœ
œœœ˜;Kšœœ
œ˜K˜—K˜KšŸœœŸœœ
˜DK˜Kšœœœ˜'šœœœ˜!KšŸœœ˜K˜—K˜Kšœ
œœ˜%šœœœ˜ K˜Kšœ‘
œ
˜Kšœœœ
˜(šœœœ
˜K™—Kšœ
œ
˜Kšœœ
˜!Kšœœ
˜Kšœ,œ
˜0Kšœ"œ
˜&Kšœ
œ‘œ
˜+Kšœ(œ
˜,Kš
œ˜—K˜KšŸœœŸœœ	˜@KšŸ	œœŸœœœœœ˜]Kš
ŸœœŸœœœ˜ZKšŸœœŸœœ
˜EK˜šœœ
˜KšœΟm
œ’
œ™-—K˜Kšœ
œœ
œ˜Kšœœœ
˜šœ
œœ˜K˜K˜Kšœœ
‘œ
˜*Kšœ
œ
˜K˜Kšœœ
˜Kš
œ˜—K˜KšŸœœœ˜<šŸœœœ˜7Kšœœ˜#—šŸ
œœœ˜9Kšœœ˜ —KšŸ
œœŸœœœœœœœ˜
K˜KšŸ	œœœ	œ˜;KšŸœœœœ˜?K˜šŸ	œœœ˜*Kšœœœ˜,—K˜Kšœœœ
œ˜*Kš	œœœ
œ
‘œ
˜?Kš	œ
œœ
œ
‘"œ
˜<K˜K˜,Kš
Ÿœœ1œœœ˜ZK˜Kšœœ‘"Πcm
‘œ
˜_K˜Kšœ
œœ˜+šœœœ˜#Kšœœ
˜Kšœ‘œ
˜.šœœ
‘,˜GKš
œ3™3K™8K™#—K˜—K˜Kšœœœ˜!šœœœ˜K˜K˜Kšœœ
˜šœœ
˜ K™K™ƒ
—K˜Kšœœ
˜K˜$Kš
œ˜Kšœœœ
˜šœ	œ˜'˜	Kšœœ
˜Kšœ+˜.K˜—˜K˜
K˜—˜	Kšœœ
˜Kšœœ‘
˜"Kšœ˜!K˜—Kšœ˜	——K˜Kšœ
œ˜/K˜Kšœœœ˜,Kšœœœ˜4Kšœœœ˜$K˜šŸœœ
œ˜+Kšœœœ˜)—K˜KšŸ	œœœ	œ˜;KšŸœœœœ˜?KšŸœœŸœœ˜PKšŸ
œœŸœœœœœœœ˜
šŸœœœ˜9Kšœœ˜%—šŸ
œœœ˜9Kšœœ˜ —K˜Kšœœœ
˜šœ
œœ˜Kšœœœ
œ˜DKšœ‘*˜5Kš
œ˜—K˜Kšœœ˜,Kšœœœ;˜eK˜Kšœ‘œœ
‘œ
˜5Kš
œ˜K˜šŸœœœ˜AKš
œœœœœCœœ˜u—K˜šŸœœ
Ÿœœœœ
œœ
œ˜”
K™—KšŸœœ
Ÿœœœœ
œœ
œ˜”
KšŸœœ
Ÿœœ˜OKšŸœœŸœœ˜MKšŸœœŸœœ˜MKšŸœœ
Ÿœœœœ
œœ
œ˜yKšŸœœ3œ
˜dKšŸœœ3œ˜gKšŸœœ œ˜PKšŸœœ œ˜NKšŸœœœ
˜6Kš
ŸœœŸœœ‘œ˜QK˜Kš
ŸœœŸœœœ˜MK˜Kšœœ˜'K˜Kšœœœ˜šœœœ˜Kšœœ
˜Kšœ!œ
˜%Kšœœ˜Kšœœ˜Kš
œ!˜!Kšœ‘£
‘œ
˜3Kšœœœ
œœ	‘£
‘£
‘£
‘œœ
œ
œ˜`šœœœ
‘£
‘£
‘œœ
œ˜HKšœ=£
œ™C—š	œœœ
œœ˜&Kš
œ™—Kšœœ‘œ
œ‘£
‘œœ
œ˜]K˜mKšœ‘£
‘£
‘
œ
˜DKšœ
‘œ
˜Kšœ‘£
‘£
‘œ
˜6K˜%Kšœ‘œ
˜(Kšœ‘!œ
˜5Kšœ‘£
‘£
‘œ
˜@Kšœ‘
£
‘ ˜?K˜—K˜Kšœ‘
œœ˜!Kšœ
œœ˜2K˜Kš	œœœœ
œ
˜#Kšœœœœ˜,Kšœœœœ˜"Kš	œœœœ
œ
˜Kš	œœœœ
œ
˜"Kš	œœœœ
œ
˜ Kš	œœœœ
œ
˜$Kšœœ
œ
œ˜$Kšœœœ
œ˜#K˜šŸ	œœœœ
˜;Kšœœ9˜A—K˜šŸ
œœœœœ
œœ
œ
˜Pšœœœ˜Kš
œZ˜ZKš
œ]˜]——K˜Kšœœœœ˜3šœœœ˜Kšœ
‘.œ
˜<Kšœœ
˜KšΟg
œ˜Kš
œ˜K™2Kš
œ=™=Kš’
œ/™0K™*Kšœ’
œ-™4Kšœ’
œ ™'Kš
œ*™*Kš€
œ ™!—K˜Kšœ
œœ˜)šœœœ˜!Kšœ‘£
‘œ
˜"Kšœ‘˜K˜—K˜Kšœœœœ˜-Kšœœœ
œ˜ Kšœœœ˜šœœœ˜Kšœœ
˜Kšœœ
˜Kšœœ
˜Kšœ
œœ
œœ
œœ
œ
œ˜>K˜	K˜—K˜Kšœœœ˜šœœœ˜Kšœ‘œ
˜$Kšœ‘Πcg
‘œ
˜Kš
œ!˜!Kšœ‘£
‘œ
˜7Kšœœœ‘£
‘£
‘£
‘˜[K˜—K˜šŸ
œœœœ
˜>Kšœœ<˜D—K˜Kšœ	œœ
œ˜Kšœœœ˜šœœœ˜Kšœœœ˜Kšœœ
˜Kšœ‘8˜IK˜K™BK™8K™?—K˜Kšœœœ
œ˜0Kšœœœ˜/šœœœ˜%K˜K˜
Kšœœ
˜Kšœ˜K˜—K˜Kšœœœ
œ˜(Kšœœœ˜1K˜Kšœœœ˜šœœœ˜Kšœ
œ
˜Kšœ œ
˜(Kš
œ˜Kšœœ	œ
œ
˜'K˜Kš
ϩ
™©
š
œ™Kšœ’
œ™4Kšœ
’
œ™Kš
œ™Kš
œB™B——K˜Kšœœœ˜3K˜Kšœœœ˜)šœœœ˜"Kšœ
œ˜Kš
œ
œ
œ	œ
œ
˜1K˜Kšœ’
œ)™C—K˜Kšœœœ˜'šœœœ˜!Kšœ‘£
‘£
‘œ
˜IKšœ
‘˜K˜—K˜Kšœœœ˜9K˜Kšœœœ˜5šœœœ˜(Kšœ‘£
‘£
‘œ
˜CK˜Kšœ‘œ
˜+Kšœ‘œ
˜*Kšœœ˜Kšœœ˜Kšœ‘8˜KKšœ‘œ˜2š	œ	œ	‘œ
œœ	˜GKš
œF™Fš
œ
™
Kš
œ=™=Kš
œ%™%——Kš	œœœœ
œ˜?Kšœ‘
£
‘˜)K˜—K˜Kš	œœœ
œœ˜,Kšœœ˜Kšœœ˜Kšœœ˜Kšœ
œ‘*œ
˜@K˜Kšœœœ#˜Išœ#œœ˜2šœœ
œ
œ˜%Kš
œ.™.Kšœœ
œ
™:—Kš€
œ
˜˜Kšœ=€
œ˜
™Φ
—K˜—K˜šŸœœœ‘˜Yšœœ˜
Kšœœ˜&Kšœœ˜'——K˜šŸœœœ˜7Kš	œœœœœ˜4—K˜šŸœœœ˜NK™M—K˜šŸœœœ˜KKš
œ ™ —K˜šŸ
œœ%œœ
˜FKšœœœ&˜6—K˜šŸ	œœ%œ˜BKšœœœ˜,—K˜šŸœœ$œœ
˜Xšœœ˜
K˜ Kš
œ)˜)——K˜Kšœœ˜Kšœ
œœ˜4K˜Kšœ
œœ
œ
˜Kš
œ!˜!K˜KšŸœœ	‘œœœ˜^K˜Kšœœ˜K˜šŸ	œœœ-œœœ˜eKšœœœŽ
˜ž
—K˜Kšœœœ
˜šœ
œœ˜Kšœœ	œ
œ
œ
œ˜+—K˜šŸœœœœ
˜6Kšœœœ˜'—K˜Kšœœœ˜%šœœœ˜Kšœœ
˜K˜—K˜šŸœœœœ˜CKšœœœ-˜@—K˜KšŸœœœ
œ˜7K˜Kšœ	œœ˜!Kšœœœœ	œ
œ˜EK˜KšŸ
œœœœ˜AK˜Kšœ	œœ˜!Kšœœœœ
œ	œ
œ
œ˜LK˜šŸ
œœœœœœ˜JKšœœœœœ
œœœ˜\—K˜šŸœœœœœ
œ˜(Kšœ+Οb™;—K˜Kš
Ÿœœœœœ˜3Kš
Ÿœœœœœ˜2K˜šŸœœœœ
˜7Kšœœ$˜,—šŸœœœ˜&Kšœœœ!˜1—šŸœœœ˜)Kšœœœ-˜=—šŸœœœ˜)Kšœœœ-˜=—šŸœœœ˜*Kšœœœ-˜=—šŸœœœœ
˜9Kš	œœœ#œœ$˜l—š
Ÿ	œœΠgn
œœœ
˜;Kšœœ€
œ˜"—šŸ	œœœœ˜0Kšœœœ#˜3—šŸœœœœ
˜(Kšœœœ ˜0—šŸ	œœœœ
˜*Kšœœœ ˜0—šŸœœœœ
˜;Kšœœ$˜,—šŸ	œœœ˜(Kšœœœ˜/—šŸ
œœœ˜)Kšœœœ˜/—šŸœœœ˜)Kšœœœ-˜=—šŸœœœ˜)Kšœœœ-˜=—šŸœœœ˜)Kšœœœ-˜=—šŸœœœ˜)Kšœœœ-˜=—š
Ÿ	œœ§
œœœ
˜;Kšœœ€
œ˜"—šŸœœœœ
˜*Kšœœœ˜$—š
Ÿœœ§
œœœ˜1Kš	œœœ
€
œ€
œ˜>—š
Ÿœœ§
œœœ˜5Kšœœœœ€
œ€
œ˜F—šŸœœœ
˜>Kšœœœ6˜W—šŸ
œœœ˜=Kšœœ$˜,—šŸœœ
œœ
˜,Kšœœœ œ!˜S—šŸœœ
œœ
˜2Kšœœœ!œ"˜V—šŸ	œœœ˜+Kšœœœ(˜8—šŸ
œœœ˜,Kšœœœ(˜8—šŸ	œœ
§
œœ	˜5Kš
œœœŸœ€
œŸœ€
œ
˜R—šŸ
œœ
§
œœ	˜9Kš
œœœŸœ€
œŸœ€
œ
˜Z—šŸœœœœ
˜5Kšœœœ#œ$˜Z—šŸ
œœœœ
˜3Kšœœœœ!˜F—šŸœœœ	˜8šœœœ˜˜Kšœœ˜!Kšœœ(˜7—˜Kšœœ˜!Kšœœ+˜:———šŸ	œœ
œœ
˜3Kšœœ4˜<—šŸ
œœ
œ˜2Kšœœ6˜>—šŸ	œœœ˜0Kšœœ(˜0—šŸœœœ
œ
˜6Kšœœ!˜)—šŸœœœœ
˜6Kšœœœ$œ%˜\—šŸœœœœ
˜4šœœœ˜Kšœœœ˜CKšœœœ˜C——KšŸ	œœ€
œ€
œœœ
˜>Kš
Ÿ	œœ
€
œ€
œœ˜=KšŸ	œœ€
œ€
œœœ
˜>Kš
Ÿ	œœ
€
œ€
œœ˜=K˜KšŸœœœœœœ	‘œ
˜YKšœ
˜—…—QΎx±