DIRECTORY Atom, Basics, IntStuff, PrincOps, Rope, RuntimeError, SetBasics;

AbSets: CEDAR DEFINITIONS
IMPORTS RuntimeError, SetBasics
= {OPEN SetBasics;
LNAT: TYPE ~ INT--[0 .. INT.LAST]--;
EINT: TYPE ~ IntStuff.EINT;
lastEINT: EINT ~ IntStuff.lastEINT;
ROPE: TYPE ~ Rope.ROPE;
LOV: TYPE ~ LIST OF Value;
Value: TYPE ~ SetBasics.Value;
noValue: Value ~ SetBasics.noValue;
MaybeValue: TYPE ~ SetBasics.MaybeValue;
noMaybe: MaybeValue ~ SetBasics.noMaybe;
Space: TYPE ~ SetBasics.Space;
RelOrder: TYPE ~ SetBasics.RelOrder;

Complain: PROC [set: Set, msg: ROPE, args: LOV _ NIL]
~ INLINE {Error[msg, CONS[[a[NEW [Set _ set]]], args]]};

R: PROC [r: ROPE] RETURNS [ROPE]
~ INLINE {RETURN [r]};

Set: TYPE ~ RECORD [class: SetClass, data: Value];

Cons: PROC [class: SetClass, data: Value] RETURNS [Set];

nilSet: Set ~ [NIL, noValue]; --a Set that is not a set
badSet: READONLY Set;	--another Set that is not a set; will not be returned by DeRef

IsNil: PROC [set: Set] RETURNS [BOOL]
~ INLINE {RETURN [set.class=NIL AND set.data.kind=noValue.kind]};
NotNil: PROC [set: Set] RETURNS [BOOL]
~ INLINE {RETURN [set.class#NIL OR set.data.kind#noValue.kind]};

Refify: PROC [set: Set] RETURNS [RefSet]
~ INLINE {RETURN [NEW [Set _ set]]};
DeRef: PROC [ra: REF ANY] RETURNS [Set]
~ INLINE {RETURN [IF ra#NIL THEN NARROW[ra, RefSet]^ ELSE nilSet]};
Cant: ERROR [set: Set];

HasMember: PROC [set: Set, elt: Value] RETURNS [BOOL]
~ INLINE {RETURN [set.class.HasMember[set, elt]]};

HasMemA: PROC [set: Set, elt: REF ANY] RETURNS [BOOL]
~ INLINE {RETURN [set.class.HasMember[set, [a[elt]] ]]};

HasMemI: PROC [set: Set, elt: INT] RETURNS [BOOL]
~ INLINE {RETURN [set.class.HasMember[set, [i[elt]] ]]};

Enumerate: PROC [set: Set, Consumer: PROC [Value], ro: RelOrder _ no];

EnumA: PROC [set: Set, Consumer: PROC [REF ANY], ro: RelOrder _ no];
EnumI: PROC [set: Set, Consumer: PROC [INT], ro: RelOrder _ no];

Tester: TYPE ~ PROC [Value] RETURNS [BOOL];
AcceptAny: Tester--={RETURN[TRUE]}--;

Scan: PROC [set: Set, Test: Tester, ro: RelOrder _ no] RETURNS [MaybeValue]
~ INLINE {RETURN set.class.Scan[set, Test, ro]};

ParallelScan: PROC [a, b: Set, Test: ParallelTester, roA, roB: RelOrder _ no] RETURNS [ParallelFind];

ParallelTester: TYPE ~ PROC [a, b: MaybeValue] RETURNS [pass: BOOL _ FALSE];
ParallelFind: TYPE ~ RECORD [found: BOOL, a, b: MaybeValue];

InterleavedProduce: PROC [a, b: Set, Consume: InterleavedConsumer, roA, roB: RelOrder _ no] RETURNS [MaybeValue];

InterleavedConsumer: TYPE ~ PROC [PROC [Which] RETURNS [MaybeValue]] RETURNS [MaybeValue];

Which: TYPE ~ {a, b};

TheElt: PROC [set: Set] RETURNS [Value]
~ INLINE {RETURN set.class.TheElt[set]};
notASingleton: READONLY ROPE;

GetOne: PROC [set: Set, remove: BOOL, ro: RelOrder] RETURNS [MaybeValue]
~ INLINE {RETURN set.class.GetOne[set, remove, ro]};
AnElt: PROC [set: Set, ro: RelOrder _ no] RETURNS [MaybeValue]
~ INLINE {RETURN set.class.GetOne[set, FALSE, ro]};
Pop: PROC [set: Set, ro: RelOrder _ no] RETURNS [MaybeValue]
~ INLINE {RETURN set.class.GetOne[set, TRUE, ro]};
First: PROC [set: Set] RETURNS [MaybeValue]
~ INLINE {RETURN set.class.GetOne[set, FALSE, fwd]};
Last: PROC [set: Set] RETURNS [MaybeValue]
~ INLINE {RETURN set.class.GetOne[set, FALSE, bwd]};

TripleMaybeValue: TYPE ~ RECORD [prev, same, next: MaybeValue];
TripleBool: TYPE ~ RECORD [prev, same, next: BOOL _ TRUE];

Next: PROC [set: Set, elt: Value] RETURNS [MaybeValue]
~ INLINE {RETURN [set.class.Get3[set, elt, [FALSE, FALSE, TRUE]].next]};
Prev: PROC [set: Set, elt: Value] RETURNS [MaybeValue]
~ INLINE {RETURN [set.class.Get3[set, elt, [TRUE, FALSE, FALSE]].prev]};
Get3: PROC [set: Set, elt: Value, want: TripleBool _ []] RETURNS [TripleMaybeValue]
~ INLINE {RETURN set.class.Get3[set, elt, want]};

Size: PROC [set: Set, limit: EINT _ lastEINT] RETURNS [EINT]
~ INLINE {RETURN [set.class.Size[set, limit]]};

Empty: PROC [set: Set] RETURNS [BOOL]
~ INLINE {RETURN [set.class.Size[set, IntStuff.one]=IntStuff.zero]};

When: TYPE ~ {now, always};

IsDense: PROC [set: Set, when: When _ always] RETURNS [BOOL]
~ INLINE {RETURN set.class.IsDense[set, when]};

EndBools: TYPE ~ PACKED ARRAY End OF TrueBool;
TrueBool: TYPE ~ BOOL _ TRUE;

GetBounds: PROC [set: Set, want: EndBools _ []] RETURNS [MaybeInterval]
~ INLINE {RETURN set.class.GetBounds[set, want]};

MaybeInterval: TYPE ~ RECORD [found: BOOL, it: Interval];

Mutability: TYPE ~ {constant, readonly, variable};

ChangeableMutability: TYPE ~ Mutability[readonly..variable];
UnwriteableMutability: TYPE ~ Mutability[constant..readonly];

MutabilityOf: PROC [set: Set] RETURNS [Mutability]
~ INLINE {RETURN [set.class.mutability]};

Copy: PROC [set: Set] RETURNS [VarSet]
~ INLINE {RETURN [set.class.Copy[set]]};

Insulate: PROC [set: Set] RETURNS [UWSet]
~ INLINE {RETURN [set.class.Insulate[set]]};

ValueOf: PROC [set: Set] RETURNS [ConstSet]
~ INLINE {RETURN set.class.ValueOf[set]};

Freeze: PROC [set: Set] RETURNS [ConstSet]
~ INLINE {RETURN set.class.Freeze[set]};
frozen, unfrozen: READONLY ROPE;

Thaw: PROC [set: Set]
~ INLINE {set.class.Thaw[set]};

AddElt: PROC [set: Set, elt: Value] RETURNS [new: BOOL]
~ INLINE {new _ set.class.AddSet[set, CreateSingleton[elt, set.SpaceOf]].new.some};

AddA: PROC [set: Set, elt: REF ANY] RETURNS [new: BOOL]
~ INLINE {new _ set.class.AddSet[set, CreateSingleton[[a[elt]], set.SpaceOf]].new.some};

AddI: PROC [set: Set, elt: INT] RETURNS [new: BOOL]
~ INLINE {new _ set.class.AddSet[set, CreateSingleton[[i[elt]], set.SpaceOf]].new.some};

NAddElt: PROC [set: Set, elt: Value] RETURNS [new: BOOL];

SomeAll: TYPE ~ RECORD [some: BOOL _ FALSE, all: BOOL _ TRUE];

AddSet: PROC [set, other: Set] RETURNS [new: SomeAll]
~ INLINE {RETURN set.class.AddSet[set, other]};

RemElt: PROC [set: Set, elt: Value] RETURNS [had: BOOL]
~ INLINE {had _ set.class.RemSet[set, CreateSingleton[elt, set.SpaceOf]].had.some};

RemA: PROC [set: Set, elt: REF ANY] RETURNS [had: BOOL]
~ INLINE {had _ set.class.RemSet[set, CreateSingleton[[a[elt]], set.SpaceOf]].had.some};

RemI: PROC [set: Set, elt: INT] RETURNS [had: BOOL]
~ INLINE {had _ set.class.RemSet[set, CreateSingleton[[i[elt]], set.SpaceOf]].had.some};

RemSet: PROC [set, other: Set] RETURNS [had: SomeAll]
~ INLINE {RETURN set.class.RemSet[set, other]};

Erase: PROC [set: Set]
~ INLINE {[] _ set.RemSet[set]};

SpaceOf: PROC [set: Set] RETURNS [Space]
~ INLINE {RETURN set.class.SpaceOf[set]};

Equal: PROC [a, b: Set] RETURNS [BOOL];

Hash: PROC [set: Set] RETURNS [CARDINAL];

Compare: PROC [a, b: Set] RETURNS [Comparison];

CreateSetSpace: PROC [eltSpace: Space] RETURNS [Space];

QuaSetSpace: PROC [Space] RETURNS [found: BOOL, eltSpace: Space];

Side: TYPE ~ {left, right};
Direction: TYPE ~ {leftToRight, rightToLeft};

OtherDirection: ARRAY Direction OF Direction ~ [rightToLeft, leftToRight];
OtherSide: ARRAY Side OF Side ~ [right, left];
Source: ARRAY Direction OF Side ~ [left, right];
Dest: ARRAY Direction OF Side ~ [right, left];
From: ARRAY Side OF Direction ~ [leftToRight, rightToLeft];
To: ARRAY Side OF Direction ~ [rightToLeft, leftToRight];

VarSet: TYPE ~ RECORD [Set] --a variable set--;
nilVarSet: VarSet ~ [nilSet];
MaybeVarSet: TYPE ~ RECORD [found: BOOL, set: VarSet];
IsVar: PROC [set: Set] RETURNS [BOOL]
~ INLINE {RETURN [set.QuaVar.found]};
AsVar: PROC [set: Set] RETURNS [VarSet] ~ INLINE {
mv: MaybeVarSet ~ set.QuaVar;
IF NOT mv.found THEN Complain[set, notVariable];
RETURN [mv.set]};
notVariable: READONLY ROPE;
QuaVar: PROC [set: Set] RETURNS [MaybeVarSet] ~ INLINE {
IF NotNil[set] AND set.class.mutability#variable THEN RETURN [[FALSE, [badSet]]];
RETURN [[TRUE, [set]]]};

UWSet: TYPE ~ RECORD [Set] --a set that cannot be changed through this reference, although it might be changeable through some other reference; the `UW' stands for `Unwritable'--;
nilUWSet: UWSet ~ [nilSet];
MaybeUWSet: TYPE ~ RECORD [found: BOOL, set: UWSet];
IsUW: PROC [set: Set] RETURNS [BOOL]
~ INLINE {RETURN [set.QuaUW.found]};
AsUW: PROC [set: Set] RETURNS [UWSet] ~ INLINE {
mv: MaybeUWSet ~ set.QuaUW;
IF NOT mv.found THEN Complain[set, writeable];
RETURN [mv.set]};
writeable: READONLY ROPE;
QuaUW: PROC [set: Set] RETURNS [MaybeUWSet] ~ INLINE {
IF NotNil[set] AND set.class.mutability=variable THEN RETURN [[FALSE, [badSet]]];
RETURN [[TRUE, [set]]]};

ConstSet: TYPE ~ RECORD [UWSet] --a constant set  i.e., a set value, rather than a set variable--;
nilConstSet: ConstSet ~ [nilUWSet];
MaybeConstSet: TYPE ~ RECORD [found: BOOL, set: ConstSet];
IsConst: PROC [set: Set] RETURNS [BOOL]
~ INLINE {RETURN [set.QuaConst.found]};
AsConst: PROC [set: Set] RETURNS [ConstSet] ~ INLINE {
mv: MaybeConstSet ~ set.QuaConst;
IF NOT mv.found THEN Complain[set, notConstant];
RETURN [mv.set]};
notConstant: READONLY ROPE;
QuaConst: PROC [set: Set] RETURNS [MaybeConstSet] ~ INLINE {
IF NotNil[set] AND set.class.mutability#constant THEN RETURN [[FALSE, [[badSet]]]];
RETURN [[TRUE, [[set]]]]};

Filter: TYPE ~ Set;
UWFilter: TYPE ~ UWSet;
ConstFilter: TYPE ~ ConstSet;
IsFilter: PROC [set: Set] RETURNS [BOOL] ~ INLINE {RETURN [set.Can[$HasMember]]};
Enumerator: TYPE ~ Set;
IsEnumerator: PROC [set: Set] RETURNS [BOOL] ~ INLINE {RETURN [set.Can[$Enumerate]]};

QuaInterval: PROC [Set] RETURNS [MaybeInterval];

MaybeIntInterval: TYPE ~ RECORD [found: BOOL, it: IntInterval];
IsIntInterval: PROC [set: Set] RETURNS [BOOL]
~ INLINE {RETURN [set.class.QuaIntInterval[set].found]};
AsIntInterval: PROC [set: Set] RETURNS [IntInterval]
~ INLINE {
mii: MaybeIntInterval ~ set.class.QuaIntInterval[set];
IF NOT mii.found THEN RuntimeError.BoundsFault[];
RETURN [mii.it]};
QuaIntInterval: PROC [set: Set] RETURNS [MaybeIntInterval]
~ INLINE {RETURN set.class.QuaIntInterval[set]};
CreateEmptySet: PROC [Space] RETURNS [ConstSet];
CreateFullSet: PROC [Space] RETURNS [ConstSet];

CreateSingleton: PROC [elt: Value, space: Space] RETURNS [ConstSet]
~ INLINE {RETURN [[[[GetSingletonClass[space], elt]]]]};
GetSingletonClass: PROC [space: Space] RETURNS [SetClass];

NCreateSingleton: PROC [elt: Value, space: Space] RETURNS [ConstSet];

IntervalAsSet: PROC [space: Space, i: Interval] RETURNS [ConstSet];
IIAsSet: PROC [IntInterval] RETURNS [ConstSet];

CreateConditional: PROC [cond, subj: Set] RETURNS [UWSet];

CreateEnumerator: PROC [e: EnumerateClosure, mutability: UnwriteableMutability _ readonly] RETURNS [Enumerator];
EnumerateClosure: TYPE ~ RECORD [
Scan: PROC [Test: Tester, data: REF ANY] RETURNS [MaybeValue],
space: Space,
data: REF ANY _ NIL];

CreateFilter: PROC [f: FilterClosure, mutability: UnwriteableMutability _ readonly] RETURNS [Filter]
~ INLINE {RETURN [[filterClasses[mutability], [a[NEW [FilterClosure _ f]]]]]};
filterClasses: READONLY ARRAY UnwriteableMutability OF SetClass;
FilterClosure: TYPE ~ RECORD [
Test: PROC [val: Value, data: REF ANY _ NIL] RETURNS [BOOL],
space: Space,
data: REF ANY _ NIL];

CreateList: PROC [vals: LOV, space: Space _ basic, mutability: Mutability _ variable, order: RelOrder _ no, assumeSorted: BOOL _ FALSE] RETURNS [Set];

ListFromLORA: PROC [vals: LORA, space: Space _ basic, mutability: Mutability _ variable, order: RelOrder _ no, assumeSorted: BOOL _ FALSE] RETURNS [Set];

HashSet: TYPE ~ VarSet;
IsHash: PROC [Set] RETURNS [BOOL];

CreateHashSet: PROC [space: Space _ basic] RETURNS [HashSet];

CreateHashRopeSet: PROC [case: BOOL] RETURNS [HashSet]
~ INLINE {RETURN CreateHashSet[ropes[case]]};

CreateHashCopy: PROC [set: Set, space: Space _ NIL--NIL means to use the same space as the given set--] RETURNS [HashSet];

CreateHashSetFromProc: PROC [Produce: PROC [Consume: PROC [Value]], space: Space _ basic] RETURNS [HashSet];

Union: PROC [a, b: Set, disjoint: BOOL _ FALSE, ro: RelOrder _ no] RETURNS [UWSet];
Intersection: PROC [Set, Set] RETURNS [UWSet];
Difference: PROC [Set, Set] RETURNS [UWSet];
SymmetricDifference: PROC [a, b: Set] RETURNS [UWSet]
~ INLINE {RETURN Union[a.Difference[b], b.Difference[a], TRUE]};
Negate: PROC [Set] RETURNS [Set];
PrimitiveAnswer: TYPE ~ {yes, no, pass};

SetClass: TYPE ~ REF SetClassPrivate;
SetClassPrivate: TYPE ~ MONITORED RECORD [
Primitive: PROC [set: Set, op: ATOM, arg1, arg2: REF ANY] RETURNS [PrimitiveAnswer] _ NIL,
HasMember: PROC [set: Set, elt: Value] RETURNS [BOOL] _ NIL,
Scan: PROC [set: Set, Test: Tester, ro: RelOrder] RETURNS [MaybeValue] _ NIL,
TheElt: PROC [set: Set] RETURNS [Value] _ NIL,
GetOne: PROC [set: Set, remove: BOOL, ro: RelOrder] RETURNS [MaybeValue] _ NIL,
Get3: PROC [set: Set, elt: Value, want: TripleBool] RETURNS [TripleMaybeValue] _ NIL,
Size: PROC [set: Set, limit: EINT] RETURNS [EINT] _ NIL,
IsDense: PROC [set: Set, when: When] RETURNS [BOOL] _ NIL,
GetBounds: PROC [set: Set, want: EndBools] RETURNS [MaybeInterval] _ NIL,
Copy: PROC [set: Set] RETURNS [VarSet] _ NIL,
Insulate: PROC [set: Set] RETURNS [UWSet] _ NIL,
ValueOf: PROC [set: Set] RETURNS [ConstSet] _ NIL,
Freeze: PROC [set: Set] RETURNS [ConstSet] _ NIL,
Thaw: PROC [set: Set] _ NIL,
AddSet: PROC [set, other: Set] RETURNS [new: SomeAll] _ NIL,
RemSet: PROC [set, other: Set] RETURNS [had: SomeAll] _ NIL,
QuaBiRel: PROC [set: Set] RETURNS [found: BOOL, class, data: REF ANY] _ NIL,
QuaIntInterval: PROC [set: Set] RETURNS [MaybeIntInterval] _ NIL,
SpaceOf: PROC [set: Set] RETURNS [Space] _,
mutability: Mutability _ variable,
other: Atom.PropList _ NIL, --the canonical expansion slot
data: REF ANY _ NIL
];

CreateClass: PROC [cp: SetClassPrivate, relable: Relable _ [TRUE, FALSE, FALSE]] RETURNS [SetClass];

Relable: TYPE ~ ARRAY RelOrder OF BOOL;

DefaultScan: PROC [set: Set, Test: Tester, ro: RelOrder] RETURNS [MaybeValue];
DefaultGetOne: PROC [set: Set, remove: BOOL, ro: RelOrder] RETURNS [MaybeValue];
DefaultSize: PROC [set: Set, limit: EINT] RETURNS [EINT];
DefaultIsDense: PROC [set: Set, when: When] RETURNS [BOOL];
DefaultGetBounds: PROC [set: Set, want: EndBools] RETURNS [MaybeInterval];
DefaultInsulate: PROC [set: Set] RETURNS [UWSet];
DefaultQuaBiRel: PROC [set: Set] RETURNS [found: BOOL, class, data: REF ANY];
DefaultQuaIntInterval: PROC [set: Set] RETURNS [MaybeIntInterval];

SpaceBeBasic: PROC [set: Set] RETURNS [Space];
SpaceBeRopes: READONLY ARRAY --case matters--BOOL OF PROC [set: Set] RETURNS [Space];

QMin: PROC [q1, q2: ImplQuality] RETURNS [ImplQuality]
~ INLINE {RETURN[IF q1<q2 THEN q1 ELSE q2]};
QMax: PROC [q1, q2: ImplQuality] RETURNS [ImplQuality]
~ INLINE {RETURN[IF q1>q2 THEN q1 ELSE q2]};

UpdateSetClassOther: PROC [class: SetClass, Update: PROC [Atom.PropList] RETURNS [Atom.PropList]];
QualityOf: PROC [set: Set, op: ATOM, arg1, arg2: REF ANY _ NIL] RETURNS [ImplQuality];

ImplQuality: TYPE ~ {cant, poorDefault, goodDefault, primitive};

Can: PROC [set: Set, op: ATOM, arg1, arg2: REF ANY _ NIL] RETURNS [BOOL]
~ INLINE {RETURN [QualityOf[set, op, arg1, arg2]#cant]};

GoodImpl: PROC [set: Set, op: ATOM, arg1, arg2: REF ANY _ NIL] RETURNS [BOOL]
~ INLINE {RETURN [QualityOf[set, op, arg1, arg2]>=goodDefault]};

RefSet: TYPE ~ REF Set;
RefEINT: TYPE ~ REF EINT;
RefInterval: TYPE ~ REF Interval;

ToBool: PROC [arg: REF ANY, default: BOOL _ FALSE] RETURNS [BOOL];
ToRO: PROC [arg: REF ANY, default: RelOrder _ no] RETURNS [RelOrder];
ToEI: PROC [arg: REF ANY, default: RefEINT _ refLastEINT] RETURNS [RefEINT];
ToSet: PROC [arg: REF ANY] RETURNS [RefSet];
ToTB: PROC [arg: REF ANY, default: TripleBool _ []] RETURNS [TripleBool];
ToEB: PROC [arg: REF ANY, default: EndBools _ ALL[TRUE]] RETURNS [EndBools];
ToInterval: PROC [arg: REF ANY, default: RefInterval _ refFullInterval] RETURNS [RefInterval];
ToWhen: PROC [arg: REF ANY, default: When _ always] RETURNS [When];

refLastEINT: READONLY RefEINT;
refFullInterval, refAllInts: READONLY RefInterval;

FromBool: PROC [BOOL] RETURNS [ATOM];
FromRO: PROC [RelOrder] RETURNS [ATOM];
FromEI: PROC [EINT] RETURNS [RefEINT];
FakeSingleton: PROC [s: Space] RETURNS [ConstSet]
~ INLINE {RETURN CreateSingleton[noValue, s]};
FakeRefSingleton: PROC [s: Space] RETURNS [RefSet]
~ INLINE {RETURN CreateSingleton[noValue, s].Refify};
FromTB: PROC [TripleBool] RETURNS [ATOM];
FromEB: PROC [EndBools] RETURNS [ATOM];
FromInterval: PROC [Interval] RETURNS [RefInterval];
FromWhen: PROC [w: When] RETURNS [ATOM]
~ INLINE {RETURN [IF w=now THEN $now ELSE $always]};
}.
 ¶AbSets.Mesa
Last tweaked by Mike Spreitzer on December 14, 1987 11:21:50 am PST
Some basic stuff
Sets
A Set is a set of values, or a variable that ranges over sets of values.  Some Sets are able to test whether they contain a given value.  Some Sets are able to enumerate the values they contain.
Note that a Set is not a dynamically allocated object (although it may include a reference to one).  This makes it relatively cheap to make new ones.
Good for calling from the interpreter.
DeRef[NIL]=nilSet.
Operations on Sets
Raised when a Set is asked to perform an operation it can't (not because it's inappropriate, that raises Error; Cant signals that a sensible operation just isn't implemented).
= HasMember[elt: [a[elt]] ]
= HasMember[elt: [a[elt]] ]
It's valid to operate on the set from inside a Consumer, but there are no guarantees about whether elements added or deleted inside a Consumer are seen in that enumeration.
A stoppable enumeration.  The Tester returns TRUE to stop the enumeration.  If the Tester returned TRUE, Scan returns [TRUE, the value accepted]; otherwise Scan returns noMaybe.
The elements are produced in the order they would be produced by calls on Scan for the individual collections.  The tester takes MaybeValues instead of Values because one collection may run out before the other.
Returns the element, if there is exactly one; Error["%g not a singleton", LIST[set]] otherwise.
Returns, and optionally deletes, some value in the set, if it's non-empty; returns noMaybe if the set is empty.  That value is the first one that would be enumerated.
=GetOne[remove: FALSE]
=GetOne[remove: TRUE]
Returns the next (according to the order of the set's space) element in the set.
No guarantees about unwanted results.
Size = number of elements, or limit <= Size <= number of elements.
Iff you can find an x and z in the set, and a y (in the set's space but) not in the set, such that x < y < z (according to the total ordering of the space of the set), then the set is not dense.  Clients may ask about the current state of a variable, or whether the variable is ever allowed to be non-dense.  Stupid implementations may return a conservative answer (i.e., FALSE).
Returns [TRUE, extrema according to the total ordering of the space] when set non-empty; NOT result.found when set empty.  No guarantees about unwanted fields (result.found is considered unwanted when neither wantMin nor wantMax).
A variable Set represents a set variable: a variable that ranges over sets (but with fixed space, and perhaps fixed denseness).  A readonly Set is a reference to a set variable that does not give write permission to the holder (but other references to that variable might have it).  A constant Set does not represent a variable; it represents a set value.
Returns a new set variable, using same implementation, initialized to the current contents of the argument.
When applied to a variable set, returns a readonly reference to that variable; otherwise returns the given set.
When applied to a variable or readonly set, returns a constant set that is the current value of the variable and has the same implementation; otherwise returns the given (constant) set.
So what do you do when you've got a variable set you want to pass to a procecure that wants a constant one?  What if you also know that the variable is not going to vary for the duration of the call?  It would be a pain to make a copy just to satisfy the mutability checking.  So here's an alternative.  Freeze[a variable set] prohibits changes, and returns a set that is allegedly constant.  Attempts to update a frozen variable raise Error[frozen, LIST[set]].  When, if ever, the variable is thawed, attempts to use the constant set raise Error[unfrozen, LIST[const]].  Pairs of Freeze and Thaw nest like parentheses; a variable can only be changed if it is outside the scope of any Freeze...Thaw.
Union the singleton set {elt} into self; obviously applicable only to set variables.  new tells whether there was already an equivalent element in the set.
A non-INLINE version, for the benefit of interpreter calling.
Like a series of AddElts.  Uses the current value of other.  When other has two elements that are considered equal by set's space, no guarantees about new.all.
RemSet is equivalent to a series of RemElts.  Uses the current value of other.
Every Set knows its space; SpaceOf never raises Cant, and never returns NIL.
A x : x in a W x in b.
Result's elements are sets whose elements are in eltSpace.
Pair Basics
A coming attraction is sets of pairs.  A pair has two values, one on either side: left or right.  When dealing with pairs, certain operations can apply in either of two directions: left-to-right or right-to-left.
Special Cases of Sets
We can identify certain special cases of Sets based on what characteristics they have.  We could envision setting up a TYPE system that statically checks this, but that's mostly unnecessary: all the operations check at runtime whether they are being applied to reasonable arguments.  So most special cases are simply declared to be equal, as far as the Cedar type system knows, to general cases.
One exception that comes to mind is the special-casing that deals with mutability: the expectations about mutability are not clearly encoded in many calls, and thus a lot of type checking is not done at runtime.  For that reason we set up Cedar TYPE stuff to deal with it.  Note how cleverly we do it.  Because a special case is a RECORD with exactly one, unnamed, component, which is a Set, all operations applicable to Sets are also applicable to the special cases.  Even object-oriented calls continue to work.  Sadly, calls that return Sets continue to return only Sets, so you have to explicitly Qua them if you want your special case back.  C'est la vie.  The alternative formulations are worse.
Some plausible terminology:
filter <=> filter.HasMember#CantHasMember
enumerator <=> filter.Enumerate#CantEnumerate
x variable <=> x.mutability#constant
variable x <=> x.mutability=variable
unwritable x <=> x.mutability#variable
readonly x <=> x.mutability=readonly
constant x <=> x.mutability=constant
Some Implementations of Sets
result varies between being empty (when cond is empty) and being subj (when cond is not empty).  Of course, if both cond and subj are constant, the result won't actually vary.
Henceforth vals is manipulated only through the created set (so mutability=readonly doesn't make much sense, so don't use it).  List elements kept in order.
The following use a standard implementation.  The result tracks changes to the arguments, if any.
When disjoint, caller asserts that henceforth a and b have no elements in common.  When ro=fwd, caller asserts that henceforth all elements of b are greater than or equal to every element of a; similarly for ro=bwd.
Implementing Sets
If Primitive is omitted or returns `pass', ability is judged based on the arguments to CreateClass.
The only part that may vary is the other, and that must be accessed through the update procedure below.
NIL procs mean the implementor declines to implement the proc; NIL fields get filled in with default procedures that compute with provided fields.  If a class implements only one direction of a proc, it should call the default below to do the other.  The relable parameter allows CreateClass to create a reasonable Primitive if it's elided.
Asking About a Set's Implementation
Use this to investigate what operations a Set supports, and how well it does so.  The quality depends on the set, the operation, and certain arguments.  Those arguments are indicated to QualityOf as arg1 and arg2.  An enumerated value is passed by an ATOM whose name is the name of the value; an other non-ref kind of value is passed as a REF to itself.  The op is the name of a procedure in this interface (other than QualityOf and derivatives) that calls class procedures.
Arguments that are passed are: RelOrders; want: *; limit: EINT; other sets.
Arguments not passed are: Values; callback procedures; remove: BOOL.
A primitive is directly implemented by the class.  A goodDefault is no worse than a small constant factor from a primitive.  A poorDefault is worse than a goodDefault, typically by a factor of Size[set].  `cant' means Cant will be raised.
e.g., FromTB[[TRUE, FALSE, FALSE]] => $TFF
returns one of: $None, $Min, $Max, $Both
�Ê`–

"cedar" style˜
codeš
œ™K™C—K˜KšÏk	œA˜JK˜šÏnœ�œ
�˜Kš�œ˜Kšœ�œ˜—
head™Kš�œ�œ�Ïcœ
˜$Kš�œ�œ�œ
˜Kšœ
�œ˜#Kš�œ
�œ�œ
˜Kš�œ�œ�œ
�œ˜Kšœ�œ˜Kš
œ#˜#Kšœ�œ˜(Kš
œ(˜(Kšœ�œ˜Kšœ
�œ˜$K˜š
žœ�œ�œ�œ�œ
˜5Kšœ�œ
�œ�œ˜8—K˜š
ž
œ�œ�œ�œ�œ
˜ Kšœ�œ�œ˜——™Ibody™Â
MšœÏbœ™•
K˜Kšœ�œ�œ ˜2K˜šžœ�œ �œ˜8K™&—K˜Kšœ�œŸ˜7Kšœ�œŸ>˜TK˜šžœ�œ�œ�œ
˜%Kš	œ�œ�œ�œ
�œ˜A—šžœ�œ�œ�œ
˜&Kš	œ�œ�œ�œ
�œ˜@—K˜šžœ�œ�œ	˜(Kšœ�œ�œ�œ˜$—š
žœ�œ�œ
�œ�œ˜'Kšœ�œ	™Kšœ�œ�œ�œ�œ
�œ
�œ�œ
˜C——™šžœ�œ˜K™¯
—K˜šž	œ�œ�œ�œ
˜5Kšœ�œ�œ"˜2—K˜šžœ�œ�œ
�œ�œ�œ
˜5Kš
œ™Kšœ�œ�œ(˜8—K˜š
žœ�œ�œ�œ�œ
˜1Kš
œ™Kšœ�œ�œ(˜8—K˜šž	œ�œžœ�œ˜FK™¬
—K˜Kšžœ�œžœ�œ�œ
�œ˜DKš
žœ�œžœ�œ�œ˜@K˜Kš	œ�œ�œ	�œ�œ˜+Kšž	œŸœ
˜%K˜šžœ�œžœ�œ
˜KK™±
Kšœ�œ�œ ˜0—K˜šžœ�œ
žœ+�œ˜eKšœ�
Ïeœ¡œ5™Ó
—K˜Kšœ�œ�œ�œ�œ�œ˜LKšœ�œ�œ	�œ˜<K˜Kšžœ�œ
žœ0�œ˜qK˜Kšœ�œ�œ�œ	�œ�œ˜ZK˜Kšœ�œ
˜K˜šžœ�œ�œ˜'KšœJ�œ™_Kšœ�œ�œ˜(Kšœ�œ
�œ
˜—K˜šžœ�œ�œ�œ
˜HKš
œ¦
™¦
Kšœ�œ�œ$˜4—šžœ�œ�œ
˜>Kšœ�œ
™Kšœ�œ�œ�œ˜3—šžœ�œ�œ
˜<Kšœ�œ
™Kšœ�œ�œ�œ˜2—šžœ�œ�œ
˜+Kšœ�œ�œ�œ˜4—šžœ�œ�œ
˜*Kšœ�œ�œ�œ˜4—K˜Kšœ�œ�œ ˜?Kš	œ�œ�œ�œ�œ˜:K˜šžœ�œ�œ
˜6K™PKšœ�œ�œ�œ�œ�œ
˜H—šžœ�œ�œ
˜6Kšœ�œ�œ�œ�œ�œ
˜H—šžœ�œ/�œ˜SK™%Kšœ�œ�œ!˜1—K˜š
žœ�œ�œ
�œ�œ
˜<K™BKšœ�œ�œ˜/—K˜šžœ�œ�œ�œ
˜%Kšœ�œ�œ4˜D—K˜Kšœ�œ˜K˜šžœ�œ!�œ�œ
˜<K™ûKšœ�œ�œ˜/—K˜Kš	œ
�œ�œ
�œ�œ
˜.Kšœ
�œ�œ�œ
˜K˜šž	œ�œ!�œ˜GKš
œJ¡œ¡œ¡œ.¡œ%¡œ¡œ™æ
Kšœ�œ�œ!˜1—K˜Kšœ�œ�œ	�œ˜9K˜šœ�œ"˜2Kš
œã™ã—K˜Kšœ�œ"˜<Kšœ�œ"˜=K˜šžœ�œ�œ
˜2Kšœ�œ�œ˜)—K˜šžœ�œ�œ	˜&K™kKšœ�œ�œ˜(—K˜šžœ�œ�œ˜)K™oKšœ�œ�œ˜,—K˜šžœ�œ�œ˜+K™¹
Kšœ�œ�œ˜)—K˜šžœ�œ�œ˜*KšœÂ�œg�œŠ
™»Kšœ�œ�œ˜(Kšœ�œ
�œ
˜ —K˜šžœ�œ˜Kšœ�œ˜—K˜šžœ�œ�œ�œ
˜7Kšœ¡œ:¡œB™›
Kšœ�œK˜S—K˜šžœ�œ�œ
�œ�œ�œ
˜7Kšœ�œP˜X—K˜š
žœ�œ�œ�œ�œ
˜3Kšœ�œP˜X—K˜šžœ�œ�œ�œ˜9K™=—K˜Kš
œ	�œ�œ�œ�œ�œ�œ˜>K˜šžœ�œ�œ˜5Kš	œ5¡œ¡œ/¡œ¡œ
™Ÿ
Kšœ�œ�œ˜/K˜—šžœ�œ�œ�œ
˜7Kšœ�œK˜S—K˜šžœ�œ�œ
�œ�œ�œ
˜7Kšœ�œP˜X—K˜š
žœ�œ�œ�œ�œ
˜3Kšœ�œP˜X—K˜šžœ�œ�œ˜5KšœH¡œ
™NKšœ�œ�œ˜/—K˜šžœ�œ˜Kšœ�œ˜ —K˜šžœ�œ�œ˜(Kš
œL™LKšœ�œ�œ˜)—K˜šžœ�œ
�œ�œ˜'KšÏm
œ¢
œ™—K˜Kšžœ�œ�œ�œ˜)K˜Kšžœ�œ
�œ˜/K˜šžœ�œ�œ	˜7Kšœ1¡œ
™:—K˜Kšžœ�œ	�œ	�œ˜A—™MšœLÏiœY£
œ!™Ô
K˜Kšœ�œ˜Kšœ�œ˜-K˜Kšžœ�œ�œ(˜JKšž	œ�œ�œ˜.Kšžœ�œ�œ˜0Kšžœ�œ�œ˜.Kšžœ�œ�œ(˜;Kšžœ�œ�œ(˜9—™M™‹M™½™Mš
œ)™)Mš
œ-™-M™$M™$M™&Mš
œ$™$Mš
œ$™$—K˜Kšœ�œ�œŸœ
˜/Kš
œ˜Kšœ
�œ�œ	�œ˜6šžœ�œ�œ�œ
˜%Kšœ�œ�œ˜%—šžœ�œ�œ�œ˜2Kš
œ˜Kš�œ
�œ
�œ˜0Kš�œ˜Kšœ
�œ
�œ
˜—šžœ�œ�œ�œ˜8Kš
�œ
�œ�œ
�œ�œ
˜QKš�œ�œ˜—K˜Kšœ�œ�œŸ—
œ
˜³
Kš
œ˜Kšœ�œ�œ	�œ˜4šžœ�œ�œ�œ
˜$Kšœ�œ�œ˜$—šžœ�œ�œ�œ˜0Kš
œ˜Kš�œ
�œ
�œ˜.Kš�œ˜Kšœ�œ
�œ
˜—šžœ�œ�œ�œ˜6Kš
�œ
�œ�œ
�œ�œ
˜QKš�œ�œ˜—K˜Kšœ
�œ�œ	ŸBœ
˜cKš
œ#˜#Kšœ�œ�œ	�œ˜:šžœ�œ�œ�œ
˜'Kšœ�œ�œ˜'—šžœ�œ�œ�œ˜6Kš
œ!˜!Kš�œ
�œ
�œ˜0Kš�œ˜Kšœ
�œ
�œ
˜—šžœ�œ�œ�œ˜<Kš
�œ
�œ�œ
�œ�œ˜SKš�œ�œ
˜—K˜Kšœ�œ˜Kšœ
�œ	˜Kšœ
�œ˜Kšžœ�œ�œ�œ�œ�œ˜QKšœ�œ˜Kšžœ�œ�œ�œ�œ�œ˜UK˜Kšžœ�œ�œ˜0K˜Kšœ�œ�œ	�œ˜?šž
œ�œ�œ�œ
˜-Kšœ�œ�œ(˜8—šž
œ�œ�œ˜4šœ�œ˜
Kš
œ6˜6Kš�œ
�œ�œ˜1Kš�œ˜——šžœ�œ�œ˜:Kšœ�œ�œ ˜0——™Kšžœ�œ	�œ˜0Kšž
œ�œ	�œ˜/K˜šžœ�œ�œ˜CKšœ�œ�œ(˜8Kšžœ�œ�œ˜:—K˜Kšžœ�œ�œ˜EK˜Kšž
œ�œ�œ˜CKšžœ�œ�œ˜/K˜šžœ�œ�œ	˜:Kšœ(¡œ¡œ¡œ$¡œ¡œ.™¯
—K˜šžœ�œE�œ˜pšœ�œ�œ˜!Kšžœ�œžœ�œ
�œ�œ˜>K˜
Kšœ�œ
�œ�œ˜——K˜šžœ�œB�œ	˜dKšœ�œ�œ!�œ˜NKšœ�œ
�œ�œ
˜@šœ�œ�œ˜Kšžœ�œ�œ
�œ�œ�œ�œ˜<K˜
Kšœ�œ
�œ�œ˜——K˜šž
œ�œ�œ_�œ�œ�œ˜–
Kšœ¡œ‡
¡œ
™œ
—K˜Kšžœ�œ�œ_�œ�œ�œ˜™
K˜Kšœ	�œ
˜Kšžœ�œ�œ�œ˜"K˜Kšž
œ�œ�œ˜=K˜šžœ�œ�œ�œ
˜6Kšœ�œ�œ˜-—K˜Kš	žœ�œ�Ÿ4œ�œ˜zK˜Kšžœ�œžœ�œžœ�œ!�œ˜lK˜Kš
œa™aš
žœ�œ�œ�œ�œ	˜SKšœ¡œK¡œr¡œ
™×
—Kšžœ�œ�œ	˜.Kšž
œ�œ�œ	˜,šžœ�œ
�œ˜5Kšœ�œ�œ)�œ˜@—Kšžœ�œ�œ˜!—™Kšœ�œ˜(K˜Kšœ
�œ�œ˜%šœ�œ�	œ
�œ˜*šž	œ�œ�œ�œ
�œ�œ�œ
˜ZKš
œc™c—Kš
ž	œ�œ�œ�œ�œ
˜<Kš
žœ�œžœ�œ�œ
˜MKšžœ�œ�œ�œ
˜.Kš
žœ�œ�œ�œ�œ
˜OKšžœ�œ*�œ�œ
˜UKšžœ�œ�œ�œ�œ�œ
˜8Kš
žœ�œ�œ�œ�œ
˜:Kšž	œ�œ�œ�œ
˜IKšžœ�œ�œ�œ
˜-Kšžœ�œ�œ�œ
˜0Kšžœ�œ�œ�œ
˜2Kšžœ�œ�œ�œ
˜1Kšžœ�œ�œ
˜Kšžœ�œ�œ�œ
˜<Kšžœ�œ�œ�œ
˜<Kšžœ�œ�œ	�œ�œ
�œ�œ
˜LKšžœ�œ�œ�œ
˜AKšžœ�œ�œ˜+K˜"Kšœ�œŸ˜:Kšœ�œ
�œ�˜K˜Kšœ#¡œ?™g—K˜šžœ�œ+�œ�œ�œ�œ˜dKšœÿ
¡œ5¡	œ™Ô—K˜Kš	œ	�œ�œ
�œ
�œ
˜'K˜Kšžœ�œžœ�œ˜NKšž
œ�œ�œ�œ˜PKš
žœ�œ�œ�œ�œ˜9Kšžœ�œ�œ�œ˜;Kšžœ�œ�œ˜JKšžœ�œ�œ	˜1Kšžœ�œ�œ	�œ�œ
�œ˜MKšžœ�œ�œ˜BK˜Kšžœ�œ�œ	˜.Kšžœ�œ
�œ
Ÿ�œ
�œ
�œ�œ	˜UK˜šžœ�œ�œ˜6Kšœ�œ�œ
�œ�œ�œ˜,—šžœ�œ�œ˜6Kšœ�œ�œ
�œ�œ�œ˜,—K˜Kš
žœ�œžœ�œ�œ˜b—™#šž	œ�œ�œ�œ
�œ�œ�œ˜VKš
œÚ™ÚKšœ:�œ
™KKš
œD™D—K˜šœ
�œ/˜@Kš
ϔ
™î
—K˜šžœ�œ�œ�œ
�œ�œ�œ�œ
˜HKšœ�œ�œ(˜8—K˜šžœ�œ�œ�œ
�œ�œ�œ�œ
˜MKšœ�œ�œ0˜@—K˜Kšœ�œ�œ˜Kšœ	�œ�œ
�œ
˜Kšœ
�œ�œ
˜!K˜Kšžœ�œ�œ
�œ�œ�œ�œ�œ˜BKš
žœ�œ�œ
�œ�œ˜EKš
žœ�œ�œ
�œ"�œ˜LKš
žœ�œ�œ
�œ�œ
˜,Kš
žœ�œ�œ
�œ�œ˜IKšžœ�œ�œ
�œ�œ
�œ�œ˜LKš
ž
œ�œ�œ
�œ*�œ˜^Kš
žœ�œ�œ
�œ�œ˜CK˜Kšœ
�œ	˜Kšœ�œ
˜2K˜Kš
žœ�œ�œ�œ�œ˜%Kšžœ�œ�œ�œ˜'Kšžœ�œ�œ�œ˜&šž
œ�œ�œ˜1Kšœ�œ�œ˜.—šžœ�œ�œ	˜2Kšœ�œ�œ%˜5—šžœ�œ�œ�œ˜)Kšœ�œ�œ�œ
™*—šžœ�œ�œ�œ˜'K™(—Kšžœ�œ�œ˜4šžœ�œ�œ�œ
˜'Kšœ�œ�œ�œ�œ�œ˜4——L˜—…—?DyZ