<> <> 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: READONLY Value; MaybeValue: TYPE ~ SetBasics.MaybeValue; noMaybe: READONLY MaybeValue; Space: TYPE ~ SetBasics.Space; RelOrder: TYPE ~ SetBasics.RelOrder; Complain: PROC [set: Set, msg: ROPE, args: LOV _ NIL] ~ INLINE {Error[msg, CONS[AV[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, []]; --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] <> ~ 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] <<= 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]; <> 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] <<=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: 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[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]; <> 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[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] <> ~ 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]; <> <> <> <> < filter.HasMember#CantHasMember>> < filter.Enumerate#CantEnumerate>> < x.mutability#constant>> < x.mutability=variable>> < x.mutability#variable>> < x.mutability=readonly>> < 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]}; <> 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]; <> 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], AV[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 _ refs, mutability: Mutability _ variable, order: RelOrder _ no, assumeSorted: BOOL _ FALSE] RETURNS [Set]; <> ListFromLORA: PROC [vals: LORA, space: Space _ refs, mutability: Mutability _ variable, order: RelOrder _ no, assumeSorted: BOOL _ FALSE] 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]; <> 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 q1q2 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]}; Primitive: PROC [set: Set, op: ATOM, arg1, arg2: REF ANY _ NIL] RETURNS [BOOL]; <> 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]; < $TFF>> 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]}; }.