• Home
• All tickets
• All wiki pages

Source for wiki SetsCowan version 14

author

cowan

comment

ipnr

74.68.121.27

name

SetsCowan

readonly

0

text

== Sets, bags, integer sets, and enumeration sets ==

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 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.

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).

Sets, bags, integer sets, enumeration sets, and enumeration types are mutually disjoint, and disjoint from other types of Scheme objects.

== Set procedures ==

`(make-set `''=''`)`

Returns a newly allocated empty set.  ''='' is the equality procedure for the set, which must be consistent with `eq?`.  If ''='' is other than `eq?`, `equal`, `string=?`, or `string-ci=?`, the implementation MAY signal an error.  '''Issue: possibly add '''`eqv?`''' to this list if hash tables support it.'''

`(set `''=''` `''element''` ...)`

Returns a newly allocated set with equality procedure ''='' and containing the ''elements''.

`(set-copy `''set''`)`

Returns a newly allocated set containing the elements of ''set'', with the same equality procedure.

`(set? `''obj''`)`

Returns `#t` if ''obj'' is a set, and `#f` otherwise.

`(set-length? `''set''`)`

Returns the number of elements in ''set''.

`(set-member? `''set''` `''element''`)`

Returns `#t` if ''element'' is a member of ''set'' and `#f` otherwise.

`(set-add! `''set''` `''element''`)`

Adds ''element'' to ''set'' unless it is already a member.  Returns an unspecified value.

`(set-remove! `''set''` `''element''`)`

Removes ''element'' from ''set'' unless it is not a member.  Returns an unspecified value.

`(set-map `''=''` `''proc''` `''set''`)`

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.

`(set-for-each `''proc''` `''set''`)`

Applies ''proc'' to ''set'' in arbitrary order, discarding the returned values.  Returns unspecified results.

`(set-fold `''proc''` `''nil''` `''set''`)`

Invokes ''proc'' on each member of ''set'' in arbitrary order, passing the result of the previous invocation as a second argument.  For the first invocation, ''nil'' is used as the second argument.  Returns the result of the last invocation.

`(set->list `''set''`)`

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.

`(list->set `''list''`)`

Returns a newly allocated set containing the elements of ''list''.

`(set=? `''set'' ...`)`

Returns `#t` if each ''set'' contains the same elements.

`(set<? `''set'' ...`)`

Returns `#t` if each ''set'' other than the last is a proper subset of the following ''set'', and `#f` otherwise.

`(set>? `''set'' ...`)`

Returns `#t` if each ''set'' other than the last is a proper superset of the following ''set'', and `#f` otherwise.

`(set<=? `''set'' ...`)`

Returns `#t` if each ''set'' other than the last is a subset of the following ''set'', and `#f` otherwise.

`(set>=? `''set'' ...`)`

Returns `#t` if each ''set'' other than the last is a superset of the following ''set'', and `#f` otherwise.

`(set-union `''set,,1'` `''other-set,,2'' ...`)`

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.

`(set-intersection `''set,,1'` `''other-set,,2'' ...`)`

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.

`(set-difference `''set,,1'` `''other-set,,2'' ...`)`

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.

`(set-xor `''set,,1''` `''set,,2''`)`

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.

`(set-union! `''set,,1'` `''other-set,,2'' ...`)`

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.

`(set-intersection! `''set,,1'` `''other-set,,2'' ...`)`

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.

`(set-difference! `''set,,1'` `''other-set,,2'' ...`)`

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.

`(set-xor! `''set,,1''` `''set,,2''`)`

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.

== Bag procedures ==

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, `bag-xor` and `bag-xor!` do not exist.

`(bag-count `''bag''` `''element''`)`

Returns an exact integer representing the number of times that ''element'' appears in ''bag''.

== Integer set procedures ==

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.  It is an error to operate on integer sets with different limits.

`(make-integer-set `''limit''`)`

Returns a newly allocated integer set.  The possible elements of the set are the exact integers from 0 to ''limit'' - 1, where ''limit'' is an exact non-negative integer.  The set is empty.

`(make-universal-integer-set `''limit''`)`

Returns a newly allocated integer set.  The possible elements of the set are the exact integers from 0 to ''limit'' - 1, where ''limit'' is an exact non-negative integer.  The set contains all possible elements.

`(integer-set `''limit''` `''element'' ...`)`

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''.

`(list->integer-set `''limit''` `''list''`)`

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.

`(integer-set-complement `''integer-set''`)`

Returns a newly allocated integer set that is the complement of ''integer-set''.

`(integer-set-complement! `''integer-set''`)`

Mutates ''integer-set'' to a new set that is the complement of ''integer-set''.

`(integer-set-least `''integer-set''`)`

`(integer-set-most `''integer-set''`)`

Returns the smallest or largest integer in ``integer-set``, or `#f` if there is none.

`(integer-set-least! `''integer-set''`)`

`(integer-set-most! `''integer-set''`)`

Removes and returns the smallest or largest integer in ``integer-set``, or `#f` if there is none.

`(integer->integer-set `''limit'' ''integer'' `)`

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.

`(integer-set->integer `''integer-set''`)`

Returns the exact integer which, considered as a bit vector, is equivalent to ''integer-set''.

== Enumeration sets ==

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.  It is an error to operate on enumeration sets of different types.

`(make-enum-type `''symbol-list''`)`

Returns 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?

`(make-enum-set `''enum-type''`)`

Returns a newly allocated enumeration set.  The possible elements of the set are the symbols in ''enum-type''.  The set is empty.

`(make-universal-enum-set `''enum-type''`)`

Returns a newly allocated enumeration set.  The possible elements of the set are the symbols in ''enum-type''.  The set contains all possible elements.

`(enum-set `''enum-type''` `''element'' ...`)`

Returns a newly allocated enumeration set.  The possible elements of the set are the symbols in ''enum-type''. The set is initialized to contain the ''elements''.

`(list->enum-set `''enum-type''` `''list''`)`

Returns a newly allocated enumeration set.  The possible elements of the set are the symbols in ''enum-type''. The set is initialized to contain the elements of ''list''.

`(enum-set-complement `''enum-set''`)`

Returns a newly allocated enumeration set that is the complement of ''enum-set''.

`(enum-set-complement! `''enum-set''`)`

Mutates ''enum-set'' to a new set that is the complement of ''enum-set''.

`(enum-set-projection `''enum-set''` `''enum-type''`)`

Returns 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''.

`(define-enumeration `<type-name>` (`<symbol> ...`)` <constructor>`)`

Defines a newly allocated enumeration type and provides macros for constructing its members and sets.  It is a definition and can appear anywhere that other definitions can appear.  The <symbol>s are in the enumeration type.  '''Issue: do we need define-enumeration?'''

The identifier <type-name> is bound to a syntax definition which accepts a symbol as its argument and returns the symbol if it is in the enumeration type.  It is a syntax error if the symbol is not in the enumeration type.

The identifier <constructor> is bound to a syntax definition which accepts symbols as its arguments and returns an enumeration set containing those symbols.  It is a syntax error if any of the symbols are not in the enumeration type.

== Conversions ==

The basic set is used as the pivot between different kinds of specialized sets.  In particular, `set->bag`, `set->integer-set`, `set->bag`, `bag->set`, `integer-set->set`, and `enum-set->set` take one argument and do the obvious thing.  `set->integer-set` takes two arguments, ''limit'' and the set.  `set->enum-set` also takes two arguments, ''enum-type'' and the set.

time

2012-12-03 13:59:02

version

14