# FUNCTION

# Public

# Undocumented

# HASH-TABLE-SAMPLE-OF-HASH-TABLE (N HASH-TABLE)

# LIST-SAMPLE-OF-HASH-TABLE-KEYS (N HASH-TABLE)

# LIST-SAMPLE-OF-HASH-TABLE-PAIRS (N HASH-TABLE)

# LIST-SAMPLE-OF-HASH-TABLE-VALUES (N HASH-TABLE)

# LIST-SAMPLE-OF-ITERATOR (N SIZE NEXT-FN)

# LIST-SAMPLE-OF-LIST (N LIST)

# LIST-SAMPLE-OF-RANGE (N LOWER UPPER)

# LIST-SAMPLE-OF-UNBOUNDED-ITERATOR (N NEXT-FN EXHAUSTED?-FN)

# LIST-SAMPLE-OF-VECTOR (N VECTOR)

# MAP-SAMPLE-OF-HASH-TABLE (FUNCTION N HASH-TABLE)

# MAP-SAMPLE-OF-HASH-TABLE-KEYS (FUNCTION N HASH-TABLE)

# MAP-SAMPLE-OF-HASH-TABLE-VALUES (FUNCTION N HASH-TABLE)

# MAP-SAMPLE-OF-ITERATOR (FUNCTION N SIZE NEXT-FN)

# MAP-SAMPLE-OF-LIST (FUNCTION N LIST)

# MAP-SAMPLE-OF-RANGE (FUNCTION N LOWER UPPER)

# MAP-SAMPLE-OF-UNBOUNDED-ITERATOR (FUNCTION N NEXT-FN EXHAUSTED?-FN)

# MAP-SAMPLE-OF-VECTOR (FUNCTION N VECTOR)

# TEST (&REST TEST-CORE-ARGS &KEY (STREAM *STANDARD-OUTPUT*) &ALLOW-OTHER-KEYS)

# VECTOR-SAMPLE-OF-HASH-TABLE-KEYS (N HASH-TABLE)

# VECTOR-SAMPLE-OF-HASH-TABLE-PAIRS (N HASH-TABLE)

# VECTOR-SAMPLE-OF-HASH-TABLE-VALUES (N HASH-TABLE)

# VECTOR-SAMPLE-OF-ITERATOR (N SIZE NEXT-FN)

# VECTOR-SAMPLE-OF-LIST (N LIST)

# VECTOR-SAMPLE-OF-RANGE (N LOWER UPPER)

# VECTOR-SAMPLE-OF-UNBOUNDED-ITERATOR (N NEXT-FN EXHAUSTED?-FN)

# VECTOR-SAMPLE-OF-VECTOR (N VECTOR)

# Private

# LIST->HASH-TABLE (LIST)

Given LIST, a list of 2-lists of the form (KEY VALUE), returns a
hash table mapping each KEY to each corresponding VALUE.

# LIST->ITERATOR-MV (LIST)

Returns two values: the length of LIST and a function that
successively returns the lists of LIST as multiple values.

# LIST->UNBOUNDED-ITERATOR (LIST)

Returns two values: a function that successively returns the values
of LIST, and a function that returns a generalized boolean indicating
whether the first function has exhausted LIST.

# MAKE-TEST-SET-AS-LIST

Returns a sample set (as a list) of lists, each list consisting of
two elements.

# MAKE-TEST-SET-AS-RANGE

Returns three values to use as a range set: a lower bound, an upper
bound, and a list of the values of the range.

# MAKE-TEST-SET-AS-VECTOR

Returns the sample set from MAKE-TEST-SET-AS-LIST, but as a vector.

# MEASURE-SELECTION-RATES (ITERATIONS SET-LOWER SET-UPPER SAMPLE-SIZE SAMPLE-FN)

Given the set of integers [SET-LOWER,SET-UPPER), measures the
selection rates of each element when repeatedly given to SAMPLE-FN,
which takes a simple random sample, without replacement, of the set.
SAMPLE-SIZE is the size of each sample.
The function SAMPLE-FN is called ITERATIONS times. Its arguments are:
SAMPLE-SIZE
The requested size of the sample to take of the set.
SET-SIZE
The size of the set.
SET-NEXT
A function of no arguments returning the next element of the set.
SET-EXHAUSTED?
A function of no arguments returning a generalized boolean
indicating whether the set has been exhausted.
VISIT-SAMPLE-ELEMENT
A function which must be called once for every element of the
chosen sample.
Returns two values: the expected rate of selection for all elements,
based on the set size and sample size, and a vector of the actual
measured rate of selection for each element of the set; each element
of the vector corresponds to [SET-LOWER,SET-UPPER) (in the same
order).
The more any actual rate varies from the expected rate, the more
likely there was some bias or error in the sample taken by SAMPLE-FN.
A lower number of iterations can also cause this problem; 1,000,000 is
a good number of iterations to use to get a clear reading.

# REPORT-SELECTION-RATES (LABEL EXPECTED-RATE ACTUAL-RATES VERBOSE-P STREAM)

Reports EXPECTED-RATE and some trivial statistics on ACTUAL-RATES,
as returned by MEASURE-SELECTION-RATES. Prints the analysis to
STREAM.
When VERBOSE-P is true, prints each element of ACTUAL-RATES, along
with its error from EXPECTED-RATE and a graph of its error.

# Undocumented

# TEST-COMPUTED-SAMPLE (LABEL SAMPLE SAMPLE-TYPE INPUT-SET REQUESTED-SAMPLE-SIZE)

# TEST-CORE (&KEY (ITERATIONS 100000) (SET-LOWER -100) (SET-UPPER 100) (SAMPLE-SIZE 15) (STREAM *STANDARD-OUTPUT*) (VERBOSE-P T))

# TEST-OUTPUT

# TEST-OUTPUT-AS-HASH-TABLE (SAMPLE-SIZE)

# TEST-OUTPUT-AS-ITERATION (SAMPLE-SIZE)

# TEST-OUTPUT-AS-LIST (SAMPLE-SIZE)

# TEST-OUTPUT-AS-MAPPING (SAMPLE-SIZE)

# TEST-OUTPUT-AS-VECTOR (SAMPLE-SIZE)

# TEST-OUTPUT-METHODS (SAMPLE-SIZE)

# MACRO

# Public

# DO-SAMPLE-OF-ITERATOR-EXPR ((VARS N-FORM SIZE-FORM NEXT-FORM &KEY (EFFECTIVE-N-VAR NIL EFFECTIVE-N-VAR-P) (INITIAL-FORM NIL INITIAL-FORM-P) (RESULT-FORM NIL RESULT-FORM-P)) &BODY BODY)

Iterates over a simple random sample of N-FORM elements, without
replacement, from a set expressed by SIZE-FORM and NEXT-FORM.
N-FORM is evaluated once, before any other arguments are evaluated.
If the value of N-FORM is larger than the size of the input set, then
the resulting sample will just contain all the elements of the
set--that is, the value of N-FORM is automatically lowered to the size
of the input set when necessary.
SIZE-FORM is then evaluated once to produce the number of elements in
the set.
When INITIAL-FORM is given, it is evaluated before iteration begins.
When RESULT-FORM is given, it is evaluated after iteration ends, and
its resulting values become the result of the iteration form; if
RESULT-FORM is not given, the result is NIL. If EFFECTIVE-N-VAR is
given, it is bound with the effective number of elements to
process (the result of N-FORM limited by the actual size of the input
set) for the evaluation of INITIAL-FORM, NEXT-FORM, RESULT-FORM, and
BODY.
NEXT-FORM is evaluated to produce the next available element,
advancing through the set. NEXT-FORM may produce multiple values;
these values taken together as a tuple constitute a single element of
the set. NEXT-FORM will never be evaluated more times than the value
of SIZE-FORM.
For each element selected for the random sample, BODY is evaluated
with the symbol specified by VARS bound to a list of each value of the
element (the values yielded by NEXT-FORM). Alternatively, VARS may be
a list of symbols, each of which is bound to each successive value of
the element, as if by MULTIPLE-VALUE-BIND. In either case, the
bindings may be shared between different iterations, or the binding
may be fresh each time.
An implicit block named NIL is established around the loop. RETURN
may be used to terminate the loop prematurely, overriding the default
resulting values of the iteration form (controlled by RESULT-FORM).
The order in which BODY is evaluated on the sampled elements is not
assured to be random. The only thing that is random is which
selection is made of all the possible subsets of the input set with
the size expressed by N-FORM.

# VECTOR-SAMPLE-OF-UNBOUNDED-ITERATOR-EXPR (N-FORM NEXT-FORM EXHAUSTED?-FORM)

Evaluates to a simple random sample of size N-FORM, without
replacement, from a set of unknown size expressed by NEXT-FORM and
EXHAUSTED?-FORM. The resulting sample is expressed as a vector.
N-FORM is evaluated once, before any other arguments are evaluated.
If the value of N-FORM is larger than the size of the input set, then
the resulting sample will just contain all the elements of the
set--that is, the value of N-FORM is automatically lowered to the size
of the input set when necessary. The value of N-FORM (before being
limited by the size of the input set) must be within the host
implementation's ARRAY-DIMENSION-LIMIT.
NEXT-FORM is evaluated to produce the next available element,
advancing through the input set. (Its first return value is used as
the element, or NIL if NEXT-FORM produced no values.) EXHAUSTED?-FORM
is evaluated to produce a generalized boolean indicating whether the
input set has been exhausted. NEXT-FORM will never be evaluated
unless EXHAUSTED?-FORM has been evaluated since the last evaluation of
NEXT-FORM, and the result was false.
The order of the returned elements is not assured to be random. The
only thing that is random is which selection is made of all the
possible subsets of the input set with the size expressed by N-FORM.

# Undocumented

# DO-SAMPLE-OF-HASH-TABLE ((KEY-VAR VALUE-VAR N-FORM HASH-TABLE-FORM &REST KW-ARGS &KEY &ALLOW-OTHER-KEYS) &BODY BODY)

# DO-SAMPLE-OF-ITERATOR ((VARS N-FORM SIZE-FORM NEXT-FN-FORM &REST KW-ARGS &KEY &ALLOW-OTHER-KEYS) &BODY BODY)

# DO-SAMPLE-OF-LIST ((VAR N-FORM LIST-FORM &REST KW-ARGS &KEY &ALLOW-OTHER-KEYS) &BODY BODY)

# DO-SAMPLE-OF-RANGE ((VAR N-FORM LOWER-FORM UPPER-FORM &REST KW-ARGS &KEY &ALLOW-OTHER-KEYS) &BODY BODY)

# DO-SAMPLE-OF-UNBOUNDED-ITERATOR ((VAR N-FORM NEXT-FN-FORM EXHAUSTED?-FN-FORM &KEY (EFFECTIVE-N-VAR NIL EFFECTIVE-N-VAR-P) (INITIAL-FORM NIL INITIAL-FORM-P) (RESULT-FORM NIL RESULT-FORM-P)) &BODY BODY)

# DO-SAMPLE-OF-VECTOR ((VAR N-FORM VECTOR-FORM &REST KW-ARGS &KEY &ALLOW-OTHER-KEYS) &BODY BODY)

# Private

# TEST-ACCUMULATED-SAMPLE ((LABEL ACCUMULATE INPUT-SET-FORM REQUESTED-SAMPLE-SIZE-FORM) &BODY BODY)

Evaluates BODY, which accumulates the elements of a sample taken
from a set. After evaluating BODY, tests the sample against the input
set and the requested sample size. If there is an error in the
resulting sample, an error is signalled. LABEL is included in any
error messages.
ACCUMULATE is defined with MACROLET for the evaluation of BODY.
(ACCUMULATE ELEMENT) is used to accumulate each ELEMENT of the sample
that is taken.
INPUT-SET-FORM is evaluated to produce the input set (or an equivalent
copy), as a SEQUENCE.
REQUESTED-SAMPLE-SIZE-FORM is evaluated to produce the requested size
of the sample to take.
Note that the input set and requested sample size are not passed to
anything within BODY, but must be equivalent to the corresponding
arguments to the function or macro form used in BODY to produce the
sample.

# TEST-DO-SAMPLE ((LABEL ACCUMULATE INITIAL-FORM RESULT-FORM INITIAL-SET-FORM REQUESTED-SAMPLE-SIZE-FORM) &BODY BODY)

Evaluates BODY, which iterates over the elements of a sample taken
from a set. After evaluating BODY, tests the sample against the input
set and the requested sample size. If there is an error in the
resulting sample, an error is signalled. LABEL is included in any
error messages.
ACCUMULATE is defined with MACROLET for the evaluation of BODY. The
result of BODY must be the result a DO-SAMPLE-OF-* macro form that
includes at least the expression (ACCUMULATE ELEMENT) in its body
(where ELEMENT is the variable naming the current element in the loop
over the resulting sample). BODY should consist solely of the
DO-SAMPLE-OF-* macro form, and the body of that macro form should
consist solely of (ACCUMULATE ELEMENT).
INITIAL-FORM is defined with MACROLET for the evaluation of BODY.
(INITIAL-FORM) must be the :INITIAL-FORM argument to the
DO-SAMPLE-OF-* macro form.
RESULT-FORM is defined with MACROLET for the evaluation of BODY.
(RESULT-FORM) must be the :RESULT-FORM argument to the DO-SAMPLE-OF-*
macro form.
INPUT-SET-FORM is evaluated to produce the input set (or an equivalent
copy), as a SEQUENCE.
REQUESTED-SAMPLE-SIZE-FORM is evaluated to produce the requested size
of the sample to take.
Note that the input set and requested sample size are not passed to
anything within BODY, but must be equivalent to the corresponding
arguments to the DO-SAMPLE-OF-* macro form used in BODY to produce the
sample.

# TEST-LIST-SAMPLE ((LABEL INPUT-SET-FORM REQUESTED-SAMPLE-SIZE-FORM) &BODY BODY)

Evaluates BODY, which takes a sample from a set, evaluating to the
sample (as a LIST). The sample is tested against the input set and
the requested sample size. If there is an error in the resulting
sample, an error is signalled. LABEL is included in any error
messages.
INPUT-SET-FORM and REQUESTED-SAMPLE-SIZE-FORM have the same meaning as
they do in the TEST-ACCUMULATED-SAMPLE macro.

# TEST-VECTOR-SAMPLE ((LABEL INPUT-SET-FORM REQUESTED-SAMPLE-SIZE-FORM) &BODY BODY)

Evaluates BODY, which takes a sample from a set, evaluating to the
sample (as a VECTOR). The sample is tested against the input set and
the requested sample size. If there is an error in the resulting
sample, an error is signalled. LABEL is included in any error
messages.
INPUT-SET-FORM and REQUESTED-SAMPLE-SIZE-FORM have the same meaning as
they do in the TEST-ACCUMULATED-SAMPLE macro.

# WITH-HASH-TABLE-ACCUMULATOR ((SET-TEST/SIZE ACCUMULATE) &BODY BODY)

Evaluates BODY, accumulating keys and values to a hash-table,
resulting in the hash-table.
SET-TEST/SIZE is defined with MACROLET. (SET-TEST/SIZE TEST SIZE)
must be evaluated once, before accumulation begins. TEST must be an
acceptable hash-table test function for MAKE-HASH-TABLE. SIZE must be
a non-negative integer indicating the expected final size of the
hash-table (the number of times ACCUMULATE is evaluated with a unique
KEY), which need not be accurate, or NIL to make no guess as to the
final size.
ACCUMULATE is defined with MACROLET. Each time (ACCUMULATE KEY VALUE)
is evaluated, KEY and TABLE are added as an entry to the hash-table,
replacing any previous entry with the same KEY.

# WITH-LIST-ACCUMULATOR ((ACCUMULATE) &BODY BODY)

Evaluates BODY, accumulating elements to a list, resulting in the
list. The order of the elements of the resulting list is undefined.
ACCUMULATE is defined with MACROLET. Each time (ACCUMULATE ELEMENT)
is evaluated, ELEMENT is accumulated to the list.

# WITH-LIST-ITERATOR ((NEXT SIZE EXHAUSTED? LIST-FORM) &BODY BODY)

Evaluates BODY with an iterator on a list.
LIST-FORM is evaluated once to produce the list to iterate upon. The
resulting list is never modified (unless from within BODY), the
consequences of which are undefined).
NEXT is defined with MACROLET. Each evaluation of (NEXT) yields the
next successive element of the list.
SIZE is defined with MACROLET. Each evaluation of (SIZE) yields the
length of the list. The length may or may not be calculated upon each
evaluation; it may (but need not be) be memoized.
EXHAUSTED? is defined with MACROLET?. Each evaluation of (EXHAUSTED?)
yields a generalized boolean indicating whether the list has been
exhausted by evaluations of NEXT.
The effect of calling NEXT more times than the length of the list is
undefined.

# WITH-RANGE-ITERATOR ((NEXT SIZE EXHAUSTED? LOWER-FORM UPPER-FORM) &BODY BODY)

Evaluates BODY with an iterator on a range of integers.
LOWER-FORM and UPPER-FORM are evaluated once to produce the range of
integers, [LOWER,UPPER), to iterate upon.
NEXT is defined with MACROLET. Each evaluation of (NEXT) yields the
next successive element of the range.
SIZE is defined with MACROLET. Each evaluation of (SIZE) yields the
length of the range.
EXHAUSTED? is defined with MACROLET?. Each evaluation of (EXHAUSTED?)
yields a generalized boolean indicating whether the range has been
exhausted by evaluations of NEXT.
The effect of calling NEXT more times than the length of the range is
undefined.

# WITH-VECTOR-ACCUMULATOR ((SET-SIZE/ELEMENT-TYPE ACCUMULATE) &BODY BODY)

Evaluates BODY, accumulating elements to a vector, resulting in the
vector. The order of the elements of the resulting vector is undefined.
SET-SIZE/ELEMENT-TYPE is defined with
MACROLET. (SET-SIZE/ELEMENT-TYPE SIZE ELEMENT-TYPE) must be evaluated
once, before accumulation begins. SIZE dictates the size of the
resulting vector. ELEMENT-TYPE is a designator for the type of
elements to be accumulated. The result of accumulating an element not
of type ELEMENT-TYPE is undefined.
ACCUMULATE is defined with MACROLET. Each time (ACCUMULATE ELEMENT)
is evaluated, ELEMENT is accumulated to the vector. It must be
evaluated exactly the number of times as given to the
SET-SIZE/ELEMENT-TYPE form before control leaves BODY in the normal
manner. (It's acceptable for control to leave BODY due to non-local
exits, such as GO, THROW, or a signalled condition.)

# WITH-VECTOR-ITERATOR ((NEXT SIZE EXHAUSTED? VECTOR-FORM) &BODY BODY)

Evaluates BODY with an iterator on a vector.
VECTOR-FORM is evaluated once to produce the vector to iterate upon.
The resulting vector is never modified (unless from within BODY, the
consequences of which are undefined).
NEXT is defined with MACROLET. Each evaluation of (NEXT) yields the
next successive element of the vector.
SIZE is defined with MACROLET. Each evaluation of (SIZE) yields the
length of the vector.
EXHAUSTED? is defined with MACROLET?. Each evaluation of (EXHAUSTED?)
yields a generalized boolean indicating whether the vector has been
exhausted by evaluations of NEXT.
The effect of calling NEXT more times than the length of the vector is
undefined.

# Undocumented

# DEFINE-TYPICAL-SAMPLE-METHODS (SPECIALIZED-FOR-CLASS-NAME GENERIC-SAMPLE-FUNCTION-NAME LIST-SAMPLE-FUNCTION-NAME VECTOR-SAMPLE-FUNCTION-NAME MAP-SAMPLE-FUNCTION-NAME)

# GENERIC-FUNCTION

# Public

# LIST-SAMPLE (N SET)

Like SAMPLE, but the result is a LIST.

# MAP-SAMPLE (FUNCTION N SET)

Like SAMPLE, but applies FUNCTION to each element
of the resulting selection.
When SET is a mapping type (e.g. a HASH-TABLE), FUNCTION is applied
with two arguments: the key and the value.

# SAMPLE (N SET)

Returns a simple random sample of size N, without
replacement, from SET. The output will be of type SEQUENCE. (Whether
a LIST is returned or a VECTOR depends on which is most efficient for
the type of SET.)
If N is larger than the size of SET, then the resulting sample will
just contain all the elements of SET--that is, N is automatically
lowered to the size of SET when necessary.
When SET is a mapping type (e.g. a HASH-TABLE), the returned elements
will be CONSes of the form (KEY . VALUE).
The order of the returned elements is not assured to be random. The
only thing that is random is which selection is made of all the
possible subsets of SET of size N.

# VECTOR-SAMPLE (N SET)

Like SAMPLE, but the result is a VECTOR.