153dc01ccd
* Wrong contract for syntax-local-value in the documentation. * Clarified signature in documentation for expand-import, expand-export and pre-expand-export * Corrected typo in documentation for "for". * Fixed error message for function which seems to have been renamed in the docs * Fixed typo in a comment in the tests * Fixed a typo in the documentation for set-subtract. * Use double ellipses for the free-id-table-set*, free-id-table-set*!, bound-id-table-set* and bound-id-table-set*! operations
948 lines
36 KiB
Racket
948 lines
36 KiB
Racket
#lang scribble/doc
|
|
@(require "mz.rkt" (for-label racket/set))
|
|
|
|
@title[#:tag "sets"]{Sets}
|
|
@(define set-eval (make-base-eval))
|
|
@examples[#:hidden #:eval set-eval (require racket/set)]
|
|
|
|
A @deftech{set} represents a collection of distinct elements. The following
|
|
datatypes are all sets:
|
|
|
|
@itemize[
|
|
|
|
@item{@techlink{hash sets};}
|
|
|
|
@item{@techlink{lists} using @racket[equal?] to compare elements; and}
|
|
|
|
@item{@techlink{structures} whose types implement the @racket[gen:set]
|
|
@tech{generic interface}.}
|
|
|
|
]
|
|
|
|
@note-lib[racket/set]
|
|
|
|
@section{Hash Sets}
|
|
|
|
A @deftech{hash set} is a set whose elements are compared via @racket[equal?],
|
|
@racket[eqv?], or @racket[eq?] and partitioned via @racket[equal-hash-code],
|
|
@racket[eqv-hash-code], or @racket[eq-hash-code]. A hash set is either
|
|
immutable or mutable; mutable hash sets retain their elements either strongly
|
|
or weakly.
|
|
|
|
@margin-note{Like operations on immutable hash tables, ``constant time'' hash
|
|
set operations actually require @math{O(log N)} time for a set of size
|
|
@math{N}.}
|
|
|
|
A hash set can be used as a @tech{stream} (see @secref["streams"]) and thus as
|
|
a single-valued @tech{sequence} (see @secref["sequences"]). The elements of the
|
|
set serve as elements of the stream or sequence. If an element is added to or
|
|
removed from the hash set during iteration, then an iteration step may fail
|
|
with @racket[exn:fail:contract], or the iteration may skip or duplicate
|
|
elements. See also @racket[in-set].
|
|
|
|
Two hash sets are @racket[equal?] when they use the same element-comparison
|
|
procedure (@racket[equal?], @racket[eqv?], or @racket[eq?]), both hold elements
|
|
strongly or weakly, have the same mutability, and have equivalent
|
|
elements. Immutable hash sets support effectively constant-time access and
|
|
update, just like mutable hash sets; the constant on immutable operations is
|
|
usually larger, but the functional nature of immutable hash sets can pay off in
|
|
certain algorithms.
|
|
|
|
All hash sets @impl{implement} @racket[set->stream],
|
|
@racket[set-empty?], @racket[set-member?], @racket[set-count],
|
|
@racket[subset?], @racket[proper-subset?], @racket[set-map],
|
|
@racket[set-for-each], @racket[set-copy], @racket[set-copy-clear],
|
|
@racket[set->list], and @racket[set-first]. Immutable hash sets in
|
|
addition @impl{implement} @racket[set-add], @racket[set-remove],
|
|
@racket[set-clear], @racket[set-union], @racket[set-intersect],
|
|
@racket[set-subtract], and @racket[set-symmetric-difference]. Mutable
|
|
hash sets in addition @impl{implement} @racket[set-add!],
|
|
@racket[set-remove!], @racket[set-clear!], @racket[set-union!],
|
|
@racket[set-intersect!], @racket[set-subtract!], and
|
|
@racket[set-symmetric-difference!].
|
|
|
|
Operations on sets that contain elements that are mutated are
|
|
unpredictable in much the same way that @tech{hash table} operations are
|
|
unpredictable when keys are mutated.
|
|
|
|
@deftogether[(
|
|
@defproc[(set-equal? [x any/c]) boolean?]
|
|
@defproc[(set-eqv? [x any/c]) boolean?]
|
|
@defproc[(set-eq? [x any/c]) boolean?]
|
|
)]{
|
|
|
|
Returns @racket[#t] if @racket[x] is a @tech{hash set} that compares
|
|
elements with @racket[equal?], @racket[eqv?], or @racket[eq?], respectively;
|
|
returns @racket[#f] otherwise.
|
|
|
|
}
|
|
|
|
@deftogether[(
|
|
@defproc[(set? [x any/c]) boolean?]
|
|
@defproc[(set-mutable? [x any/c]) boolean?]
|
|
@defproc[(set-weak? [x any/c]) boolean?]
|
|
)]{
|
|
|
|
Returns @racket[#t] if @racket[x] is a @tech{hash set} that is respectively
|
|
immutable, mutable with strongly-held keys, or mutable with weakly-held keys;
|
|
returns @racket[#f] otherwise.
|
|
|
|
}
|
|
|
|
@deftogether[(
|
|
@defproc[(set [v any/c] ...) (and/c generic-set? set-equal? set?)]
|
|
@defproc[(seteqv [v any/c] ...) (and/c generic-set? set-eqv? set?)]
|
|
@defproc[(seteq [v any/c] ...) (and/c generic-set? set-eq? set?)]
|
|
@defproc[(mutable-set [v any/c] ...) (and/c generic-set? set-equal? set-mutable?)]
|
|
@defproc[(mutable-seteqv [v any/c] ...) (and/c generic-set? set-eqv? set-mutable?)]
|
|
@defproc[(mutable-seteq [v any/c] ...) (and/c generic-set? set-eq? set-mutable?)]
|
|
@defproc[(weak-set [v any/c] ...) (and/c generic-set? set-equal? set-weak?)]
|
|
@defproc[(weak-seteqv [v any/c] ...) (and/c generic-set? set-eqv? set-weak?)]
|
|
@defproc[(weak-seteq [v any/c] ...) (and/c generic-set? set-eq? set-weak?)]
|
|
)]{
|
|
|
|
Creates a @tech{hash set} with the given @racket[v]s as elements. The
|
|
elements are added in the order that they appear as arguments, so in the case
|
|
of sets that use @racket[equal?] or @racket[eqv?], an earlier element may be
|
|
replaced by a later element that is @racket[equal?] or @racket[eqv?] but not
|
|
@racket[eq?].
|
|
|
|
}
|
|
|
|
@deftogether[(
|
|
@defproc[(list->set [lst list?]) (and/c generic-set? set-equal? set?)]
|
|
@defproc[(list->seteqv [lst list?]) (and/c generic-set? set-eqv? set?)]
|
|
@defproc[(list->seteq [lst list?]) (and/c generic-set? set-eq? set?)]
|
|
@defproc[(list->mutable-set [lst list?]) (and/c generic-set? set-equal? set-mutable?)]
|
|
@defproc[(list->mutable-seteqv [lst list?]) (and/c generic-set? set-eqv? set-mutable?)]
|
|
@defproc[(list->mutable-seteq [lst list?]) (and/c generic-set? set-eq? set-mutable?)]
|
|
@defproc[(list->weak-set [lst list?]) (and/c generic-set? set-equal? set-weak?)]
|
|
@defproc[(list->weak-seteqv [lst list?]) (and/c generic-set? set-eqv? set-weak?)]
|
|
@defproc[(list->weak-seteq [lst list?]) (and/c generic-set? set-eq? set-weak?)]
|
|
)]{
|
|
|
|
Creates a @tech{hash set} with the elements of the given @racket[lst] as
|
|
the elements of the set. Equivalent to @racket[(apply set lst)],
|
|
@racket[(apply seteqv lst)], @racket[(apply seteq lst)], and so on,
|
|
respectively.
|
|
|
|
}
|
|
|
|
@deftogether[(
|
|
@defform[(for/set (for-clause ...) body ...+)]
|
|
@defform[(for/seteq (for-clause ...) body ...+)]
|
|
@defform[(for/seteqv (for-clause ...) body ...+)]
|
|
@defform[(for*/set (for-clause ...) body ...+)]
|
|
@defform[(for*/seteq (for-clause ...) body ...+)]
|
|
@defform[(for*/seteqv (for-clause ...) body ...+)]
|
|
@defform[(for/mutable-set (for-clause ...) body ...+)]
|
|
@defform[(for/mutable-seteq (for-clause ...) body ...+)]
|
|
@defform[(for/mutable-seteqv (for-clause ...) body ...+)]
|
|
@defform[(for*/mutable-set (for-clause ...) body ...+)]
|
|
@defform[(for*/mutable-seteq (for-clause ...) body ...+)]
|
|
@defform[(for*/mutable-seteqv (for-clause ...) body ...+)]
|
|
@defform[(for/weak-set (for-clause ...) body ...+)]
|
|
@defform[(for/weak-seteq (for-clause ...) body ...+)]
|
|
@defform[(for/weak-seteqv (for-clause ...) body ...+)]
|
|
@defform[(for*/weak-set (for-clause ...) body ...+)]
|
|
@defform[(for*/weak-seteq (for-clause ...) body ...+)]
|
|
@defform[(for*/weak-seteqv (for-clause ...) body ...+)]
|
|
)]{
|
|
|
|
Analogous to @racket[for/list] and @racket[for*/list], but to
|
|
construct a @tech{hash set} instead of a list.
|
|
}
|
|
|
|
@deftogether[(
|
|
@defproc[(in-immutable-set [st set?]) sequence?]
|
|
@defproc[(in-mutable-set [st set-mutable?]) sequence?]
|
|
@defproc[(in-weak-set [st set-weak?]) sequence?]
|
|
)]{
|
|
|
|
Explicitly converts a specific kind of @tech{hash set} to a sequence for
|
|
use with @racket[for] forms.
|
|
|
|
As with @racket[in-list] and some other sequence constructors,
|
|
@racket[in-immutable-set] is more performant when it appears directly in a
|
|
@racket[for] clause.
|
|
|
|
These sequence constructors are compatible with
|
|
@secref["Custom_Hash_Sets" #:doc '(lib "scribblings/reference/reference.scrbl")].
|
|
|
|
}
|
|
|
|
@section{Set Predicates and Contracts}
|
|
|
|
@defproc[(generic-set? [v any/c]) boolean?]{
|
|
|
|
Returns @racket[#t] if @racket[v] is a @tech{set}; returns @racket[#f]
|
|
otherwise.
|
|
|
|
@examples[
|
|
#:eval set-eval
|
|
(generic-set? (list 1 2 3))
|
|
(generic-set? (set 1 2 3))
|
|
(generic-set? (mutable-seteq 1 2 3))
|
|
(generic-set? (vector 1 2 3))
|
|
]
|
|
|
|
}
|
|
|
|
@defproc[(set-implements? [st generic-set?] [sym symbol?] ...) boolean?]{
|
|
|
|
Returns @racket[#t] if @racket[st] implements all of the methods from
|
|
@racket[gen:set] named by the @racket[sym]s; returns @racket[#f] otherwise.
|
|
Fallback implementations do not affect the result; @racket[st] may support the
|
|
given methods via fallback implementations yet produce @racket[#f].
|
|
|
|
@examples[
|
|
#:eval set-eval
|
|
(set-implements? (list 1 2 3) 'set-add)
|
|
(set-implements? (list 1 2 3) 'set-add!)
|
|
(set-implements? (set 1 2 3) 'set-add)
|
|
(set-implements? (set 1 2 3) 'set-add!)
|
|
(set-implements? (mutable-seteq 1 2 3) 'set-add)
|
|
(set-implements? (mutable-seteq 1 2 3) 'set-add!)
|
|
(set-implements? (weak-seteqv 1 2 3) 'set-remove 'set-remove!)
|
|
]
|
|
|
|
}
|
|
|
|
@defproc[(set-implements/c [sym symbol?] ...) flat-contract?]{
|
|
|
|
Recognizes sets that support all of the methods from @racket[gen:set]
|
|
named by the @racket[sym]s.
|
|
|
|
}
|
|
|
|
@defproc[(set/c [elem/c chaperone-contract?]
|
|
[#:cmp cmp
|
|
(or/c 'dont-care 'equal 'eqv 'eq)
|
|
'dont-care]
|
|
[#:kind kind
|
|
(or/c 'dont-care 'immutable 'mutable 'weak 'mutable-or-weak)
|
|
'immutable]
|
|
[#:lazy? lazy? any/c
|
|
(not (and (equal? kind 'immutable)
|
|
(flat-contract? elem/c)))]
|
|
[#:equal-key/c equal-key/c contract? any/c])
|
|
contract?]{
|
|
|
|
Constructs a contract that recognizes sets whose elements match
|
|
@racket[elem/c].
|
|
|
|
If @racket[kind] is @racket['immutable], @racket['mutable], or
|
|
@racket['weak], the resulting contract accepts only @tech{hash sets} that
|
|
are respectively immutable, mutable with strongly-held keys, or mutable with
|
|
weakly-held keys. If @racket[kind] is @racket['mutable-or-weak], the
|
|
resulting contract accepts any mutable @tech{hash sets}, regardless of
|
|
key-holding strength.
|
|
|
|
If @racket[cmp] is @racket['equal], @racket['eqv], or @racket['eq], the
|
|
resulting contract accepts only @tech{hash sets} that compare elements
|
|
using @racket[equal?], @racket[eqv?], or @racket[eq?], respectively.
|
|
|
|
If @racket[cmp] is @racket['eqv] or @racket['eq], then @racket[elem/c] must
|
|
be a @tech{flat contract}.
|
|
|
|
If @racket[cmp] and @racket[kind] are both @racket['dont-care], then the
|
|
resulting contract will accept any kind of set, not just @tech{hash
|
|
sets}.
|
|
|
|
If @racket[lazy?] is not @racket[#f], then the elements of the set are not checked
|
|
immediately by the contract and only the set itself is checked (according to the
|
|
@racket[cmp] and @racket[kind] arguments). If @racket[lazy?] is
|
|
@racket[#f], then the elements are checked immediately by the contract.
|
|
The @racket[lazy?] argument is ignored when the set contract accepts generic sets
|
|
(i.e., when @racket[cmp] and @racket[kind] are both @racket['dont-care]); in that
|
|
case, the value being checked in that case is a @racket[list?], then the contract
|
|
is not lazy otherwise the contract is lazy.
|
|
|
|
If @racket[kind] allows mutable sets (i.e., is @racket['dont-care],
|
|
@racket['mutable], @racket['weak], or
|
|
@racket['mutable-or-weak]) and @racket[lazy?] is @racket[#f], then the elements
|
|
are checked both immediately and when they are accessed from the set.
|
|
|
|
The @racket[equal-key/c] contract is used when values are passed to the comparison
|
|
and hashing functions used internally.
|
|
|
|
The result contract will be a @tech{flat contract} when @racket[elem/c]
|
|
and @racket[equal-key/c] are both @tech{flat contracts},
|
|
@racket[lazy?] is @racket[#f], and @racket[kind] is @racket['immutable].
|
|
The result will be a @tech{chaperone contract} when @racket[elem/c] is a
|
|
@tech{chaperone contract}.
|
|
}
|
|
|
|
@section{Generic Set Interface}
|
|
|
|
|
|
@defidform[gen:set]{
|
|
|
|
A @tech{generic interface} (see @secref["struct-generics"]) that
|
|
supplies set method implementations for a structure type via the
|
|
@racket[#:methods] option of @racket[struct] definitions. This interface can
|
|
be used to implement any of the methods documented as
|
|
@secref["set-methods"].
|
|
|
|
@examples[
|
|
#:eval set-eval
|
|
(struct binary-set [integer]
|
|
#:transparent
|
|
#:methods gen:set
|
|
[(define (set-member? st i)
|
|
(bitwise-bit-set? (binary-set-integer st) i))
|
|
(define (set-add st i)
|
|
(binary-set (bitwise-ior (binary-set-integer st)
|
|
(arithmetic-shift 1 i))))
|
|
(define (set-remove st i)
|
|
(binary-set (bitwise-and (binary-set-integer st)
|
|
(bitwise-not (arithmetic-shift 1 i)))))])
|
|
(define bset (binary-set 5))
|
|
bset
|
|
(generic-set? bset)
|
|
(set-member? bset 0)
|
|
(set-member? bset 1)
|
|
(set-member? bset 2)
|
|
(set-add bset 4)
|
|
(set-remove bset 2)
|
|
]
|
|
|
|
}
|
|
|
|
@subsection[#:tag "set-methods"]{Set Methods}
|
|
|
|
@(define (supp . args) (apply tech #:key "supported generic method" args))
|
|
@(define (impl . args) (apply tech #:key "implemented generic method" args))
|
|
|
|
The methods of @racket[gen:set] can be classified into three categories, as determined by their fallback implementations:
|
|
|
|
@itemlist[#:style 'ordered
|
|
@item{methods with no fallbacks,}
|
|
@item{methods whose fallbacks depend on other, non-fallback methods,}
|
|
@item{and methods whose fallbacks can depend on either fallback or non-fallback methods.}]
|
|
|
|
As an example, implementing the following methods would guarantee that all the methods in @racket[gen:set] would at least have a fallback method:
|
|
|
|
@itemlist[@item{@racket[set-member?]}
|
|
@item{@racket[set-add]}
|
|
@item{@racket[set-add!]}
|
|
@item{@racket[set-remove]}
|
|
@item{@racket[set-remove!]}
|
|
@item{@racket[set-first]}
|
|
@item{@racket[set-empty?]}
|
|
@item{@racket[set-copy-clear]}]
|
|
|
|
There may be other such subsets of methods that would guarantee at least a fallback for every method.
|
|
|
|
@defproc[(set-member? [st generic-set?] [v any/c]) boolean?]{
|
|
|
|
Returns @racket[#t] if @racket[v] is in @racket[st], @racket[#f]
|
|
otherwise. Has no fallback.
|
|
|
|
}
|
|
|
|
@defproc[(set-add [st generic-set?] [v any/c]) generic-set?]{
|
|
|
|
Produces a set that includes @racket[v] plus all elements of
|
|
@racket[st]. This operation runs in constant time for @tech{hash sets}. Has no fallback.
|
|
|
|
}
|
|
|
|
@defproc[(set-add! [st generic-set?] [v any/c]) void?]{
|
|
|
|
Adds the element @racket[v] to @racket[st]. This operation runs in constant
|
|
time for @tech{hash sets}. Has no fallback.
|
|
|
|
}
|
|
|
|
@defproc[(set-remove [st generic-set?] [v any/c]) generic-set?]{
|
|
|
|
Produces a set that includes all elements of @racket[st] except
|
|
@racket[v]. This operation runs in constant time for @tech{hash sets}. Has no fallback.
|
|
|
|
}
|
|
|
|
@defproc[(set-remove! [st generic-set?] [v any/c]) void?]{
|
|
|
|
Removes the element @racket[v] from @racket[st]. This operation runs in constant
|
|
time for @tech{hash sets}. Has no fallback.
|
|
|
|
}
|
|
|
|
@defproc[(set-empty? [st generic-set?]) boolean?]{
|
|
|
|
Returns @racket[#t] if @racket[st] has no members; returns @racket[#f]
|
|
otherwise.
|
|
|
|
Supported for any @racket[st] that @impl{implements} @racket[set->stream] or
|
|
@racket[set-count].
|
|
|
|
}
|
|
|
|
@defproc[(set-count [st generic-set?]) exact-nonnegative-integer?]{
|
|
|
|
Returns the number of elements in @racket[st].
|
|
|
|
Supported for any @racket[st] that @supp{supports} @racket[set->stream].
|
|
|
|
}
|
|
|
|
@defproc[(set-first [st (and/c generic-set? (not/c set-empty?))]) any/c]{
|
|
|
|
Produces an unspecified element of @racket[st]. Multiple uses of
|
|
@racket[set-first] on @racket[st] produce the same result.
|
|
|
|
Supported for any @racket[st] that @impl{implements} @racket[set->stream].
|
|
|
|
}
|
|
|
|
|
|
@defproc[(set-rest [st (and/c generic-set? (not/c set-empty?))]) generic-set?]{
|
|
|
|
Produces a set that includes all elements of @racket[st] except
|
|
@racket[(set-first st)].
|
|
|
|
Supported for any @racket[st] that @impl{implements} @racket[set-remove] and either
|
|
@racket[set-first] or @racket[set->stream].
|
|
|
|
}
|
|
|
|
@defproc[(set->stream [st generic-set?]) stream?]{
|
|
|
|
Produces a stream containing the elements of @racket[st].
|
|
|
|
Supported for any @racket[st] that @impl{implements}:
|
|
@itemlist[@item{@racket[set->list]}
|
|
@item{@racket[in-set]}
|
|
@item{@racket[set-empty?], @racket[set-first], @racket[set-rest]}
|
|
@item{@racket[set-empty?], @racket[set-first], @racket[set-remove]}
|
|
@item{@racket[set-count], @racket[set-first], @racket[set-rest]}
|
|
@item{@racket[set-count], @racket[set-first], @racket[set-remove]}]
|
|
}
|
|
|
|
@defproc[(set-copy [st generic-set?]) generic-set?]{
|
|
|
|
Produces a new, mutable set of the same type and with the same elements as
|
|
@racket[st].
|
|
|
|
Supported for any @racket[st] that @supp{supports} @racket[set->stream] and
|
|
@impl{implements} @racket[set-copy-clear] and @racket[set-add!].
|
|
|
|
}
|
|
|
|
@defproc[(set-copy-clear [st generic-set?]) (and/c generic-set? set-empty?)]{
|
|
|
|
Produces a new, empty set of the same type, mutability, and key strength as
|
|
@racket[st].
|
|
|
|
A difference between @racket[set-copy-clear] and @racket[set-clear] is
|
|
that the latter conceptually iterates @racket[set-remove] on the given
|
|
set, and so it preserves any contract on the given set. The
|
|
@racket[set-copy-clear] function produces a new set without any
|
|
contracts.
|
|
|
|
The @racket[set-copy-clear] function must call concrete set constructors
|
|
and thus has no generic fallback.
|
|
}
|
|
|
|
@defproc[(set-clear [st generic-set?]) (and/c generic-set? set-empty?)]{
|
|
|
|
Produces a set like @racket[st] but with all elements removed.
|
|
|
|
Supported for any @racket[st] that @impl{implements} @racket[set-remove] and @supp{supports}
|
|
@racket[set->stream].
|
|
|
|
}
|
|
|
|
@defproc[(set-clear! [st generic-set?]) void?]{
|
|
|
|
Removes all elements from @racket[st].
|
|
|
|
Supported for any @racket[st] that @impl{implements} @racket[set-remove!] and either
|
|
@supp{supports} @racket[set->stream] or @impl{implements} @racket[set-first] and either @racket[set-count] or @racket[set-empty?].
|
|
|
|
}
|
|
|
|
@defproc[(set-union [st0 generic-set?] [st generic-set?] ...) generic-set?]{
|
|
|
|
Produces a set of the same type as @racket[st0] that includes the elements from
|
|
@racket[st0] and all of the @racket[st]s.
|
|
|
|
If @racket[st0] is a list, each @racket[st] must also be a list. This
|
|
operation runs on lists in time proportional to the total size of the
|
|
@racket[st]s times the size of the result.
|
|
|
|
If @racket[st0] is a @tech{hash set}, each @racket[st] must also be a
|
|
@tech{hash set} that uses the same comparison function (@racket[equal?],
|
|
@racket[eqv?], or @racket[eq?]). The mutability and key strength of the hash
|
|
sets may differ. This operation runs on hash sets in time proportional to the
|
|
total size of all of the sets except the largest immutable set.
|
|
|
|
At least one set must be provided to @racket[set-union] to determine the type
|
|
of the resulting set (list, hash set, etc.). If there is a case where
|
|
@racket[set-union] may be applied to zero arguments, instead pass an empty set
|
|
of the intended type as the first argument.
|
|
|
|
Supported for any @racket[st] that @impl{implements} @racket[set-add] and @supp{supports} @racket[set->stream].
|
|
|
|
@examples[#:eval set-eval
|
|
(set-union (set))
|
|
(set-union (seteq))
|
|
(set-union (set 1 2) (set 2 3))
|
|
(set-union (list 1 2) (list 2 3))
|
|
(eval:error (set-union (set 1 2) (seteq 2 3))) (code:comment "Sets of different types cannot be unioned")
|
|
]}
|
|
|
|
@defproc[(set-union! [st0 generic-set?] [st generic-set?] ...) void?]{
|
|
|
|
Adds the elements from all of the @racket[st]s to @racket[st0].
|
|
|
|
If @racket[st0] is a @tech{hash set}, each @racket[st] must also be a
|
|
@tech{hash set} that uses the same comparison function (@racket[equal?],
|
|
@racket[eqv?], or @racket[eq?]). The mutability and key strength of the hash
|
|
sets may differ. This operation runs on hash sets in time proportional to the
|
|
total size of the @racket[st]s.
|
|
|
|
Supported for any @racket[st] that @impl{implements} @racket[set-add!] and @supp{supports} @racket[set->stream].
|
|
|
|
}
|
|
|
|
@defproc[(set-intersect [st0 generic-set?] [st generic-set?] ...) generic-set?]{
|
|
|
|
Produces a set of the same type as @racket[st0] that includes the elements from
|
|
@racket[st0] that are also contained by all of the @racket[st]s.
|
|
|
|
If @racket[st0] is a list, each @racket[st] must also be a list. This
|
|
operation runs on lists in time proportional to the total size of the
|
|
@racket[st]s times the size of @racket[st0].
|
|
|
|
If @racket[st0] is a @tech{hash set}, each @racket[st] must also be a
|
|
@tech{hash set} that uses the same comparison function (@racket[equal?],
|
|
@racket[eqv?], or @racket[eq?]). The mutability and key strength of the hash
|
|
sets may differ. This operation runs on hash sets in time proportional to the
|
|
size of the smallest immutable set.
|
|
|
|
Supported for any @racket[st] that @impl{implements} either @racket[set-remove] or
|
|
both @racket[set-clear] and @racket[set-add], and @supp{supports} @racket[set->stream].
|
|
|
|
}
|
|
|
|
@defproc[(set-intersect! [st0 generic-set?] [st generic-set?] ...) void?]{
|
|
|
|
Removes every element from @racket[st0] that is not contained by all of the
|
|
@racket[st]s.
|
|
|
|
If @racket[st0] is a @tech{hash set}, each @racket[st] must also be a
|
|
@tech{hash set} that uses the same comparison function (@racket[equal?],
|
|
@racket[eqv?], or @racket[eq?]). The mutability and key strength of the hash
|
|
sets may differ. This operation runs on hash sets in time proportional to the
|
|
size of @racket[st0].
|
|
|
|
Supported for any @racket[st] that @impl{implements} @racket[set-remove!] and @supp{supports} @racket[set->stream].
|
|
|
|
}
|
|
|
|
@defproc[(set-subtract [st0 generic-set?] [st generic-set?] ...) generic-set?]{
|
|
|
|
Produces a set of the same type as @racket[st0] that includes the elements from
|
|
@racket[st0] that are not contained by any of the @racket[st]s.
|
|
|
|
If @racket[st0] is a list, each @racket[st] must also be a list. This
|
|
operation runs on lists in time proportional to the total size of the
|
|
@racket[st]s times the size of @racket[st0].
|
|
|
|
If @racket[st0] is a @tech{hash set}, each @racket[st] must also be a
|
|
@tech{hash set} that uses the same comparison function (@racket[equal?],
|
|
@racket[eqv?], or @racket[eq?]). The mutability and key strength of the hash
|
|
sets may differ. This operation runs on hash sets in time proportional to the
|
|
size of @racket[st0].
|
|
|
|
Supported for any @racket[st] that @impl{implements} either @racket[set-remove] or
|
|
both @racket[set-clear] and @racket[set-add], and @supp{supports} @racket[set->stream].
|
|
|
|
}
|
|
|
|
@defproc[(set-subtract! [st0 generic-set?] [st generic-set?] ...) void?]{
|
|
|
|
Removes every element from @racket[st0] that is contained by any of the
|
|
@racket[st]s.
|
|
|
|
If @racket[st0] is a @tech{hash set}, each @racket[st] must also be a
|
|
@tech{hash set} that uses the same comparison function (@racket[equal?],
|
|
@racket[eqv?], or @racket[eq?]). The mutability and key strength of the hash
|
|
sets may differ. This operation runs on hash sets in time proportional to the
|
|
size of @racket[st0].
|
|
|
|
Supported for any @racket[st] that @impl{implements} @racket[set-remove!] and @supp{supports} @racket[set->stream].
|
|
|
|
}
|
|
|
|
@defproc[(set-symmetric-difference [st0 generic-set?] [st generic-set?] ...) generic-set?]{
|
|
|
|
Produces a set of the same type as @racket[st0] that includes all of the
|
|
elements contained an odd number of times in @racket[st0] and the
|
|
@racket[st]s.
|
|
|
|
If @racket[st0] is a list, each @racket[st] must also be a list. This
|
|
operation runs on lists in time proportional to the total size of the
|
|
@racket[st]s times the size of @racket[st0].
|
|
|
|
If @racket[st0] is a @tech{hash set}, each @racket[st] must also be a
|
|
@tech{hash set} that uses the same comparison function (@racket[equal?],
|
|
@racket[eqv?], or @racket[eq?]). The mutability and key strength of the hash
|
|
sets may differ. This operation runs on hash sets in time proportional to the
|
|
total size of all of the sets except the largest immutable set.
|
|
|
|
Supported for any @racket[st] that @impl{implements} @racket[set-remove] or both @racket[set-clear] and @racket[set-add], and @supp{supports} @racket[set->stream].
|
|
|
|
@examples[#:eval set-eval
|
|
(set-symmetric-difference (set 1) (set 1 2) (set 1 2 3))
|
|
]
|
|
|
|
}
|
|
|
|
@defproc[(set-symmetric-difference! [st0 generic-set?] [st generic-set?] ...) void?]{
|
|
|
|
Adds and removes elements of @racket[st0] so that it includes all of the
|
|
elements contained an odd number of times in the @racket[st]s and the
|
|
original contents of @racket[st0].
|
|
|
|
If @racket[st0] is a @tech{hash set}, each @racket[st] must also be a
|
|
@tech{hash set} that uses the same comparison function (@racket[equal?],
|
|
@racket[eqv?], or @racket[eq?]). The mutability and key strength of the hash
|
|
sets may differ. This operation runs on hash sets in time proportional to the
|
|
total size of the @racket[st]s.
|
|
|
|
Supported for any @racket[st] that @impl{implements} @racket[set-remove!] and @supp{supports} @racket[set->stream].
|
|
|
|
}
|
|
|
|
@defproc[(set=? [st generic-set?] [st2 generic-set?]) boolean?]{
|
|
|
|
Returns @racket[#t] if @racket[st] and @racket[st2] contain the same
|
|
members; returns @racket[#f] otherwise.
|
|
|
|
If @racket[st0] is a list, each @racket[st] must also be a list. This
|
|
operation runs on lists in time proportional to the size of @racket[st] times
|
|
the size of @racket[st2].
|
|
|
|
If @racket[st0] is a @tech{hash set}, each @racket[st] must also be a
|
|
@tech{hash set} that uses the same comparison function (@racket[equal?],
|
|
@racket[eqv?], or @racket[eq?]). The mutability and key strength of the hash
|
|
sets may differ. This operation runs on hash sets in time proportional to the
|
|
size of @racket[st] plus the size of @racket[st2].
|
|
|
|
Supported for any @racket[st] and @racket[st2] that both @supp{support}
|
|
@racket[subset?]; also supported for any if @racket[st2] that @impl{implements}
|
|
@racket[set=?] regardless of @racket[st].
|
|
|
|
@examples[#:eval set-eval
|
|
(set=? (list 1 2) (list 2 1))
|
|
(set=? (set 1) (set 1 2 3))
|
|
(set=? (set 1 2 3) (set 1))
|
|
(set=? (set 1 2 3) (set 1 2 3))
|
|
(set=? (seteq 1 2) (mutable-seteq 2 1))
|
|
(eval:error (set=? (seteq 1 2) (seteqv 1 2))) (code:comment "Sets of different types cannot be compared")
|
|
]
|
|
|
|
}
|
|
|
|
@defproc[(subset? [st generic-set?] [st2 generic-set?]) boolean?]{
|
|
|
|
Returns @racket[#t] if @racket[st2] contains every member of @racket[st];
|
|
returns @racket[#f] otherwise.
|
|
|
|
If @racket[st0] is a list, each @racket[st] must also be a list. This
|
|
operation runs on lists in time proportional to the size of @racket[st] times
|
|
the size of @racket[st2].
|
|
|
|
If @racket[st0] is a @tech{hash set}, each @racket[st] must also be a
|
|
@tech{hash set} that uses the same comparison function (@racket[equal?],
|
|
@racket[eqv?], or @racket[eq?]). The mutability and key strength of the hash
|
|
sets may differ. This operation runs on hash sets in time proportional to the
|
|
size of @racket[st].
|
|
|
|
Supported for any @racket[st] that @supp{supports} @racket[set->stream].
|
|
|
|
@examples[#:eval set-eval
|
|
(subset? (set 1) (set 1 2 3))
|
|
(subset? (set 1 2 3) (set 1))
|
|
(subset? (set 1 2 3) (set 1 2 3))
|
|
]
|
|
|
|
}
|
|
|
|
@defproc[(proper-subset? [st generic-set?] [st2 generic-set?]) boolean?]{
|
|
|
|
Returns @racket[#t] if @racket[st2] contains every member of @racket[st] and at
|
|
least one additional element; returns @racket[#f] otherwise.
|
|
|
|
If @racket[st0] is a list, each @racket[st] must also be a list. This
|
|
operation runs on lists in time proportional to the size of @racket[st] times
|
|
the size of @racket[st2].
|
|
|
|
If @racket[st0] is a @tech{hash set}, each @racket[st] must also be a
|
|
@tech{hash set} that uses the same comparison function (@racket[equal?],
|
|
@racket[eqv?], or @racket[eq?]). The mutability and key strength of the hash
|
|
sets may differ. This operation runs on hash sets in time proportional to the
|
|
size of @racket[st] plus the size of @racket[st2].
|
|
|
|
Supported for any @racket[st] and @racket[st2] that both @supp{support}
|
|
@racket[subset?].
|
|
|
|
@examples[#:eval set-eval
|
|
(proper-subset? (set 1) (set 1 2 3))
|
|
(proper-subset? (set 1 2 3) (set 1))
|
|
(proper-subset? (set 1 2 3) (set 1 2 3))
|
|
]
|
|
|
|
}
|
|
|
|
@defproc[(set->list [st generic-set?]) list?]{
|
|
|
|
Produces a list containing the elements of @racket[st].
|
|
|
|
Supported for any @racket[st] that @supp{supports} @racket[set->stream].
|
|
|
|
}
|
|
|
|
@defproc[(set-map [st generic-set?]
|
|
[proc (any/c . -> . any/c)])
|
|
(listof any/c)]{
|
|
|
|
Applies the procedure @racket[proc] to each element in
|
|
@racket[st] in an unspecified order, accumulating the results
|
|
into a list.
|
|
|
|
Supported for any @racket[st] that @supp{supports} @racket[set->stream].
|
|
|
|
}
|
|
|
|
|
|
@defproc[(set-for-each [st generic-set?]
|
|
[proc (any/c . -> . any)])
|
|
void?]{
|
|
|
|
Applies @racket[proc] to each element in @racket[st] (for the
|
|
side-effects of @racket[proc]) in an unspecified order.
|
|
|
|
Supported for any @racket[st] that @supp{supports} @racket[set->stream].
|
|
|
|
}
|
|
|
|
@defproc[(in-set [st generic-set?]) sequence?]{
|
|
|
|
Explicitly converts a set to a sequence for use with @racket[for] and
|
|
other forms.
|
|
|
|
Supported for any @racket[st] that @supp{supports} @racket[set->stream].
|
|
|
|
}
|
|
|
|
@defproc[(impersonate-hash-set [st (or/c mutable-set? weak-set?)]
|
|
[inject-proc (or/c #f (-> set? any/c any/c))]
|
|
[add-proc (or/c #f (-> set? any/c any/c))]
|
|
[shrink-proc (or/c #f (-> set? any/c any/c))]
|
|
[extract-proc (or/c #f (-> set? any/c any/c))]
|
|
[clear-proc (or/c #f (-> set? any)) #f]
|
|
[equal-key-proc (or/c #f (-> set? any/c any/c)) #f]
|
|
[prop impersonator-property?]
|
|
[prop-val any/c] ... ...)
|
|
(and/c (or/c mutable-set? weak-set?) impersonator?)]{
|
|
Impersonates @racket[st], redirecting various set operations via the given procedures.
|
|
|
|
The @racket[inject-proc] procedure
|
|
is called whenever an element is temporarily put into the set for the purposes
|
|
of comparing it with other elements that may already be in the set. For example,
|
|
when evaluating @racket[(set-member? s e)], @racket[e] will be passed to the
|
|
@racket[inject-proc] before comparing it with other elements of @racket[s].
|
|
|
|
The @racket[add-proc] procedure is called when adding an element to a set, e.g.,
|
|
via @racket[set-add] or @racket[set-add!]. The result of the @racket[add-proc] is
|
|
stored in the set.
|
|
|
|
The @racket[shrink-proc] procedure is called when building a new set with
|
|
one fewer element. For example, when evaluating @racket[(set-remove s e)]
|
|
or @racket[(set-remove! s e)],
|
|
an element is removed from a set, e.g.,
|
|
via @racket[set-remove] or @racket[set-remove!]. The result of the @racket[shrink-proc]
|
|
is the element actually removed from the set.
|
|
|
|
The @racket[extract-proc] procedure is called when an element is pulled out of
|
|
a set, e.g., by @racket[set-first]. The result of the @racket[extract-proc] is
|
|
the element actually produced by from the set.
|
|
|
|
The @racket[clear-proc] is called by @racket[set-clear] and @racket[set-clear!]
|
|
and if it returns (as opposed to escaping, perhaps via raising an exception),
|
|
the clearing operation is permitted. Its result is ignored. If @racket[clear-proc]
|
|
is @racket[#f], then clearing is done element by element (via calls into the other
|
|
supplied procedures).
|
|
|
|
The @racket[equal-key-proc] is called when an element's hash code is needed of when an
|
|
element is supplied to the underlying equality in the set. The result of
|
|
@racket[equal-key-proc] is used when computing the hash or comparing for equality.
|
|
|
|
If any of the @racket[inject-proc], @racket[add-proc], @racket[shrink-proc], or
|
|
@racket[extract-proc] arguments are @racket[#f], then they all must be @racket[#f],
|
|
the @racket[clear-proc] and @racket[equal-key-proc] must also be @racket[#f],
|
|
and there must be at least one property supplied.
|
|
|
|
Pairs of @racket[prop] and @racket[prop-val] (the number of arguments to
|
|
@racket[impersonate-hash-set] must be odd) add @tech{impersonator properties} or
|
|
override impersonator property values of @racket[st].
|
|
}
|
|
|
|
@defproc[(chaperone-hash-set [st (or/c set? mutable-set? weak-set?)]
|
|
[inject-proc (or/c #f (-> set? any/c any/c))]
|
|
[add-proc (or/c #f (-> set? any/c any/c))]
|
|
[shrink-proc (or/c #f (-> set? any/c any/c))]
|
|
[extract-proc (or/c #f (-> set? any/c any/c))]
|
|
[clear-proc (or/c #f (-> set? any)) #f]
|
|
[equal-key-proc (or/c #f (-> set? any/c any/c)) #f]
|
|
[prop impersonator-property?]
|
|
[prop-val any/c] ... ...)
|
|
(and/c (or/c set? mutable-set? weak-set?) chaperone?)]{
|
|
Chaperones @racket[st]. Like @racket[impersonate-hash-set] but with
|
|
the constraints that the results of the @racket[inject-proc],
|
|
@racket[add-proc], @racket[shrink-proc], @racket[extract-proc], and
|
|
@racket[equal-key-proc] must be
|
|
@racket[chaperone-of?] their second arguments. Also, the input
|
|
may be an @racket[immutable?] set.
|
|
}
|
|
|
|
@section{Custom Hash Sets}
|
|
|
|
@defform[(define-custom-set-types name
|
|
optional-predicate
|
|
comparison-expr
|
|
optional-hash-functions)
|
|
#:grammar ([optional-predicate
|
|
(code:line)
|
|
(code:line #:elem? predicate-expr)]
|
|
[optional-hash-functions
|
|
(code:line)
|
|
(code:line hash1-expr)
|
|
(code:line hash1-expr hash2-expr)])]{
|
|
|
|
Creates a new hash set type based on the given comparison @racket[comparison-expr],
|
|
hash functions @racket[hash1-expr] and @racket[hash2-expr], and element
|
|
predicate @racket[predicate-expr]; the interfaces for these functions are the
|
|
same as in @racket[make-custom-set-types]. The new set type has three
|
|
variants: immutable, mutable with strongly-held elements, and mutable with
|
|
weakly-held elements.
|
|
|
|
Defines seven names:
|
|
|
|
@itemize[
|
|
@item{@racket[name]@racketidfont{?} recognizes instances of the new type,}
|
|
@item{@racketidfont{immutable-}@racket[name]@racketidfont{?} recognizes
|
|
immutable instances of the new type,}
|
|
@item{@racketidfont{mutable-}@racket[name]@racketidfont{?} recognizes
|
|
mutable instances of the new type with strongly-held elements,}
|
|
@item{@racketidfont{weak-}@racket[name]@racketidfont{?} recognizes
|
|
mutable instances of the new type with weakly-held elements,}
|
|
@item{@racketidfont{make-immutable-}@racket[name] constructs
|
|
immutable instances of the new type,}
|
|
@item{@racketidfont{make-mutable-}@racket[name] constructs
|
|
mutable instances of the new type with strongly-held elements, and}
|
|
@item{@racketidfont{make-weak-}@racket[name] constructs
|
|
mutable instances of the new type with weakly-held elements.}
|
|
]
|
|
|
|
The constructors all accept a stream as an optional argument, providing
|
|
initial elements.
|
|
|
|
@examples[
|
|
#:eval set-eval
|
|
(define-custom-set-types string-set
|
|
#:elem? string?
|
|
string=?
|
|
string-length)
|
|
(define imm
|
|
(make-immutable-string-set '("apple" "banana")))
|
|
(define mut
|
|
(make-mutable-string-set '("apple" "banana")))
|
|
(generic-set? imm)
|
|
(generic-set? mut)
|
|
(set? imm)
|
|
(generic-set? imm)
|
|
(string-set? imm)
|
|
(string-set? mut)
|
|
(immutable-string-set? imm)
|
|
(immutable-string-set? mut)
|
|
(set-member? imm "apple")
|
|
(set-member? mut "banana")
|
|
(equal? imm mut)
|
|
(set=? imm mut)
|
|
(set-remove! mut "banana")
|
|
(set-member? mut "banana")
|
|
(equal? (set-remove (set-remove imm "apple") "banana")
|
|
(make-immutable-string-set))
|
|
]
|
|
|
|
}
|
|
|
|
@defproc[(make-custom-set-types
|
|
[eql?
|
|
(or/c (any/c any/c . -> . any/c)
|
|
(any/c any/c (any/c any/c . -> . any/c) . -> . any/c))]
|
|
[hash1
|
|
(or/c (any/c . -> . exact-integer?)
|
|
(any/c (any/c . -> . exact-integer?) . -> . exact-integer?))
|
|
(const 1)]
|
|
[hash2
|
|
(or/c (any/c . -> . exact-integer?)
|
|
(any/c (any/c . -> . exact-integer?) . -> . exact-integer?))
|
|
(const 1)]
|
|
[#:elem? elem? (any/c . -> . boolean?) (const #true)]
|
|
[#:name name symbol? 'custom-set]
|
|
[#:for who symbol? 'make-custom-set-types])
|
|
(values (any/c . -> . boolean?)
|
|
(any/c . -> . boolean?)
|
|
(any/c . -> . boolean?)
|
|
(any/c . -> . boolean?)
|
|
(->* [] [stream?] generic-set?)
|
|
(->* [] [stream?] generic-set?)
|
|
(->* [] [stream?] generic-set?))]{
|
|
|
|
Creates a new set type based on the given comparison function @racket[eql?],
|
|
hash functions @racket[hash1] and @racket[hash2], and predicate @racket[elem?].
|
|
The new set type has variants that are immutable, mutable with strongly-held
|
|
elements, and mutable with weakly-held elements. The given @racket[name] is
|
|
used when printing instances of the new set type, and the symbol @racket[who]
|
|
is used for reporting errors.
|
|
|
|
The comparison function @racket[eql?] may accept 2 or 3 arguments. If it
|
|
accepts 2 arguments, it given two elements to compare them. If it accepts 3
|
|
arguments and does not accept 2 arguments, it is also given a recursive
|
|
comparison function that handles data cycles when comparing sub-parts of the
|
|
elements.
|
|
|
|
The hash functions @racket[hash1] and @racket[hash2] may accept 1 or 2
|
|
arguments. If either hash function accepts 1 argument, it is applied to a
|
|
element to compute the corresponding hash value. If either hash function
|
|
accepts 2 arguments and does not accept 1 argument, it is also given a
|
|
recursive hash function that handles data cycles when computing hash values of
|
|
sub-parts of the elements.
|
|
|
|
The predicate @racket[elem?] must accept 1 argument and is used to recognize
|
|
valid elements for the new set type.
|
|
|
|
Produces seven values:
|
|
|
|
@itemize[
|
|
@item{a predicate recognizing all instances of the new set type,}
|
|
@item{a predicate recognizing immutable instances,}
|
|
@item{a predicate recognizing mutable instances,}
|
|
@item{a predicate recognizing weak instances,}
|
|
@item{a constructor for immutable instances,}
|
|
@item{a constructor for mutable instances, and}
|
|
@item{a constructor for weak instances.}
|
|
]
|
|
|
|
See @racket[define-custom-hash-types] for an example.
|
|
|
|
}
|
|
|
|
@close-eval[set-eval]
|