Chapter 8

Collections

Collection Alignment

Some operations on collections are defined to allow the use of more than a single collection. For example, some looping functions accept any number of collections and operate on these collections in parallel. Each pass through the loop uses one element from each collection. The presence of collections that are unstable under iteration can create problems for multi-collection operations unless special care is taken. If iteration is effectively performed in random order, then naively performing parallel iterations over two different collections would randomly combine values from the two collections. This would presumably have no meaning.

To prevent such random combinations, operations on more than one collection must in general align the collections. Collection alignment consists of effectively computing the intersection of the collections' key sequences and then using the random-access operations (element and element-setter) to operate on the collections themselves.

If implemented naively, this definition of alignment has the potential for extreme inefficiency because of its dependence on element and the potential loops implied by the calls to key-sequence. However, an important special case of this problem is that of iterating over multiple sequences. In this case, the intersection of key sequences will always be the non-negative integers up to the length of the shortest sequence. Further, unlike collections in general, sequences are required to exhibit stability so the explicit computation of key sequences is not actually required. It is correct simply to iterate until one or more of the sequences is exhausted.

Iteration operations that store results in a target collection must generally include the target collection during alignment. This alignment requirement is relaxed if the target collection is a <stretchy-collection>. In this case, the target collection is not considered during alignment. Rather, only the source collections are aligned. New keys may be added to the target collection during the course of the iteration, and keys may be given new values. Other keys are left undisturbed.

It is only possible to align collections that have identical key tests.