# LispKit GVector

This library defines an API for growable vectors. Just like regular vectors, growable vectors are heterogeneous sequences of elements which are indexed by a range of integers. Unlike for regular vectors, the length of a growable vector is not fixed. Growable vectors may expand or shrink in length. Nevertheless, growable vectors are fully compatible to regular vectors and all operations from library `(lispkit vector)` may also be used in combination with growable vectors. The main significance of library `(lispkit gvector)` is in providing functions to construct growable vectors. Growable vectors are always mutable by design.

Just like for vectors with a fixed length, the valid indexes of a growable vector are the exact, non-negative integers less than the length of the vector. The first element in a vector is indexed by zero, and the last element is indexed by one less than the length of the growable vector.

Two growable vectors are `equal?` if they have the same length, and if the values in corresponding slots of the vectors are `equal?`. A growable vector is never `equal?` a regular vector of fixed length.

Growable vectors are written using the notation `#g(obj ...)`. For example, a growable vector of initial length 3 containing the number one as element 0, the list (8 16 32) as element 1, and the string “Scheme” as element 2 can be written as follows: `#g(1 (8 16 32) "Scheme")`.

Growable vector constants are self-evaluating, so they do not need to be quoted in programs.

## Predicates

(gvector? obj) [procedure]

Returns `#t` if obj is a growable vector; otherwise returns `#f`.

(gvector-empty? obj) [procedure]

Returns `#t` if obj is a growable vector of length zero; otherwise returns `#f`.

## Constructors

(make-gvector k) [procedure]
(make-gvector k fill)

Returns a newly allocated vector of k elements. If a second argument is given, then each element is initialized to fill. Otherwise the initial contents of each element is unspecified.

(gvector obj …) [procedure]

Returns a newly allocated mutable vector whose elements contain the given arguments. It is analogous to `list`.

    (vector ’a ’b ’c)  ⇒  #(a b c)

(list->gvector list) [procedure]

The `list->vector` procedure returns a newly created mutable vector initialized to the elements of the list list in the order of the list.

    (list->vector ’(a b c))  ⇒  #(a b c)

(vector->gvector vector) [procedure]

Returns a newly allocated growable vector initialized to the elements of the vector vector in the order of vector.

(gvector-copy vector) [procedure]
(gvector-copy vector start)
(gvector-copy vector start end)

Returns a newly allocated copy of the elements of the given vector between start and end, but excluding the element at index end. The elements of the new vector are the same (in the sense of `eqv?`) as the elements of the old.

mutable is a boolean argument. If it is set to `#f`, an immutable copy of vector will be created. The type of the second argument of `vector-copy` is used to disambiguate between the second and third version of the function. An exact integer will always be interpreted as start, a boolean value will always be interpreted as mutable.

    (define a #(1 8 2 8))         ; a may be immutable
    (define b (vector-copy a))    ; creates a mutable copy of a
    (vector-set! b 0 3)           ; b is mutable
    b  ⇒  #(3 8 2 8)
    (define c (vector-copy a #f)) ; creates an immutable copy of a
    (vector-set! c 0 3)  ⇒  error  ; error, since c is immutable
    (define d (vector-copy b 1 3))
    d  ⇒  #(8 2)

(gvector-append vector …) [procedure]

Returns a newly allocated mutable vector whose elements are the concatenation of the elements of the given vectors.

    (vector-append #(a b c) #(d e f))  ⇒  #(a b c d e f)

(gvector-concatenate vector xs) [procedure]

Returns a newly allocated mutable vector whose elements are the concatenation of the elements of the vectors in xs. xs is a proper list of vectors.

    (vector-concatenate '(#(a b c) #(d) #(e f)))  ⇒  #(a b c d e f)

(gvector-map f vector1 vector2 …) [procedure]

Constructs a new mutable vector of the shortest size of the vector arguments vector1, vector2, etc. Each element at index i of the new vector is mapped from the old vectors by `(f (vector-ref vector1 i) (vector-ref vector2 i) ...)`. The dynamic order of the application of f is unspecified.

    (vector-map + #(1 2 3 4 5) #(10 20 30 40))  ⇒  #(11 22 33 44)

(gvector-map/index f vector1 vector2 …) [procedure]

Constructs a new mutable vector of the shortest size of the vector arguments vector1, vector2, etc. Each element at index i of the new vector is mapped from the old vectors by `(f i (vector-ref vector1 i) (vector-ref vector2 i) ...)`. The dynamic order of the application of f is unspecified.

    (vector-map/index (lambda (i x y) (cons i (+ x y))) #(1 2 3) #(10 20 30))  ⇒  #((0 . 11) (1 . 22) (2 . 33))

## Iterating over vector elements

(gvector-for-each f vector1 vector2 …) [procedure]

`gvector-for-each` implements a simple vector iterator: it applies f to the corresponding list of parallel elements from vectors vector1 vector2 … in the range [0, length), where length is the length of the smallest vector argument passed. In contrast with `gvector-map`, f is reliably applied to each subsequent element, starting at index 0, in the vectors.

    (gvector-for-each (lambda (x) (display x) (newline))
                      #g("foo" "bar" "baz" "quux" "zot"))
    ⇒
    foo
    bar
    baz
    quux
    zot

(gvector-for-each/index f vector1 vector2 …) [procedure]

`gvector-for-each/index` implements a simple vector iterator: it applies f to the index i and the corresponding list of parallel elements from vector1 vector2 … in the range [0, length), where length is the length of the smallest vector argument passed. The only difference to `gvector-for-each` is that `gvector-for-each/index` always passes the current index as the first argument of f in addition to the elements from the vectors vector1 vector2 ….

    (gvector-for-each/index
      (lambda (i x) (display i)(display ": ")(display x)(newline))
      #g("foo" "bar" "baz" "quux" "zot"))
    ⇒
    0: foo
    1: bar
    2: baz
    3: quux
    4: zot

## Managing vector state

(gvector-length vector) [procedure]

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

(gvector-ref vector k) [procedure]

The `vector-ref` procedure returns the contents of element k of vector. It is an error if k is not a valid index of vector.

    (vector-ref ’#(1 1 2 3 5 8 13 21) 5) ⇒  8
    (vector-ref ’#(1 1 2 3 5 8 13 21) (exact (round (* 2 (acos -1)))))  ⇒  13

(gvector-set! vector k obj) [procedure]

The `vector-set!` procedure stores obj in element k of vector. It is an error if k is not a valid index of vector.

    (let ((vec (vector 0 '(2 2 2 2) "Anna")))
      (vector-set! vec 1 '("Sue" "Sue"))
      vec)
      ⇒  #(0 ("Sue" "Sue") "Anna")
    (vector-set! '#(0 1 2) 1 "doe")
      ⇒  error    ;; constant/immutable vector

(gvector-add! vector obj …) [procedure]

Appends the values obj, … to growable vector vector. This increases the length of the growable vector by the number of obj arguments.

    (let ((vec (gvector 0 '(2 2 2 2) "Anna")))
    (gvector-add! vec "Micha")
    vec)
    ⇒  #g(0 (2 2 2 2) "Anna" "Micha")

(gvector-insert! vector k obj) [procedure]

Inserts the value obj into growable vector vector at index k. This increases the length of the growable vector by one.

    (let ((vec (gvector 0 '(2 2 2 2) "Anna")))
    (gvector-insert! vec 1 "Micha")
    vec)
    ⇒  #g(0 "Micha" (2 2 2 2) "Anna")

(gvector-remove! vector k) [procedure]

Removes the element at index k from growable vector vector. This decreases the length of the growable vector by one.

    (let ((vec (gvector 0 '(2 2 2 2) "Anna")))
    (gvector-remove! vec 1)
    vec)
    ⇒  #g(0 "Anna")

(gvector-remove-last! vector) [procedure]

Removes the last element of the growable vector vector. This decreases the length of the growable vector by one.

    (let ((vec (gvector 0 '(2 2 2 2) "Anna")))
    (gvector-remove-last! vec)
    vec)
    ⇒  #g(0 (2 2 2 2))

## Destructive growable vector operations

Procedures which operate only on a part of a growable vector specify the applicable range in terms of an index interval [start; end[; i.e. the end index is always exclusive.

(gvector-copy! to at from) [procedure]
(gvector-copy! to at from start)
(gvector-copy! to at from start end)

Copies the elements of vector from between start and end to growable vector to, starting at at. The order in which elements are copied is unspecified, except that if the source and destination overlap, copying takes place as if the source is first copied into a temporary vector and then into the destination. start defaults to 0 and end defaults to the length of vector.

It is an error if at is less than zero or greater than the length of to. It is also an error if `(- (gvector-length to) at)` is less than `(- end start)`.

    (define a (vector 1 2 3 4 5))
    (define b (gvector 10 20 30 40 50))
    (gvector-copy! b 1 a 0 2)
    b  ⇒  #g(10 1 2 40 50)

(gvector-append! vector v1 …) [procedure]

Appends the elements of the vectors v1 … to the growable vector vector in the given order.

(gvector-reverse! vector) [procedure]
(gvector-reverse! vector start)
(gvector-reverse! vector start end)

Procedure `gvector-reverse!` destructively reverses the contents of growable vector between start and end. start defaults to 0 and end defaults to the length of vector.

    (define a (gvector 1 2 3 4 5))
    (vector-reverse! a)
    a  ⇒  #g(5 4 3 2 1)

(gvector-sort! pred vector) [procedure]

Procedure `gvector-sort!` destructively sorts the elements of growable vector vector using the “less than” predicate pred.

    (define a (gvector 7 4 9 1 2 8 5))
    (gvector-sort! < a)
    a  ⇒  #g(1 2 4 5 7 8 9)

(gvector-map! f vector1 vector2 …) [procedure]

Similar to `gvector-map` which maps the various elements into a new vector via function f, procedure `gvector-map!` destructively inserts the mapped elements into growable vector vector1. The dynamic order in which f gets applied to the elements is unspecified.

    (define a (gvector 1 2 3 4))
    (gvector-map! + a #(10 20 30))
    a  ⇒  #g(11 22 33 4)

(gvector-map/index! f vector1 vector2 …) [procedure]

Similar to `gvector-map/index` which maps the various elements together with their index into a new vector via function f, procedure `gvector-map/index!` destructively inserts the mapped elements into growable vector vector1. The dynamic order in which f gets applied to the elements is unspecified.

    (define a #g(1 2 3 4))
    (gvector-map/index! (lambda (i x y) (cons i (+ x y))) a #(10 20 30))
    a  ⇒  #g((0 . 11) (1 . 22) (2 . 33) 4)

## Converting growable vectors

(gvector->list vector) [procedure]
(gvector->list vector start)
(gvector->list vector start end)

The `gvector->list` procedure returns a newly allocated list of the objects contained in the elements of growable vector between start and end in the same order as in vector.

    (gvector->list ’#g(dah dah didah))  ⇒  (dah dah didah)
    (gvector->list ’#g(dah dah didah) 1 2)  ⇒  (dah)

(gvector->vector vector) [procedure]
(gvector->vector vector start)
(gvector->vector vector start end)

The `gvector->list` procedure returns a newly allocated list of the objects contained in the elements of growable vector vector between start and end in the same order as in vector.

    (gvector->list ’#(dah dah didah))  ⇒  error since the argument is not a gvector
    (gvector->list ’#g(dah dah didah) 1 2)  ⇒  (dah)