Next: I/O extensions, Previous: Macros for writing loops, Up: Libraries
Scheme48 includes several libraries for a variety of data structures.
The arrays
structure exports a facility for multi-dimensional
arrays, based on Alan Bawden's interface.
Array constructors.
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 value.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 dimensions.Copy-array
constructs an array with the same dimensions and contents as array.
Array element dereferencing and assignment. Each index must be in the half-open interval [0,d), where d is the respective dimension of array corresponding with that index.
Creates a vector of the elements in array in row-major order.
Creates a new array that shares storage with array and uses the procedure linear-map to map indices in the new array to indices in array. Linear-map must accept as many arguments as dimension ..., 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 array, and which must be valid indices into array.
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
search-trees
structure.
Make-search-tree
creates a new search tree with the given key equality comparison & ordering functions.Search-tree?
is the disjoint type predicate for red/black binary search trees.
#f
Search-tree-ref
returns the value associated with key in search-tree, or#f
if no such association exists.Search-tree-set!
assigns the value of an existing association in search-tree for key to be value, if the association already exists; or, if not, it creates a new association with the given key and value. If value is#f
, however, any association is removed.Search-tree-modify!
modifies the association in search-tree for key by applying modifier to the previous value of the association. If no association previously existed, one is created whose key is key and whose value is the result of applying modifier to#f
. If modifier returns#f
, the association is removed. This is equivalent to(search-tree-set!
search-tree key(
modifier(search-tree-ref
search-tree key)))
, but it is implemented more efficiently.
#f
#f
#f
#f
These all return two values: the key & value for the association in search-tree whose key is the maximum or minimum of the tree.
Search-tree-max
andsearch-tree-min
do not remove the association from search-tree;pop-search-tree-max!
andpop-search-tree-min!
do. If search-tree is empty, these all return the two values#f
and#f
.
This applies proc to two arguments, the key & value, for every association in search-tree.
Sparse vectors, exported by the structure 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.
#f
Sparse vector element accessor and modifier. In the case of
sparse-vector-ref
, if index is beyond the highest index that was inserted into sparse-vector, it returns#f
; ifsparse-vector-set!
is passed an index beyond what was already assigned, it simply extends the vector.