Semi-persistent Vectors🔗 i

Jay McCarthy <jay@racket-lang.org>

(require data/spvector ) package: spvector

This package defines semi-persistent vectors. These vectors are persistent, because old versions are maintained. However, performance degrades when old versions are used. Each operation is O(1) if the newest version is used, otherwise each operation is O(n) where n is the number of versions to the current.

procedure
( spvector? v)→boolean?
v:any/c

Determines if v is a semi-persistent vector.

procedure
( build-spvector nf)→spvector?
n:exact-positive-integer?
f:(exact-nonnegative-integer? . -> .any/c )

Like build-vector , but builds a semi-persistent vector.

procedure
( make-spvector e...)→spvector?
e:any/c

Like vector , but builds a semi-persistent vector.

procedure
( spvector-length vec)→exact-positive-integer?
vec:spvector?

Returns the length of vec.

procedure
( spvector-ref veci)→any/c
vec:spvector?
i:exact-nonnegative-integer?

Returns the value at i of vec, if it is a valid reference.

procedure
( spvector-set veciv)→spvector?
vec:spvector?
i:exact-nonnegative-integer?
v:any/c

Returns a new semi-persistent vector where (spvector-ref new-veci) returns v.

procedure
( spvector-set! veciv)→void
vec:spvector?
i:exact-nonnegative-integer?
v:any/c

Destructively modifies vec, like vector-set! .

1Implementation notes🔗 i

Semi-persistent vectors may be used as sequences.

Semi-persistent vectors are implemented using a weak hash table to log undo information for modifications. These are indexed by uninterned symbols that are stored in the spvector? struct. This means that the garbage collector reclaims space in the log when the old version symbols are no longer reachable. Thus, if you use this structure in a purely linear way, it will behavior exactly like normal vectors asymptotically.

top ← prev up next →