SetsByVectors.Mesa
Last tweaked by Mike Spreitzer on February 27, 1988 3:06:22 pm PST
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];
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.
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 new
D > old
D
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-new
D .. oldBounds.max-old
D]
DO
oldVals[i] ← FALSE;
ENDLOOP;
};
IF new
D < old
D
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-old
D .. oldBounds.min-new
D)
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.