DIRECTORY AbSets, BiRelBasics, BiRels, IntStuff, SetBasics;

BiRelVectors: CEDAR PROGRAM
IMPORTS AbSets, BiRelBasics, BiRels, IntStuff, SetBasics
EXPORTS BiRels
=

BEGIN OPEN IntStuff, SetBasics, Sets:AbSets, Sets, BiRelBasics, BiRels;

Simple: TYPE ~ REF SimplePrivate;
SimplePrivate: TYPE ~ RECORD [
right: Space,
bounds: IntInterval,
leftDense, domFixed: BOOL,
d: INT,
vals: SimpleElts,
size, freezeCount: INT _ 0];

SimpleElts: TYPE ~ REF SimpleEltsPrivate;
SimpleEltsPrivate: TYPE ~ RECORD [vals: SEQUENCE size: NATURAL OF Value];

CreateVectorCopy: PUBLIC PROC [of: IntFn, bounds: IntInterval _ [], oneToOne, dense, domainFixed: RelBool _ SAME, rightSpace: Space _ NIL] RETURNS [IntFn] ~ {
realBounds: IntInterval ~ of.GetIntDom.Intersect[bounds];
realOneToOne: BOOL ~ oneToOne.RelativizeBool[of.Functional[][rightToLeft]];
realDense: BOOL ~ dense.RelativizeBool[of.IsDense[always, left]];
realDomainFixed: BOOL ~ domainFixed.RelativizeBool[of.SideFixed[left]];
realSpace: Space ~ IF rightSpace#NIL THEN rightSpace ELSE of.Spaces[][right];
vals: SimpleElts ~ NEW [SimpleEltsPrivate[realBounds.Length.EN]];
simple: Simple ~ NEW [SimplePrivate _ [realSpace, realBounds, realDense, realDomainFixed, realBounds.min, vals, of.Size[].EN]];
FOR i: INT IN [realBounds.min .. realBounds.max] DO {
mv: MaybeValue ~ of.ApplyI[i];
vals[i-simple.d] _ mv.it;
}ENDLOOP;
RETURN [[simpleClasses[realOneToOne][realDense][realDomainFixed][variable], simple]]};

CreateVector: PUBLIC PROC [bounds: IntInterval _ [0, -1], val: Value _ noValue, oneToOne, dense, domainFixed: BOOL _ FALSE, rightSpace: Space _ refs] RETURNS [IntFn] ~ {
vals: SimpleElts ~ NEW [SimpleEltsPrivate[bounds.Length.EN]];
simple: Simple ~ NEW [SimplePrivate _ [rightSpace, bounds, dense, domainFixed, bounds.min, vals, bounds.Length.EN]];
FOR i: NATURAL IN [0 .. vals.size) DO vals[i] _ val ENDLOOP;
IF val=noValue THEN {
simple.bounds _ simple.bounds.ClipTop[simple.bounds.min];
simple.size _ 0};
RETURN [[simpleClasses[oneToOne][dense][domainFixed][variable], simple]]};

SimpleClasses: TYPE ~ ARRAY --oneToOne--BOOL OF ARRAY --leftDense--BOOL OF ARRAY --domainFixed--BOOL OF ARRAY Mutability OF BiRelClass;
simpleClasses: REF SimpleClasses ~ NEW [SimpleClasses];

SimplePrimitive: PROC [br: BiRel, op: ATOM, arg1, arg2: REF ANY] RETURNS [PrimitiveAnswer] ~ {
simple: Simple ~ NARROW[br.data];
SELECT op FROM
$Apply, $Update => {dir: Direction ~ ToDir[arg1];
RETURN [IF dir=leftToRight THEN yes ELSE no]};
$ScanRestriction, $GetBounds => {ro: RelOrder ~ ToRO[arg2];
RETURN [IF ro.first#left AND ro.sub[ro.first]#no THEN no ELSE yes]};
$RestrictionSize => {sets: RefSetPair ~ ToSets[arg1];
RETURN [IF sets^=ALL[nilSet] THEN yes ELSE no]};
ENDCASE => RETURN [pass]};

SimpleApply: PROC [br: BiRel, v: Value, dir: Direction] RETURNS [MaybeValue] ~ {
simple: Simple ~ NARROW[br.data];
IF br.MutabilityOf=constant AND simple.freezeCount=0 THEN Complain[br, unfrozen];
IF dir=rightToLeft THEN RETURN DefaultApply[br, v, dir];
{i: INT ~ v.VI;
w: Value ~ IF simple.bounds.Contains[i] THEN simple.vals[i-simple.d] ELSE noValue;
RETURN [[w#noValue, w]]}};

SimpleUpdate: PROC [br: BiRel, val: Value, dir: Direction, Decide: UpdateDecider] ~ {
simple: Simple ~ NARROW[br.data];
IF br.MutabilityOf=constant AND simple.freezeCount=0 THEN Complain[br, unfrozen];
IF dir=rightToLeft THEN {DefaultUpdate[br, val, dir, Decide]; RETURN};
{i: INT ~ val.VI;
inBounds: BOOL ~ simple.bounds.Contains[i];
old: MaybeValue _ noMaybe;
IF inBounds THEN {
ov: Value ~ simple.vals[i-simple.d];
IF ov#noValue THEN old _ [TRUE, ov]};
{new: MaybeValue ~ Decide[old];
IF old=new THEN RETURN;
IF old.found AND new.found AND simple.right.SEqual[old.it, new.it] THEN RETURN;
IF (NOT old.found) AND (NOT new.found) THEN RETURN;
IF br.MutabilityOf[]#variable THEN br.Complain[notVariable];
IF new.found THEN {
IF old.found THEN {simple.vals[i-simple.d] _ new.it; RETURN};
IF simple.domFixed THEN br.Complain[fixedSide, LIST[AV[$left]]];
IF simple.leftDense AND (NOT inBounds) AND (simple.bounds.min=INT.FIRST OR i#simple.bounds.min-1) AND (simple.bounds.max=INT.LAST OR i#simple.bounds.max+1) THEN br.Complain[denseSide, LIST[AV[$left]]];
IF NOT inBounds THEN {de: NATURAL ~ EnsureContains[simple, [i, i]]; IF de=0 THEN ERROR};
simple.size _ simple.size+1;
simple.vals[i-simple.d] _ new.it;
RETURN};
{atEdge: BOOL ~ i=simple.bounds.min OR i=simple.bounds.max;
IF simple.domFixed THEN br.Complain[fixedSide, LIST[AV[$left]]];
IF simple.leftDense AND NOT atEdge THEN br.Complain[denseSide, LIST[AV[$left]]];
simple.vals[i-simple.d] _ noValue;
simple.size _ simple.size - 1;
IF atEdge THEN FixBounds[br, simple];
RETURN}}}};

SimpleScanRestriction: PROC [br: BiRel, sets: SetPair, Test: Tester, ro: RelOrder] RETURNS [MaybePair] ~ {
simple: Simple ~ NARROW[br.data];
IF br.MutabilityOf=constant AND simple.freezeCount=0 THEN Complain[br, unfrozen];
IF ro.first#left AND ro.sub[ro.first]#no THEN RETURN DefaultScanRestriction[br, sets, Test, ro];
{vals: SimpleElts ~ simple.vals;
left: Set ~ sets[left];
right: Set ~ sets[right];
leftTested: BOOL ~ left=nilSet OR left.GoodImpl[$QuaIntInterval];
lb: MaybeIntInterval ~ IF left#nilSet AND leftTested THEN left.QuaIntInterval ELSE [TRUE, []];
scanBounds: IntInterval ~ simple.bounds.Intersect[IF lb.found THEN lb.it ELSE []];
rn: BOOL ~ right=nilSet;
ld: BOOL ~ leftTested AND lb.found;
IF ro.sub[left]=bwd
THEN FOR i: INT DECREASING IN [scanBounds.min .. scanBounds.max] DO
pair: Pair ~ [IV[i], simple.vals[i-simple.d]];
IF pair[right]#noValue AND (ld OR left.HasMember[IV[i]]) AND (rn OR right.HasMember[pair[right]]) AND Test[pair] THEN RETURN [[TRUE, pair]];
ENDLOOP
ELSE FOR i: INT IN [scanBounds.min .. scanBounds.max] DO
pair: Pair ~ [IV[i], simple.vals[i-simple.d]];
IF pair[right]#noValue AND (ld OR left.HasMember[IV[i]]) AND (rn OR right.HasMember[pair[right]]) AND Test[pair] THEN RETURN [[TRUE, pair]];
ENDLOOP;
RETURN [noMaybePair]}};

SimpleRestrictionSize: PROC [br: BiRel, sets: SetPair, limit: EINT] RETURNS [EINT] ~ {
simple: Simple ~ NARROW[br.data];
IF sets # ALL[nilSet] THEN RETURN DefaultRestrictionSize[br, sets, limit];
RETURN [IE[simple.size]]};

SimpleGetBounds: PROC [br: BiRel, want: EndBools, ro: RelOrder] RETURNS [MaybePairInterval] ~ {
simple: Simple ~ NARROW[br.data];
IF br.MutabilityOf=constant AND simple.freezeCount=0 THEN Complain[br, unfrozen];
IF ro.first#left AND ro.sub[left]#no THEN RETURN DefaultGetBounds[br, want, ro];
IF simple.bounds.Empty THEN RETURN [[FALSE, [
min: [IV[simple.bounds.min], noValue],
max: [IV[simple.bounds.max], noValue]] ]];
{pi: PairInterval ~ [min: [IV[simple.bounds.min], simple.vals[simple.bounds.min-simple.d]], max: [IV[simple.bounds.max], simple.vals[simple.bounds.max-simple.d]]];
RETURN [[TRUE, IF ro.sub[left]#bwd THEN pi ELSE RevPI[pi] ]]}};

SimpleCopy: PROC [br: BiRel] RETURNS [VarBiRel] ~ {
simple: Simple ~ NARROW[br.data];
v1: SimpleElts ~ simple.vals;
IF br.MutabilityOf=constant AND simple.freezeCount=0 THEN Complain[br, unfrozen];
{v2: SimpleElts ~ NEW [SimpleEltsPrivate[v1.size]];
s2: Simple ~ NEW [SimplePrivate _ simple^];
s2.vals _ v2;
s2.freezeCount _ 0;
FOR i: NATURAL IN [0 .. v2.size) DO v2[i] _ v1[i] ENDLOOP;
RETURN AsVar[[simpleClasses [br.Functional[][rightToLeft]] [simple.leftDense] [simple.domFixed] [variable], s2]]}};

SimpleFreeze: PROC [br: BiRel] RETURNS [ConstBiRel] ~ {
simple: Simple ~ NARROW[br.data];
IF br.MutabilityOf#variable THEN Complain[br, notVariable];
simple.freezeCount _ simple.freezeCount + 1;
RETURN AsConst[[
simpleClasses [br.IsOneToOne] [simple.leftDense] [br.SideFixed[left]] [constant],
simple]];
};

SimpleThaw: PROC [br: BiRel] ~ {
simple: Simple ~ NARROW[br.data];
IF br.MutabilityOf#variable THEN Complain[br, notVariable];
IF simple.freezeCount<=0 THEN Complain[br, "too many thaws"];
simple.freezeCount _ simple.freezeCount-1;
RETURN};

SimpleAddSet: PROC [br, other: BiRel, if: IfHadPair] RETURNS [some: HadSetPair] ~ {
simple: Simple ~ NARROW[br.data];
right: Space ~ simple.right;
invSearch: BOOL ~ br.Functional[][rightToLeft];
urSize: INT ~ simple.size;
bounds: IntInterval;
d: INT;
vals: SimpleElts;
expansionCount: NATURAL _ 0;
Per: PROC [pair: Pair] RETURNS [BOOL] ~ {
i: INT ~ pair[left].VI;
news: Had _ different;
IF invSearch THEN FOR j: INT IN [bounds.min-d .. bounds.max-d] DO
IF vals[j]#noValue AND right.SEqual[vals[j], pair[right]] THEN
{some[rightToLeft][IF i=j THEN same ELSE different] _ TRUE; EXIT};
REPEAT FINISHED => some[rightToLeft][none] _ TRUE;
ENDLOOP;
IF bounds.Contains[i] THEN {
old: Value ~ vals[i-d];
IF old=noValue THEN {
news _ none;
simple.size _ simple.size+1;
}
ELSE IF right.SEqual[pair[right], old] THEN news _ same
}
ELSE IF simple.domFixed THEN br.Complain[fixedSide, LIST[AV[$left]]]
ELSE {
de: NATURAL ~ EnsureContains[simple, [i, i]];
IF de=0 THEN ERROR;
expansionCount _ expansionCount + de;
simple.size _ simple.size+1;
bounds _ simple.bounds; d _ simple.d; vals _ simple.vals; news _ none};
vals[i-d] _ pair[right];
some[leftToRight][news] _ TRUE;
RETURN [FALSE]};
IF br.MutabilityOf # variable THEN br.Complain[notVariable];
IF simple.freezeCount#0 THEN br.Complain[frozen];
some _ ALL[ALL[FALSE]];
IF other.QualityOf[$GetIntDom] >= goodDefault THEN expansionCount _ EnsureContains[simple, other.GetIntDom[]];
bounds _ simple.bounds; d _ simple.d; vals _ simple.vals;
[] _ other.Scan[Per];
{newCount: NATURAL ~ simple.size - urSize;
IF simple.leftDense AND newCount<expansionCount THEN br.Complain[denseSide, LIST[AV[$left]]];
IF newCount#0 THEN some[leftToRight][none] _ TRUE;
RETURN}};

EnsureContains: PROC [simple: Simple, bounds: IntInterval] RETURNS [expansionCount: NATURAL] ~ {
IF bounds.min >= simple.bounds.min AND bounds.max <= simple.bounds.max THEN RETURN [0];
{oldVals: SimpleElts ~ simple.vals;
oldSize: NATURAL ~ oldVals.size;
oldBounds: IntInterval ~ simple.bounds;
newBounds: IntInterval ~ simple.bounds.MBI[bounds];
newLen: NATURAL ~ newBounds.Length.EN;
oldD: INT ~ simple.d;
expansionCount _ newLen - oldBounds.Length.EN;
simple.bounds _ newBounds;
IF newBounds.min >= oldD AND newBounds.max <= oldD+(oldSize-1) THEN RETURN;
IF newLen <= oldSize THEN {
newPad: INT ~ (oldSize - newLen)/2;
newD: INT ~ ISub[newBounds.min, newPad].ClipI;
IF newD > oldD THEN {
FOR i: INT IN [oldBounds.min .. oldBounds.max] DO
oldVals[i-newD] _ oldVals[i-oldD];
ENDLOOP;
IF NOT oldBounds.Empty THEN FOR i: INT IN (oldBounds.max-newD .. oldBounds.max-oldD] DO
oldVals[i] _ noValue;
ENDLOOP;
};
IF newD < oldD THEN {
FOR i: INT DECREASING IN [oldBounds.min .. oldBounds.max] DO
oldVals[i-newD] _ oldVals[i-oldD];
ENDLOOP;
IF NOT oldBounds.Empty THEN FOR i: INT IN [oldBounds.min-oldD .. oldBounds.min-newD) DO
oldVals[i] _ noValue;
ENDLOOP;
};
simple.d _ newD;
RETURN};
{newSize: NATURAL ~ MIN[INT[NATURAL.LAST], MAX[newLen, INT[oldSize]*2]];
newVals: SimpleElts ~ NEW [SimpleEltsPrivate[newSize]];
newPad: INT ~ (newSize - newLen)/2;
newD: INT ~ newBounds.min - newPad;
IF oldBounds.Empty THEN {
FOR i: INT IN [0 .. newSize) DO newVals[i] _ noValue ENDLOOP;
}
ELSE {
FOR i: INT IN [0 .. oldBounds.min-newD) DO newVals[i] _ noValue ENDLOOP;
FOR i: INT IN [oldBounds.min .. oldBounds.max] DO newVals[i-newD] _ oldVals[i-oldD] ENDLOOP;
FOR i: INT IN (oldBounds.max-newD .. newSize) DO newVals[i] _ noValue ENDLOOP;
};
simple.d _ newD;
simple.vals _ newVals;
RETURN}}};

SimpleDenseRemSet: PROC [br, other: BiRel] RETURNS [some: HadSetPair _ []] ~ {
simple: Simple ~ NARROW[br.data];
vals: SimpleElts ~ simple.vals;
right: Space ~ simple.right;
urSize: INT ~ simple.size;
oldBounds: IntInterval ~ simple.bounds;
otherBounds: IntInterval ~ other.GetIntDom[];
scanBounds: IntInterval ~ oldBounds.Intersect[otherBounds];
mustKeep: IntInterval _ anEmptyInterval;
may: IntInterval _ oldBounds;
Per: PROC [pair: Pair] RETURNS [BOOL] ~ {
i: INT ~ pair[left].VI;
w: Value ~ vals[i-simple.d];
hadIt: BOOL ~ right.SEqual[pair[right], w];
IF hadIt THEN {
IF simple.domFixed THEN br.Complain[fixedSide, LIST[AV[$left]]]
ELSE IF mustKeep.Contains[i] THEN br.Complain[denseSide, LIST[AV[$left]]]
ELSE IF may.Contains[i] THEN {
SELECT i FROM
< mustKeep.min => may.min _ i+1;
> mustKeep.max => may.max _ i-1;
ENDCASE => ERROR;
};
vals[i-simple.d] _ noValue;
some[leftToRight][same] _ TRUE; simple.size _ simple.size - 1}
ELSE {
IF NOT may.Contains[i] THEN br.Complain[denseSide, LIST[AV[$left]]]
ELSE IF NOT mustKeep.Contains[i] THEN mustKeep _ [min: MIN[mustKeep.min, i], max: MAX[mustKeep.max, i]];
some[leftToRight][different] _ TRUE};
RETURN [FALSE]};
IF br.MutabilityOf # variable THEN br.Complain[notVariable];
IF simple.freezeCount#0 THEN br.Complain[frozen];
some[leftToRight][none] _ scanBounds#otherBounds;
IF br.Functional[][rightToLeft] THEN some[rightToLeft] _ Has[br, other, [FALSE, TRUE]][rightToLeft];
[] _ other.ScanHalfRestriction[IIAsSet[scanBounds], Per];
simple.bounds _ may;
simple.d _ simple.d - oldBounds.min + simple.bounds.min;
IF may.Length.AddI[urSize-simple.size] # oldBounds.Length THEN br.Complain[denseSide, LIST[AV[$left]]];
RETURN};

SimpleSparseRemSet: PROC [br, other: BiRel] RETURNS [some: HadSetPair _ []] ~ {
simple: Simple ~ NARROW[br.data];
vals: SimpleElts ~ simple.vals;
right: Space ~ simple.right;
oldBounds: IntInterval ~ simple.bounds;
otherBounds: IntInterval ~ other.GetIntDom[];
scanBounds: IntInterval ~ otherBounds.Intersect[oldBounds];
rebound: BOOL _ FALSE;
Per: PROC [pair: Pair] RETURNS [pass: BOOL _ FALSE] ~ {
i: INT ~ pair[left].VI;
w: Value ~ vals[i-simple.d];
notno: BOOL ~ w#noValue;
hadIt: BOOL ~ notno AND right.SEqual[pair[right], w];
IF hadIt THEN {
IF simple.domFixed THEN br.Complain[fixedSide, LIST[AV[$left]]];
IF i=oldBounds.min OR i=oldBounds.max THEN rebound _ TRUE;
vals[i-simple.d] _ noValue;
simple.size _ simple.size - 1;
some[leftToRight][same] _ TRUE}
ELSE some[leftToRight][IF notno THEN different ELSE none] _ TRUE;
};
IF br.MutabilityOf # variable THEN br.Complain[notVariable];
IF simple.freezeCount#0 THEN br.Complain[frozen];
some[leftToRight][none] _ scanBounds#otherBounds;
IF br.Functional[][rightToLeft] THEN some[rightToLeft] _ Has[br, other, [FALSE, TRUE]][rightToLeft];
[] _ other.ScanHalfRestriction[IIAsSet[scanBounds], Per];
IF rebound THEN FixBounds[br, simple];
RETURN};

FixBounds: PROC [br: BiRel, simple: Simple] ~ {
vals: SimpleElts ~ simple.vals;
d: INT ~ simple.d;
oldBounds: IntInterval ~ simple.bounds;
newBounds: IntInterval _ oldBounds;
WHILE newBounds.min<=newBounds.max AND vals[newBounds.min-d]=noValue DO newBounds _ newBounds.ClipBot[newBounds.min] ENDLOOP;
WHILE newBounds.min<=newBounds.max AND vals[newBounds.max-d]=noValue DO newBounds _ newBounds.ClipTop[newBounds.max] ENDLOOP;
simple.bounds _ newBounds;
IF NOT (oldBounds.Empty OR newBounds.Empty) THEN simple.d _ simple.d - simple.bounds.min + newBounds.min;
RETURN};

LeftDelete: PROC [simple: Simple, where: IntInterval] ~ {
in: IntInterval ~ where.Intersect[simple.bounds];
IF in.Empty THEN RETURN;
FOR i: INT IN [in.min-simple.d .. in.max-simple.d] DO
IF simple.vals[i]#noValue THEN {
simple.vals[i] _ noValue;
simple.size _ simple.size-1};
ENDLOOP;
IF where.min > simple.bounds.min
THEN IF where.max < simple.bounds.max
THEN NULL
ELSE simple.bounds.max _ where.min-1
ELSE IF where.max < simple.bounds.max
THEN simple.bounds.min _ where.max+1
ELSE simple.bounds _ anEmptyInterval;
RETURN};

SimpleReplaceMe: PROC [br, with: BiRel, where: IntInterval] ~ {
simple: Simple ~ NARROW[br.data];
clip: IntInterval ~ with.GetIntDom[];
clipLen: EINT ~ clip.Length;
whereLen: EINT ~ where.Length;
tailShift: EINT ~ clipLen.Sub[whereLen];
insertShift: EINT ~ ISub[where.min, clip.min];
oldBounds: IntInterval ~ simple.bounds;
insertBoundsEst: IntInterval ~ clip.ClipShiftInterval[insertShift];
beforeTail: INT ~ IF where.Empty THEN where.min-1 ELSE where.max;
bounds: IntInterval _ anEmptyInterval;
newBoundsEst, headNeed, tailNeed: IntInterval;
AddStuff: PROC [new: IntInterval] ~ {bounds _ bounds.MBI[new]};
AddPair: PROC [pair: Pair] RETURNS [BOOL] ~ {
i: INT ~ insertShift.AddI[pair[left].VI].EI;
[] _ EnsureContains[simple, [i, i]];
AddStuff[[i, i]]; simple.size _ simple.size + 1;
simple.vals[i-simple.d] _ pair[right];
RETURN [FALSE]};
IF br.MutabilityOf # variable THEN br.Complain[notVariable];
IF simple.freezeCount#0 THEN br.Complain[frozen];
SELECT TRUE FROM
oldBounds.max < where.min => {headNeed _ newBoundsEst _ oldBounds; tailNeed _ anEmptyInterval};
oldBounds.min > beforeTail => {tailNeed _ newBoundsEst _ oldBounds.ShiftInterval[tailShift]; headNeed _ anEmptyInterval};
ENDCASE => {
newBoundsEst _ [
min: MIN[oldBounds.min, where.min],
max: tailShift.AddI[MAX[oldBounds.max, where.max]].ClipI];
headNeed _ newBoundsEst.ClipTop[where.min];
tailNeed _ newBoundsEst.ClipBot[tailShift.AddI[beforeTail].ClipI]};
[] _ EnsureContains[simple, tailNeed];
AddStuff[headNeed];
AddStuff[tailNeed];
IF NOT tailNeed.Empty THEN SELECT tailShift.Sgn[] FROM
<0 => {
FOR i: INT IN [tailNeed.min-simple.d .. tailNeed.max-simple.d] DO
j: INT ~ tailShift.SubFromI[i].EI;
IF simple.vals[i]=noValue THEN simple.size _ simple.size-1;
simple.vals[i] _ simple.vals[j]; simple.vals[j] _ noValue;
ENDLOOP;
};
>0 => {
olds: IntInterval ~ oldBounds.ClipBot[insertBoundsEst.max].ClipTop[tailNeed.min];
FOR i: INT DECREASING IN [tailNeed.min .. tailNeed.max] DO
j: INT ~ tailShift.SubFromI[i].EI;
simple.vals[i-simple.d] _ simple.vals[j-simple.d];
ENDLOOP;
FOR i: INT IN [olds.min .. olds.max] DO
simple.vals[i-simple.d] _ noValue;
ENDLOOP;
};
=0 => NULL;
ENDCASE => ERROR;
LeftDelete[simple, insertBoundsEst];
{midSize: INT ~ simple.size;
[] _ with.Scan[AddPair];
IF simple.leftDense AND headNeed.Length.Add[tailNeed.Length].AddI[simple.size-midSize] # bounds.Length THEN br.Complain[denseSide, LIST[AV[$left]]];
IF simple.domFixed AND bounds#oldBounds THEN br.Complain[fixedSide, LIST[AV[$left]]];
simple.bounds _ bounds;
IF NOT (bounds.Empty OR oldBounds.Empty) THEN simple.d _ simple.d-oldBounds.min+simple.bounds.min;
RETURN}};

SimpleShiftAndClipMe: PROC [br: BiRel, shift: EINT, clip: IntInterval] ~ {
simple: Simple ~ NARROW[br.data];
unshifted: IntInterval ~ simple.bounds.Intersect[clip];
newBounds: IntInterval ~ unshifted.ClipShiftInterval[shift];
IF br.MutabilityOf#variable THEN br.Complain[notVariable];
IF simple.freezeCount#0 THEN br.Complain[frozen];
IF simple.domFixed AND newBounds#simple.bounds THEN br.Complain[fixedSide, LIST[AV[$left]]];
FOR i: INT IN [simple.bounds.min-simple.d .. unshifted.min-simple.d) DO
IF simple.vals[i]#noValue THEN {simple.vals[i] _ noValue; simple.size _ simple.size-1};
ENDLOOP;
FOR i: INT IN (unshifted.max-simple.d .. simple.bounds.max-simple.d] DO
IF simple.vals[i]#noValue THEN {simple.vals[i] _ noValue; simple.size _ simple.size-1};
ENDLOOP;
simple.d _ shift.AddI[simple.d].EI;
simple.bounds _ newBounds;
RETURN};

SimpleSpaces: PROC [br: BiRel] RETURNS [SpacePair] ~ {
simple: Simple ~ NARROW[br.data];
RETURN [[ints, simple.right]]};

SimpleIsDense: PROC [br: BiRel, when: When, side: Side] RETURNS [BOOL] ~ {
simple: Simple ~ NARROW[br.data];
RETURN [side=left AND simple.leftDense]};

SimpleSideFixed: PROC [br: BiRel, side: Side] RETURNS [BOOL] ~ {
simple: Simple ~ NARROW[br.data];
RETURN [br.MutabilityOf=constant OR (side=left AND simple.domFixed)]};

Start: PROC ~ {
FOR isOneToOne: BOOL IN BOOL DO FOR dense: BOOL IN BOOL DO FOR domainFixed: BOOL IN BOOL DO FOR mutability: Mutability IN Mutability DO
simpleClasses[isOneToOne][dense][domainFixed][mutability] _ CreateClass[
cp: [
Primitive: SimplePrimitive,
Apply: SimpleApply,
ScanRestriction: SimpleScanRestriction,
RestrictionSize: SimpleRestrictionSize,
GetBounds: SimpleGetBounds,
Copy: SimpleCopy,
Freeze: SimpleFreeze,
Thaw: SimpleThaw,
AddSet: SimpleAddSet,
RemSet: IF dense THEN SimpleDenseRemSet ELSE SimpleSparseRemSet,
Update: SimpleUpdate,
ReplaceMe: SimpleReplaceMe,
ShiftAndClipMe: SimpleShiftAndClipMe,
Spaces: SimpleSpaces,
IsDense: SimpleIsDense,
SideFixed: SimpleSideFixed,
functional: [TRUE, isOneToOne],
mutability: mutability
],
dirable: [TRUE, TRUE]
];
ENDLOOP ENDLOOP ENDLOOP ENDLOOP;
};

Start[];

END.
τBiRelVectors.Mesa
Last tweaked by Mike Spreitzer on January 20, 1988 7:37:11 pm PST
elt i is stored in vals[i-d].  Thus, there is storage for elts [d .. d+vals.size).  Storage cells not corresponding to domain elts have noValue in them.
Κ$–

"cedar" style˜
code™Kš
œA™A—K˜KšΟk	œ2˜;K˜šΟnœœ
˜Kšœ1˜8Kšœ˜K˜
—K˜Kšœ
œžœ#˜GK˜Kšœœœ˜!šœœœ˜K˜
K˜Kšœœ
˜KšΟg
œœ
˜K˜Kšœœ˜KšœŸ
œ%Ÿ
œŸ
œR™˜
—K˜Kšœœœ˜)Kšœœœœœ
œ˜IK˜šžœœ
œOœœœ˜ž
Kš
œ9˜9Kšœœ9˜KKšœœ2˜AKšœœ2˜GKš	œœœ
œœ˜MKšœœ&œ˜AKšœœfœ˜šœœ
œ$œ˜5Kš
œ˜KšœŸ
œ
˜Kšœ
œ
˜	—KšœP˜V—K˜šžœœ
œUœœœ˜©
Kšœœ"œ˜=Kšœœ[œ˜tKš
œœ
œœœ
˜<šœ
œ˜Kš
œ9˜9K˜—KšœD˜J—K˜Kšœœœ
Οcœ
œ
œ
 
œ
œ
œ
 œ
œ
œœ˜‡
Kšœœœ˜7K˜šžœœœœ
œœ˜^Kšœœ
˜!šœ˜š
œ1˜1Kšœœœœ˜.—š
œ;˜;Kš
œœœœœ˜D—š
œ5˜5Kš
œœœ	œœ˜0—Kšœœ	˜——K˜šžœœ'œ˜PKšœœ
˜!Kšœœœ˜QKšœœ
œ˜8Kšœœœ
˜Kš	œœœŸ
œœ	˜RKšœ˜—K˜šžœœ)žœ˜UKšœœ
˜!Kšœœœ˜QKšœœ'œ˜FKšœœœ
˜Kšœ
œ˜+Kš
œ˜šœ
œ˜Kšœ!Ÿ
œ˜$Kšœœœ˜%—K˜Kšœ	œ
œ
˜Kš
œœœ%œ
œ
˜OKšœœœœœ
œ
˜3Kšœœ˜<šœœ˜KšœœŸ
œœ˜=Kšœœœ
œ
˜@Kšœœœœœ
œ
œœœ
œ
œœœ
œ
˜Ι
Kšœ
œ
œŸ
œœ#œ
Ÿ
œœ
œ˜XKš
œ˜KšœŸ
œ˜!Kšœ˜—Kšœ	œœ˜;Kšœœœ
œ
˜@Kšœœ
œœœ
œ
˜PKšœŸ
œ˜"K˜Kšœœ˜%Kšœ˜—K˜šžœœžœœ˜jKšœœ
˜!Kšœœœ˜QKšœœœ
œ,˜`Kš
œ ˜ K˜K˜Kšœœœ ˜AKšœœ
œœœœ˜^Kšœ2œ
œœ˜RKšœœ˜Kšœœœ
˜#šœ˜šœ
œœ

œ
œ$˜CKšœœŸ
œ˜.Kšœœœœœœœœ
œœ	˜Œ
Kš
˜—š	œ
œœ
œ$˜8KšœœŸ
œ˜.Kšœœœœœœœœ
œœ	˜Œ
Kšœ
˜——Kšœ˜—K˜š
žœœ#œœœ˜VKšœœ
˜!Kšœœ	œ
œ)˜JKšœœ˜—K˜šžœœ+œ˜_Kšœœ
˜!Kšœœœ˜QKšœœœ
œ ˜Pšœœ
œœ˜-Kšœœ˜&Kšœœ"˜*—Kš	œœ:Ÿ
œ
œ:Ÿ
œ˜£
Kš
œœœœœ˜?—K˜šž
œœ
œ˜3Kšœœ
˜!Kš
œ˜Kšœœœ˜QKšœœ˜3Kšœ
œ˜+K˜
Kš
œ˜Kš
œœ
œœœ
˜:Kšœm˜s—K˜šžœœ
œ˜7Kšœœ
˜!Kšœœ˜;Kš
œ,˜,šœ
˜Kš
œQ˜QK˜	—K˜—K˜šž
œœ˜ Kšœœ
˜!Kšœœ˜;Kšœœ ˜=Kš
œ*˜*Kšœ˜—K˜šžœœ#œ˜SKšœœ
˜!K˜Kšœœ ˜/Kšœœ˜K˜KšŸ
œœ
˜K˜Kšœœ˜šžœœœœ˜)Kšœœœ
˜Kš
œ˜šœœ
œœ
œ ˜Ašœœ$˜>Kšœœœœœœ˜B—Kšœ
œœ
˜2Kšœ
˜—šœœ˜KšœŸ
œ˜šœ
œ˜K˜Kš
œ˜K˜
—Kšœ
œ œ˜7Kš
œ
˜
—Kš
œ
œœœ
œ	˜Dšœ˜KšŸ
œœ"˜-Kšœ
Ÿ
œœ
œ
˜Kšœ"Ÿ
œ˜%Kš
œ˜KšœŸ
œ
Ÿ
œ#˜G—KšœŸ
œ˜Kšœœ
˜Kšœœ˜—Kšœœ˜<Kšœœ˜1Kšœœ
œ
œ˜Kšœ,œ<˜nKšœŸ
œ
Ÿ
œ˜9K˜Kšœœ˜*Kš
œœœœ
œ
˜]Kšœœœ
˜2Kšœ˜	—K˜šžœœ'œœ˜`Kšœ!œ!œ
œ˜WK˜#Kšœ	œ˜ K˜'Kšœ'œ	˜3Kšœœœ
˜&KšœŸ
œœ
Ÿ
œ
˜Kšœ+œ
˜.K˜KšœŸ
œ
œŸ
œ
œ
œ
˜Kšœœ˜Kšœœ˜#KšœŸ
œœ%˜.šœŸ
œŸ
œ
œ˜šœœ
œ"˜1Kšœ
Ÿ
œŸ
œ˜"Kšœ
˜—šœ
œœ
œœ
œŸ
œŸ
œ˜WKš
œ˜Kšœ
˜—K˜—šœŸ
œŸ
œ
œ˜š	œœ

œ
œ"˜<Kšœ
Ÿ
œŸ
œ˜"Kšœ
˜—šœ
œœ
œœ
œŸ
œŸ
œ˜WKš
œ˜Kšœ
˜—K˜—KšœŸ
œŸ
œ
˜Kšœ˜—Kšœ
œœ
œ
œ
œœ	œ˜HKšœœ˜7Kšœœ˜#KšœŸ
œœ˜#šœœ˜Kš
œœ
œœœ
˜=K˜
—šœ˜Kšœœ
œŸ
œœœ
˜HKšœœ
œ"œŸ
œŸ
œœ
˜\Kšœœ
œŸ
œ
œœ
˜NK˜—KšœŸ
œŸ
œ
˜K˜Kšœ˜
—K˜šžœœœ˜NKšœœ
˜!K˜K˜Kšœœ˜K˜'K˜-K˜;Kš
œ(˜(K˜šžœœœœ˜)Kšœœœ
˜KšœŸ
œ˜Kšœœ ˜+šœœ˜Kšœœœ
œ	˜?Kš
œ
œœœ
œ	˜Išœ
œœ˜šœ˜
K˜ K˜ Kšœœ
˜—K˜—KšœŸ
œ˜Kšœœ ˜>—šœ˜Kš
œ
œœœ
œ	˜CKšœ
œ
œœœœ˜hKšœœ˜%—Kšœœ˜—Kšœœ˜<Kšœœ˜1Kš
œ1˜1Kšœœ%œœ˜dKš
œ9˜9Kš
œ˜KšœŸ
œ
Ÿ
œ%˜8Kšœ8œœ
œ
˜gKšœ˜—K˜šžœœœ˜OKšœœ
˜!K˜K˜K˜'Kš
œ-˜-Kš
œ;˜;Kšœ	œœ
˜š
žœœœœœ˜7Kšœœœ
˜KšœŸ
œ˜Kšœœ
˜Kšœœ	œ˜5šœœ˜Kšœœœ
œ
˜@Kšœœœœ
˜:KšœŸ
œ˜K˜Kšœœ
˜—Kš
œœœœ	œ
˜AK˜—Kšœœ˜<Kšœœ˜1Kš
œ1˜1Kšœœ%œœ˜dKš
œ9˜9Kšœ	œ˜&Kšœ˜—K˜šž	œœ ˜/K˜KšŸ
œœ
Ÿ
œ
˜K˜'K˜#Kš
œœŸ
œ
œ.œ
˜}Kš
œœŸ
œ
œ.œ
˜}K˜Kšœ
œœœŸ
œ
Ÿ
œ%˜iKšœ˜—K˜šž
œœ)˜9Kš
œ1˜1Kšœ
œ
œ
˜šœœ
œŸ
œŸ
œ˜5šœœ˜ Kš
œ˜Kš
œ˜—Kšœ
˜—šœ˜ šœ
œ˜%Kšœ
˜	Kšœ ˜$—šœ
œ˜%Kšœ ˜$Kšœ!˜%——Kšœ˜—K˜šžœœ*˜?Kšœœ
˜!Kš
œ%˜%Kšœ	œ˜Kšœ
œ˜Kšœœ˜(Kšœ
œ˜.K˜'Kš
œC˜CKš	œœœ
œ
œ˜AK˜&Kš
œ.˜.Kšžœœ'œ˜?šžœœœœ˜-Kšœœœœ
˜,Kš
œ$˜$Kš
œ0˜0KšœŸ
œ˜&Kšœœ˜—Kšœœ˜<Kšœœ˜1šœ
œ
˜Kš
œ_˜_Kš
œy˜yšœ˜˜Kšœœ˜#Kšœœ#˜:—K˜+Kš
œC˜C——Kš
œ&˜&Kš
œ˜Kš
œ˜š	œ
œœ
œ˜6š
œ˜šœœ
œŸ
œŸ
œ˜AKšœœœ
˜"Kšœœ˜;Kš
œ:˜:Kšœ
˜—K˜—˜Kš
œQ˜Qš	œœ

œ
œ ˜:Kšœœœ
˜"KšœŸ
œŸ
œ˜2Kšœ
˜—šœœ
œ˜'KšœŸ
œ˜"Kšœ
˜—K˜—Kšœœ
˜Kšœœ
˜—Kš
œ$˜$Kšœ
œ˜K˜Kš
œœPœœ
œ
˜”
Kš
œœœœ
œ
˜UKš
œ˜Kšœ
œœœŸ
œ
Ÿ
œ!˜bKšœ˜	—K˜šžœœœ˜JKšœœ
˜!K˜7Kš
œ<˜<Kšœœ˜:Kšœœ˜1Kš
œœœœ
œ
˜\šœœ
œŸ
œŸ
œ˜GKšœœ9˜WKšœ
˜—šœœ
œŸ
œŸ
œ˜GKšœœ9˜WKšœ
˜—KšœŸ
œŸ
œœ
˜#K˜Kšœ˜—K˜šžœœ
œ˜6Kšœœ
˜!Kšœ˜—K˜šž
œœ%œœ˜JKšœœ
˜!Kšœœ˜)—K˜šžœœœœ˜@Kšœœ
˜!Kšœœœ˜FK˜—šžœœ˜š#œ
œ
œ
œ
œ
œœ
œ
œ
œ
œœ
œ
œ
œ
œœ˜‡
š
œH˜H˜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šœ
˜—…—NDg\