s48-refman/library/data.texi

@node Library data structures
@section Library data structures

Scheme48 includes several libraries for a variety of data structures.

@subsection Multi-dimensional arrays

@cindex arrays
@stindex arrays
The @code{arrays} structure exports a facility for multi-dimensional
arrays, based on Alan Bawden's interface.

@deffn procedure make-array value dimension @dots{} @returns{} array
@deffnx procedure array dimensions element @dots{} @returns{} array
@deffnx procedure copy-array array @dots{} @returns{} array
Array constructors.  @code{Make-array} constructs an array with the
given dimensions, each of which must be an exact, non-negative integer,
and fills all of the elements with @var{value}.  @code{Array} creates
an array with the given list of dimensions, which must be a list of
exact, non-negative integers, and fills it with the given elements in
row-major order.  The number of elements must be equal to the product
of @var{dimensions}.  @code{Copy-array} constructs an array with the
same dimensions and contents as @var{array}.
@end deffn

@deffn procedure array? object @returns{} boolean
Disjoint type predicate for arrays.
@end deffn

@deffn procedure array-shape array @returns{} integer-list
Returns the list of dimensions of @var{array}.
@end deffn

@deffn procedure array-ref array index @dots{} @returns{} value
@deffnx procedure array-set! array value index @dots{} @returns{} unspecified
Array element dereferencing and assignment.  Each @var{index} must be
in the half-open interval [0,@var{d}), where @var{d} is the respective
dimension of @var{array} corresponding with that index.
@end deffn

@deffn procedure array->vector array @returns{} vector
Creates a vector of the elements in @var{array} in row-major order.
@end deffn

@deffn procedure make-shared-array array linear-map dimension @dots{} @returns{} array
Creates a new array that shares storage with @var{array} and uses the
procedure @var{linear-map} to map indices in the new array to indices in
@var{array}.  @var{Linear-map} must accept as many arguments as
@var{dimension} @dots{}, each of which must be an exact, non-negative
integer; and must return a list of exact, non-negative integers equal
in length to the number of dimensions of @var{array}, and which must
be valid indices into @var{array}.
@end deffn

@subsection Red/black search trees

@cindex binary search trees
@stindex search-trees
Along with hash tables for general object maps, Scheme48 also provides
red/black binary search trees generalized across key equality
comparison & ordering functions, as opposed to key equality comparison
& hash functions with hash tables.  These names are exported by the
@code{search-trees} structure.

@deffn procedure make-search-tree key= key< @returns{} search-tree
@deffnx procedure search-tree? object @returns{} boolean
@code{Make-search-tree} creates a new search tree with the given key
equality comparison & ordering functions.  @code{Search-tree?} is the
disjoint type predicate for red/black binary search trees.
@end deffn

@deffn procedure search-tree-ref search-tree key @returns{} value or @code{#f}
@deffnx procedure search-tree-set! search-tree key value @returns{} unspecified
@deffnx procedure search-tree-modify! search-tree key modifier @returns{} unspecified
@code{Search-tree-ref} returns the value associated with @var{key} in
@var{search-tree}, or @code{#f} if no such association exists.
@code{Search-tree-set!} assigns the value of an existing association in
@var{search-tree} for @var{key} to be @var{value}, if the association
already exists; or, if not, it creates a new association with the given
key and value.  If @var{value} is @code{#f}, however, any association
is removed.  @code{Search-tree-modify!} modifies the association in
@var{search-tree} for @var{key} by applying @var{modifier} to the
previous value of the association.  If no association previously
existed, one is created whose key is @var{key} and whose value is the
result of applying @var{modifier} to @code{#f}.  If @var{modifier}
returns @code{#f}, the association is removed.  This is equivalent to
@code{(search-tree-set! @var{search-tree} @var{key} (@var{modifier}
(search-tree-ref @var{search-tree} @var{key})))}, but it is implemented
more efficiently.
@end deffn

@deffn procedure search-tree-max search-tree @returns{} value or @code{#f}
@deffnx procedure search-tree-min search-tree @returns{} value or @code{#f}
@deffnx procedure pop-search-tree-max! search-tree @returns{} value or @code{#f}
@deffnx procedure pop-search-tree-min! search-tree @returns{} value or @code{#f}
These all return two values: the key & value for the association in
@var{search-tree} whose key is the maximum or minimum of the tree.
@code{Search-tree-max} and @code{search-tree-min} do not remove the
association from @var{search-tree}; @code{pop-search-tree-max!} and
@code{pop-search-tree-min!} do.  If @var{search-tree} is empty, these
all return the two values @code{#f} and @code{#f}.
@end deffn

@deffn procedure walk-search-tree proc search-tree @returns{} unspecified
This applies @var{proc} to two arguments, the key & value, for every
association in @var{search-tree}.
@end deffn

@subsection Sparse vectors

@cindex resizable vectors
@cindex growing vectors
@stindex sparse-vectors
Sparse vectors, exported by the structure @code{sparse-vectors}, are
vectors that grow as large as necessary without leaving large, empty
spaces in the vector.  They are implemented as trees of subvectors.

@deffn procedure make-sparse-vector @returns{} sparse-vector
Sparse vector constructor.
@end deffn

@deffn procedure sparse-vector-ref sparse-vector index @returns{} value or @code{#f}
@deffnx procedure sparse-vector-set! sparse-vector index value @returns{} unspecified
Sparse vector element accessor and modifier.  In the case of
@code{sparse-vector-ref}, if @var{index} is beyond the highest index
that was inserted into @var{sparse-vector}, it returns @code{#f}; if
@code{sparse-vector-set!} is passed an index beyond what was already
assigned, it simply extends the vector.
@end deffn

@deffn procedure sparse-vector->list sparse-vector @returns{} list
Creates a list of the elements in @var{sparse-vector}.  Elements that
uninitialized gaps comprise are denoted by @code{#f} in the list.
@end deffn