Changes between Version 13 and Version 14 of SetsCowan


Ignore:
Timestamp:
12/03/12 00:59:02 (5 years ago)
Author:
cowan
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • SetsCowan

    v13 v14  
    11== Sets, bags, integer sets, and enumeration sets == 
    22 
    3 Sets and bags (multisets) are mutable collections that can contain any Scheme object.  Integer sets are mutable collections that can contain non-negative exact integers from 0 to a maximum value that is 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. 
     3Sets and bags (multisets) are mutable collections that can contain any Scheme object.  Integer sets are mutable collections that can contain non-negative 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. 
    44 
    55Sets 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). 
     
    4141Removes ''element'' from ''set'' unless it is not a member.  Returns an unspecified value. 
    4242 
    43 `(set-map `''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`(set-map `''=''` `''proc''` `''set''`)` 
     44 
     45Applies ''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. 
    4646 
    4747`(set-for-each `''proc''` `''set''`)` 
     
    5555`(set->list `''set''`)` 
    5656 
    57 Returns a newly allocated list containing the members of ''set'' in unspecified order. 
     57Returns 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. 
    5858 
    5959`(list->set `''list''`)` 
     
    8181Returns `#t` if each ''set'' other than the last is a superset of the following ''set'', and `#f` otherwise. 
    8282 
    83 `(set-union `''set'` `''other-set'' ...`)` 
    84  
    85 Returns a newly allocated set that is the union of ''set'' and the ''other-sets''. 
    86  
    87 `(set-intersection `''set'` `''other-set'' ...`)` 
    88  
    89 Returns a newly allocated set that is the intersection of ''set'' and the ''other-sets''. 
    90  
    91 `(set-difference `''set'` `''other-set'' ...`)` 
    92  
    93 Returns a newly allocated set that is the difference of ''set'' and the union of the ''other-sets''. 
    94  
    95 `(set-xor `''set''` `''other-set'' ...`)` 
    96  
    97 Returns a newly allocated set that is the xor (symmetric difference) of the ''sets''. 
    98  
    99 `(set-union! `''set''` `''other-set'' ...`)` 
    100  
    101 Mutates ''set'' to a new set that is the union of ''set'' and the ''other-sets''. 
    102  
    103 `(set-intersection! `''set''` `''other-set'' ...`)` 
    104  
    105 Mutates ''set'' to a new set that is the intersection of ''set'' and the ''other-sets''. 
    106  
    107 `(set-difference! `''set''` `''other-set'' ...`)` 
    108  
    109 Mutates ''set'' to a new set that is the difference of ''set'' and the union of the ''other-sets''. 
    110  
    111 `(set-xor! `''set''` `''other-set'' ...`)` 
    112  
    113 Mutates ''set'' to a new set that is the xor (symmetric difference) of ''set'' and the ''other-sets''. 
     83`(set-union `''set,,1'` `''other-set,,2'' ...`)` 
     84 
     85Returns 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`(set-intersection `''set,,1'` `''other-set,,2'' ...`)` 
     88 
     89Returns 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`(set-difference `''set,,1'` `''other-set,,2'' ...`)` 
     92 
     93Returns 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`(set-xor `''set,,1''` `''set,,2''`)` 
     96 
     97Returns 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`(set-union! `''set,,1'` `''other-set,,2'' ...`)` 
     100 
     101Mutates ''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`(set-intersection! `''set,,1'` `''other-set,,2'' ...`)` 
     104 
     105Mutates ''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`(set-difference! `''set,,1'` `''other-set,,2'' ...`)` 
     108 
     109Mutates ''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`(set-xor! `''set,,1''` `''set,,2''`)` 
     112 
     113Mutates ''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. 
    114114 
    115115== Bag procedures == 
    116116 
    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. 
     117The 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, `bag-xor` and `bag-xor!` do not exist. 
    118118 
    119119`(bag-count `''bag''` `''element''`)` 
     
    123123== Integer set procedures == 
    124124 
    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 `integer-set` in their names.  Wherever a newly allocated integer set is returned, it has the same limit as the source sets. 
     125Except as noted below, the procedures for creating and manipulating integer sets are the same as those for sets, except that `set` is replaced by `integer-set` 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. 
    126126 
    127127`(make-integer-set `''limit''`)` 
     
    139139`(list->integer-set `''limit''` `''list''`)` 
    140140 
    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''. 
     141Returns 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. 
    142142 
    143143`(integer-set-complement `''integer-set''`)` 
     
    149149Mutates ''integer-set'' to a new set that is the complement of ''integer-set''. 
    150150 
     151`(integer-set-least `''integer-set''`)` 
     152 
     153`(integer-set-most `''integer-set''`)` 
     154 
     155Returns the smallest or largest integer in ``integer-set``, or `#f` if there is none. 
     156 
     157`(integer-set-least! `''integer-set''`)` 
     158 
     159`(integer-set-most! `''integer-set''`)` 
     160 
     161Removes and returns the smallest or largest integer in ``integer-set``, or `#f` if there is none. 
     162 
     163`(integer->integer-set `''limit'' ''integer'' `)` 
     164 
     165Creates 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`(integer-set->integer `''integer-set''`)` 
     168 
     169Returns the exact integer which, considered as a bit vector, is equivalent to ''integer-set''. 
     170 
    151171== Enumeration sets == 
    152172 
    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 `enum-set` in their names.  Wherever a newly allocated enumeration set is returned, it has the same enumeration type as the source sets. 
     173Except as noted below, the procedures for creating and manipulating enumeration sets are the same as those for sets, except that `set` is replaced by `enum-set` 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. 
    154174 
    155175`(make-enum-type `''symbol-list''`)` 
    156176 
    157 Returns a newly allocated enumeration type suitable for constructing enumeration sets whose members are the symbols in ''symbol-list''.  These symbols are said to be ''in the enumeration type''. 
     177Returns an enumeration type suitable for constructing enumeration sets whose members are the symbols in ''symbol-list''.  These symbols are said to be ''in the enumeration type''.  '''Issue''': are enumeration types the same if they have the same symbols? 
    158178 
    159179`(make-enum-set `''enum-type''`)` 
     
    181201Mutates ''enum-set'' to a new set that is the complement of ''enum-set''. 
    182202 
    183 `(enum-set-projection `''enum-set-1''` `''enum-set-2''`)` 
    184  
    185 Returns a newly allocated enumeration set of the same enumeration type as ''enum-set-2''.  The elements of the enumeration set are the symbols belonging to ''enum-set-1'', ignoring any symbols which are not in the enumeration type of ''enum-set-2''. 
     203`(enum-set-projection `''enum-set''` `''enum-type''`)` 
     204 
     205Returns a newly allocated enumeration set of type ''enum-type''.  Its elements are the symbols belonging to ''enum-set'', ignoring any symbols which are not in ''enum-type''. 
    186206 
    187207`(define-enumeration `<type-name>` (`<symbol> ...`)` <constructor>`)`