DIRECTORY Atom, Basics, Collections;

PairCollections: CEDAR DEFINITIONS
IMPORTS Collections
= {OPEN Colls: Collections, Collections;
Collection: TYPE ~ Colls.Collection;
Value: TYPE ~ Colls.Value;
Direction: TYPE ~ Colls.Direction;
Side: TYPE ~ Colls.Side;
BoolPair: TYPE ~ Colls.BoolPair;
Pair: TYPE ~ ARRAY Side OF Value;
noPair: READONLY Pair -- = [noValue, noValue] --;

PairColl: TYPE ~ RECORD [class: PairCollClass, data: Value];

Cons: PROC [class: PairCollClass, data: REF ANY] RETURNS [PairColl];

nilPairColl: PairColl ~ [NIL, NIL];
DeRef: PROC [ra: REF ANY] RETURNS [PairColl]
~ INLINE {RETURN [IF ra#NIL THEN NARROW[ra, REF PairColl]^ ELSE nilPairColl]};
Refify: PROC [pc: PairColl] RETURNS [ref: REF ANY]
~ INLINE {ref _ NEW [PairColl _ pc]};
Cant: ERROR [pc: PairColl];

QualityOf: PROC [pc: PairColl, op: ATOM, args: ArgList _ NIL] RETURNS [ImplQuality];

Can: PROC [pc: PairColl, op: ATOM, args: ArgList _ NIL] RETURNS [BOOL]
~ INLINE {RETURN [QualityOf[pc, op, args]#cant]};

Widen: PROC [pc: PairColl] RETURNS [Collection--of REF Pair--]
~ INLINE {RETURN pc.class.Widen[pc]};

HasPair: PROC [pc: PairColl, pair: Pair] RETURNS [BOOL]
~ INLINE {RETURN pc.class.HasPair[pc, pair]};

OrderStyleOf: PROC [pc: PairColl] RETURNS [OrderStyle]
~ INLINE {RETURN [pc.class.orderStyle]};

Ordering: TYPE ~ RECORD [Compare: PairCompareProc, data: REF ANY, sideCare: SideCare];
PairCompareProc: TYPE ~ PROC [data: REF ANY, elt1, elt2: Pair] RETURNS [Basics.Comparison];
SideCare: TYPE ~ {neither, left, right, both};
unordered: Ordering ~ [NIL, NIL, neither];

OrderBySide: PROC [side: Side, o: Colls.Ordering] RETURNS [Ordering];
OrderByBoth: PROC [highSide: Side, high, low: Colls.Ordering] RETURNS [Ordering];

OrderingOf: PROC [pc: PairColl] RETURNS [Ordering]
~ INLINE {RETURN pc.class.OrderingOf[pc]};

CaresAbout: PROC [sideCare: SideCare, side: Side] RETURNS [BOOL]
~ INLINE {RETURN [SELECT sideCare FROM
neither => FALSE,
left => side=left,
right => side=right,
both => TRUE,
ENDCASE => ERROR]};

Image: PROC [pc: PairColl, coll: Collection, dir: Direction _ leftToRight] RETURNS [UWColl]
~ INLINE {RETURN pc.class.Image[pc, coll, dir]};

Mapping: PROC [pc: PairColl, v: Value, dir: Direction _ leftToRight] RETURNS [UWColl]
~ INLINE {RETURN pc.class.Image[pc, Colls.CreateSingleton[v, pc.Spaces[][Source[dir]]], dir]};

Enumerate: PROC [pc: PairColl, Consume: PROC [Pair], bkwd: BOOL _ FALSE];

MaybePair: TYPE ~ RECORD [found: BOOL, pair: Pair];
noMaybePair: READONLY MaybePair -- = [FALSE, noPair] --;
ParallelFind: TYPE ~ RECORD [found: BOOL, a, b: MaybePair];
Tester: TYPE ~ PROC [pair: Pair] RETURNS [pass: BOOL _ FALSE];

Scan: PROC [pc: PairColl, Test: Tester, bkwd: BOOL _ FALSE] RETURNS [MaybePair]
~ INLINE {RETURN pc.class.Scan[pc, Test, bkwd]};

EnumerateImage: PROC [pc: PairColl, coll: Collection, Consume: PROC [Value], dir: Direction _ leftToRight, bkwd: BOOL _ FALSE];

EnumerateMapping: PROC [pc: PairColl, v: Value, Consume: PROC [Value], dir: Direction _ leftToRight, bkwd: BOOL _ FALSE]
~ INLINE {EnumerateImage[pc, Colls.CreateSingleton[v, pc.Spaces[][Source[dir]]], Consume, dir, bkwd]};

EnumerateHalfRestriction: PROC [pc: PairColl, coll: Collection, Consume: PROC [Pair], side: Side _ left, bkwd: BOOL _ FALSE];

ScanImage: PROC [pc: PairColl, coll: Collection, Test: Colls.Tester, dir: Direction _ leftToRight, bkwd: BOOL _ FALSE] RETURNS [MaybePair];

ScanMapping: PROC [pc: PairColl, v: Value, Test: Colls.Tester, dir: Direction _ leftToRight, bkwd: BOOL _ FALSE] RETURNS [MaybePair]
~ INLINE {RETURN ScanImage[pc, Colls.CreateSingleton[v, pc.Spaces[][Source[dir]]], Test, dir, bkwd]};

ScanHalfRestriction: PROC [pc: PairColl, coll: Collection, Test: Tester, side: Side _ left, bkwd: BOOL _ FALSE] RETURNS [MaybePair]
~ INLINE {RETURN pc.class.ScanHalfRestriction[pc, side, coll, Test, bkwd]};

ParallelTester: TYPE ~ PROC [a, b: MaybePair] RETURNS [pass: BOOL _ FALSE];

ParallelScan: PROC [a, b: PairColl, Test: ParallelTester, bkwd: BOOL _ FALSE] RETURNS [ParallelFind]
~ INLINE {RETURN ParallelScanHalfRestriction[a, b, passAll, Test, left, bkwd]};

ParallelScanHalfRestriction: PROC [a, b: PairColl, coll: Collection, Test: ParallelTester, side: Side _ left, bkwd: BOOL _ FALSE] RETURNS [ParallelFind];

First: PROC [pc: PairColl] RETURNS [MaybePair]
~ INLINE {RETURN pc.class.Extremum[pc, FALSE, FALSE]};
Last: PROC [pc: PairColl] RETURNS [MaybePair]
~ INLINE {RETURN pc.class.Extremum[pc, TRUE, FALSE]};
Pop: PROC [pc: PairColl, bkwd: BOOL _ FALSE] RETURNS [MaybePair]
~ INLINE {RETURN pc.class.Extremum[pc, bkwd, TRUE]};
Extremum: PROC [pc: PairColl, bkwd, remove: BOOL] RETURNS [MaybePair]
~ INLINE {RETURN pc.class.Extremum[pc, bkwd, remove]};

Next: PROC [pc: PairColl, pair: Pair] RETURNS [MaybePair]
~ INLINE {RETURN [pc.class.Get3[pc, pair].next]};
Prev: PROC [pc: PairColl, pair: Pair] RETURNS [MaybePair]
~ INLINE {RETURN [pc.class.Get3[pc, pair].prev]};
Get3: PROC [pc: PairColl, pair: Pair] RETURNS [prev, same, next: MaybePair]
~ INLINE {RETURN pc.class.Get3[pc, pair]};

Size: PROC [pc: PairColl, limit: LNAT _ LNAT.LAST] RETURNS [LNAT]
~ INLINE {RETURN [pc.class.Size[pc, limit]]};

Empty: PROC [pc: PairColl] RETURNS [BOOL]
~ INLINE {RETURN [pc.class.Size[pc, 1]=0]};

ImageSize: PROC [pc: PairColl, coll: Collection, dir: Direction _ leftToRight, limit: LNAT _ LNAT.LAST] RETURNS [LNAT]
~ INLINE {RETURN [pc.class.ImageSize[pc, coll, dir, limit]]};

MappingSize: PROC [pc: PairColl, v: Value, dir: Direction _ leftToRight, limit: LNAT _ LNAT.LAST] RETURNS [LNAT]
~ INLINE {RETURN [pc.class.ImageSize[pc, Colls.CreateSingleton[v, pc.Spaces[][Source[dir]]], dir, limit]]};

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

Copy: PROC [pc: PairColl] RETURNS [VarPairColl]
~ INLINE {RETURN pc.class.Copy[pc]};

Insulate: PROC [pc: PairColl] RETURNS [UWPairColl]
~ INLINE {RETURN pc.class.Insulate[pc]};

ValueOf: PROC [pc: PairColl] RETURNS [ConstPairColl]
~ INLINE {RETURN pc.class.ValueOf[pc]};

Freeze: PROC [pc: PairColl] RETURNS [const: ConstPairColl]
~ INLINE {RETURN pc.class.Freeze[pc]};

Thaw: PROC [pc: PairColl]
~ INLINE {pc.class.Thaw[pc]};

Where: TYPE ~ RECORD [SELECT kind: WhereKind FROM
any => [],
end => [end: End],
rel => [pair: Pair, reln: WhereReln],
ENDCASE _ any[]];

News: TYPE ~ {same, different, new};
NewsPair: TYPE ~ PACKED ARRAY Direction OF News;
NewsSetPair: TYPE ~ ARRAY Direction OF PACKED ARRAY News OF BOOL;

IfNews: TYPE ~ PACKED ARRAY --news=new--BOOL OF --add:--BOOL;
IfNewsPair: TYPE ~ ARRAY Direction OF IfNews;

alwaysAdd: IfNewsPair ~ ALL[ALL[TRUE]];
addIfNew: IfNewsPair ~ ALL[[FALSE, TRUE]];
addIfOld: IfNewsPair ~ ALL[[TRUE, FALSE]];

AddPair: PROC [pc: PairColl, pair: Pair, if: IfNewsPair _ alwaysAdd, where: Where _ []] RETURNS [news: NewsPair];

AddNewPair: PROC [pc: PairColl, pair: Pair, where: Where _ []];

AddColl: PROC [pc, other: PairColl, if: IfNewsPair _ alwaysAdd, where: Where _ []] RETURNS [some: NewsSetPair]
~ INLINE {RETURN pc.class.AddColl[pc, other, if, where]};

AddNewColl: PROC [pc, other: PairColl, where: Where _ []];

RemPair: PROC [pc: PairColl, pair: Pair, style: RemoveStyle _ any] RETURNS [hadMapping: BoolPair]
~ INLINE {RETURN [pc.class.RemColl[pc, CreateSingleton[pair, pc.Spaces[]], style].hadAll]};

RemColl: PROC [pc, other: PairColl, style: RemoveStyle _ any] RETURNS [hadSome, hadAll: BoolPair]
~ INLINE {RETURN pc.class.RemColl[pc, other, style]};

Delete: PROC [pc: PairColl, val: Value, side: Side _ left, style: RemoveStyle _ all] RETURNS [hadSome: BOOL]
~ INLINE {RETURN [pc.class.DeleteColl[pc, Colls.CreateSingleton[val, pc.Spaces[][side]], side, style].hadSome]};

DeleteColl: PROC [pc: PairColl, coll: Collection, side: Side _ left, style: RemoveStyle _ all] RETURNS [hadSome, hadAll: BOOL]
~ INLINE {RETURN pc.class.DeleteColl[pc, coll, side, style]};

Spaces: PROC [pc: PairColl] RETURNS [SpacePair]
~ INLINE {RETURN pc.class.Spaces[pc]};

CollectionOn: PROC [pc: PairColl, side: Side] RETURNS [UWColl]
~ INLINE {RETURN [pc.class.CollectionOn[pc, side]]};

CurSetOn: PROC [pc: PairColl, side: Side] RETURNS [ConstSet]
~ INLINE {RETURN [[pc.class.CurSetOn[pc, side]]]};

Functional: PROC [pc: PairColl] RETURNS [BoolPair]
~ INLINE {RETURN [pc.class.functional]};

MayDuplicate: PROC [pc: PairColl] RETURNS [BOOL]
~ INLINE {RETURN [pc.class.mayDuplicate]};

refPairColls: READONLY Space;

Equal: PROC [a, b: PairColl, bounds: CollPair _ [passAll, passAll]] RETURNS [BOOL];

Hash: PROC [pc: PairColl, bounds: CollPair _ [passAll, passAll]] RETURNS [CARDINAL];

Compare: PROC [a, b: PairColl, bounds: CollPair _ [passAll, passAll]] RETURNS [Basics.Comparison];
VarPairColl: TYPE ~ RECORD [PairColl] --a variable PairColl--;
IsVar: PROC [pc: PairColl] RETURNS [BOOL]
~ INLINE {RETURN [pc.class.mutability=variable]};
AsVar: PROC [pc: PairColl] RETURNS [VarPairColl]
~ INLINE {IF pc#nilPairColl AND pc.class.mutability#variable THEN Complain[pc, notVariable]; RETURN [[pc]]};

UWPairColl: TYPE ~ RECORD [PairColl] --an unwritable PairColl--;
IsUW: PROC [pc: PairColl] RETURNS [BOOL]
~ INLINE {RETURN [pc.class.mutability#variable]};
AsUW: PROC [pc: PairColl] RETURNS [UWPairColl]
~ INLINE {IF pc#nilPairColl AND pc.class.mutability=variable THEN Complain[pc, writeable]; RETURN [[pc]]};

ConstPairColl: TYPE ~ RECORD [UWPairColl] --a constant PairColl--;
IsConst: PROC [pc: PairColl] RETURNS [BOOL]
~ INLINE {RETURN [pc.class.mutability=constant]};
AsConst: PROC [pc: PairColl] RETURNS [ConstPairColl]
~ INLINE {IF pc#nilPairColl AND pc.class.mutability#constant THEN Complain[pc, notConstant]; RETURN [[[pc]]]};

Relation: TYPE ~ PairColl --a binary relation: a non-duplicating pair collection--;
VarRelation: TYPE ~ VarPairColl;
ConstRelation: TYPE ~ ConstPairColl;
IsRelation: PROC [pc: PairColl] RETURNS [BOOL]
~ INLINE {RETURN [NOT pc.class.mayDuplicate]};

Function: TYPE ~ PairColl --a non-duplicating pair collection that doesn't have two pairs with equal left sides--;
VarFunction: TYPE ~ VarPairColl;
UWFunction: TYPE ~ UWPairColl;
ConstFunction: TYPE ~ ConstPairColl;
IsFunction: PROC [pc: PairColl] RETURNS [BOOL]
~ INLINE {RETURN [pc.class.functional[leftToRight] AND NOT pc.class.mayDuplicate]};

InvFunction: TYPE ~ PairColl --a non-duplicating pair collection that doesn't have two pairs with equal right sides--;
VarInvFunction: TYPE ~ VarPairColl;
UWInvFunction: TYPE ~ UWPairColl;
ConstInvFunction: TYPE ~ ConstPairColl;
IsInvFunction: PROC [pc: PairColl] RETURNS [BOOL]
~ INLINE {RETURN [pc.class.functional[rightToLeft] AND NOT pc.class.mayDuplicate]};

OneToOne: TYPE ~ PairColl --a one-to-one relation--;
VarOneToOne: TYPE ~ VarPairColl;
ConstOneToOne: TYPE ~ ConstPairColl;
IsOneToOne: PROC [pc: PairColl] RETURNS [BOOL]
~ INLINE {RETURN [pc.class.functional=ALL[TRUE] AND NOT pc.class.mayDuplicate]};

Store: PROC [pc: Function, pair: Pair] RETURNS [new: BOOL]
~ INLINE {RETURN [pc.AddPair[pair][leftToRight]=new]};

Replace: PROC [pc: Function, pair: Pair] RETURNS [old: BOOL]
~ INLINE {RETURN [pc.AddPair[pair, [[TRUE, FALSE], ALL[TRUE]]][leftToRight]#new]};

Insert: PROC [pc: Function, pair: Pair] RETURNS [new: BOOL]
~ INLINE {RETURN [pc.AddPair[pair, [[FALSE, TRUE], ALL[TRUE]]][leftToRight]=new]};

Inserted: PROC [pc: Function, pair: Pair] RETURNS [Value]
~ INLINE {
IF NOT pc.Insert[pair] THEN Error[notNew, LIST[NEW [Function _ pc], NEW [Pair _ pair]]];
RETURN [pair[right]]};
notNew: READONLY ROPE;

Apply: PROC [pc: PairColl, v: Value, dir: Direction _ leftToRight] RETURNS [MaybeValue]
~ INLINE {RETURN pc.class.Apply[pc, v, dir]};

Bag: TYPE ~ Function --where range is REF INT; this is a.k.a. a multiset; it is a function from an item to the number of occurrences of that item--;

IsIntFn: PROC [pc: PairColl, dir: Direction _ leftToRight] RETURNS [BOOL]
~ INLINE {RETURN [pc.QuaIntFn.found]};

AsIntFn: PROC [pc: PairColl, dir: Direction _ leftToRight] RETURNS [REF ANY]
~ INLINE {RETURN [QuaIntFn[pc].val]};

QuaIntFn: PROC [pc: PairColl, dir: Direction _ leftToRight] RETURNS [MaybeValue]
~ INLINE {RETURN pc.class.QuaIntFn[pc, dir]};
empty, id: READONLY ConstPairColl;

CreateSingleton: PROC [elt: Pair, spaces: SpacePair] RETURNS [ConstPairColl]
~ INLINE {RETURN [[[[GetSingletonClass[spaces], NEW [Pair _ elt]]]]]};
GetSingletonClass: PROC [spaces: SpacePair] RETURNS [PairCollClass];

NCreateSingleton: PROC [elt: Pair, spaces: SpacePair] RETURNS [ConstPairColl];

CreateIDSubset: PROC [Collection] RETURNS [PairColl];

CreateProduct: PROC [CollPair] RETURNS [PairColl];

CreateFromList: PROC [vals: LOP, functional: BoolPair _ [FALSE, FALSE], spaces: SpacePair _ [refs, refs], mayDuplicate: BOOL _ FALSE] RETURNS [ConstPairColl];

HashFn: TYPE ~ VarFunction;

CreateHashReln: PROC [spaces: SpacePair _ [refs, refs], functional: BoolPair _ [FALSE, FALSE], mappable: BoolPair _ [TRUE, TRUE]] RETURNS [VarPairColl];
CreateHashOTO: PROC [spaces: SpacePair _ [refs, refs]] RETURNS [VarOneToOne]
~ INLINE {RETURN CreateHashReln[spaces, ALL[TRUE]]};
CreateHashFn: PROC [spaces: SpacePair _ [refs, refs], invable: BOOL _ TRUE] RETURNS [HashFn]
~ INLINE {RETURN CreateHashReln[spaces, [TRUE, FALSE], [TRUE, invable]]};
CreateHashTable: PROC [right: Space _ refs, invable: BOOL _ TRUE] RETURNS [HashFn]
~ INLINE {RETURN CreateHashReln[[refs, right], [TRUE, FALSE], [TRUE, invable]]};
CreateHashDictionary: PROC [case: BOOL _ TRUE, right: Space _ refs, invable: BOOL _ TRUE] RETURNS [HashFn]
~ INLINE {RETURN CreateHashReln[[ropes[case], right], [TRUE, FALSE], [TRUE, invable]]};
CreateHashCopy: PROC [pc: PairColl, spaces: SpacePair _ [NIL, NIL], mappable: BoolPair _ [FALSE, FALSE]] RETURNS [HashFn];

RedBlackReln: TYPE ~ VarRelation;

CreateRedBlackReln: PROC [spaces: SpacePair _ [refs, refs], functional: BoolPair _ [FALSE, FALSE], mappable: BoolPair _ [TRUE, TRUE]] RETURNS [RedBlackReln];
CreateRedBlackCopy: PROC [pc: PairColl, spaces: SpacePair _ [NIL, NIL], mappable: BoolPair _ [FALSE, FALSE]] RETURNS [RedBlackReln];

Union: PROC [a, b: PairColl] RETURNS [PairColl];
DisjointUnion: PROC [a, b: Relation] RETURNS [Relation];
Intersection: PROC [PairColl, PairColl] RETURNS [PairColl];
Difference: PROC [PairColl, PairColl] RETURNS [PairColl];
SymmetricDifference: PROC [a, b: PairColl] RETURNS [c: PairColl];
Negate: PROC [PairColl] RETURNS [PairColl];
Compose: PROC [pcs: ARRAY Side OF PairColl, restricts: ARRAY Side OF BOOL _ [TRUE, TRUE]] RETURNS [PairColl];
Invert: PROC [PairColl] RETURNS [PairColl];

FnFromProc: PROC [Apply: PROC [data: REF ANY, v: Value] RETURNS [mv: MaybeValue], spaces: SpacePair _ [refs, refs], data: REF ANY _ NIL, constant, oneToOne: BOOL _ FALSE, ScanInverse: PROC [data: REF ANY, v: Value, Test: Tester] RETURNS [MaybePair] _ NIL] RETURNS [Function];

CreateCountingBag: PROC [coll: Collection] RETURNS [Bag]
~ INLINE {RETURN [[countingBagClass, NEW [Collection _ coll]]]};
countingBagClass: READONLY PairCollClass;
PairCollClass: TYPE ~ REF PairCollClassPrivate;
PairCollClassPrivate: TYPE ~ MONITORED RECORD [
Primitive: PROC [pc: PairColl, op: ATOM, args: ArgList _ NIL] RETURNS [PrimitiveAnswer] _ NIL,
Widen: PROC [pc: PairColl] RETURNS [Collection--of REF Pair--] _ NIL,
HasPair: PROC [pc: PairColl, pair: Pair] RETURNS [BOOL] _ NIL,
Image: PROC [pc: PairColl, coll: Collection, dir: Direction] RETURNS [UWColl] _ NIL,
Apply: PROC [pc: PairColl, v: Value, dir: Direction] RETURNS [MaybeValue] _ NIL,
Scan: PROC [pc: PairColl, Test: Tester, bkwd: BOOL] RETURNS [MaybePair] _ NIL,
ScanHalfRestriction: PROC [pc: PairColl, side: Side, coll: Collection, Test: Tester, bkwd: BOOL] RETURNS [MaybePair] _ NIL,
Extremum: PROC [pc: PairColl, bkwd, remove: BOOL] RETURNS [MaybePair] _ NIL,
Get3: PROC [pc: PairColl, pair: Pair] RETURNS [prev, same, next: MaybePair] _ NIL,
Size: PROC [pc: PairColl, limit: LNAT] RETURNS [LNAT] _ NIL,
ImageSize: PROC [pc: PairColl, coll: Collection, dir: Direction, limit: LNAT] RETURNS [LNAT] _ NIL,
Copy: PROC [pc: PairColl] RETURNS [VarPairColl] _ NIL,
Insulate: PROC [pc: PairColl] RETURNS [UWPairColl] _ NIL,
ValueOf: PROC [pc: PairColl] RETURNS [ConstPairColl] _ NIL,
Freeze: PROC [pc: PairColl] RETURNS [const: ConstPairColl] _ NIL,
Thaw: PROC [pc: PairColl] _ NIL,
CollectionOn: PROC [pc: PairColl, side: Side] RETURNS [UWColl] _ NIL,
CurSetOn: PROC [pc: PairColl, side: Side] RETURNS [ConstSet] _ NIL,
AddColl: PROC [pc, other: PairColl, if: IfNewsPair, where: Where] RETURNS [some: NewsSetPair] _ NIL,
RemColl: PROC [pc, other: PairColl, style: RemoveStyle] RETURNS [hadSome, hadAll: BoolPair] _ NIL,
DeleteColl: PROC [pc: PairColl, coll: Collection, side: Side, style: RemoveStyle] RETURNS [hadSome, hadAll: BOOL] _ NIL,
QuaIntFn: PROC [pc: PairColl, dir: Direction] RETURNS [MaybeValue] _ NIL,
Spaces: PROC [pc: PairColl] RETURNS [SpacePair] _ NIL,
OrderingOf: PROC [pc: PairColl] RETURNS [Ordering] _ NIL,
functional: BoolPair _ [FALSE, FALSE],
mayDuplicate: BOOL _ TRUE,
orderStyle: OrderStyle _ none,
mutability: Mutability _ variable,
other: Atom.PropList _ NIL, --the canonical expansion slot
data: Value _ NIL
];

CreateClass:
PROC [cp: PairCollClassPrivate,
bkwdable: BB _ [TRUE, FALSE],
dirable: BoolPair _ [TRUE, FALSE]]
RETURNS [PairCollClass];

DefaultWiden: PROC [pc: PairColl] RETURNS [Collection--of REF Pair--];
DefaultImage: PROC [pc: PairColl, coll: Collection, dir: Direction] RETURNS [UWColl];
DefaultApply: PROC [pc: PairColl, v: Value, dir: Direction] RETURNS [MaybeValue];
DefaultScan: PROC [pc: PairColl, Test: Tester, bkwd: BOOL] RETURNS [MaybePair];
DefaultScanHalfRestriction: PROC [pc: PairColl, side: Side, coll: Collection, Test: Tester, bkwd: BOOL] RETURNS [MaybePair];
DefaultExtremum: PROC [pc: PairColl, bkwd, remove: BOOL] RETURNS [MaybePair];
DefaultGet3: PROC [pc: PairColl, pair: Pair] RETURNS [prev, same, next: MaybePair];
DefaultImageSize: PROC [pc: PairColl, coll: Collection, dir: Direction, limit: LNAT] RETURNS [LNAT];
DefaultCollectionOn: PROC [pc: PairColl, side: Side] RETURNS [UWColl];
DefaultCurSetOn: PROC [pc: PairColl, side: Side] RETURNS [ConstSet];
DefaultInsulate: PROC [pc: PairColl] RETURNS [UWPairColl];
DefaultDeleteColl: PROC [pc: PairColl, coll: Collection, side: Side, style: RemoveStyle] RETURNS [hadSome, hadAll: BOOL];
DefaultQuaIntFn: PROC [pc: PairColl, dir: Direction] RETURNS [MaybeValue];
DefaultSpaces: PROC [pc: PairColl] RETURNS [SpacePair];
DefaultOrderingOf: PROC [pc: PairColl] RETURNS [Ordering];
IsDefaultOrdering: PROC [Ordering] RETURNS [BOOL];

GetSide: PROC [args: ArgList, i: NAT, default: Side _ left] RETURNS [Side];
FromSide: PROC [Side] RETURNS [ATOM];

UpdatePairCollClassOther: PROC [class: PairCollClass, Update: PROC [Atom.PropList] RETURNS [Atom.PropList]];
InvertSideCare: ARRAY SideCare OF SideCare
~ [neither: neither, left: right, right: left, both: both];

SpacePair: TYPE ~ ARRAY Side OF Space;
LOP: TYPE ~ LIST OF Pair;
CollPair: TYPE ~ ARRAY Side OF Collection;

ConsPair: PROC [first: Side, v1, v2: Value] RETURNS [pair: Pair]
~ INLINE {pair[first] _ v1; pair[OtherSide[first]] _ v2};

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

P: PROC [mp: MaybePair] RETURNS [Pair]
~ INLINE {IF mp.found THEN RETURN [mp.pair] ELSE Error[notFound, NIL]};

DP: PROC [mp: MaybePair, ifNotFound: Pair _ [NIL, NIL]] RETURNS [Pair]
~ INLINE {RETURN [IF mp.found THEN mp.pair ELSE ifNotFound]};

WidenSpacePair: PROC [sp: SpacePair] RETURNS [s: Space];

IsPairSpace: PROC [s: Space] RETURNS [BOOL];

NarrowSpace: PROC [s: Space] RETURNS [sp: SpacePair];

WidenOrdering: PROC [o: Ordering] RETURNS [wo: Colls.Ordering];

NarrowOrdering: PROC [wo: Colls.Ordering] RETURNS [o: Ordering];

InvertPair: PROC [x: Pair] RETURNS [Pair]
~ INLINE {RETURN [[x[right], x[left]]]};

InvertBoolPair: PROC [x: BoolPair] RETURNS [BoolPair]
~ INLINE {RETURN [[x[rightToLeft], x[leftToRight]]]};

InvertMaybe: PROC [mp: MaybePair] RETURNS [MaybePair]
~ INLINE {RETURN [[mp.found, InvertPair[mp.pair]]]};

InvertNewsPair: PROC [x: NewsPair] RETURNS [NewsPair]
~ INLINE {RETURN [[x[rightToLeft], x[leftToRight]]]};

InvertNewsSetPair: PROC [x: NewsSetPair] RETURNS [NewsSetPair]
~ INLINE {RETURN [[x[rightToLeft], x[leftToRight]]]};

InvertIfNewsPair: PROC [x: IfNewsPair] RETURNS [IfNewsPair]
~ INLINE {RETURN [[x[rightToLeft], x[leftToRight]]]};

InvertSpacePair: PROC [x: SpacePair] RETURNS [SpacePair]
~ INLINE {RETURN [[x[right], x[left]]]};

InvertWhere: PROC [x: Where] RETURNS [Where]
~ INLINE {WITH x SELECT FROM
y: any Where => RETURN [y];
y: end Where => RETURN [y];
y: rel Where => RETURN [[rel[InvertPair[y.pair], y.reln]]];
ENDCASE => ERROR};

InvertOrdering: PROC [o: Ordering] RETURNS [io: Ordering];

ReverseOrdering: PROC [o: Ordering] RETURNS [ro: Ordering];
}.
ŽPairCollections.Mesa
Last tweaked by Mike Spreitzer on October 16, 1987 10:03:48 am PDT
Random Old Stuff
Pairs, and Collections of Them
A collection of Pairs, or a variable such.
Good for calling from the interpreter.
Operations on PairColls
Raised when a pair collection is asked to perform an operation it can't.
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, or the Side, or the bkwds: 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.
For leftToRight, the result is the things that are on the right sides of pairs in pc that have an element of coll on their left side.  The result tracks changes to the PairColl, but may not be changed directly.
The image of a singleton.
Enumerates those pairs such that pair[side] is in coll.
When adding a pair to a variable collection that is Functional[dir], the resultant NewsPair[dir] tells about the previous state of that variable: new means there was previously no pair with equivalent [Source[dir]]; different means there was a pair with equivalent [Source[dir]] and non-equivalent [Dest[dir]]; same means there was previously an equivalent pair.  If the collection is not Functional[dir], the resultant NewsPair[dir] can be anything.
The procedures that add to variable pair collections can be conditional on the previous state: if the collection is Functional[dir], if[dir][news[dir]=new] must be TRUE in order for the addition to happen.
Like AddPair, with the expectation that the pair is new.
Equivalent to a series of AddPairs. some[n][dir] iff some AddPair[..][dir]=n.
Same as AddColl[if: addIfNew], and then in functional directions d insist that some[d][same] = some[d][different] = FALSE.
For collections that are Functional[dir]: hadMapping[dir] tells whether there was a pair with an equivalent Value on the Source[dir] side; for those not functional, hadMapping[dir] is unrestricted.
Equivalent to a bunch of RemPairs.  hadSome[dir] is the OR of the hadMapping[dir]s, and hadAll[dir] is the AND.
Remove pair(s) with equivalent values on the given side.  hadSome tells whether there were any.
A PairColl must know the space on either side if it's functional in either direction.
Returns a collection of the elements on the given side of the pairs of pc.  Result tracks changes to pc.
Returns the current value, and thus does not track changes to pc.
Functional[pc][leftToRight] => pc can't have two pairs with equivalent left Values and non-equivalent right Values.
Might this relation enumerate equivalent pairs (or mappings) more than once?
A x in bounds[left], y in bounds[right] : <x,y> in a W <x,y> in b.
Special Cases of PairColls
pc must be Functional[dir]. Returns noMaybe if no such pair.
Some Implementations of PairColls
(functional[dir] OR mappable[dir]) tells whether the result can Image in direction dir.
NIL space means use the same space as the given PairColl.  Can map in direction d if the orginial can or if mappable[d].
The following use a standard implementation.  The result tracks changes to the arguments, if any.  Result may duplicate iff any argument may.
Assumes arguments have no elements in common.
restricts[side]=FALSE means caller is guaranteeing that henceforth CollectionOn[pcs[OtherSide[side]], side] is included in CollectionOn[pcs[side], OtherSide[side]].
Implementing PairColls
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.  Iff Primitive is elided, `bkwdable' and `dirable' are taken into consideration when constructing Primitive.
Other Random New Stuff
s is a space of REF Pair, where [left] is in sp[left] and [right] is in sp[right].
Is s the result of WidenSpacePair?
Please apply only if IsPairSpace[s].
wo gives the same order to REF Pairs as o gives to their referents.
wo gives the same order to REF Pairs as o gives to their referents.
Swap [left] and [right].
o relates [a1, a2] to [b1, b2] as io relates [a2, a1] to [b2, b1].
If o says a before b, ro says b before a.
�Ê:–

"cedar" style˜
code™Kš
œB™B—K˜KšÏk	œ˜$K˜šÏnœ�œ
�˜"Kš�œ˜Kšœ�œ
žœ˜(—
head™Kšœ�œ˜$Kšœ�œ˜Kšœ�œ˜"Kšœ�œ˜Kšœ
�œ˜ —™Kšœ�œ�œ�œ˜!Kšœ�œÏcœ
˜1K˜šœ
�œ�œ%˜<K™*—K˜š
žœ�œ�œ
�œ�œ˜DK™&—K˜Kšœ�œ�œ˜#š
žœ�œ�œ
�œ�œ˜,Kšœ�œ�œ�œ�œ
�œ
�œ�œ�œ˜N—š
žœ�œ�œ�œ
�œ
˜2Kšœ�œ�œ˜%——š
œ™šžœ�œ˜K™H—K˜š
ž	œ�œ�œ�œ�œ˜TKš
œ�™�—K˜šžœ�œ�œ�œ�œ�œ
˜FKšœ�œ�œ!˜1—K˜šžœ�œ�œŸœ
˜>Kšœ�œ�œ˜%—K˜šžœ�œ�œ�œ
˜7Kšœ�œ�œ˜-—K˜šžœ�œ�œ
˜6Kšœ�œ�œ˜(—K˜Kšœ
�œ�œžœ�œ
�œ˜VKšœ�œ�œ�œ
�œ�œ˜[Kšœ
�œ ˜.Kšœ�œ�œ˜*K˜Kšžœ�œ!�œ˜EKšžœ�œ-�œ˜QK˜šž
œ�œ�œ˜2Kšœ�œ�œ˜*—K˜šž
œ�œ"�œ�œ
˜@šœ�œ�œ�œ
�˜&Kšœ�œ
˜K˜K˜Kšœ�œ
˜
Kš�œ�œ˜——K˜šžœ�œ@�œ	˜[Kš
œÒ
™Ò
Kšœ�œ�œ ˜0—K˜šžœ�œ8�œ	˜UKš
œ™Kšœ�œ�œN˜^—K˜Kšž	œ�œžœ�œ�œ�œ˜IK˜Kšœ�œ�œ	�œ˜3Kšœ
�œŸœ
˜8Kšœ�œ�œ	�œ˜;Kšœ�œ�œ�œ�œ�œ˜>K˜šžœ�œžœ�œ�œ�œ˜OKšœ�œ�œ ˜0K˜—Kšžœ�œ"žœ�œ.�œ�œ˜K˜šžœ�œžœ�œ.�œ�œ
˜xKšœ�œ^˜f—K˜šžœ�œ"žœ�œ"�œ�œ˜}K™7—K˜Kšž	œ�œ"žœ4�œ�œ�œ
˜‹
K˜šžœ�œžœ4�œ�œ�œ˜„
Kšœ�œ�œU˜e—K˜šžœ�œ"žœ#�œ�œ�œ˜ƒ
Kšœ�œ�œ;˜K—K˜Kšœ�œ�œ�œ�œ�œ˜KK˜šžœ�œžœ�œ�œ�œ˜dKšœ�œ�œ?˜OK˜—Kšžœ�œ$žœ+�œ�œ�œ˜™
K˜šžœ�œ�œ˜.Kš	œ�œ�œ�œ�œ˜6—šžœ�œ�œ˜-Kš	œ�œ�œ�œ�œ˜5—š
žœ�œ�œ�œ�œ˜@Kšœ�œ�œ�œ˜4—šžœ�œ�œ�œ˜EKšœ�œ�œ&˜6—K˜šžœ�œ�œ˜9Kšœ�œ�œ!˜1—šžœ�œ�œ˜9Kšœ�œ�œ!˜1—šžœ�œ�œ˜KKšœ�œ�œ˜*—K˜šžœ�œ�œ�œ
�œ�œ�œ
˜AKšœ�œ�œ˜-—K˜šžœ�œ�œ�œ
˜)Kšœ�œ�œ˜+—K˜šž	œ�œG�œ�œ
�œ�œ�œ
˜vKšœ�œ�œ-˜=—K˜šžœ�œ?�œ�œ
�œ�œ�œ
˜pKšœ�œ�œ[˜k—K˜šžœ�œ�œ
˜6Kšœ�œ�œ˜(—K˜šžœ�œ�œ˜/Kšœ�œ�œ˜$—K˜šžœ�œ�œ
˜2Kšœ�œ�œ˜(—K˜šžœ�œ�œ˜4Kšœ�œ�œ˜'—K˜šžœ�œ�œ˜:Kšœ�œ�œ˜&—K˜šžœ�œ˜Kšœ�œ˜—K˜šœ�œ�œ�œ�˜1K˜
K˜K˜%Kš�œ
˜K˜—Kšœ�œ˜$Kš	œ
�œ�œ
�œ�œ˜0šœ
�œ�œ�œ
�œ
�œ�œ
�œ
˜AKšœ’
ÏeœC 	œV œ‡
™Â—K˜Kšœ�œ�œ
�œ
Ÿ�œ
�œ
Ÿ�œ
˜=šœ�œ�œ�œ˜-Kš
œÍ
™Í
—K˜Kšœ�œ
�œ
�œ˜'Kšœ�œ�œ�œ˜*Kšœ�œ�œ�œ˜*K˜Kšžœ�œK�œ˜qK˜šž
œ�œ/˜?Kš
œ8™8—K˜šžœ�œF�œ˜nKš
œM™MKšœ�œ�œ)˜9—K˜šž
œ�œ*˜:K™z—K˜šžœ�œ6�œ˜aKš
ρ
™Å
Kšœ�œ�œK˜[—K˜šžœ�œ1�œ˜aKš
œo™oKšœ�œ�œ%˜5—K˜šžœ�œI�œ�œ
˜lKš
œ_™_Kšœ�œ�œ`˜p—K˜šž
œ�œO�œ�œ
˜~Kšœ�œ�œ-˜=—K˜šžœ�œ�œ˜/K™UKšœ�œ�œ˜&—K˜šžœ�œ�œ	˜>K™hKšœ�œ�œ$˜4—K˜šžœ�œ�œ˜<K™AKšœ�œ�œ"˜2—K˜šž
œ�œ�œ˜2K™sKšœ�œ�œ˜(—K˜šžœ�œ�œ�œ
˜0K™LKšœ�œ�œ˜*—K˜Kšœ�œ˜K˜šžœ�œ9�œ�œ˜SKšÏm
œ4¡
œ™B—K˜Kšžœ�œ7�œ�œ˜TK˜Kšžœ�œ9�œ˜b—™Kšœ
�œ�œŸœ
˜>šžœ�œ�œ�œ
˜)Kšœ�œ�œ!˜1—šžœ�œ�œ˜0Kšœ�œ�œ�œ�œ�œ	˜l—K˜Kšœ�œ�œŸœ
˜@šžœ�œ�œ�œ
˜(Kšœ�œ�œ!˜1—šžœ�œ�œ
˜.Kšœ�œ�œ�œ�œ�œ	˜j—K˜Kšœ�œ�œŸœ
˜Bšžœ�œ�œ�œ
˜+Kšœ�œ�œ!˜1—šžœ�œ�œ˜4Kšœ�œ�œ�œ�œ�œ˜n—K˜Kšœ
�œŸ8œ
˜SKšœ
�œ˜ Kšœ�œ˜$šž
œ�œ�œ�œ
˜.Kšœ�œ�œ�œ˜.—K˜Kšœ
�œŸWœ
˜rKšœ
�œ˜ Kšœ�œ˜Kšœ�œ˜$šž
œ�œ�œ�œ
˜.Kš	œ�œ�œ#�œ
�œ˜S—K˜Kšœ
�œŸXœ
˜vKšœ�œ˜#Kšœ�œ˜!Kšœ�œ˜'šž
œ�œ�œ�œ
˜1Kš	œ�œ�œ#�œ
�œ˜S—K˜Kšœ
�œŸœ
˜4Kšœ
�œ˜ Kšœ�œ˜$šž
œ�œ�œ�œ
˜.Kš
œ�œ�œ�œ
�œ�œ
�œ˜P—K˜šžœ�œ�œ�œ
˜:Kšœ�œ�œ&˜6—K˜šžœ�œ�œ�œ
˜<Kš
œ�œ�œ�œ�œ�œ
�œ˜R—K˜šžœ�œ�œ�œ
˜;Kš
œ�œ�œ�œ�œ�œ
�œ˜R—K˜šžœ�œ�œ˜9šœ�œ˜
Kš�œ
�œ�œ�œ
�œ�œ˜XKš�œ˜—Kšœ�œ
�œ
˜—K˜šžœ�œ8�œ
˜WKš
œ<™<Kšœ�œ�œ˜-—K˜Kšœ�œŸ~œ
˜”
K˜šžœ�œ.�œ�œ
˜IKšœ�œ�œ˜&—K˜š
žœ�œ.�œ�œ
�œ
˜LKšœ�œ�œ˜%—K˜šžœ�œ.�œ
˜PKšœ�œ�œ˜-——™!Kšœ�œ˜"K˜šžœ�œ �œ˜LKšœ�œ�œ �œ˜FKšžœ�œ�œ˜D—K˜Kšžœ�œ �œ˜NK˜Kšžœ�œ�œ˜5K˜Kšž
œ�œ�œ˜2K˜Kšžœ�œ�œ�œ�œ3�œ�œ�œ˜ž
K˜Kšœ�œ˜K˜šžœ�œ<�œ�œ�œ�œ�œ˜˜
Kš
œW™W—šž
œ�œ$�œ˜LKš	œ�œ�œ�œ
�œ˜4—š
žœ�œ-�œ�œ�œ	˜\Kšœ�œ�œ�œ�œ�œ
˜I—š
žœ�œ �œ�œ�œ	˜RKšœ�œ�œ �œ�œ�œ
˜P—šžœ�œ�œ�œ �œ�œ�œ	˜jKšœ�œ�œ'�œ�œ�œ
˜W—šžœ�œ%�œ�œ�œ�œ�œ
˜zK™x—K˜Kšœ�œ˜!K˜Kšžœ�œ<�œ�œ�œ�œ�œ˜�
Kšžœ�œ%�œ�œ�œ�œ�œ˜„
K˜Kš
œ�
™�
Kšžœ�œ�œ˜0šž
œ�œ�œ˜8K™-—Kšžœ�œ�œ˜;Kšž
œ�œ�œ˜9Kšžœ�œ�œ˜AKšžœ�œ�œ˜+šžœ�œ�œ�œ�œ�œ
�œ�œ�œ�œ˜mK™¤
—Kšžœ�œ�œ˜+K˜Kš(ž
œ�œžœ�œ�œ
�œ�œ;�œ
�œ�œ�œ�œžœ�œ�œ
�œžœ
�œ�œ�œ˜“K˜šžœ�œ�œ˜8Kšœ�œ�œ�œ˜@Kšœ�œ˜)——š
œ™Kšœ�œ�œ˜/šœ�œ�	œ
�œ˜/Kšž	œ�œ�œ�œ�œ�œ
˜^Kš
žœ�œ�œŸœ�œ
˜EKš
žœ�œ�œ�œ�œ
˜>Kšžœ�œ2�œ�œ
˜TKšžœ�œ*�œ�œ
˜PKšžœ�œžœ�œ�œ�œ
˜NKšžœ�œ.žœ�œ�œ�œ
˜{Kš
žœ�œ�œ�œ�œ
˜LKšžœ�œ�œ!�œ
˜RKšžœ�œ�œ�œ�œ�œ
˜<Kšž	œ�œ9�œ�œ�œ�œ
˜cKšžœ�œ�œ�œ
˜6Kšžœ�œ�œ�œ
˜9Kšžœ�œ�œ�œ
˜;Kšžœ�œ�œ�œ
˜AKšžœ�œ�œ
˜ Kšžœ�œ�œ�œ
˜EKšžœ�œ�œ�œ
˜CKšžœ�œ5�œ�œ
˜dKšžœ�œ+�œ�œ
˜bKš
ž
œ�œB�œ�œ�œ
˜xKšžœ�œ �œ�œ
˜IKšžœ�œ�œ�œ
˜6Kšž
œ�œ�œ�œ
˜9Kšœ�œ�œ˜&Kšœ�œ�œ
˜Kš
œ˜K˜"Kšœ�œŸ˜:Kšœ�˜K˜Kšœ# œ?™g—K˜šžœ
˜š�œ˜Kšœ
�œ�œ�œ˜Kšœ�œ�œ˜"—Kš�œ˜Kš
œÿ
™ÿ
—K˜Kšžœ�œ�œŸœ˜FKšžœ�œ2�œ
˜UKšžœ�œ*�œ˜QKš
žœ�œžœ�œ�œ
˜OKš
žœ�œ.žœ�œ�œ
˜|Kšžœ�œ�œ�œ
˜MKšžœ�œ�œ˜SKš
žœ�œ9�œ�œ�œ˜dKšžœ�œ�œ
˜FKšžœ�œ�œ˜DKšžœ�œ�œ˜:Kšžœ�œB�œ�œ˜yKšžœ�œ �œ˜JKšž
œ�œ�œ
˜7Kšžœ�œ�œ˜:Kšžœ�œ�œ�œ˜2K˜Kšžœ�œ�œ�œ˜KKšžœ�œ�œ�œ˜%K˜Kš
žœ�œžœ�œ�œ˜l—™šžœ�œ
�œ	˜*K˜;—K˜Kšœ�œ�œ�œ˜&Kš�œ�œ�œ
�œ˜Kšœ
�œ�œ�œ˜*K˜šžœ�œ�œ
˜@Kšœ�œ1˜9—K˜š
žœ�œ�œ�œ�œ
˜9Kšœ�œ
�œ
�œ˜7—K˜šž
œ�œ�œ˜&Kš
œ�œ�œ
�œ
�œ�œ�œ˜G—K˜š
�œ�œ%�œ�œ�œ˜FKšœ�œ�œ�œ
�œ	�œ˜=—K˜šžœ�œ�œ˜8Kš 
œ, œ œ™R—K˜šžœ�œ�œ�œ˜,Kš
œ"™"—K˜šžœ�œ�œ˜5Kš
œ$™$—K˜šž
œ�œ�œ˜?Kš œ& 
œ™C—K˜šžœ�œ�œ˜@Kš œ& 
œ™C—K˜šž
œ�œ�œ˜)K™Kšœ�œ�œ˜(—K˜šžœ�œ�œ˜5Kšœ�œ�œ%˜5—K˜šžœ�œ�œ˜5Kšœ�œ�œ$˜4—K˜šžœ�œ�œ˜5Kšœ�œ�œ%˜5—K˜šžœ�œ�œ˜>Kšœ�œ�œ%˜5—K˜šžœ�œ�œ
˜;Kšœ�œ�œ%˜5—K˜šžœ�œ�œ˜8Kšœ�œ�œ˜(—K˜šžœ�œ�œ˜,šœ�œ�œ�œ
�˜Kšœ�œ˜Kšœ�œ˜Kšœ�œ%˜;Kš�œ�œ˜——K˜šžœ�œ�œ˜:Kš 
œ! œ™B—K˜šžœ�œ�œ˜;Kšœ 
œ œ™)——L˜—…—Q}Ì