Version 14 (modified by cowan, 4 years ago) (diff) |
---|

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