doc.txt

# EXTENSIBLE VECTORS - Jens Axel Søgaard

```EXTENSIBLE VECTORS  -  Jens Axel Søgaard

(require (planet "evector.scm" (soegaard "evector.plt" 1 1)))

NEWS
Version 1.1
Added evector-map, evector-for-each, evector=? and evector-copy.
Thanks to Paulo Matos for code and documentation.
Version 1.0
First release as PLaneT package.

ABSTRACT

Extensible vectors are a low level resizeable data structure
resembling normal Scheme vectors.

RATIONALE

The purpose of extensible vectors is to provide a low level
vector-like data structure, that unlike vectors can be resized in
constant amortized time.

SPECIFICATION

Extensible vectors are heterogenous structures whose elements are
indexed by integers.  The average time to access a randomly chosen
element is typically the same as for a vector.

The length of an extensible vector is the number of elements that it
contains. This number is a non-negative integer. The valid indexes of
an extensible vector are the exact non-negative integers less than the
length of the extensible vector. The first element in an extensible
vector is indexed by zero, and the last element is indexed by one less
than the length of the extensible vector.

The length of an extensible vector is set by the procedure
set-evector-length!. Increasing the length of an extensible vector
will initialize the new elements with the fill value of the extensible
vector. The fill value is a value associated with the extensible
vector.

An extensible vector may be automatically expandable. If the
extensible vector is automatically expandable, an attempt to store an
element in the extensible vector at an index k larger than or equal to
the length of the extensible vector will automatically increase the
length of the extensible vector to k+1 before storing the element;
otherwise an error is signaled.

The space occupied by an extensible vector is affected by the history
of the extensible vector. The space occupied is typically less than
twice the space of a vector with a length equal to the maximum of the
lengths the extensible vector has had.

Example:

(require (planet "evector.scm" ("soegaard" "evector.plt" 1 1)))
> (define ev (evector 1 2 3))
> (evector-pop! ev)
3
> (evector-length ev)
2
> (evector->list ev)
(1 2)
> (evector-set! ev 7 7)
> (evector->vector ev)
#8(1 2 3 #f #f #f #f 7)
> (evector-push! ev 8)
8
> (evector->list ev)
(1 2 3 #f #f #f #f 7 8)

Further examples are found in the test suite in test-evector.scm.

PROCEDURES

> make-evector
procedure: (make-evector k)
procedure: (make-evector k fill)
procedure: (make-evector k fill automatic-expansion?)

Returns a newly allocated extensible vector of k elements, whose
elements are initialized to the fill value. If a second argument is
given, fill is used as the fill value; otherwise the fill value is
unspecified. If a third argument is given, it determines whether the
extensible vector is automatically expandable. Otherwise the
extensible vector will be automatically expandable.

> evector
procedure:  (evector obj ...)

Returns a newly allocated automatically expandabale extensible
vector whose elements contain the given arguments. The fill value is
unspecified.

> evector-ref
procedure:  (evector-ref evector k)

k must be a valid index of evector. Evector-ref returns the contents
of element k of evector.

> evector-set!
procedure:  (evector-set! evector k obj)

Evector-set! stores obj in element k of evector. If k is greater
than the length of evector, then evector is expanded if it is
automatically expandable; otherwise an error is signaled. The value
returned by evector-set! is unspecified.

> evector-length
procedure:  (evector-length evector)

Returns the number of elements in evector as an exact integer.

>set-evector-length!
procedure:  (set-evector-length! evector k)

Sets the length of the extensible vector evector to k. If k is
greater than the previous size of evector, the new elements with
index equal to or greater to the old size will be initialised to the
fill value of evector.

> evector?
procedure: (evector obj)

Returns #t if obj is an evector, otherwise returns #f.

> evector-fill
> set-evector-fill!
procedure:  (evector-fill evector)
procedure:  (set-evector-fill! evector fill)

Evector-fill returns the fill value of evector. Set-evector-fill!
changes the fill value to fill.

> evector->list
> list->evector
procedure:  (evector->list evector)
procedure:  (list->evector list)

Evector->list returns a newly allocated list of the objects
contained in the elements of evector. List->evector returns a newly
created extensible vector initialized to the elements of the list
list.

> evector->vector
> vector->evector
procdure:   (evector->vector evector)
procdure:   (vector->evector vector)

Evector->vector returns a newly allocated vector containing the
elements of evector. Vector->evector returns a newly allocated
extensible vector initialized to the elements of the vector vector.

> evector-fill!
procedure:  (evector-fill! evector fill)
procedure:  (evector-fill! evector fill start)
procedure:  (evector-fill! evector fill start end)

Stores fill in the elements of the evector with indexes from start
inclusive to end exclusive. The default value for start is 0, and
the default value for the end is the length of the extensible
vector.

> evector=?
procedure:   (evector=? evector)
procedure:   (evector=? evector procedure)

Given two evectors ev1, ev2 and optionally an equality procedure
(defaults to eqv?) returns true if, the evectors are of the same
length, and ev1[i] is equal to ev2[i] for all i according to
the equality procedure.

> evector-map
procedure:   (evector-map procedure evector evector ...)

The procedure must taking as many arguments as there are evectors and
returning a single value. If more than one evector is given, then the
returned evector has same length as the shortest evector. Evector-map
applies the procedure element-wise to the elements of the evectors and
returns a evector of the results in order.

> evector-for-each
procedure:   (evector-for-each procedure evector evector ...)

The arguments to for-each are like the arguments to evector-map, but
evector-for-each calls the procedure for its side effects  rather than
for its values. Evector-for-each is guaranteed to call
proc on the elements of the evectors in order from the first
element(s) to the last. The value returned by for-each is
unspecified.

> evector-copy
procedure:   (evector-copy evector)

Given an evector and a copy procedure, evector-copy
returns an evector with the same elements as the given evector.
The properties size and automatic expandability is also
copied.
```