Collection Extensions

• 1. Introduction
• 2. The Self-Organizing-List Module
• 3. The Subsequence Module
• 4. The Vector-Search Module

The Collection extensions Library

1. Introduction

The various modules in this library contain a few new types and operations which are compatible with the collection types specified in the Dylan Reference Manual, but which are not part of that specification.

It is to be expected that more collection types will appear in time, and they will likely be added to this library. This may also result in reorganizations which could force incompatible changes to the existing modules. We hope to minimize such imcompatibilities and, when forced to them, will include sufficient information to facilitate conversion of existing code.

Collection-extensions exports these modules:

self-organizing-list

Provides "self-organizing lists". These explicit key collections provide roughly the semantics of hash tables, but use a probabilistic implementation which provides O(n) worst case performance but can provide very fast constant time access in the best case.

subseq

Provides "subsequences", which represent an aliased reference to some part of an existing sequence. These are analogous to slices (in Ada or Perl) or displaced arrays (in Common Lisp). Subsequences are themselves subclasses of <sequence>, and can therefore be passed any <collection> or <sequence> operation.

vector-search

Provides a small assortment of specialized operations for searching and modifying <vector>s. These operations are analogous to existing collection operations but provide keywords and efficiency improvements which are meaningful only within the more limited domain.

2. The Self-Organizing-List Module

The "Self Organizing List" is a poor man’s hash table. More precisely, <self-organizing-list> is a subclass of <mutable-explicit-key-collection> and <stretchy-collection> for which addition and retrieval are both linear in the worst case, but which use a probabilistic strategy which yields nearly constant time in the best case.

Because they have a very low overhead, self-organizing lists may provide better peformance than hash tables in cases where references have a high degree of temporal locality. They may also be useful in situations where it is difficult to create a proper hash function.

Instantiate <self-organizing-list>s with

            make(<self-organizing-list>, test: test)

Test is expected to be an equality function. In particular, it is expected to satisfy the identity and transitivity requirements as described in the DRM. If not specified, test defaults to \==.

3. The Subsequence Module

<Subsequence> is a new subclass of <sequence>. A subsequence represents an aliased reference to some part of an existing sequence. Although they may be created by make (with required keywords source:, start: and end:) on one of the instantiable subclasses, they are more often created by calls of the form

            subsequence(sequence, start: 0, end: 3)

where start: and end: are optional keywords which default to the beginning and end, respectively, of the source sequence. No other new operations are defined for subsequences, since all necessary operations are inherited from <sequence>.

Because subsequences are aliased references into other sequences, several properties must be remembered:

• The contents of a subsequence are undefined after any destructive operation upon the source sequence.
• Destructive operations upon subsequences may be reflected in the source. The results of reverse! and sort! should be expected to affect the source sequence for vector subsequences.

If the source sequences are instances of <vector> or <string>, then the implementation will use subclasses of <subsequence> which are also subclasses of <vector> or <string>.

Efficiency notes:

• The implementation tries to insure that subsequences of subsequences can be accessed as efficiently as the original subsequence. (For example, the result of

            subsequence(subsequence(source, start: 1), start: 2)

would produce a subsequence identical to the one produced by

            subsequence(source, start: 3)

• Vector subsequences, like all other vectors, implement constant time element access.
• Non-vector subsequences may take non-constant time to create, but will provide constant-time access to the first element. This should produce the best performance provided some element of the subsequence is accessed at least once.

4. The Vector-Search Module

The vector-search module provides basic search and replace capabilities upon restricted subsets of <sequence> -- primarily <vector>. Exploiting the known properties of these types yields substantially better performance than can be achieved for sequences in general.

The following functions are supplied:

find-first-key(vector, predicate?, #key start, end, failure) => key [Function]

Find the index of first element (after start but before end) of a vector which satisfies predicate?. If no matching element is found, return failure. The defaults for start, end and failure are, respectively, 0, size(vector), and #f. This function is like find-key, but accepts start: and end: rather than skip:.

find-last-key(vector, predicate?, #key start, end, failure) => key [Function]

This is like find-first-key, but goes backward from end.

Send comments and bug reports to gwydion-bugs@cs.cmu.edu