Changes between Version 13 and Version 14 of SetsCowan
 Timestamp:
 12/03/12 00:59:02 (5 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

SetsCowan
v13 v14 1 1 == Sets, bags, integer sets, and enumeration sets == 2 2 3 Sets and bags (multisets) are mutable collections that can contain any Scheme object. Integer sets are mutable collections that can contain nonnegative exact integers from 0 to a maximum value that isspecified when the integer set is created. Enumeration sets are mutable collections that can contain symbols chosen from a set of symbols represented by an enumeration type.3 Sets and bags (multisets) are mutable collections that can contain any Scheme object. Integer sets are mutable collections that can contain nonnegative exact integers that are less than a maximum value specified when the integer set is created. Enumeration sets are mutable collections that can contain symbols chosen from a set of symbols represented by an enumeration type. 4 4 5 5 Sets and bags (multisets) are intended to be a thin veneer over hashtables, and integer sets are a thin veneer over bit vectors. In turn, enumeration sets are a thin veneer over integer sets. Consequently, the `member?`, `add!`, and `remove!` procedures are required to have an amortized cost of O(1). … … 41 41 Removes ''element'' from ''set'' unless it is not a member. Returns an unspecified value. 42 42 43 `(setmap `'' proc''` `''set''`)`44 45 Applies ''proc'' to each element of ''set'' in arbitrary order and returns a newly allocated set with the same equality predicate containing the values of the applications. '''Issue: Should we provide this at all? The fold is sufficient.'''43 `(setmap `''=''` `''proc''` `''set''`)` 44 45 Applies ''proc'' to each element of ''set'' in arbitrary order and returns a newly allocated set with the equality predicate ''='' which contains the results of the applications. 46 46 47 47 `(setforeach `''proc''` `''set''`)` … … 55 55 `(set>list `''set''`)` 56 56 57 Returns a newly allocated list containing the members of ''set'' in unspecified order. 57 Returns a newly allocated list containing the members of ''set'' in unspecified order. However, repeated calls to this procedure will return a list in the same order until the set is mutated. 58 58 59 59 `(list>set `''list''`)` … … 81 81 Returns `#t` if each ''set'' other than the last is a superset of the following ''set'', and `#f` otherwise. 82 82 83 `(setunion `''set '` `''otherset'' ...`)`84 85 Returns a newly allocated set that is the union of ''set'' and the ''othersets''.86 87 `(setintersection `''set '` `''otherset'' ...`)`88 89 Returns a newly allocated set that is the intersection of ''set'' and the ''othersets''.90 91 `(setdifference `''set '` `''otherset'' ...`)`92 93 Returns a newly allocated set that is the difference of ''set'' and the union of the ''othersets''.94 95 `(setxor `''set ''` `''otherset'' ...`)`96 97 Returns a newly allocated set that is the xor (symmetric difference) of the ''sets''.98 99 `(setunion! `''set ''` `''otherset'' ...`)`100 101 Mutates ''set'' to a new set that is the union of ''set'' and the ''othersets''.102 103 `(setintersection! `''set ''` `''otherset'' ...`)`104 105 Mutates ''set'' to a new set that is the intersection of ' 'set'' and the ''othersets''.106 107 `(setdifference! `''set ''` `''otherset'' ...`)`108 109 Mutates ''set '' to a new set that is the difference of ''set'' and the union of the ''othersets''.110 111 `(setxor! `''set ''` `''otherset'' ...`)`112 113 Mutates ''set'' to a new set that is the xor (symmetric difference) of ''set '' and the ''othersets''.83 `(setunion `''set,,1'` `''otherset,,2'' ...`)` 84 85 Returns a newly allocated set that is the union of the ''sets''. It is an error if the sets do not have the same equality predicate. 86 87 `(setintersection `''set,,1'` `''otherset,,2'' ...`)` 88 89 Returns a newly allocated set that is the intersection of the ''sets''. It is an error if the sets do not have the same equality predicate. 90 91 `(setdifference `''set,,1'` `''otherset,,2'' ...`)` 92 93 Returns a newly allocated set that is the difference of the ''sets''. It is an error if the sets do not have the same equality predicate. 94 95 `(setxor `''set,,1''` `''set,,2''`)` 96 97 Returns a newly allocated set that is the xor (symmetric difference) of ''set,,1'' and ''set,,2,,''. It is an error if the sets do not have the same equality predicate. 98 99 `(setunion! `''set,,1'` `''otherset,,2'' ...`)` 100 101 Mutates ''set'' to a new set that is the union of the ''sets''. It is an error if the sets do not have the same equality predicate. 102 103 `(setintersection! `''set,,1'` `''otherset,,2'' ...`)` 104 105 Mutates ''set'' to a new set that is the intersection of 'the ''sets''. It is an error if the sets do not have the same equality predicate. 106 107 `(setdifference! `''set,,1'` `''otherset,,2'' ...`)` 108 109 Mutates ''set,,1'' to a new set that is the difference of the ''sets''. It is an error if the sets do not have the same equality predicate. 110 111 `(setxor! `''set,,1''` `''set,,2''`)` 112 113 Mutates ''set'' to a new set that is the xor (symmetric difference) of ''set,,1'' and ''set,,2''. It is an error if the sets do not have the same equality predicate. 114 114 115 115 == Bag procedures == 116 116 117 The procedures for creating and manipulating bags are the same as those for sets, except that `set` is replaced by `bag` in their names, and that adding an element to a bag is effective even if the bag already contains the element. 117 The procedures for creating and manipulating bags are the same as those for sets, except that `set` is replaced by `bag` in their names, and that adding an element to a bag is effective even if the bag already contains the element. However, `bagxor` and `bagxor!` do not exist. 118 118 119 119 `(bagcount `''bag''` `''element''`)` … … 123 123 == Integer set procedures == 124 124 125 Except as noted below, the procedures for creating and manipulating integer sets are the same as those for sets, except that `set` is replaced by `integerset` in their names. Wherever a newly allocated integer set is returned, it has the same limit as the source sets. 125 Except as noted below, the procedures for creating and manipulating integer sets are the same as those for sets, except that `set` is replaced by `integerset` in their names. Wherever a newly allocated integer set is returned, it has the same limit as the source sets. It is an error to operate on integer sets with different limits. 126 126 127 127 `(makeintegerset `''limit''`)` … … 139 139 `(list>integerset `''limit''` `''list''`)` 140 140 141 Returns a newly allocated integer set. The possible elements of the set are the exact integers from 0 to ''limit''  1. The set is initialized to contain the elements of ''list'' .141 Returns a newly allocated integer set. The possible elements of the set are the exact integers from 0 to ''limit''  1. The set is initialized to contain the elements of ''list'' in increasing numerical order. 142 142 143 143 `(integersetcomplement `''integerset''`)` … … 149 149 Mutates ''integerset'' to a new set that is the complement of ''integerset''. 150 150 151 `(integersetleast `''integerset''`)` 152 153 `(integersetmost `''integerset''`)` 154 155 Returns the smallest or largest integer in ``integerset``, or `#f` if there is none. 156 157 `(integersetleast! `''integerset''`)` 158 159 `(integersetmost! `''integerset''`)` 160 161 Removes and returns the smallest or largest integer in ``integerset``, or `#f` if there is none. 162 163 `(integer>integerset `''limit'' ''integer'' `)` 164 165 Creates a newly allocated integer set with the specified ''limit'' initialized from the bits of ''integer'', which must be exact, considered as a bit vector. 166 167 `(integerset>integer `''integerset''`)` 168 169 Returns the exact integer which, considered as a bit vector, is equivalent to ''integerset''. 170 151 171 == Enumeration sets == 152 172 153 Except as noted below, the procedures for creating and manipulating enumeration sets are the same as those for sets, except that `set` is replaced by `enumset` in their names. Wherever a newly allocated enumeration set is returned, it has the same enumeration type as the source sets. 173 Except as noted below, the procedures for creating and manipulating enumeration sets are the same as those for sets, except that `set` is replaced by `enumset` in their names. Wherever a newly allocated enumeration set is returned, it has the same enumeration type as the source sets. It is an error to operate on enumeration sets of different types. 154 174 155 175 `(makeenumtype `''symbollist''`)` 156 176 157 Returns a newly allocated enumeration type suitable for constructing enumeration sets whose members are the symbols in ''symbollist''. These symbols are said to be ''in the enumeration type''.177 Returns an enumeration type suitable for constructing enumeration sets whose members are the symbols in ''symbollist''. These symbols are said to be ''in the enumeration type''. '''Issue''': are enumeration types the same if they have the same symbols? 158 178 159 179 `(makeenumset `''enumtype''`)` … … 181 201 Mutates ''enumset'' to a new set that is the complement of ''enumset''. 182 202 183 `(enumsetprojection `''enumset 1''` `''enumset2''`)`184 185 Returns a newly allocated enumeration set of t he same enumeration type as ''enumset2''. The elements of the enumeration set are the symbols belonging to ''enumset1'', ignoring any symbols which are not in the enumeration type of ''enumset2''.203 `(enumsetprojection `''enumset''` `''enumtype''`)` 204 205 Returns a newly allocated enumeration set of type ''enumtype''. Its elements are the symbols belonging to ''enumset'', ignoring any symbols which are not in ''enumtype''. 186 206 187 207 `(defineenumeration `<typename>` (`<symbol> ...`)` <constructor>`)`