DIRECTORY PrincOpsUtils USING [BITOR, BITAND, BITNOT, BITSHIFT], PascalBasic; PascalSets: CEDAR DEFINITIONS IMPORTS PrincOpsUtils = BEGIN OPEN PascalBasic; PascalSmallSetRange: TYPE = PascalInteger [0..16); PascalSmallSet: TYPE = PACKED ARRAY PascalSmallSetRange OF BOOLEAN _ ALL[FALSE]; PascalMediumSetRange: TYPE = PascalInteger [0..64); PascalMediumSet: TYPE = PACKED ARRAY PascalMediumSetRange OF BOOLEAN _ ALL[ FALSE]; PascalLargeSetRange: TYPE = PascalInteger [0..256); PascalLargeSet: TYPE = PACKED ARRAY PascalLargeSetRange OF BOOLEAN _ ALL[FALSE]; PascalSmallSetEmpty: PascalSmallSet = ALL[FALSE]; PascalSmallSetGenerateElement: PROCEDURE [i: PascalInteger] RETURNS [PascalSmallSet] = INLINE {s: PascalSmallSet; s[i] _ TRUE; RETURN[s]}; PascalSmallSetGenerateInterval: PROCEDURE [i, j: PascalInteger] RETURNS [PascalSmallSet] = INLINE BEGIN s: PascalSmallSet; k: PascalInteger; FOR k IN [i..j] DO s[k] _ TRUE ENDLOOP; RETURN[s] END; PascalSmallSetAddElement: PROCEDURE [s: PascalSmallSet, i: PascalInteger] RETURNS [PascalSmallSet] = INLINE {s[i] _ TRUE; RETURN[s]}; PascalSmallSetAddInterval: PROCEDURE [s: PascalSmallSet, i, j: PascalInteger] RETURNS [PascalSmallSet] = INLINE BEGIN k: PascalInteger; FOR k IN [i..j] DO s[k] _ TRUE ENDLOOP; RETURN[s] END; PascalSmallSetUnion: PROCEDURE [x, y: PascalSmallSet] RETURNS [PascalSmallSet] = TRUSTED INLINE {RETURN[LOOPHOLE[PrincOpsUtils.BITOR[LOOPHOLE[x],LOOPHOLE[y]]]]}; PascalSmallSetIntersection: PROCEDURE [x, y: PascalSmallSet] RETURNS [PascalSmallSet] = TRUSTED INLINE {RETURN[LOOPHOLE[PrincOpsUtils.BITAND[LOOPHOLE[x],LOOPHOLE[y]]]]}; PascalSmallSetDifference: PROCEDURE [x, y: PascalSmallSet] RETURNS [PascalSmallSet] = TRUSTED INLINE { RETURN[LOOPHOLE[PrincOpsUtils.BITAND[LOOPHOLE[x], PrincOpsUtils.BITNOT[LOOPHOLE[y]]]]]}; PascalSmallSetIsSubset: PROCEDURE [x, y: PascalSmallSet] RETURNS [PascalBoolean] = INLINE {RETURN[y = PascalSmallSetUnion[y, x]]}; PascalSmallSetIsSuperset: PROCEDURE [x, y: PascalSmallSet] RETURNS [PascalBoolean] = INLINE {RETURN[x = PascalSmallSetUnion[y, x]]}; PascalSmallSetIsSame: PROCEDURE [x, y: PascalSmallSet] RETURNS [PascalBoolean] = INLINE {RETURN[LOOPHOLE[y, CARDINAL] = LOOPHOLE[x, CARDINAL]]}; PascalSmallSetIsDifferent: PROCEDURE [x, y: PascalSmallSet] RETURNS [PascalBoolean] = INLINE { RETURN[LOOPHOLE[y, CARDINAL] # LOOPHOLE[x, CARDINAL]]}; PascalSmallSetCARD: PROCEDURE [x: PascalSmallSet] RETURNS [PascalInteger] = TRUSTED INLINE BEGIN OPEN PrincOpsUtils; c: CARDINAL _ BITAND[LOOPHOLE[x], 52525B] + BITAND[BITSHIFT[LOOPHOLE[x], -1], 52525B]; c _ BITAND[c, 31463B] + BITAND[BITSHIFT[c, -2], 31463B]; c _ BITAND[c, 7417B] + BITAND[BITSHIFT[c, -4], 7417B]; RETURN[BITAND[c, 377B] + BITAND[BITSHIFT[c, -8], 377B]]; END; PascalSmallSetContains: PROCEDURE [s: PascalSmallSet, e: PascalInteger] RETURNS [PascalBoolean] = INLINE {RETURN[s[e]]}; PascalMediumSetEmpty: PascalMediumSet = ALL[FALSE]; PascalMediumSetGenerateElement: PROCEDURE [i: PascalInteger] RETURNS [PascalMediumSet]; PascalMediumSetGenerateInterval: PROCEDURE [i, j: PascalInteger] RETURNS [PascalMediumSet]; PascalMediumSetAddElement: PROCEDURE [i: PascalInteger, s: PascalMediumSet] RETURNS [PascalMediumSet]; PascalMediumSetAddInterval: PROCEDURE [i, j: PascalInteger, s: PascalMediumSet] RETURNS [PascalMediumSet]; PascalMediumSetUnion, PascalMediumSetIntersection, PascalMediumSetDifference: PROCEDURE [x, y: PascalMediumSet] RETURNS [PascalMediumSet]; PascalMediumSetIsSubset, PascalMediumSetIsSame: PROCEDURE [ x, y: PascalMediumSet] RETURNS [PascalBoolean]; PascalMediumSetIsSuperset: PROCEDURE [x, y: PascalMediumSet] RETURNS [PascalBoolean] = INLINE {RETURN[PascalMediumSetIsSubset[y, x]]}; PascalMediumSetIsDifferent: PROCEDURE [x, y: PascalMediumSet] RETURNS [PascalBoolean] = INLINE {RETURN[NOT PascalMediumSetIsSame[x, y]]}; PascalMediumSetCARD: PROCEDURE [x: PascalMediumSet] RETURNS [PascalInteger]; PascalMediumSetContains: PROCEDURE [s: PascalMediumSet, e: PascalInteger] RETURNS [PascalBoolean] = INLINE {RETURN[s[e]]}; PascalLargeSetEmpty: PascalLargeSet = ALL[FALSE]; PascalLargeSetGenerateElement: PROCEDURE [i: PascalInteger] RETURNS [PascalLargeSet]; PascalLargeSetGenerateInterval: PROCEDURE [i, j: PascalInteger] RETURNS [PascalLargeSet]; PascalLargeSetAddElement: PROCEDURE [i: PascalInteger, s: PascalLargeSet] RETURNS [PascalLargeSet]; PascalLargeSetAddInterval: PROCEDURE [i, j: PascalInteger, s: PascalLargeSet] RETURNS [PascalLargeSet]; PascalLargeSetUnion, PascalLargeSetIntersection, PascalLargeSetDifference: PROCEDURE [x, y: PascalLargeSet] RETURNS [PascalLargeSet]; PascalLargeSetIsSubset, PascalLargeSetIsSame: PROCEDURE [x, y: PascalLargeSet] RETURNS [PascalBoolean]; PascalLargeSetIsSuperset: PROCEDURE [x, y: PascalLargeSet] RETURNS [PascalBoolean] = INLINE {RETURN[PascalLargeSetIsSubset[y, x]]}; PascalLargeSetIsDifferent: PROCEDURE [x, y: PascalLargeSet] RETURNS [PascalBoolean] = INLINE {RETURN[NOT PascalLargeSetIsSame[x, y]]}; PascalLargeSetCARD: PROCEDURE [x: PascalLargeSet] RETURNS [PascalInteger]; PascalLargeSetContains: PROCEDURE [s: PascalLargeSet, e: PascalInteger] RETURNS [PascalBoolean] = INLINE {RETURN[s[e]]}; END. -- PascalSets @file: PascalSets.mesa last modified by Ramshaw, December 24, 1982 10:38 pm written by McCreight, November 17, 1980 3:13 PM Changed by Pavel on May 9, 1985 6:37:47 pm PDT Cedar Pascal-to-Mesa Runtime support for sets May 9, 1985: Pavel moved to Cedar6.0 by adding a bunch of LOOPHOLEs in the SmallSet stuff. T Y P E S C O N S T A N T S A N D P R O C S fast bit-counter that adds a pair of eight one-bit registers to yield eight two-bit sums, then breaks those into a pair of four two-bit registers which are combined to yield four four-bit sums, and so on. Κ‹˜Jšœ™Jšœ4™4Jšœ0™0J™.J˜Jšœ-™-J™J™ZJ˜šΟk ˜ Jš œœœœœœ˜6J˜ J˜—Jšœ œ œœ˜5˜Jšœœ ˜J˜Jšœ ™ J˜Jšœœ˜2Jšœœœœœœœœ˜PJšœœ˜3š œœœœœœœ˜KJšœ˜—Jšœœ˜3Jšœœœœœœœœ˜P˜Jšœ*™*J˜—Jšœ&œœ˜1šΟnœ œ˜;Jšœœœœ˜NJ˜—šžœ œ˜?Jšœ˜!Jš˜J˜J˜Jš œœœœœ˜'Jšœ˜ Jšœ˜J˜—šžœ œ&˜IJšœœ œœ˜;J˜—šžœ œ)˜MJšœ˜!Jšœœœœœœœœ˜NJ˜—šžœ œœ˜PJšœœœœœœœ˜P—šžœ œ˜