Extensible Vectors
The :std/misc/evector
library implements extensible vectors,
that grow as you add elements to them, in the style of Common Lisp extensible vectors.
In this implementation, the underlying vectors double their size each time they need to grow, guaranteeing constant factor size and time overhead over having known the correct size initially. The current implementation does not support shrinking an extensible vector, but you can extract the non-extensible vector and forget the extensible one when you’re done.
ebytes
and ebits
are variants of evector
specialized for holding
respectively 8-bit bytes and 1-bit bits.
The functions with names starting with &
are fast but unsafe variants
that do not do checking, but trust you to provide arguments of the correct
types and sizes, with bad consequences if you don’t.
To use the bindings from this module:
(import :std/misc/evector)
evector
make-evector
(make-evector vector fill-pointer) => evector
Create an evector
from initial values for the supporting vector
and the fill-pointer
.
The fill-pointer
must be a non-negative exact integer no greater than the length of the vector
.
Beware that the vector
and the evector
will share side-effects until the evector
grows;
expected use is that ownership of the vector
is transfered to the new evector
.
Examples:
> (make-evector #(1 2 3 #f) 3)
evector?
(evector? x) => bool
Recognize an evector
.
check-argument-evector
(check-argument-evector x)
Raise an error if x
is not an evector
.
vector->evector &vector->evector
(vector->evector v)
(&vector->evector v)
Convert a vector
to an evector
.
Beware that the two structures will share state until the evector
grows and no further.
evector->vector &evector->vector
(evector->vector v)
(&evector->vector v)
Convert an evector
to an vector
containing just
the initialized elements before the fill-pointer
.
The vector
will not share structure with the evector
.
list->evector &list->evector
(list->evector l)
(&list->evector l)
Convert a list
to an evector
.
evector->list &evector->list
(vector->evector v)
(&vector->evector v)
Convert an evector
to an vector
containing just
the initialized elements before the fill-pointer
.
The vector
will not share structure with the evector
.
evector-ref &evector-ref
(evector-ref e i) => value
(&evector-ref e i) => value
Given an evector e
and an index i
, return the value at index i
.
evector-ref
will check that the arguments are of the correct types and
that i
is less than the fill-pointer
of e
, whereas
&evector-ref
will behave in unspecified way if these prerequisites are not met.
evector-set! &evector-set! evector-ref-set! &evector-ref-set!
(evector-set! e i v) => unspecified
(evector-ref-set! e i v) => unspecified
(&evector-set! e i v) => unspecified
(&evector-ref-set! e i v) => unspecified
Given an evector e
, an index i
below its fill-pointer
, and a value v
,
set the value of the evector at the given index to the given value.
evector-set!
will check that the arguments are of the correct types and
that i
is less than the fill-pointer
of e
, whereas
&evector-set!
will behave in unspecified way if these prerequisites are not met.
evector-ref-set!
and &evector-ref-set!
aliases that enable use of the set!
macro,
as in (set! (evector-ref e i) v)
.
extend-evector! &extend-evector!
(extend-evector! e ll initial-value: (iv #f))
(&extend-evector! e ll iv)
Extend the evector e
to have length at least ll
,
using the initial value iv
for new vector values.
evector-fill-pointer &evector-fill-pointer
(evector-fill-pointer e) => fixnum
(&evector-fill-pointer e) => fixnum
Return the current value of the fill-pointer for an evector e
.
evector-fill-pointer-set! &evector-fill-pointer-set!
(evector-fill-pointer-set! e fp initial-value: (iv #f) extend: (extend #t)) => fixnum or bool
(&evector-fill-pointer-set! e fp iv extend) => fixnum or bool
Given an evector e
, a new value fp
for its fill-pointer,
an initial value iv
for new elements, and a boolean or fixnum extend
,
try to set the fill-pointer of e
to fp
:
- If
fp
is greater than the length of the supporting ofe
, butextend
is#f
or a negative fixnum, then don’t set the fill-pointer, and instead return#f
. - If
fp
is no greater than the length of the supporting vector ofe
, set the fill-pointer ofe
tofp
, and returnfp
. - If
extend
is#t
, extend the evector using an exponential backoff strategy guaranteeing a constant-time space and time overhead factor over non-extensible vectors, set the fill-pointer tofp
and returnfp
. - If
extend
is a non-negative fixnum, extend the evector to have length(+ fp extend)
, set the fill-pointer tofp
and returnfp
.
evector-push! &evector-push!
(evector-push! e x initial-value: (iv #f) extend: (extend #t)) => unspecified
(&evector-push! e x iv extend) => unspecified
Try to push value x
at the end of the evector e
:
Increment the fill-pointer of e
as if using evector-extend!
with initial value iv
and argument extend
;
if the fill-pointer could be incremented, set the value at last index to x
.
memoize-recursive-sequence
(memoize-recursive-sequence fun init: (init '()) cache: (cache (list->evector init))) => function
Define a function f
from a non-negative fixnum n
that caches its initial values (zero-based) in extensible vector cache
,
that by default is initialized from list init
, that defaults to the empty list.
The function body fun
may make recursive calls to the outer function f
with strictly lower values of the integer argument n
;
the cache
can be initialized with the initial values for f
;
it will be consulted rather than calling fun
, and
entries filled after fun
returns.
Examples:
> (def fibonacci
(memoize-recursive-sequence (λ (n) (+ (fibonacci (- n 1)) (fibonacci (- n 2))))
init: '(0 1)))
> (fibonacci 8)
21
> (def fact-e (list->evector '(1)))
> (def fact (memoize-recursive-sequence (λ (n) (* n (fact (1- n)))) cache: fact-e))
> (fact 7)
5040
> (subvector (evector->vector fact-e) 3 8)
#(6 24 120 720 5040)
ebytes
make-ebytes
(make-ebytes u8vector fill-pointer) => ebytes
Create an ebytes
from initial values for the supporting u8vector
and the fill-pointer
.
The fill-pointer
must be a non-negative exact integer no greater than the length of the u8vector
.
Beware that the u8vector
and the ebytes
will share side-effects until the ebytes
grows;
expected use is that ownership of the u8vector
is transfered to the new ebytes
.
Examples:
> (make-ebytes #u8(1 2 3 0) 3)
ebytes?
(ebytes? x) => bool
Recognize an ebytes
.
check-argument-ebytes
(check-argument-ebytes x)
Raise an error if x
is not an ebytes
.
bytes->ebytes &bytes->ebytes
(bytes->ebytes u8vector)
(&bytes->ebytes u8vector)
Convert a u8vector
to an ebytes
.
Beware that the two structures will share state until the ebytes
grows and no further.
ebytes->bytes &ebytes->bytes
(ebytes->bytes e)
(&ebytes->bytes e)
Convert an ebytes
to a u8vector
containing just
the initialized elements before the fill-pointer
.
The bytes
will not share structure with the ebytes
.
string->ebytes &string->ebytes
(string->ebytes s)
(&string->ebytes s)
Convert a string
to an ebytes
containing just
the initialized elements before the fill-pointer
,
using utf8 to encode the string into bytes.
ebytes-ref &ebytes-ref
(ebytes-ref e i) => value
(&ebytes-ref e i) => value
Given an ebytes e
and an index i
, return the byte at index i
.
ebytes-ref
will check that the arguments are of the correct types and
that i
is less than the fill-pointer
of e
, whereas
&ebytes-ref
will behave in unspecified way if these prerequisites are not met.
ebytes-set! &ebytes-set! ebytes-ref-set! &ebytes-ref-set!
(ebytes-set! e i v) => unspecified
(ebytes-ref-set! e i v) => unspecified
(&ebytes-set! e i v) => unspecified
(&ebytes-ref-set! e i v) => unspecified
Given an ebytes e
, an index i
below its fill-pointer
, and a byte value v
,
set the value of the ebytes at the given index to the given value.
ebytes-set!
will check that the arguments are of the correct types and
that i
is less than the fill-pointer
of e
, whereas
&ebytes-set!
will behave in unspecified way if these prerequisites are not met.
ebytes-ref-set!
and &ebytes-ref-set!
aliases that enable use of the set!
macro,
as in (set! (ebytes-ref e i) v)
.
extend-ebytes! &extend-ebytes!
(extend-ebytes! e ll initial-value: (iv #f))
(&extend-ebytes! e ll iv)
Extend the ebytes e
to have length at least ll
,
using the initial value iv
for new bytes values.
ebytes-fill-pointer
(ebytes-fill-pointer e) => fixnum
(&ebytes-fill-pointer e) => fixnum
Return the current value of the fill-pointer for an ebytes e
.
ebytes-fill-pointer-set!
(ebytes-fill-pointer-set! e fp initial-value: (iv #f) extend: (extend #t)) => fixnum or bool
(&ebytes-fill-pointer-set! e fp iv extend) => fixnum or bool
Given an ebytes e
, a new value fp
for its fill-pointer,
an initial value iv
for new elements, and a boolean or fixnum extend
,
try to set the fill-pointer of e
to fp
:
- If
fp
is greater than the length of the supporting ofe
, butextend
is#f
or a negative fixnum, then don’t set the fill-pointer, and instead return#f
. - If
fp
is no greater than the length of the supporting bytes ofe
, set the fill-pointer ofe
tofp
, and returnfp
. - If
extend
is#t
, extend the ebytes using an exponential backoff strategy guaranteeing a constant-time space and time overhead factor over non-extensible bytess, set the fill-pointer tofp
and returnfp
. - If
extend
is a non-negative fixnum, extend the ebytes to have length(+ fp extend)
, set the fill-pointer tofp
and returnfp
.
ebytes-push! &ebytes-push!
(ebytes-push! e x initial-value: (iv #f) extend: (extend #t)) => unspecified
(&ebytes-push! e x iv extend) => unspecified
Try to push value x
at the end of the ebytes e
:
Increment the fill-pointer of e
as if using ebytes-extend!
with initial value iv
and argument extend
;
if the fill-pointer could be incremented, set the value at last index to x
.
ebits
make-ebits
(make-ebits u8vector fill-pointer) => ebits
Create an ebits
from initial values for the supporting u8vector
and the fill-pointer
.
The fill-pointer
must be a non-negative exact integer no greater than the length of the u8vector
.
Bits are stored in u8vector
in a little endian way:
i.e. bit 0 is the low-order bit of byte 0, bit 7 is the high-order bit of byte 0,
bit 8 is the low-order bit of byte 1, etc.
Beware that the u8vector
and the ebits
will share side-effects until the ebits
grows;
expected use is that ownership of the u8vector
is transfered to the new ebits
.
Examples:
> (make-ebits #u8(1 2 3 0) 20)
ebits?
(ebits? x) => bool
Recognize an ebits
.
check-argument-ebits
(check-argument-ebits x)
Raise an error if x
is not an ebits
.
bits->ebits &bits->ebits
(bits->ebits u8vector b l)
(&bits->ebits u8vector b l)
Convert a exact-integer
to an ebits
of given length l
,
where the bits of the ebits
will be those of the integer, in little-endian order.
ebits->bits &ebits->bits
(ebits->bits e)
(&ebits->bits e)
Convert an ebits
to an exact-integer
containing just
the initialized bits before the fill-pointer
, in little-endian order.
ebits-set? &ebits-set?
(ebits-set? e i) => bool
(&ebits-set? e i) => bool
Given an ebits e
and an index i
, return true if the bit at index i
is set.
ebits-ref &ebits-ref
(ebits-ref e i) => value
(&ebits-ref e i) => value
Given an ebits e
and an index i
, return the bit at index i
.
ebits-ref
will check that the arguments are of the correct types and
that i
is less than the fill-pointer
of e
, whereas
&ebits-ref
will behave in unspecified way if these prerequisites are not met.
ebits-set! &ebits-set! ebits-ref-set! &ebits-ref-set!
(ebits-set! e i v) => unspecified
(ebits-ref-set! e i v) => unspecified
(&ebits-set! e i v) => unspecified
(&ebits-ref-set! e i v) => unspecified
Given an ebits e
, an index i
below its fill-pointer
, and a bit value v
,
set the value of the ebits at the given index to the given value.
ebits-set!
will check that the arguments are of the correct types and
that i
is less than the fill-pointer
of e
, whereas
&ebits-set!
will behave in unspecified way if these prerequisites are not met.
ebits-ref-set!
and &ebits-ref-set!
aliases that enable use of the set!
macro,
as in (set! (ebits-ref e i) v)
.
extend-ebits! &extend-ebits!
(extend-ebits! e ll initial-value: (iv #f))
(&extend-ebits! e ll iv)
Extend the ebits e
to have length at least ll
,
using the initial value iv
for new bits values.
ebits-fill-pointer
(ebits-fill-pointer e) => fixnum
(&ebits-fill-pointer e) => fixnum
Return the current value of the fill-pointer for an ebits e
.
ebits-fill-pointer-set!
(ebits-fill-pointer-set! e fp initial-value: (iv #f) extend: (extend #t)) => fixnum or bool
(&ebits-fill-pointer-set! e fp iv extend) => fixnum or bool
Given an ebits e
, a new value fp
for its fill-pointer,
an initial value iv
for new elements, and a boolean or fixnum extend
,
try to set the fill-pointer of e
to fp
:
- If
fp
is greater than the length of the supporting ofe
, butextend
is#f
or a negative fixnum, then don’t set the fill-pointer, and instead return#f
. - If
fp
is no greater than the length of the supporting bits ofe
, set the fill-pointer ofe
tofp
, and returnfp
. - If
extend
is#t
, extend the ebits using an exponential backoff strategy guaranteeing a constant-time space and time overhead factor over non-extensible bitss, set the fill-pointer tofp
and returnfp
. - If
extend
is a non-negative fixnum, extend the ebits to have length(+ fp extend)
, set the fill-pointer tofp
and returnfp
.
ebits-push! &ebits-push!
(ebits-push! e x initial-value: (iv #f) extend: (extend #t)) => unspecified
(&ebits-push! e x iv extend) => unspecified
Try to push value x
at the end of the ebits e
:
Increment the fill-pointer of e
as if using ebits-extend!
with initial value iv
and argument extend
;
if the fill-pointer could be incremented, set the value at last index to x
.