Library data structures
=======================

Scheme48 includes several libraries for a variety of data structures.

Multi-dimensional arrays
------------------------

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

 -- procedure: make-array value dimension ... returns array
 -- procedure: array dimensions element ... returns array
 -- procedure: copy-array array ... returns 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 returns boolean
     Disjoint type predicate for arrays.

 -- procedure: array-shape array returns integer-list
     Returns the list of dimensions of ARRAY.

 -- procedure: array-ref array index ... returns value
 -- procedure: array-set! array value index ... returns 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 returns vector
     Creates a vector of the elements in ARRAY in row-major order.

 -- procedure: make-shared-array array linear-map dimension ... returns 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.

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< returns search-tree
 -- procedure: search-tree? object returns 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 returns value or #f
 -- procedure: search-tree-set! search-tree key value returns unspecified
 -- procedure: search-tree-modify! search-tree key modifier returns 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 returns value or #f
 -- procedure: search-tree-min search-tree returns value or #f
 -- procedure: pop-search-tree-max! search-tree returns value or #f
 -- procedure: pop-search-tree-min! search-tree returns 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 returns unspecified
     This applies PROC to two arguments, the key & value, for every association in SEARCH-TREE.

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 returns sparse-vector
     Sparse vector constructor.

 -- procedure: sparse-vector-ref sparse-vector index returns value or #f
 -- procedure: sparse-vector-set! sparse-vector index value returns 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 returns list
     Creates a list of the elements in SPARSE-VECTOR.  Elements that uninitialized gaps comprise are denoted by #f in the list.