-- SetImpl.Mesa
-- Last Modified by Paul Rovner on January 16, 1984 4:15 pm

DIRECTORY
Set;

SetImpl: CEDAR MONITOR LOCKS set USING set: Handle
EXPORTS Set

= BEGIN OPEN Set;

-- TYPEs
RefList: TYPE = LIST OF REF ANY;

Handle: TYPE = REF SetRep;
SetRep: PUBLIC TYPE = MONITORED RECORD
[ head: RefList ← NIL,
last: RefList ← NIL,
cardinality: LONG CARDINAL ← 0
];
Comparison: TYPE = {less, equal, greater};

-- VARIABLES
PHI: PUBLIC Handle ← New[];

-- PUBLIC PROCs
Nth: PUBLIC PROC[set: Handle, index: LONG CARDINAL--from 1--]
RETURNS[element: Element ← NIL] =
{ count: LONG CARDINAL ← 0;
proc: PROC[e: Element] RETURNS[stop: BOOLEAN] =
{element ← e;
RETURN[(count ← count + 1) = index]};

IF Cardinality[set] >= index THEN [] ← Enumerate[set, proc];
};

New: PUBLIC PROC RETURNS[Handle] =
{RETURN[NEW[SetRep ← []]]};

Equal: PUBLIC PROC[s1, s2: Handle] RETURNS[BOOLEAN] =
{ proc: PROC[e: Element] RETURNS[stop: BOOLEAN] =
{RETURN[NOT In[s2, e]]};
IF Cardinality[s1] # Cardinality[s2] THEN RETURN[FALSE]
ELSE RETURN[NOT Enumerate[s1, proc]]};

In: PUBLIC PROC[set: Handle, element: Element] RETURNS[found: BOOLEAN] =
{ p: PROC[e: Element] RETURNS[stop: BOOLEAN] =
{ SELECT CompareRefs[element, e] FROM
equal => {found ← TRUE; RETURN[TRUE]};
less => RETURN[TRUE]; -- stop. It ain't there
ENDCASE => RETURN[FALSE];
};

found ← FALSE;
[] ← Enumerate[set, p];
RETURN[found];
};

Put: PUBLIC PROC[set: Handle, element: Element] RETURNS[found: BOOLEAN] =
{ p: PROC[e: Element, prev: RefList] RETURNS[stop: BOOLEAN] =
{ SELECT CompareRefs[element, e] FROM
equal => {found ← TRUE; RETURN[TRUE]}; -- it exists; stop the enumeration
less => -- Put it here and then stop the enumeration
{IF prev = NIL THEN
{ set.head ← CONS[element, set.head];
IF set.head.rest = NIL THEN set.last ← set.head}
ELSE
{ prev.rest ← CONS[element, prev.rest];
IF prev.rest.rest = NIL THEN set.last ← prev.rest};
set.cardinality ← set.cardinality + 1;
RETURN[TRUE]};
ENDCASE => RETURN[FALSE];
};

found ← FALSE;
IF set.head = NIL THEN
{ set.head ← set.last ← LIST[element];
set.cardinality ← set.cardinality + 1; IF set.cardinality # 1 THEN ERROR}
ELSE IF CompareRefs[element, set.last.first] = greater THEN
{ set.last.rest ← LIST[element];
set.last ← set.last.rest;
set.cardinality ← set.cardinality + 1}
ELSE [] ← PrivateEnumerate[set, p];
RETURN[found];
};

Remove: PUBLIC PROC[set: Handle, element: Element] RETURNS[found: BOOLEAN] =
{ p: PROC[e: Element, prev: RefList] RETURNS[stop: BOOLEAN] =
{ SELECT CompareRefs[element, e] FROM
equal => -- remove it and stop the enumeration
{found ← TRUE;
IF prev = NIL THEN
{ set.head ← set.head.rest;
IF set.head = NIL THEN set.last ← NIL}
ELSE
{ prev.rest ← prev.rest.rest;
IF prev.rest = NIL THEN set.last ← prev};
set.cardinality ← set.cardinality - 1;
RETURN[TRUE]};
less =>
{RETURN[TRUE]}; -- Not found; stop the enumeration
ENDCASE => RETURN[FALSE];
};

found ← FALSE;
[] ← PrivateEnumerate[set, p];
RETURN[found];
};

Union: PUBLIC PROC[s1, s2: Handle] RETURNS[ans: Handle] =
{ s1Next: RefList ← s1.head;
s2Next: RefList ← s2.head;
ans ← New[];
DO
IF s1Next = NIL THEN {s1Next ← s2Next; s2Next ← NIL};
IF s1Next = NIL THEN EXIT;
IF s2Next = NIL THEN {[] ← Put[ans, s1Next.first]; s1Next ← s1Next.rest}
ELSE
SELECT CompareRefs[s1Next.first, s2Next.first] FROM
equal => {[] ← Put[ans, s1Next.first]; s1Next ← s1Next.rest; s2Next ← s2Next.rest};
less => {[] ← Put[ans, s1Next.first]; s1Next ← s1Next.rest};
greater => {[] ← Put[ans, s2Next.first]; s2Next ← s2Next.rest};
ENDCASE => ERROR;
ENDLOOP;
RETURN[ans];
};

Intersection: PUBLIC PROC[s1, s2: Handle] RETURNS[ans: Handle] =
{ s1Next: RefList ← s1.head;
s2Next: RefList ← s2.head;
ans ← New[];
DO
IF s1Next = NIL OR s2Next = NIL THEN EXIT
ELSE
SELECT CompareRefs[s1Next.first, s2Next.first] FROM
equal => {[] ← Put[ans, s1Next.first]; s1Next ← s1Next.rest; s2Next ← s2Next.rest};
less => {s1Next ← s1Next.rest};
greater => {s2Next ← s2Next.rest};
ENDCASE => ERROR;
ENDLOOP;
RETURN[ans];
};

Difference: PUBLIC PROC[s1, s2: Handle] RETURNS[ans: Handle] =
{ s1Next: RefList ← s1.head;
s2Next: RefList ← s2.head;
ans ← New[];
DO
IF s1Next = NIL THEN EXIT;
IF s2Next = NIL THEN {[] ← Put[ans, s1Next.first]; s1Next ← s1Next.rest}
ELSE
SELECT CompareRefs[s1Next.first, s2Next.first] FROM
equal => {s1Next ← s1Next.rest; s2Next ← s2Next.rest};
less => {[] ← Put[ans, s1Next.first]; s1Next ← s1Next.rest};
greater => {s2Next ← s2Next.rest};
ENDCASE => ERROR;
ENDLOOP;
RETURN[ans];
};

Cardinality: PUBLIC PROC[set: Handle] RETURNS[LONG CARDINAL] =
{RETURN[IF set = NIL THEN 0 ELSE set.cardinality]};

CompareRefs: PUBLIC PROC[e1, e2: Element] RETURNS[Comparison] =
{RETURN[IF e1 = e2 THEN equal
ELSE IF LOOPHOLE[e1, LONG CARDINAL] < LOOPHOLE[e2, LONG CARDINAL] THEN less
ELSE greater]};

Enumerate: PUBLIC PROC[set: Handle,
proc: PROC[e: Element] RETURNS[stop: BOOLEAN]]
RETURNS[stopped: BOOLEAN] =
{ next: RefList ← NIL;
IF set = NIL THEN RETURN[FALSE];
next ← set.head;

UNTIL next = NIL DO
this: REF ANY = next.first;
next ← next.rest;
IF proc[this] THEN RETURN[TRUE];
ENDLOOP;
RETURN[FALSE];
};



-- PRIVATE PROCs

PrivateEnumerate: ENTRY PROC[set: Handle,
proc: PROC[e: Element, prev: RefList] RETURNS[stop: BOOLEAN]]
RETURNS[stopped: BOOLEAN] =
{ next, prev: RefList ← NIL;
IF set = NIL THEN RETURN[FALSE];
next ← set.head;

UNTIL next = NIL DO
this: REF ANY = next.first;
nextPrev: RefList = next;
next ← next.rest;
IF proc[this, prev] THEN RETURN[TRUE];
prev ← nextPrev;
ENDLOOP;
RETURN[FALSE];
};

END.