LichenDataStructure.Mesa
Last tweaked by Mike Spreitzer on August 26, 1987 11:09:31 am PDT
DIRECTORY Asserting, Basics, CardHashTableThreaded, IntHashTable, LichenCollections, LichenIntFunctions, LichenPairCollections, RefTab, Rope;
LichenDataStructure:
CEDAR
DEFINITIONS
IMPORTS RefTab, IntHashTable, LichenCollections, LichenIntFunctions
=
BEGIN OPEN Colls:LichenCollections, PairColls:LichenPairCollections, IntFns:LichenIntFunctions;
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;
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,
Leftover
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;
private CellType b VarFunction(ROPE b Vertex)
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 b 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
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
];
Vertex: TYPE = REF VertexPrivate;
VertexPrivate:
TYPE =
RECORD [
containingCT: CellType,
QNext: Vertex ← notInQ,
colorNext, equiv: Vertex ← NIL,
firstEdge, lastEdge: Edge ←
NIL,
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.
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];
the Port is the wireward one.
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 b Groupings--,
toRole: ARRAY Dim OF ARRAY End OF RefTable--dim b side b port b SidedPortData-- ← ALL[ALL[NIL]],
roles:
ARRAY Dim
OF VarRefSeq
--dim
b index
b SidedPortData-- ←
ALL[
NIL],
Indices are not contiguously allocated; some roles[d][i] may b NIL.
nextRP:
ARRAY Dim
OF
NATURAL ←
ALL[0],
all indices < nextRP[d].
joints: ARRAY Dim--in which we are joining-- OF RefSeq--composite phase b 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 b IntTable (PackedArrayIndex b ArrayWire)--,
wires: VarSet--of ArrayWire--,
portWire: RefTable--ap array.port b aw: ArrayWire--
];
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;
ArrayIndex: TYPE = ARRAY Dim OF INT;
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
];
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
Groupings: TYPE = REF GroupingsPrivate;
GroupingsPrivate:
TYPE =
RECORD [
toGroup: RefTable--port b 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 b VarSet(of Tie)--,
toTie: ARRAY End OF RefSeq--side of joint b joint groupings index b RefTable(Group b 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--
];
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.
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
];
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]> ¥ <lai[Foo], lai[Bar]>
`¥' 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
Sublg: TYPE = NATURAL [0 .. Basics.logBitsPerWord];
Completion: TYPE = REF CompletionPrivate;
CompletionPrivate:
TYPE =
RECORD [
nIncomplete: NATURAL ← 0,
complete: PACKED SEQUENCE length: NATURAL OF BOOL
];
complete[instance index] { all connections present at this instance
ArrayWire: TYPE = REF ArrayWirePrivate;
ArrayWirePrivate:
TYPE =
RECORD [
members: VarFunction--Group b BoolSeq(group instance index b isMember)--,
ports: VarSet--of array Port--
];
ArrayWireElt: TYPE = RECORD [g: Group, ai: ArrayIndex];
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];
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];
Treat the result as a REF READONLY INT, or you'll be sorry!
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};
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};
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};
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]]]]};
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};
RangesIntersect:
PROC [r1, r2: Range]
RETURNS [theyDo:
BOOL]
=
INLINE {theyDo ←
(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.