-- 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. Êü˜JšëÏcLœÏk œžœžœžœžœžœžœžœ œ žœžœžœžœžœ žœžœžœžœž œžœ#žœ$žœ!žœžœ$žœ žœžœÏnœžœžœžœž œžœžœžœžœžœ žœžœžœ)žœžœ#ŸœžœžœžœžœžœŸœžœžœžœžœžœ žœžœ žœžœžœ#žœžœžœžœžœžœŸœžœžœ žœžœ žœ žœžœ žœžœžœžœžœžœžœœ žœžœžœžœ"žœŸœžœžœ žœžœ žœžœžœ žœžœžœžœžœ#œ-œ žœžœžœžœ&žœžœžœ$žœžœ'žœžœžœYžœžœ žœžœžœžœžœ žœžœžœ:žœžœžœžœžœ0žœžœažœ$žœŸœžœžœ žœžœ žœžœžœ žœžœ&œžœžœžœžœ>žœ žœžœ žœžœ@žœ žœžœTžœžœ#žœžœ#œ žœžœžœžœ)žœŸœžœžœžœcžœžœ žœžœžœ žœ žœžœžœžœ žœžœ<žœ žœ)žœùžœžœžœžœ Ÿ œžœžœžœcžœžœ žœžœ žœžœžœžœ žœ)žœ¿žœžœžœžœ Ÿ œžœžœžœcžœžœ žœžœžœžœ žœžœ<žœ žœ)žœ¿žœžœžœžœ Ÿ œžœžœžœžœžœžœžœžœžœžœŸ œžœžœžœžœžœ žœžœžœžœžœžœžœžœžœžœžœ Ÿ œžœžœ+žœ žœžœ žœ žœžœžœžœžœžœžœžœžœžœ žœžœ-žœ žœžœžœžœžœžœ œŸœžœžœ1žœžœžœ žœ žœžœžœžœžœžœžœžœžœžœ žœžœMžœžœžœžœžœžœžœ žœ˜¥3—…—¨ª