AbSets.Mesa
Last tweaked by Mike Spreitzer on January 6, 1988 4:00:29 pm PST
DIRECTORY Atom, Basics, IntStuff, PrincOps, Rope, RuntimeError, SetBasics;
AbSets: CEDAR DEFINITIONS
IMPORTS RuntimeError, SetBasics
= {OPEN SetBasics;
Some basic stuff
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: READONLY Value;
MaybeValue: TYPE ~ SetBasics.MaybeValue;
noMaybe: READONLY MaybeValue;
Space: TYPE ~ SetBasics.Space;
RelOrder: TYPE ~ SetBasics.RelOrder;
Complain: PROC [set: Set, msg: ROPE, args: LOVNIL]
~ INLINE {Error[msg, CONS[AV[NEW [Set ← set]], args]]};
R: PROC [r: ROPE] RETURNS [ROPE]
~ INLINE {RETURN [r]};
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.
Set: TYPE ~ RECORD [class: SetClass, data: Value];
Cons: PROC [class: SetClass, data: Value] RETURNS [Set];
Good for calling from the interpreter.
nilSet: Set ~ [NIL, []]; --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=nilSet]};
NotNil: PROC [set: Set] RETURNS [BOOL]
~ INLINE {RETURN [set#nilSet]};
Refify: PROC [set: Set] RETURNS [RefSet]
~ INLINE {RETURN [NEW [Set ← set]]};
DeRef: PROC [ra: REF ANY] RETURNS [Set]
DeRef[NIL]=nilSet.
~ INLINE {RETURN [IF ra#NIL THEN NARROW[ra, RefSet]^ ELSE nilSet]};
Operations on Sets
Cant: ERROR [set: Set];
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: PROC [set: Set, elt: Value] RETURNS [BOOL]
~ INLINE {RETURN [set.class.HasMember[set, elt]]};
HasMemA: PROC [set: Set, elt: REF ANY] RETURNS [BOOL]
= HasMember[elt: [a[elt]] ]
~ INLINE {RETURN [set.class.HasMember[set, AV[elt] ]]};
HasMemI: PROC [set: Set, elt: INT] RETURNS [BOOL]
= HasMember[elt: [a[elt]] ]
~ INLINE {RETURN [set.class.HasMember[set, IV[elt] ]]};
Enumerate: PROC [set: Set, Consumer: PROC [Value], ro: RelOrder ← no];
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.
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]
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.
~ INLINE {RETURN set.class.Scan[set, Test, ro]};
ParallelScan: PROC [a, b: Set, Test: ParallelTester, roA, roB: RelOrder ← no] RETURNS [ParallelFind];
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.
ParallelTester: TYPE ~ PROC [a, b: MaybeValue] RETURNS [pass: BOOLFALSE];
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]
Returns the element, if there is exactly one; Error["%g not a singleton", LIST[set]] otherwise.
~ INLINE {RETURN set.class.TheElt[set]};
notASingleton: READONLY ROPE;
GetOne: PROC [set: Set, remove: BOOL, ro: RelOrder] RETURNS [MaybeValue]
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.
~ INLINE {RETURN set.class.GetOne[set, remove, ro]};
AnElt: PROC [set: Set, ro: RelOrder ← no] RETURNS [MaybeValue]
=GetOne[remove: FALSE]
~ INLINE {RETURN set.class.GetOne[set, FALSE, ro]};
Pop: PROC [set: Set, ro: RelOrder ← no] RETURNS [MaybeValue]
=GetOne[remove: TRUE]
~ 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: BOOLTRUE];
Next: PROC [set: Set, elt: Value] RETURNS [MaybeValue]
Returns the next (according to the order of the set's space) element in the set.
~ 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]
No guarantees about unwanted results.
~ INLINE {RETURN set.class.Get3[set, elt, want]};
Size: PROC [set: Set, limit: EINT ← lastEINT] RETURNS [EINT]
Size = number of elements, or limit <= Size <= number of elements.
~ 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]
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).
~ INLINE {RETURN set.class.IsDense[set, when]};
EndBools: TYPE ~ PACKED ARRAY End OF TrueBool;
TrueBool: TYPE ~ BOOLTRUE;
GetBounds: PROC [set: Set, want: EndBools ← []] RETURNS [MaybeInterval]
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).
~ INLINE {RETURN set.class.GetBounds[set, want]};
MaybeInterval: TYPE ~ RECORD [found: BOOL, it: Interval];
Mutability: TYPE ~ {constant, readonly, variable};
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.
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]
Returns a new set variable, using same implementation, initialized to the current contents of the argument.
~ INLINE {RETURN [set.class.Copy[set]]};
Insulate: PROC [set: Set] RETURNS [UWSet]
When applied to a variable set, returns a readonly reference to that variable; otherwise returns the given set.
~ INLINE {RETURN [set.class.Insulate[set]]};
ValueOf: PROC [set: Set] RETURNS [ConstSet]
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.
~ INLINE {RETURN set.class.ValueOf[set]};
Freeze: PROC [set: Set] RETURNS [ConstSet]
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.
~ 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]
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.
~ 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[AV[elt], set.SpaceOf]].new.some};
AddI: PROC [set: Set, elt: INT] RETURNS [new: BOOL]
~ INLINE {new ← set.class.AddSet[set, CreateSingleton[IV[elt], set.SpaceOf]].new.some};
NAddElt: PROC [set: Set, elt: Value] RETURNS [new: BOOL];
A non-INLINE version, for the benefit of interpreter calling.
SomeAll: TYPE ~ RECORD [some: BOOLFALSE, all: BOOLTRUE];
AddSet: PROC [set, other: Set] RETURNS [new: SomeAll]
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.
~ 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[AV[elt], set.SpaceOf]].had.some};
RemI: PROC [set: Set, elt: INT] RETURNS [had: BOOL]
~ INLINE {had ← set.class.RemSet[set, CreateSingleton[IV[elt], set.SpaceOf]].had.some};
RemSet: PROC [set, other: Set] RETURNS [had: SomeAll]
RemSet is equivalent to a series of RemElts. Uses the current value of other.
~ INLINE {RETURN set.class.RemSet[set, other]};
Erase: PROC [set: Set]
~ INLINE {[] ← set.RemSet[set]};
SpaceOf: PROC [set: Set] RETURNS [Space]
Every Set knows its space; SpaceOf never raises Cant, and never returns NIL.
~ INLINE {RETURN set.class.SpaceOf[set]};
Equal: PROC [a, b: Set] RETURNS [BOOL];
x : x in a { x in b.
Hash: PROC [set: Set] RETURNS [CARDINAL];
Compare: PROC [a, b: Set] RETURNS [Comparison];
CreateSetSpace: PROC [eltSpace: Space] RETURNS [Space];
Result's elements are sets whose elements are in eltSpace.
QuaSetSpace: PROC [Space] RETURNS [found: BOOL, eltSpace: Space];
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.
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];
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
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]};
Some Implementations of Sets
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];
IsSingletonClass: PROC [SetClass] RETURNS [BOOL];
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];
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.
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 ANYNIL];
CreateFilter: PROC [f: FilterClosure, mutability: UnwriteableMutability ← readonly] RETURNS [Filter]
~ INLINE {RETURN [[filterClasses[mutability], AV[NEW [FilterClosure ← f]]]]};
filterClasses: READONLY ARRAY UnwriteableMutability OF SetClass;
FilterClosure: TYPE ~ RECORD [
Test: PROC [val: Value, data: REF ANYNIL] RETURNS [BOOL],
space: Space,
data: REF ANYNIL];
CreateList: PROC [vals: LOV, space: Space ← refs, mutability: Mutability ← variable, order: RelOrder ← no, assumeSorted: BOOLFALSE] RETURNS [Set];
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.
ListFromLORA: PROC [vals: LORA, space: Space ← refs, mutability: Mutability ← variable, order: RelOrder ← no, assumeSorted: BOOLFALSE] RETURNS [Set];
HashSet: TYPE ~ VarSet;
IsHash: PROC [Set] RETURNS [BOOL];
CreateHashSet: PROC [space: Space ← refs] 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 ← refs] RETURNS [HashSet];
The following use a standard implementation. The result tracks changes to the arguments, if any.
Union: PROC [a, b: Set, disjoint: BOOLFALSE, ro: RelOrder ← no] RETURNS [UWSet];
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.
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];
Implementing Sets
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,
If Primitive is omitted or returns `pass', ability is judged based on the arguments to CreateClass.
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 ANYNIL
];
The only part that may vary is the other, and that must be accessed through the update procedure below.
CreateClass: PROC [cp: SetClassPrivate, relable: Relable ← [TRUE, FALSE, FALSE]] RETURNS [SetClass];
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.
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]];
Asking About a Set's Implementation
QualityOf: PROC [set: Set, op: ATOM, arg1, arg2: REF ANYNIL] RETURNS [ImplQuality];
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.
ImplQuality: TYPE ~ {cant, poorDefault, goodDefault, primitive};
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.
Can: PROC [set: Set, op: ATOM, arg1, arg2: REF ANYNIL] RETURNS [BOOL]
~ INLINE {RETURN [QualityOf[set, op, arg1, arg2]#cant]};
GoodImpl: PROC [set: Set, op: ATOM, arg1, arg2: REF ANYNIL] RETURNS [BOOL]
~ INLINE {RETURN [QualityOf[set, op, arg1, arg2]>=goodDefault]};
Primitive: PROC [set: Set, op: ATOM, arg1, arg2: REF ANYNIL] RETURNS [BOOL];
Like QualityOf[]=primitive, except that it may only be called on class procedures, and does not think hard about what the quality is if it's not primitive.
RefSet: TYPE ~ REF Set;
RefEINT: TYPE ~ REF EINT;
RefInterval: TYPE ~ REF Interval;
ToBool: PROC [arg: REF ANY, default: BOOLFALSE] 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];
e.g., FromTB[[TRUE, FALSE, FALSE]] => $TFF
FromEB: PROC [EndBools] RETURNS [ATOM];
returns one of: $None, $Min, $Max, $Both
FromInterval: PROC [Interval] RETURNS [RefInterval];
FromWhen: PROC [w: When] RETURNS [ATOM]
~ INLINE {RETURN [IF w=now THEN $now ELSE $always]};
}.