DIRECTORY AbSets, IntStuff, SetBasics;

SetsByVectors: CEDAR PROGRAM
IMPORTS AbSets, IntStuff, SetBasics
EXPORTS AbSets
=

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

Simple: TYPE ~ REF SimplePrivate;
SimplePrivate: TYPE ~ RECORD [
bounds: IntInterval,
dense, expandable: BOOL,
d: INT,
occ, freezeCount: INT _ 0,
ext: Simple _ NIL,
bits: PACKED SEQUENCE alloc: NATURAL OF BOOL];

SimpleElts: TYPE ~ Simple;

GetVals: PROC [s: Simple] RETURNS [SimpleElts]
~ INLINE {RETURN [IF s.ext#NIL THEN s.ext ELSE s]};

CreateBitVector: PUBLIC PROC [bounds: IntInterval _ [0, -1], dense: BOOL _ FALSE, expandable: BOOL _ TRUE] RETURNS [VarSet--of ints--] ~ {
givenLen: NATURAL ~ bounds.Length.EN;
startLen: NATURAL ~ IF expandable THEN MAX[givenLen, 32] ELSE givenLen;
buff: NATURAL ~ (startLen - givenLen)/2;
simple: Simple ~ NEW [SimplePrivate[startLen]];
simple.bounds _ bounds.ClipTop[bounds.min];
simple.dense _ dense;
simple.expandable _ expandable;
simple.d _ MAX[bounds.min, INT.FIRST+buff]-buff;
simple.occ _ simple.freezeCount _ 0;
simple.ext _ NIL;
FOR i: NATURAL IN [0 .. simple.alloc) DO simple[i] _ FALSE ENDLOOP;
RETURN AsVar[[simpleClasses[dense][expandable][variable], AV[simple]]]};

SimpleClasses: TYPE ~ ARRAY --dense--BOOL OF ARRAY --expandable--BOOL OF ARRAY Mutability OF SetClass;
simpleClasses: REF SimpleClasses ~ NEW [SimpleClasses];

HasMemByUpdate: PROC [set: Set, elt: Value] RETURNS [BOOL] ~ {
had: BOOL _ FALSE;
TestHas: PROC [has: BOOL] RETURNS [BOOL] ~ {RETURN [had _ has]};
SimpleUpdate[set, elt, TestHas];
RETURN [had]};

UpdateDecider: TYPE ~ PROC [BOOL] RETURNS [BOOL];

SimpleUpdate: PROC [set: Set, val: Value, Decide: UpdateDecider] ~ {
simple: Simple ~ NARROW[set.data.VA];
IF set.MutabilityOf=constant AND simple.freezeCount=0 THEN Complain[set, unfrozen];
{i: INT ~ val.VI;
inBounds: BOOL ~ simple.bounds.Contains[i];
vals: SimpleElts ~ GetVals[simple];
old: BOOL ~ inBounds AND vals[i-simple.d];
new: BOOL ~ Decide[old];
IF old=new THEN RETURN;
IF set.MutabilityOf[]#variable THEN set.Complain[notVariable];
IF new THEN {
IF simple.dense 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 set.Complain[denseSet];
IF NOT inBounds THEN {de: NATURAL ~ EnsureContains[set, simple, [i, i]]; IF de=0 THEN ERROR};
simple.occ _ simple.occ+1;
vals[i-simple.d] _ TRUE;
RETURN}
ELSE {
atEdge: BOOL ~ i=simple.bounds.min OR i=simple.bounds.max;
IF simple.dense AND NOT atEdge THEN set.Complain[denseSet];
simple.occ _ simple.occ - 1;
vals[i-simple.d] _ FALSE;
IF atEdge THEN FixBounds[set, simple];
RETURN}}};

SimpleScan: PROC [set: Set, Test: Tester, ro: RelOrder] RETURNS [MaybeValue] ~ {
simple: Simple ~ NARROW[set.data.VA];
IF set.MutabilityOf=constant AND simple.freezeCount=0 THEN Complain[set, unfrozen];
IF ro=bwd
THEN FOR i: INT DECREASING IN [simple.bounds.min .. simple.bounds.max] DO
IF GetVals[simple][i-simple.d] AND Test[IV[i]] THEN RETURN [[TRUE, IV[i]]];
ENDLOOP
ELSE FOR i: INT IN [simple.bounds.min .. simple.bounds.max] DO
IF GetVals[simple][i-simple.d] AND Test[IV[i]] THEN RETURN [[TRUE, IV[i]]];
ENDLOOP;
RETURN [noMaybe]};

SimpleSize: PROC [set: Set, limit: EINT] RETURNS [EINT] ~ {
simple: Simple ~ NARROW[set.data.VA];
RETURN [IE[simple.occ]]};

SimpleGetBounds: PROC [set: Set, want: EndBools] RETURNS [MaybeInterval] ~ {
simple: Simple ~ NARROW[set.data.VA];
IF set.MutabilityOf=constant AND simple.freezeCount=0 THEN Complain[set, unfrozen];
RETURN [[NOT simple.bounds.Empty, IValify[simple.bounds]]]};

SimpleCopy: PROC [set: Set] RETURNS [VarSet] ~ {
simple: Simple ~ NARROW[set.data.VA];
v1: SimpleElts ~ GetVals[simple];
IF set.MutabilityOf=constant AND simple.freezeCount=0 THEN Complain[set, unfrozen];
{s2: Simple ~ NEW [SimplePrivate[IF simple.ext=NIL THEN simple.alloc ELSE 0]];
s2.bounds _ simple.bounds;
s2.dense _ simple.dense;
s2.expandable _ simple.expandable;
s2.d _ simple.d;
s2.occ _ simple.occ;
s2.freezeCount _ 0;
s2.ext _ IF simple.ext#NIL THEN NEW[SimplePrivate[simple.ext.alloc]] ELSE NIL;
{v2: SimpleElts ~ GetVals[simple];
FOR i: NATURAL IN [0 .. v2.alloc) DO v2[i] _ v1[i] ENDLOOP;
RETURN AsVar[[simpleClasses[s2.dense][s2.expandable][variable], AV[s2]]]}}};

SimpleFreeze: PROC [set: Set] RETURNS [ConstSet] ~ {
simple: Simple ~ NARROW[set.data.VA];
IF set.MutabilityOf#variable THEN Complain[set, notVariable];
simple.freezeCount _ simple.freezeCount + 1;
RETURN AsConst[[
simpleClasses[simple.dense][set.IsDense[always]][constant],
AV[simple]]];
};

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

SimpleAddSet: PROC [set, other: Set] RETURNS [new: SomeAll _ []] ~ {
simple: Simple ~ NARROW[set.data.VA];
urSize: INT ~ simple.occ;
bounds: IntInterval;
d: INT;
vals: SimpleElts;
expansionCount: NATURAL _ 0;
Per: PROC [val: Value] RETURNS [BOOL] ~ {
i: INT ~ val.VI;
IF bounds.Contains[i] THEN {
IF vals[i-d] THEN new.all _ FALSE ELSE {
vals[i-d] _ TRUE;
simple.occ _ simple.occ+1}}
ELSE {
de: NATURAL ~ EnsureContains[set, simple, [i, i]];
IF de=0 THEN ERROR;
expansionCount _ expansionCount + de;
bounds _ simple.bounds; d _ simple.d; vals _ GetVals[simple];
vals[i-d] _ TRUE;
simple.occ _ simple.occ+1};
RETURN [FALSE]};
IF set.MutabilityOf # variable THEN set.Complain[notVariable];
IF simple.freezeCount#0 THEN set.Complain[frozen];
IF other.QualityOf[$GetIntBounds] >= goodDefault THEN expansionCount _ EnsureContains[set, simple, other.GetIntBounds[]];
bounds _ simple.bounds; d _ simple.d; vals _ GetVals[simple];
IF other.Scan[Per].found THEN ERROR;
{newCount: NATURAL ~ simple.occ - urSize;
IF simple.dense AND newCount#expansionCount THEN set.Complain[denseSet];
IF newCount#0 THEN new.some _ TRUE;
RETURN}};

EnsureContains: PROC [set: Set, simple: Simple, bounds: IntInterval] RETURNS [expansionCount: NATURAL] ~ {
IF bounds.min >= simple.bounds.min AND bounds.max <= simple.bounds.max THEN RETURN [0];
{oldVals: SimpleElts ~ GetVals[simple];
oldD: INT ~ simple.d;
oldSize: NATURAL ~ oldVals.alloc;
oldBounds: IntInterval ~ simple.bounds;
newBounds: IntInterval ~ simple.bounds.MBI[bounds];
newLen: NATURAL ~ newBounds.Length.EN;
expansionCount _ newLen - oldBounds.Length.EN;
IF newBounds.min >= oldD AND newBounds.max <= oldD+(oldSize-1) THEN {simple.bounds _ newBounds; RETURN};
IF NOT simple.expandable THEN set.Complain[notExpandable];
simple.bounds _ newBounds;
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] _ FALSE;
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] _ FALSE;
ENDLOOP;
};
simple.d _ newD;
RETURN};
{newSize: NATURAL ~ MIN[INT[NATURAL.LAST], MAX[newLen, INT[oldSize]*2]];
newVals: SimpleElts ~ NEW [SimplePrivate[newSize]];
newPad: INT ~ (newSize - newLen)/2;
newD: INT ~ newBounds.min - newPad;
IF oldBounds.Empty THEN {
FOR i: INT IN [0 .. newSize) DO newVals[i] _ FALSE ENDLOOP;
}
ELSE {
FOR i: INT IN [0 .. oldBounds.min-newD) DO newVals[i] _ FALSE 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] _ FALSE ENDLOOP;
};
simple.d _ newD;
simple.ext _ newVals;
RETURN}}};

SimpleDenseRemSet: PROC [set, other: Set] RETURNS [had: SomeAll _ []] ~ {
simple: Simple ~ NARROW[set.data.VA];
vals: SimpleElts ~ GetVals[simple];
urSize: INT ~ simple.occ;
oldBounds: IntInterval ~ simple.bounds;
mustKeep: IntInterval _ anEmptyInterval;
may: IntInterval _ oldBounds;
Per: PROC [val: Value] RETURNS [BOOL] ~ {
i: INT ~ val.VI;
IF vals[i-simple.d] THEN {
IF mustKeep.Contains[i] THEN set.Complain[denseSet]
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] _ FALSE;
had.some _ TRUE; simple.occ _ simple.occ - 1}
ELSE {
IF NOT may.Contains[i] THEN set.Complain[denseSet]
ELSE IF NOT mustKeep.Contains[i] THEN mustKeep _ [min: MIN[mustKeep.min, i], max: MAX[mustKeep.max, i]];
had.all _ FALSE};
RETURN [FALSE]};
IF set.MutabilityOf # variable THEN set.Complain[notVariable];
IF simple.freezeCount#0 THEN set.Complain[frozen];
IF other.Scan[Per].found THEN ERROR;
simple.bounds _ may;
IF simple.expandable THEN simple.d _ simple.d - oldBounds.min + simple.bounds.min;
IF may.Length.AddI[urSize-simple.occ] # oldBounds.Length THEN set.Complain[denseSet];
RETURN};

SimpleSparseRemSet: PROC [set, other: Set] RETURNS [had: SomeAll _ []] ~ {
simple: Simple ~ NARROW[set.data.VA];
vals: SimpleElts ~ GetVals[simple];
oldBounds: IntInterval ~ simple.bounds;
rebound: BOOL _ FALSE;
Per: PROC [val: Value] RETURNS [BOOL] ~ {
i: INT ~ val.VI;
IF vals[i-simple.d] THEN {
IF i=oldBounds.min OR i=oldBounds.max THEN rebound _ TRUE;
vals[i-simple.d] _ FALSE;
simple.occ _ simple.occ - 1;
had.some _ TRUE}
ELSE had.all _ FALSE;
RETURN [FALSE]};
IF set.MutabilityOf # variable THEN set.Complain[notVariable];
IF simple.freezeCount#0 THEN set.Complain[frozen];
IF other.Scan[Per].found THEN ERROR;
IF rebound THEN FixBounds[set, simple];
RETURN};

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

SimpleQuaIntInterval: PROC [set: Set] RETURNS [MaybeIntInterval] ~ {
simple: Simple ~ NARROW[set.data.VA];
RETURN [[simple.dense, simple.bounds]]};

SimpleSpaceOf: PROC [set: Set] RETURNS [Space] ~ {
simple: Simple ~ NARROW[set.data.VA];
RETURN [ints]};

SimpleIsDense: PROC [set: Set, when: When] RETURNS [BOOL] ~ {
simple: Simple ~ NARROW[set.data.VA];
RETURN [simple.dense]};

Start: PROC ~ {
FOR dense: BOOL IN BOOL DO FOR expandable: BOOL IN BOOL DO FOR mutability: Mutability IN Mutability DO
simpleClasses[dense][expandable][mutability] _ CreateClass[
cp: [
HasMember: HasMemByUpdate,
Scan: SimpleScan,
Size: SimpleSize,
IsDense: SimpleIsDense,
GetBounds: SimpleGetBounds,
Copy: SimpleCopy,
Freeze: SimpleFreeze,
Thaw: SimpleThaw,
AddSet: SimpleAddSet,
RemSet: IF dense THEN SimpleDenseRemSet ELSE SimpleSparseRemSet,
SpaceOf: SimpleSpaceOf,
mutability: mutability
],
relable: ALL[TRUE]
];
ENDLOOP ENDLOOP ENDLOOP;
};

Start[];

END.
όSetsByVectors.Mesa
Last tweaked by Mike Spreitzer on February 27, 1988 3:06:22 pm PST
the bit for i is stored in vals[i-d].  Thus, there is storage for bits [d .. d+vals.alloc).  Storage cells not corresponding to domain elts have FALSE in them.
Κ3–

"cedar" style˜
code™Kš
œB™B—K˜KšΟk	œ˜&K˜šΟn
œœ
˜Kšœ˜#Kšœ˜K˜
—K˜Kšœ
œžœ˜2K˜Kšœœœ˜!šœœœ˜K˜Kšœœ
˜KšΟg
œœ
˜Kšœœ˜Kšœœ
˜Kšœœ
œœ
œ
œ˜.Kš	œ"Ÿ
œ%Ÿ
œŸ
œCœ	™Ÿ
—K˜Kšœœ
˜K˜šžœœ
œ
˜.Kš
œœœœœ
œœ˜3—K˜šžœœ
œ(œœœœœΟcœ˜Š
Kšœ
œœ
˜%Kšœ
œœœ
œœ
˜GKšœœ˜(Kšœœ˜/Kš
œ+˜+Kš
œ˜Kš
œ˜Kš	œŸ
œœ
œ
œ˜0Kš
œ$˜$Kšœ
œ
˜Kšœœ
œœ
œ
œ
˜CKšœ4œ˜H—K˜Kšœœœ
 	œ
œ
œ
 œ
œ
œœ
˜fKšœœœ˜7K˜šžœœœœ˜>Kšœœœ
˜Kšžœœœœœœ˜@Kš
œ ˜ Kšœ˜—K˜Kšœœœœœœ˜1K˜šžœœžœ˜DKšœœ
œ˜%Kšœœœ˜SKšœœœ
˜Kšœ
œ˜+K˜#KšœœœŸ
œ˜*Kšœœ˜Kšœ	œ
œ
˜Kšœœ˜>šœœ˜
Kšœœœœœ
œ
œœœ
œ
œœ˜΄
Kšœ
œ
œŸ
œœ(œ
Ÿ
œœ
œ˜]Kš
œ˜KšœŸ
œœ
˜Kšœ
˜—šœ˜Kšœœœ˜:Kšœœ
œœ˜;K˜KšœŸ
œœ
˜Kšœœ˜&Kšœ˜
——K˜šž
œœžœœ˜PKšœœ
œ˜%Kšœœœ˜Sšœ˜	šœ
œœ

œ
œ*˜IKšœŸ
œœœœ
œœœ˜KKš
˜—š	œ
œœ
œ*˜>KšœŸ
œœœœ
œœœ˜KKšœ
˜——Kšœ˜—K˜š
ž
œœœœœ˜;Kšœœ
œ˜%Kšœœ˜—K˜šžœœœ˜LKšœœ
œ˜%Kšœœœ˜SKšœœ/˜<—K˜šž
œœœ
˜0Kšœœ
œ˜%Kš
œ!˜!Kšœœœ˜SKšœœœœ
œœ˜NK˜K˜Kš
œ"˜"KšœŸ
œ
Ÿ
œ
˜K˜Kš
œ˜Kš
œ	œœ
œ
œ"œ
œ
˜NK˜"Kš
œœ
œœœ
˜;Kšœ:œ
˜L—K˜šžœœœ˜4Kšœœ
œ˜%Kšœœ˜=Kš
œ,˜,šœ
˜Kš
œ;˜;Kšœ˜
—K˜—K˜šž
œœ˜Kšœœ
œ˜%Kšœœ˜=Kšœœ!˜>Kš
œ*˜*Kšœ˜—K˜šžœœœ˜DKšœœ
œ˜%Kšœœ˜K˜KšŸ
œœ
˜K˜Kšœœ˜šžœœœœ˜)Kšœœœ
˜šœœ˜š
œŸ
œœœ
œ˜(KšœŸ
œœ
˜Kš
œ˜——šœ˜KšŸ
œœ'˜2Kšœ
Ÿ
œœ
œ
˜Kšœ"Ÿ
œ˜%KšœŸ
œ
Ÿ
œ˜=KšœŸ
œœ
˜Kš
œ˜—Kšœœ˜—Kšœœ˜>Kšœœ˜2Kšœ/œD˜yKšœŸ
œ
Ÿ
œ˜=Kšœœ
œ
˜$Kšœœ˜)Kšœœœ˜HKšœœœ
˜#Kšœ˜	—K˜šžœœ1œœ˜jKšœ!œ!œ
œ˜WKš
œ'˜'KšœŸ
œœ
Ÿ
œ
˜Kšœ	œ˜!K˜'Kšœ'œ	˜3Kšœœœ
˜&Kšœ+œ
˜.KšœŸ
œ
œŸ
œ
œœ˜hKšœ
œœ˜:K˜šœœ˜Kšœœ˜#KšœŸ
œœ%˜.šœŸ
œŸ
œ
œ˜šœœ
œ"˜1Kšœ
Ÿ
œŸ
œ˜"Kšœ
˜—šœ
œœ
œœ
œŸ
œŸ
œ˜WKšœ
œ
˜Kšœ
˜—K˜—šœŸ
œŸ
œ
œ˜š	œœ

œ
œ"˜<Kšœ
Ÿ
œŸ
œ˜"Kšœ
˜—šœ
œœ
œœ
œŸ
œŸ
œ˜WKšœ
œ
˜Kšœ
˜—K˜—KšœŸ
œŸ
œ
˜Kšœ˜—Kšœ
œœ
œ
œ
œœ	œ˜HKšœœ˜3Kšœœ˜#KšœŸ
œœ˜#šœœ˜Kšœœ
œœœ
œ
˜;K˜
—šœ˜Kšœœ
œŸ
œœœ
œ
˜FKšœœ
œ"œŸ
œŸ
œœ
˜\Kšœœ
œŸ
œ
œœ
œ
˜LK˜—KšœŸ
œŸ
œ
˜K˜Kšœ˜
—K˜šžœœœ˜IKšœœ
œ˜%Kš
œ#˜#Kšœœ˜K˜'Kš
œ(˜(K˜šžœœœœ˜)Kšœœœ
˜šœŸ
œœ˜Kšœœ˜3šœ
œœ˜šœ˜
K˜ K˜ Kšœœ
˜—K˜—KšœŸ
œœ
˜Kšœœ˜-—šœ˜Kšœ
œœ˜2Kšœ
œ
œœœœ˜hKšœ
œ˜—Kšœœ˜—Kšœœ˜>Kšœœ˜2Kšœœ
œ
˜$Kš
œ˜KšœœŸ
œ
Ÿ
œ%˜RKšœ7œ˜UKšœ˜—K˜šžœœœ˜JKšœœ
œ˜%Kš
œ#˜#K˜'Kšœ	œœ
˜šžœœœœ˜)Kšœœœ
˜šœŸ
œœ˜Kšœœœœ
˜:KšœŸ
œœ
˜K˜Kšœœ
˜—Kšœœ
˜Kšœœ˜—Kšœœ˜>Kšœœ˜2Kšœœ
œ
˜$Kšœ	œ˜'Kšœ˜—K˜šž	œœ˜.Kš
œ#˜#KšŸ
œœ
Ÿ
œ
˜K˜'K˜#Kšœœ
œŸ
œœ.œ
˜yKšœœ
œŸ
œœ.œ
˜yK˜Kšœœ
œœœŸ
œ
Ÿ
œ%˜Kšœ˜—K˜šžœœœ˜DKšœœ
œ˜%Kšœ"˜(—K˜šž
œœœ˜2Kšœœ
œ˜%Kšœ	˜—K˜šž
œœœœ˜=Kšœœ
œ˜%Kšœ˜—K˜šžœœ˜šœœ
œ
œ
œ
œ
œ
œ
œ
œ
œœ˜fš
œ;˜;˜Kšž	œ˜Kšžœ
˜Kšžœ
˜Kšžœ˜Kšž	œ˜Kšžœ
˜Kšžœ˜Kšžœ
˜Kšžœ˜Kšžœœœœ˜@Kšžœ˜K˜Kš
œ˜—Kšœ	œ
œ
˜K˜—Kšœ
œ
œ
˜—K˜—K˜K˜K˜Kšœ
˜—…—+†<΅