Next: , Previous: Macros for writing loops, Up: Libraries


6.4 Library data structures

Scheme48 includes several libraries for a variety of data structures.

6.4.1 Multi-dimensional arrays

The arrays structure exports a facility for multi-dimensional arrays, based on Alan Bawden's interface.

— procedure: make-array value dimension ... –> array
— procedure: array dimensions element ... –> array
— procedure: copy-array array ... –> array

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.

— procedure: array? object –> boolean

Disjoint type predicate for arrays.

— procedure: array-dimensions array –> integer-list

Returns the list of dimensions of array.

— procedure: array-ref array index ... –> value
— procedure: array-set! array value index ... –> unspecified

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.

— procedure: array->vector array –> vector

Creates a vector of the elements in array in row-major order.

— procedure: make-shared-array array linear-map dimension ... –> array

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.

6.4.2 Red/black 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 search-trees structure.

— procedure: make-search-tree key= key< –> search-tree
— procedure: search-tree? object –> boolean

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.

— procedure: search-tree-ref search-tree key –> value or #f
— procedure: search-tree-set! search-tree key value –> unspecified
— procedure: search-tree-modify! search-tree key modifier –> unspecified

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.

— procedure: search-tree-max search-tree –> value or #f
— procedure: search-tree-min search-tree –> value or #f
— procedure: pop-search-tree-max! search-tree –> value or #f
— procedure: pop-search-tree-min! search-tree –> value or #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 and search-tree-min do not remove the association from search-tree; pop-search-tree-max! and pop-search-tree-min! do. If search-tree is empty, these all return the two values #f and #f.

— procedure: walk-search-tree proc search-tree –> unspecified

This applies proc to two arguments, the key & value, for every association in search-tree.

6.4.3 Sparse vectors

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.

— procedure: make-sparse-vector –> sparse-vector

Sparse vector constructor.

— procedure: sparse-vector-ref sparse-vector index –> value or #f
— procedure: sparse-vector-set! sparse-vector index value –> unspecified

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; if sparse-vector-set! is passed an index beyond what was already assigned, it simply extends the vector.

— procedure: sparse-vector->list sparse-vector –> list

Creates a list of the elements in sparse-vector. Elements that uninitialized gaps comprise are denoted by #f in the list.