[_CD4_]<datools7.0>Lichen>LichenDataStructure.Mesa!47

LichenDataStructure.Mesa

Last tweaked by Mike Spreitzer on February 2, 1988 11:57:11 am PST

DIRECTORY AbSets, Asserting, Basics, BasicTime, BiRels, CardHashTableThreaded, IntHashTable, RefTab, Rope, TextReplace;

LichenDataStructure: CEDAR DEFINITIONS

IMPORTS AbSets, BiRels, IntHashTable, RefTab

BEGIN OPEN Sets:AbSets;

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;

RopeMap: TYPE ~ TextReplace.RopeMap;

Time: TYPE ~ RECORD [BasicTime.GMT]; --so we can discriminate REFS to them; you can't discriminate REFS to opaque types, and BasicTime.GMT is opaque.

Set: TYPE ~ Sets.Set;

VarSet: TYPE ~ Sets.VarSet;

ConstSet: TYPE ~ Sets.ConstSet;

ConstFilter: TYPE ~ Sets.ConstFilter;

BiRel: TYPE ~ BiRels.BiRel;

VarBiRel: TYPE ~ BiRels.VarBiRel;

ConstBiRel: TYPE ~ BiRels.ConstBiRel;

Function: TYPE ~ BiRels.Function;

VarFunction: TYPE ~ BiRels.VarFunction;

UWFunction: TYPE ~ BiRels.UWFunction;

ConstFunction: TYPE ~ BiRels.ConstFunction;

InvFunction: TYPE ~ BiRels.InvFunction;

OneToOne: TYPE ~ BiRels.OneToOne;

VarOneToOne: TYPE ~ BiRels.VarOneToOne;

ConstOneToOne: TYPE ~ BiRels.ConstOneToOne;

IntFn: TYPE ~ BiRels.IntFn;

Permutation: TYPE ~ BiRels.Permutation;

AV: PROC [a: REF ANY] RETURNS [Sets.Value]

~ INLINE {RETURN [[ra: a]]};

IV: PROC [i: INT] RETURNS [Sets.Value]

~ INLINE {RETURN [[i: i]]};

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[]};

TList: TYPE ~ RECORD [head, tail: LORA ← NIL];

Cat: PROC [a, b: TList] RETURNS [TList]

~ INLINE {IF a.head=NIL THEN RETURN [b] ELSE IF b.head=NIL THEN RETURN [a] ELSE {a.tail.rest ← b.head; RETURN [[a.head, b.tail]]}};

Prepend: PROC [l: TList, ra: REF ANY] RETURNS [l2: TList]

~ INLINE {l2.head ← CONS[ra, l.head]; l2.tail ← IF l.tail#NIL THEN l.tail ELSE l2.head};

Append: PROC [l: TList, ra: REF ANY] RETURNS [l2: TList]

~ INLINE {l2.tail ← LIST[ra]; IF l.head=NIL THEN l2.head ← l2.tail ELSE {l2.head ← l.head; l.tail.rest ← l2.tail}};

CopyTil: PROC [TList] RETURNS [TList];

Reln1Set: PROC [reln: REF ANY, assns: Assertions] RETURNS [Set];

TermsSet: PROC [reln: REF ANY, assns: Assertions] RETURNS [Set];

Reln2Reln: PROC [reln: REF ANY, assns: Assertions] RETURNS [BiRel];

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--,

inheritNames: BOOL --inherit names into me now, or later?--,

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];

PortSeqSize: PROC [Port] RETURNS [LNAT--number of leaves--];

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 [child: Port] RETURNS [index: INT];

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

PortNames: PROC [port: Port] RETURNS [Set]

~ INLINE {RETURN [[listClass, AV[port.names]]]};

SteppyName: TYPE ~ RECORD [

steps: NameStepList,

grade: SteppyNameGrade];

SteppyNameList: TYPE ~ LIST OF SteppyName;

NameStepList: TYPE ~ LIST OF NameStep --most significant first--;

NameStep: TYPE ~ REF ANY --actually UNION [ROPE, REF INT]--;

SteppyNameGrade: TYPE ~ RECORD [

global: BOOL,

nonsubs: NATURAL,

gend: BOOL,

subs: NATURAL];

noGrade: SteppyNameGrade ~ [FALSE, 0, FALSE, 0];

noName: SteppyName ~ [NIL, noGrade];

noNameVal: Sets.Value ~ [NIL, LOOPHOLE[noGrade]];

SNCat: PROC [a, b: SteppyName] RETURNS [SteppyName];

SNPrepend: PROC [ns: NameStep, sn: SteppyName] RETURNS [SteppyName];

SNAppend: PROC [sn: SteppyName, ns: NameStep] RETURNS [SteppyName];

SnV: PROC [sn: SteppyName] RETURNS [Sets.Value]

~ INLINE {RETURN [[ra: sn.steps, i: LOOPHOLE[sn.grade]]]};

VSn: PROC [v: Sets.Value] RETURNS [SteppyName]

~ INLINE {RETURN [[steps: NARROW[v.ra], grade: LOOPHOLE[v.i]]]};

LSn: PROC [NameStepList] RETURNS [SteppyName];

nameStepSpace, steppyNameSpace: Sets.Space;

SteppyNameEqual: PROC [n1, n2: SteppyName, clip1, clip2: NameStepList ← 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, AV[v.names]]]};

WireIndex: PROC [parent, child: Wire] RETURNS [index: INT];

SubWire: PROC [parent: Wire, index: INT] RETURNS [child: Wire];

WireSeqSize: PROC [Wire] RETURNS [LNAT];

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.

ScanImmediateEdges: PROC [v: Vertex, Test: PROC [Port, Vertex, Edge] RETURNS [BOOL], filter: ARRAY GraphDirection OF BOOL ← ALL[TRUE], order: Order ← any] RETURNS [BOOL];

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, from, to: Port] RETURNS [v: Vertex];

FindCellConnection: PROC [ci: CellInstance, port: Port] RETURNS [v: Vertex]

~ INLINE {RETURN FindTransitiveConnection[ci, ci.type.port, port]};

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];

ScanParts: PROC [ct: CellType, Test: Sets.Tester, filter: PartFilter, mirrorToo: BOOL] RETURNS [Sets.MaybeValue];

PartFilter: TYPE ~ PACKED ARRAY VertexClass OF BOOL;

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

Array: TYPE = REF ArrayPrivate;

ArrayPrivate: TYPE = RECORD [

eltType: CellType ← NIL,

nextArray, prevArray: CellType ← NIL,

size2: Size2 ← ALL[1],

size: NATURAL,

basePeriod: Nat2 ← ALL[1],

buildPhase: {buildingStatrep, statrepFixed} ← buildingStatrep,

dumrep: DumRep ← NIL,

statrep: StatRep ← NIL

];

DumRep: TYPE ~ REF DumRepPrivate;

DumRepPrivate: TYPE ~ RECORD [

topWires: Set--of TopDumbWire--,

epToTopWire: Function--elt port b RefSeq(CompositeArrayIndex b TopDumbWire)--,

apToWire: Function--array port b DumbWire--

];

DumbWire: TYPE ~ REF DumbWirePrivate;

DumbWireKind: TYPE ~ {top, child};

DumbWirePrivate: TYPE ~ RECORD [

children: Function--port b ChildDumbWire--,

variant: SELECT kind: DumbWireKind FROM

top => [eps: Function--elt port b BoolSeq(CompositeArrayIndex b member)--],

child => [parent: DumbWire, port: Port],

ENDCASE];

TopDumbWire: TYPE ~ REF DumbWirePrivate[top];

ChildDumbWire: TYPE ~ REF DumbWirePrivate[child];

StatRep: TYPE ~ REF StatRepPrivate;

StatRepPrivate: TYPE ~ RECORD [

edges: Set--of StatEdge--,

portEdge: ARRAY BOOL OF InvFunction--elt port ← StatEdge--,

apToPAI: Function--array port b PortAtIndex--

];

StatEdge: TYPE ~ REF StatEdgePrivate;

StatEdgePrivate: TYPE ~ RECORD [

vs: ARRAY BOOL OF StatVertex,

d: Int2];

StatVertex: TYPE ~ REF StatVertexPrivate;

StatVertexPrivate: TYPE ~ RECORD [port: Port, phase: Nat2];

PortAtIndex: TYPE ~ REF PortAtIndexPrivate;

PortAtIndexPrivate: TYPE ~ RECORD [port: Port, ai: ArrayIndex];

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 = Int2;

PhaseIndex: TYPE ~ Int2;

CompositeArrayIndex: TYPE ~ NATURAL;

CompositePhaseIndex: TYPE ~ NATURAL;

nullAI: ArrayIndex ~ ALL[INT.FIRST];

PackedArrayIndex: TYPE [SIZE[INT]];

ListData: TYPE ~ RECORD [REF ANY];

noListData: ListData ~ [NIL];

listClass: Sets.SetClass;

CreateSteppyNames: PROC [names: SteppyNameList ← NIL] RETURNS [ListData];

Setify: PROC [l: ListData] RETURNS [Set] ~ INLINE {RETURN [[listClass, AV[l]]]};

SteppyNameGradeCompare: PROC [g1, g2: SteppyNameGrade] RETURNS [Basics.Comparison];

SteppyNamePartsCompare: PROC [l1, l2: NameStepList] RETURNS [Basics.Comparison];

Seq: TYPE ~ BiRels.Sequence;

CreateSeq: PROC [len: NATURAL ← 0, oneToOne, dense, domainFixed: BOOL ← FALSE] RETURNS [Seq]

~ INLINE {RETURN [BiRels.CreateVector[bounds: [0, len-1], val: Sets.noValue, oneToOne: oneToOne, dense: dense, domainFixed: domainFixed]]};

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};

CopyBoolSeq: PROC [bs: BoolSeq] RETURNS [copy: BoolSeq]

~ INLINE {copy ← CreateBoolSeq[bs.length]; FOR i: NATURAL IN [0 .. copy.length) DO copy[i] ← bs[i] 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 [INT] ~ INLINE {

IF den<0 THEN {num ← -num; den ← -den};

RETURN [IF num>=0 THEN (num/den) ELSE ((num-den+1)/den)]};

CeilDiv: PROC [num, den: INT] RETURNS [INT] ~ INLINE {

IF den<0 THEN {num ← -num; den ← -den};

RETURN [IF num>=0 THEN ((num+den-1)/den) ELSE (num/den)]};

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};

Int2Mul: PROC [i: Int2, t, f: Nat2] RETURNS [m: Int2]

~ INLINE {RETURN [[Foo: i[Foo]*t[Foo]+f[Foo], Bar: i[Bar]*t[Bar]+f[Bar]]]};

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]]};

Int2Mod: PROC [a: Int2, mod: Nat2] RETURNS [Nat2]

~ INLINE {RETURN [[

Foo: ((a[Foo] MOD mod[Foo])+mod[Foo]) MOD mod[Foo],

Bar: ((a[Bar] MOD mod[Bar])+mod[Bar]) MOD mod[Bar]]]};

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]]]};

Nat2AddMod: PROC [a: Nat2, b: Int2, mod: Nat2] RETURNS [Nat2]

~ INLINE {RETURN [[

Foo: (a[Foo]+b[Foo]+mod[Foo]) MOD mod[Foo],

Bar: (a[Bar]+b[Bar]+mod[Bar]) MOD mod[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};

Int2sRange: PROC [a, b: Int2] RETURNS [r: Range2]

~ INLINE {RETURN [[

Foo: [MIN[a[Foo], b[Foo]], MAX[a[Foo], b[Foo]]+1],

Bar: [MIN[a[Bar], b[Bar]], MAX[a[Bar], b[Bar]]+1]]]};

Range2Mbb: PROC [a, b: Range2] RETURNS [Range2]

~ INLINE {RETURN [[Foo: RangeMbb[a[Foo], b[Foo]], Bar: RangeMbb[a[Bar], b[Bar]]]]};

RangeMbb: PROC [a, b: Range] RETURNS [Range]

~ INLINE {RETURN [[min: MIN[a.min, b.min], maxPlusOne: MAX[a.maxPlusOne, b.maxPlusOne]]]};

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)]};

Range2Div: PROC [r: Range2, t, f: Nat2] RETURNS [rr: Range2];

Range1Div: PROC [r: Range, t, f: NATURAL] RETURNS [rr: Range];

The range of i such that i*t+f is in r.

Range2MulA: PROC [r: Range2, t, f: Nat2] RETURNS [rr: Range2];

Range1MulA: PROC [r: Range, t, f: NATURAL] RETURNS [rr: Range];

rr.maxPlusOne-1 has given phase.

Range2MulB: PROC [r: Range2, t, f: Nat2] RETURNS [rr: Range2];

Range1MulB: PROC [r: Range, t, f: NATURAL] RETURNS [rr: Range];

rr.maxPlusOne has given phase.

Range2RoundA: PROC [r: Range2, t, f: Nat2] RETURNS [rr: Range2];

Range2RoundB: PROC [r: Range2, t, f: Nat2] RETURNS [rr: Range2];

FmtRange: PROC [r: Range] RETURNS [asRope: ROPE];

BeRope: PROC [r: ROPE] RETURNS [r2: ROPE] = INLINE {r2 ← r}--stupid goddam anachronism--;

END.