[Cyan]<CedarChest7.0>SetsAndStuff>Collections.Mesa!5

Collections.Mesa

Last tweaked by Mike Spreitzer on October 19, 1987 1:43:50 pm PDT

DIRECTORY Atom, Basics, PrincOps, Rope;

Collections: CEDAR DEFINITIONS IMPORTS Basics = {

Some basic stuff

LNAT: TYPE ~ INT--[0 .. INT.LAST]--;

ROPE: TYPE ~ Rope.ROPE;

LOV: TYPE ~ LIST OF Value;

Error: ERROR [msg: ROPE, args: LOV];

For random objections to calls.

Complain: PROC [coll: Collection, msg: ROPE, args: LOV ← NIL]

~ INLINE {Error[msg, CONS[NEW [Collection ← coll], args]]};

Values

A value is represented by a REF ANY. But the value is not necessarily the address in the REF — it might be something represented by the referent. For example, some values might be character sequences, represented by ROPEs. Note also that not every Value is a valid representation of a value in every Space. For example, a REF INT, although a REF ANY, is not usable as a value in a space of ROPEs. One particular Value, `noValue', is exceptional in all spaces. It does not represent a value in any space, but rather the fact that no value is suitable for whatever purpose it is being put to. `noValue' is not NIL. It is a REF to a NoValuePrivate. This TYPE is publicized so you can put an arm recognizing it in a WITH .. SELECT.

A MaybeValue is used for the result of an opreation that might yield a value, or might not. When found=FALSE, the val is noValue.

Value: TYPE ~ REF ANY;

noValue: READONLY NoValue;

NoValue: TYPE ~ REF NoValuePrivate;

NoValuePrivate: TYPE ~ RECORD [];

MaybeValue: TYPE ~ RECORD [found: BOOL, val: Value];

noMaybe: READONLY MaybeValue -- = [FALSE, noValue]--;

Val: PROC [mv: MaybeValue] RETURNS [Value]

~ INLINE {RETURN [IF mv.found THEN mv.val ELSE Error[notFound, NIL]]};

notFound: READONLY ROPE;

DVal: PROC [mv: MaybeValue, ifNotFound: Value ← NIL] RETURNS [Value]

~ INLINE {RETURN [IF mv.found THEN mv.val ELSE ifNotFound]};

Spaces

A Space tells how to interpret REF ANYs as `value's. All spaces implement equality testing. Some Spaces might also implement hashing and/or ordering.

Space: TYPE ~ REF SpacePrivate;

refs, refInts, refColls: READONLY Space;

ropes: READONLY ARRAY --case matters--BOOL OF Space;

SpaceEqual: PROC [space: Space, elt1, elt2: Value] RETURNS [BOOL]

~ INLINE {RETURN [elt1=elt2 OR space.Equal#NIL AND space.Equal[space.data, elt1, elt2]]};

SpaceHash: PROC [space: Space, elt: Value] RETURNS [CARDINAL]

~ INLINE {RETURN [IF space.Hash#NIL THEN space.Hash[space.data, elt] ELSE HashRefI[elt]]};

SpaceCompare: PROC [space: Space, elt1, elt2: Value] RETURNS [Basics.Comparison]

~ INLINE {RETURN [IF space.Compare#NIL THEN space.Compare[space.data, elt1, elt2] ELSE CompareRefI[elt1, elt2]]};

Collections

A Collection is a collection of values, or a variable that ranges over collections of values. Some Collections may contain a given value more than once. Some Collections are able to test whether they contain a given value. Some Collections are able to enumerate the values they contain.

Note that a Collection is not a dynamically allocated object (although it may include a reference to one). This makes it relatively cheap to make new ones.

Collection: TYPE ~ RECORD [class: CollectionClass, data: REF ANY];

Cons: PROC [class: CollectionClass, data: REF ANY] RETURNS [Collection];

Good for calling from the interpreter.

nilColl: Collection ~ [NIL, NIL]; --a Collection that is not a collection

badColl: Collection; --another Collection that is not a collection; will not be returned by DeRef

Refify: PROC [coll: Collection] RETURNS [ref: REF ANY]

~ INLINE {ref ← NEW [Collection ← coll]};

DeRef: PROC [ra: REF ANY] RETURNS [Collection]

DeRef[NIL]=nilColl.

~ INLINE {RETURN [IF ra#NIL THEN NARROW[ra, REF Collection]^ ELSE nilColl]};

Operations on Collections

Cant: ERROR [coll: Collection];

Raised when a collection 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).

QualityOf: PROC [coll: Collection, op: ATOM, args: ArgList ← NIL] RETURNS [ImplQuality];

Use this to investigate what operations a collection supports, and how well it does so. The quality depends on the collection, the operation, and certain arguments. Those arguments are the Direction, the bkwds: BOOL, or the remove: BOOL, if any. They are indicated to QualityOf as a LIST OF REF ANY, where each REF ANY is an ATOM whose name is the name of the enumerated value (e.g., $leftToRight, $FALSE). The op is the name of a procedure in this interface (other than QualityOf and derivatives) that calls class procedures.

ArgList: TYPE ~ LIST OF REF ANY;

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[coll]. `cant' means Cant will be raised (except for the cases of SpaceOf and OrderingOf, wherein a nil value will be returned).

GetBool: PROC [args: ArgList, i: NAT, default: BOOL ← FALSE] RETURNS [BOOL];

args.first ~ i=1

GetDir: PROC [args: ArgList, i: NAT, default: Direction ← leftToRight] RETURNS [Direction];

FromBool: PROC [BOOL] RETURNS [ATOM];

FromDir: PROC [Direction] RETURNS [ATOM];

Can: PROC [coll: Collection, op: ATOM, args: ArgList ← NIL] RETURNS [BOOL]

~ INLINE {RETURN [QualityOf[coll, op, args]#cant]};

HasMember: PROC [coll: Collection, elt: Value] RETURNS [BOOL]

~ INLINE {RETURN [coll.class.HasMember[coll, elt]]};

OrderStyle: TYPE ~ {none, client, value};

Every collection is either ordered or unordered. An ordered collection considers its elements to be arranged in some order; an unordered collection does not. An ordered collection is either client-ordered or value-ordered. In a value-ordered collection, the order is determined solely by an Ordering among the elements. In a client-ordered collection, the order is determined by information (other than the elements) the client passes when creating or changing the collection.

OrderStyleOf: PROC [coll: Collection] RETURNS [OrderStyle]

~ INLINE {RETURN [coll.class.orderStyle]};

Ordering: TYPE ~ RECORD [Compare: CompareProc, data: REF ANY];

unordered: Ordering ~ [NIL, NIL];

An ordering is a closure that reveals the ordering relation between two values (in the same Space). unordered is an Ordering that isn't really an ordering.

ReverseOrdering: PROC [o: Ordering] RETURNS [ro: Ordering];

If o says a before b, ro says b before a.

ComposeOrderings: PROC [mso, lso: Ordering] RETURNS [Ordering];

If mso (most significant ordering) doesn't say equal, that's it; otherwise consult lso.

OrderingList: TYPE ~ LIST OF Ordering;

LexOrdering: PROC [prefix, repeat: OrderingList] RETURNS [Ordering];

Returns an ordering on LOVs. The first elements are compared with prefix.first; if not equal, that's it. Otherwise the second elements are compared with prefix.rest.first; if not equal, that's it. Otherwise continue, until either prefix or one of the LOVs is exhausted. If one of the LOVs is exhausted, return: equal if the other is, less or greater if the other isn't (dependening on whether the empty one was the first or second argument). If prefix is exhausted before both lists, pick up with repeat. If repeat is exhausted before both lists, use it over again.

SpaceOrdering: PROC [space: Space] RETURNS [Ordering];

OrderingOf: PROC [coll: Collection] RETURNS [Ordering]

Only meaningful for value-ordered collections.

~ INLINE {RETURN coll.class.OrderingOf[coll]};

Enumerate: PROC [coll: Collection, Consumer: PROC [Value], bkwd: BOOL ← FALSE]

Passing bkwd~TRUE means to enumerate the elements in the opposite order from what would happen if bkwd~FALSE this call; some collections don't implement this, and raise Cant.

It's valid to operate on the collection from inside a Consumer, but there are no guarantees about whether elements added or deleted inside a Consumer are seen in that enumeration.

~ INLINE {coll.class.Enumerate[coll, Consumer, bkwd]};

PreserveValue: PROC [coll: Collection, val: Value] RETURNS [preserved: Value]

Note that the Consumer passed to Enumerate gets a REF ANY to indicate the value being enumerated. Now, since a REF ANY is, in general, a reference to a variable, that variable could vary; and that might mean a change of the value represented by that REF ANY. Now, for this enumeration mechanism to make any sense at all, that can't happen for the duration of any call on Consumer; but what about after Consumer returns? Another way to ask this is, is it valid for the Consumer to store the REF ANY somewhere for use after it returns? Let us say that it is not, in general. However, for the Consumer that simply must save a value for later use, we provide the PreserveValue procedure, which produces a REF ANY that will never change which value it represents. Of course, for many Collections this will not be an issue, and PreserveValue will return the same REF ANY it is given.

~ INLINE {RETURN [IF coll.class.PreserveValue=NIL THEN val ELSE coll.class.PreserveValue[coll, val]]};

Tester: TYPE ~ PROC [val: Value] RETURNS [pass: BOOL ← FALSE];

Scan: PROC [coll: Collection, Test: Tester, bkwd: BOOL ← FALSE] RETURNS [MaybeValue]

A stoppable enumeration.

~ INLINE {RETURN coll.class.Scan[coll, Test, bkwd]};

ParallelTester: TYPE ~ PROC [a, b: MaybeValue] RETURNS [pass: BOOL ← FALSE];

ParallelScan: PROC [a, b: Collection, Test: ParallelTester, bkwd: BOOL ← FALSE] 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.

ParallelFind: TYPE ~ RECORD [found: BOOL, a, b: MaybeValue];

TheElt: PROC [coll: Collection] RETURNS [Value]

Returns the element, if there is exactly one; Error["%g not a singleton", LIST[coll]] otherwise.

~ INLINE {RETURN coll.class.TheElt[coll]};

notASingleton: READONLY ROPE;

First: PROC [coll: Collection] RETURNS [MaybeValue]

Returns the first Value that Enumerate would enumerate, or noMaybe if coll is empty.

~ INLINE {RETURN coll.class.Extremum[coll, FALSE, FALSE]};

Last: PROC [coll: Collection] RETURNS [MaybeValue]

~ INLINE {RETURN coll.class.Extremum[coll, TRUE, FALSE]};

Pop: PROC [coll: Collection, bkwd: BOOL ← FALSE] RETURNS [MaybeValue]

Returns and removes the first or last Value that Enumerate would enumerate, or noMaybe if coll is empty.

~ INLINE {RETURN coll.class.Extremum[coll, bkwd, TRUE]};

Extremum: PROC [coll: Collection, bkwd, remove: BOOL] RETURNS [MaybeValue]

~ INLINE {RETURN coll.class.Extremum[coll, bkwd, remove]};

Next: PROC [coll: Collection, elt: Value] RETURNS [MaybeValue]

Returns first the Value, not equal to elt, that would follow some instance of elt in enumeration, or noMaybe if all instances of elt are at the end. Ordered collections can do this even if elt is not in them; an unordered collection will raise Error["%g not in %g", LIST[elt, coll]].

~ INLINE {RETURN [coll.class.Get3[coll, elt].next]};

Prev: PROC [coll: Collection, elt: Value] RETURNS [MaybeValue]

~ INLINE {RETURN [coll.class.Get3[coll, elt].prev]};

Get3: PROC [coll: Collection, elt: Value] RETURNS [prev, same, next: MaybeValue]

equivalent to [coll.Prev[elt], IF coll.HasMember[elt] THEN [TRUE, elt] ELSE noMaybe, coll.Next[elt]].

~ INLINE {RETURN coll.class.Get3[coll, elt]};

Size: PROC [coll: Collection, limit: LNAT ← LNAT.LAST] RETURNS [LNAT]

Size = number of elements, or limit <= Size <= number of elements.

~ INLINE {RETURN [coll.class.Size[coll, limit]]};

Empty: PROC [coll: Collection] RETURNS [BOOL]

~ INLINE {RETURN [coll.class.Size[coll, 1]=0]};

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

A variable collection represents a collection variable: a variable that ranges over collections (but with fixed space, duplicity, and ordering). A readonly collection is a reference to a collection variable that does not give write permission to the holder (but other references to that variable might have it). A constant collection does not represent a variable; it represents a collection value.

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

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

MutabilityOf: PROC [coll: Collection] RETURNS [Mutability]

~ INLINE {RETURN [coll.class.mutability]};

Copy: PROC [coll: Collection] RETURNS [VarColl]

Returns a new collection variable, initialized to the current contents of the argument.

~ INLINE {RETURN [coll.class.Copy[coll]]};

Insulate: PROC [coll: Collection] RETURNS [UWColl]

When applied to a variable collection, returns a readonly reference to that variable; otherwise returns the given collection.

~ INLINE {RETURN [coll.class.Insulate[coll]]};

ValueOf: PROC [coll: Collection] RETURNS [ConstColl]

When applied to a variable or readonly collection, returns a constant collection that is the current value of the variable; otherwise returns the given (constant) collection.

~ INLINE {RETURN [coll.class.ValueOf[coll]]};

Freeze: PROC [coll: Collection] RETURNS [const: ConstColl]

So what do you do when you've got a variable collection 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 collection] prohibits changes, and returns a collection that is allegedly constant. Attempts to update a frozen variable raise Error[frozen, LIST[coll]]. When, if ever, the variable is thawed, attempts to use the constant collection 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 coll.class.Freeze[coll]};

frozen, unfrozen: READONLY ROPE;

Thaw: PROC [coll: Collection]

~ INLINE {coll.class.Thaw[coll]};

WhereKind: TYPE ~ {any, end, rel};

End: TYPE ~ {front, back};

WhereReln: TYPE ~ {before, after};

Where: TYPE ~ RECORD [SELECT kind: WhereKind FROM

any => [],

end => [end: End],

rel => [elt: Value, reln: WhereReln],

ENDCASE ← any[]];

AddElt: PROC [coll: Collection, elt: Value, where: Where ← []] RETURNS [new: BOOL]

For non-client-ordered collections, where must be [any[]], which means the client is not restricting where the element goes in the collection (if that even makes sense).

AddElt does not change whether a collection MayDuplicate. For non-duplicating collections, it is union with the singleton set {elt}. For duplicating ones, it adds a new occurrence of elt.

For non-duplicating collections, new tells whether there was already an equivalent element in the collection; for duplicating ones, new can be anything.

~ INLINE {[new, new] ← coll.class.AddColl[coll, CreateSingleton[elt, coll.SpaceOf], where]};

NAddElt: PROC [coll: Collection, elt: Value, where: Where ← []] RETURNS [new: BOOL];

A non-INLINE version, for the benefit of interpreter calling.

AddColl: PROC [coll, other: Collection, where: Where ← []] RETURNS [someNew, allNew: BOOL]

Like a series of AddElts. If coll is client-ordered, the elements of other appear together in the order they would come from Enumerate.

~ INLINE {RETURN coll.class.AddColl[coll, other, where]};

RemoveStyle: TYPE ~ {any--don't care--, one, first, last, all};

When removing an element from a duplicating collection, the question arises: do you mean to remove every occurence, or just one? Which one?

RemoveElt: PROC [coll: Collection, elt: Value, style: RemoveStyle ← any] RETURNS [had: BOOL]

~ INLINE {[had, had] ← coll.class.RemoveColl[coll, CreateSingleton[elt, coll.SpaceOf], style]};

RemoveColl: PROC [coll, other: Collection, style: RemoveStyle ← any] RETURNS [hadSome, hadAll: BOOL]

RemoveColl is equivalent to a series of RemoveElts. Thus, when style is one, first, or last, and coll is duplicating, other must be able to enumerate (so we know how many instances of a member of other to delete); otherwise either being able to enumerate or test membership suffices.

~ INLINE {RETURN coll.class.RemoveColl[coll, other, style]};

Erase: PROC [coll: Collection]

~ INLINE {[] ← coll.RemoveColl[coll]};

SpaceOf: PROC [coll: Collection] RETURNS [Space]

A collection is allowed to not know its space (in which case this proc returns NIL) if it doesn't need to know in order to implement the operations it implements.

~ INLINE {RETURN coll.class.SpaceOf[coll]};

MayDuplicate: PROC [coll: Collection] RETURNS [BOOL]

Might this collection enumerate equal elements twice? Uninteresting, and unspecified, for collections that don't enumerate.

~ INLINE {RETURN [coll.class.mayDuplicate]};

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

If a and b may not duplicate, x : x in a { x in b; if they may, i : a[i] = b[i].

Hash: PROC [coll: Collection] RETURNS [CARDINAL];

Compare: PROC [a, b: Collection] RETURNS [Basics.Comparison];

Pair Basics

A coming attraction is collections 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];

BoolPair: TYPE ~ PACKED ARRAY Direction OF BOOL;

ReverseBoolPair: PROC [x: BoolPair] RETURNS [BoolPair]

~ INLINE {RETURN [[x[rightToLeft], x[leftToRight]]]};

Special Cases of Collections

We can identify certain special cases of Collections 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 Collection, all operations applicable to Collections are also applicable to the special cases. Even object-oriented calls continue to work. Sadly, calls that return Collections continue to return only Collections, so you have to explicitly Qua them if you want your special case back. C'est la vie. The alternative formulations are worse.

You might think that special-casing on duplicity should go like that for mutability, and you'd even be essentially right. But note that programmers are less likely to make mistakes with duplicity. Note also that we'd actually have to special-case in both dimensions, making a big mess that couldn't inherit along both dimensions.

Some plausible terminology:

filter <=> filter.HasMember#CantHasMember

enumerator <=> filter.Enumerate#CantEnumerate

setlike x <=> x.mayDuplicate=FALSE

set <=> setlike enumerator & filter

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

ordered x <=> Ordered[x]

unordered x <=> NOT Ordered[x]

VarColl: TYPE ~ RECORD [Collection] --a variable collection--;

nilVarColl: VarColl ~ [nilColl];

MaybeVarColl: TYPE ~ RECORD [found: BOOL, coll: VarColl];

IsVar: PROC [coll: Collection] RETURNS [BOOL]

~ INLINE {RETURN [coll.QuaVar.found]};

AsVar: PROC [coll: Collection] RETURNS [VarColl] ~ INLINE {

mv: MaybeVarColl ~ coll.QuaVar;

IF NOT mv.found THEN Complain[coll, notVariable];

RETURN [mv.coll]};

notVariable: READONLY ROPE;

QuaVar: PROC [coll: Collection] RETURNS [MaybeVarColl] ~ INLINE {

IF coll#nilColl AND coll.class.mutability#variable THEN RETURN [[FALSE, [badColl]]];

RETURN [[TRUE, [coll]]]};

UWColl: TYPE ~ RECORD [Collection] --a collection that cannot be changed through this reference, although it might be changeable through some other reference; the `UW' stands for `Unwritable'--;

nilUWColl: UWColl ~ [nilColl];

MaybeUWColl: TYPE ~ RECORD [found: BOOL, coll: UWColl];

IsUW: PROC [coll: Collection] RETURNS [BOOL]

~ INLINE {RETURN [coll.QuaUW.found]};

AsUW: PROC [coll: Collection] RETURNS [UWColl] ~ INLINE {

mv: MaybeUWColl ~ coll.QuaUW;

IF NOT mv.found THEN Complain[coll, writeable];

RETURN [mv.coll]};

writeable: READONLY ROPE;

QuaUW: PROC [coll: Collection] RETURNS [MaybeUWColl] ~ INLINE {

IF coll#nilColl AND coll.class.mutability=variable THEN RETURN [[FALSE, [badColl]]];

RETURN [[TRUE, [coll]]]};

ConstColl: TYPE ~ RECORD [UWColl] --a constant collection — i.e., a collection value, rather than a collection variable--;

nilConstColl: ConstColl ~ [nilUWColl];

MaybeConstColl: TYPE ~ RECORD [found: BOOL, coll: ConstColl];

IsConst: PROC [coll: Collection] RETURNS [BOOL]

~ INLINE {RETURN [coll.QuaConst.found]};

AsConst: PROC [coll: Collection] RETURNS [ConstColl] ~ INLINE {

mv: MaybeConstColl ~ coll.QuaConst;

IF NOT mv.found THEN Complain[coll, notConstant];

RETURN [mv.coll]};

notConstant: READONLY ROPE;

QuaConst: PROC [coll: Collection] RETURNS [MaybeConstColl] ~ INLINE {

IF coll#nilColl AND coll.class.mutability#constant THEN RETURN [[FALSE, [[badColl]]]];

RETURN [[TRUE, [[coll]]]]};

Setlike: TYPE ~ Collection;

IsSetlike: PROC [coll: Collection] RETURNS [BOOL] ~ INLINE {RETURN [coll.class.mayDuplicate=FALSE]};

Filter: TYPE ~ Collection;

UWFilter: TYPE ~ UWColl;

ConstFilter: TYPE ~ ConstColl;

IsFilter: PROC [coll: Collection] RETURNS [BOOL] ~ INLINE {RETURN [coll.Can[$HasMember]]};

Enumerator: TYPE ~ Collection;

IsEnumerator: PROC [coll: Collection] RETURNS [BOOL] ~ INLINE {RETURN [coll.Can[$Enumerate]]};

Set: TYPE ~ Collection;

VarSet: TYPE ~ VarColl;

UWSet: TYPE ~ UWColl;

ConstSet: TYPE ~ ConstColl;

nilSet: Set ~ nilColl;

nilVarSet: VarSet ~ nilVarColl;

nilUWSet: UWSet ~ nilUWColl;

nilConstSet: ConstSet ~ nilConstColl;

MaybeSet: TYPE ~ RECORD [found: BOOL, coll: Set];

IsSet: PROC [coll: Collection] RETURNS [BOOL]

~ INLINE {RETURN [coll.QuaSet.found]};

AsSet: PROC [coll: Collection] RETURNS [Set]

~ INLINE {RETURN [coll.QuaSet.coll]};

QuaSet: PROC [coll: Collection] RETURNS [MaybeSet] ~ INLINE {

IF coll.class.mayDuplicate OR NOT coll.Can[$HasMember] OR NOT coll.Can[$Enumerate] THEN RETURN [[FALSE, badColl]];

RETURN [[TRUE, coll]]};

IsPairColl: PROC [coll: Collection] RETURNS [BOOL]

~ INLINE {RETURN [QuaPairColl[coll].found]};

AsPairColl: PROC [coll: Collection] RETURNS [REF ANY]

~ INLINE {RETURN [QuaPairColl[coll].val]};

QuaPairColl: PROC [coll: Collection] RETURNS [MaybeValue]

Returns found iff the collection is a collection of pairs. Since we can't mention PairColl in this interface, you get a REF to it in the val.

~ INLINE {RETURN coll.class.QuaPairColl[coll]};

IsIntFn: PROC [coll: Collection, dir: Direction ← leftToRight] RETURNS [BOOL]

~ INLINE {RETURN [QuaIntFn[coll].found]};

AsIntFn: PROC [coll: Collection, dir: Direction ← leftToRight] RETURNS [REF ANY]

~ INLINE {RETURN [QuaIntFn[coll].val]};

QuaIntFn: PROC [coll: Collection, dir: Direction ← leftToRight] RETURNS [MaybeValue]

~ INLINE {RETURN coll.class.QuaIntFn[coll, dir]};

Some Implementations of Collections

emptySet: READONLY ConstSet;

passAll: READONLY ConstFilter;

CreateSingleton: PROC [elt: Value, space: Space] RETURNS [ConstSet]

~ INLINE {RETURN [[[[GetSingletonClass[space], elt]]]]};

GetSingletonClass: PROC [space: Space] RETURNS [CollectionClass];

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

CreateEnumerator: PROC [e: EnumerateClosure, mayDuplicate: BOOL ← TRUE, orderStyle: OrderStyle ← none, mutability: UnwriteableMutability ← readonly] RETURNS [Enumerator];

EnumerateClosure: TYPE ~ RECORD [

Enumerate: PROC [Consume: PROC [val: Value], data: REF ANY],

space: Space,

Preserve: PROC [val: Value, data: REF ANY] RETURNS [Value] ← NIL,

data: REF ANY ← NIL];

CreateFilter: PROC [f: FilterClosure, mutability: UnwriteableMutability ← readonly] RETURNS [Filter]

~ INLINE {RETURN [[filterClasses[mutability], NEW [FilterClosure ← f]]]};

filterClasses: READONLY ARRAY UnwriteableMutability OF CollectionClass;

FilterClosure: TYPE ~ RECORD [

Test: PROC [val: Value, data: REF ANY ← NIL] RETURNS [BOOL],

space: Space,

data: REF ANY ← NIL];

CreateConditional: PROC [cond: Condition, coll: Collection] RETURNS [UWColl];

Condition: TYPE ~ REF ConditionPrivate;

ConditionPrivate: TYPE ~ RECORD [

EvalMe: PROC [data: REF ANY] RETURNS [BOOL],

data: REF ANY ← NIL

];

Eval: PROC [cond: Condition] RETURNS [BOOL]

~ INLINE {RETURN cond.EvalMe[cond.data]};

CreateList: PROC [vals: LOV, space: Space ← refs, mayDuplicate: BOOL ← TRUE, mutability: Mutability ← variable, orderStyle: OrderStyle ← client, ordering: Ordering ← unordered] RETURNS [Collection];

Henceforth vals is manipulated only through the created collection (so mutability=readonly doesn't make much sense, so don't use it).

HashSet: TYPE ~ VarSet;

IsHash: PROC [Collection] RETURNS [BOOL];

CreateHashSet: PROC [space: Space ← refs] RETURNS [HashSet];

CreateHashRopeSet: PROC [case: BOOL] RETURNS [HashSet]

~ INLINE {RETURN CreateHashSet[ropes[case]]};

CreateHashCopy: PROC [coll: Collection, space: Space ← NIL--NIL means to use the same space as the given collection--] RETURNS [HashSet];

CreateHashSetFromProc: PROC [Produce: PROC [Consume: PROC [Value]], space: Space ← refs] RETURNS [HashSet];

RedBlackSet: TYPE ~ VarSet;

CreateRedBlackSet: PROC [space: Space ← refs] RETURNS [RedBlackSet];

CreateRedBlackCopy: PROC [coll: Collection, space: Space ← NIL--NIL means to use the same space as the given collection--] RETURNS [RedBlackSet];

The following use a standard implementation. The result tracks changes to the arguments, if any. Result may duplicate iff any argument may.

Union: PROC [a, b: Collection] RETURNS [Collection];

DisjointUnion: PROC [a, b: Collection] RETURNS [Set];

Assumes arguments have no elements in common.

Intersection: PROC [Collection, Collection] RETURNS [Collection];

Difference: PROC [Collection, Collection] RETURNS [Collection];

SymmetricDifference: PROC [a, b: Collection] RETURNS [c: Collection]

~ INLINE {RETURN [Union[a.Difference[b], b.Difference[a]]]};

Negate: PROC [Collection] RETURNS [Collection];

Implementing Collections

PrimitiveAnswer: TYPE ~ {yes, no, pass};

CollectionClass: TYPE ~ REF CollectionClassPrivate;

CollectionClassPrivate: TYPE ~ MONITORED RECORD [

Primitive: PROC [coll: Collection, op: ATOM, args: ArgList] RETURNS [PrimitiveAnswer] ← NIL,

If Primitive is omitted or returns `pass', ability is judged based on the arguments to CreateClass.

HasMember: PROC [coll: Collection, elt: Value] RETURNS [BOOL] ← NIL,

Enumerate: PROC [coll: Collection, Consumer: PROC [elt: Value], bkwd: BOOL] ← NIL,

Scan: PROC [coll: Collection, Test: Tester, bkwd: BOOL] RETURNS [MaybeValue] ← NIL,

TheElt: PROC [coll: Collection] RETURNS [Value] ← NIL,

Extremum: PROC [coll: Collection, bkwd, remove: BOOL] RETURNS [MaybeValue] ← NIL,

Get3: PROC [coll: Collection, elt: Value] RETURNS [prev, same, next: MaybeValue] ← NIL,

Size: PROC [coll: Collection, limit: LNAT ← LNAT.LAST] RETURNS [LNAT] ← NIL,

Copy: PROC [coll: Collection] RETURNS [VarColl] ← NIL,

Insulate: PROC [coll: Collection] RETURNS [UWColl] ← NIL,

ValueOf: PROC [coll: Collection] RETURNS [ConstColl] ← NIL,

Freeze: PROC [coll: Collection] RETURNS [const: ConstColl] ← NIL,

Thaw: PROC [coll: Collection] ← NIL,

AddColl: PROC [coll, other: Collection, where: Where] RETURNS [someNew, allNew: BOOL] ← NIL,

RemoveColl: PROC [coll, other: Collection, style: RemoveStyle] RETURNS [hadSome, hadAll: BOOL] ← NIL,

QuaPairColl: PROC [coll: Collection] RETURNS [MaybeValue] ← NIL,

QuaIntFn: PROC [coll: Collection, dir: Direction] RETURNS [MaybeValue] ← NIL,

SpaceOf: PROC [coll: Collection] RETURNS [Space] ← NIL,

OrderingOf: PROC [coll: Collection] RETURNS [Ordering] ← NIL,

PreserveValue: PROC [coll: Collection, val: Value] RETURNS [Value] ← NIL,

mayDuplicate: BOOL ← TRUE,

orderStyle: OrderStyle ← none,

mutability: Mutability ← variable,

other: Atom.PropList ← NIL, --the canonical expansion slot

data: REF ANY ← NIL

];

The only part that may vary is the other, and that must be accessed through the update procedure below.

CreateClass: PROC

[cp: CollectionClassPrivate,

bkwdable: BB ← [TRUE, FALSE],

dirable: BoolPair ← [TRUE, TRUE]]

RETURNS [CollectionClass];

NIL procs mean the implementor declines to implement the proc; NIL fields get filled in with default procedures that compute with provided fields. (The exception is PreserveValue, where NIL means the trivial implementation.) If a class implements only one direction of a proc, it should call the default below to do the other. The bkwdable and dirable parameters allows CreateClass to create a reasonable Primitive if it's elided.

BB: TYPE ~ ARRAY --bkwd--BOOL OF BOOL;

DefaultEnumerate: PROC [coll: Collection, Consumer: PROC [elt: Value], bkwd: BOOL];

DefaultScan: PROC [coll: Collection, Test: Tester, bkwd: BOOL] RETURNS [mv: MaybeValue ← noMaybe];

DefaultExtremum: PROC [coll: Collection, bkwd, remove: BOOL] RETURNS [mv: MaybeValue];

DefaultQuaPairColl: PROC [coll: Collection] RETURNS [MaybeValue];

DefaultQuaIntFn: PROC [coll: Collection, dir: Direction] RETURNS [MaybeValue];

SpaceBeRefs, DontKnowSpace: PROC [coll: Collection] RETURNS [Space];

SpaceBeRopes: READONLY ARRAY --case matters--BOOL OF PROC [coll: Collection] RETURNS [Space];

BeOrderedBySpace: PROC [coll: Collection] RETURNS [Ordering];

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]};

UpdateCollectionClassOther: PROC [class: CollectionClass, Update: PROC [Atom.PropList] RETURNS [Atom.PropList]];

Implementing Spaces

SpacePrivate: TYPE ~ MONITORED RECORD [

Equal: EqualProc ← NIL,

Hash: HashProc ← NIL,

Compare: CompareProc ← NIL,

other: Atom.PropList ← NIL, --the canonical expansion slot

data: REF ANY

];

The only thing that may vary is the other, and that must accessed through the monitor entry procedures below.

NIL values in the fields mean to do obvious things with the addresses. The following two procedures are used to signify the inability of the Space to perform the given operation.

CantHash: HashProc;

CantCompare: CompareProc;

EqualProc: TYPE ~ PROC [data: REF ANY, elt1, elt2: Value] RETURNS [BOOL];

HashProc: TYPE ~ PROC [data: REF ANY, elt: Value] RETURNS [CARDINAL];

CompareProc: TYPE ~ PROC [data: REF ANY, elt1, elt2: Value] RETURNS [Basics.Comparison];

EqualAddresses: EqualProc;

HashAddress: HashProc;

CompareAddresses: CompareProc;

HashIntI: PROC [INT] RETURNS [CARDINAL]

~ TRUSTED MACHINE CODE { PrincOps.zXOR };

HashRefI: PROC [REF ANY] RETURNS [CARDINAL]

~ TRUSTED MACHINE CODE { PrincOps.zXOR };

CompareIntI: PROC [a, b: INT] RETURNS [Basics.Comparison]

~ Basics.CompareInt;

CompareRefI: PROC [a, b: REF ANY] RETURNS [Basics.Comparison]

~ TRUSTED INLINE {RETURN [Basics.CompareInt[LOOPHOLE[a], LOOPHOLE[b]]]};

UpdateSpaceOther: PROC [s: Space, Update: PROC [Atom.PropList] RETURNS [Atom.PropList]];