(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)

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

(gvector-empty? obj)

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

Constructors

(make-gvector) (make-gvector c)

Returns a newly allocated growable vector of capacity c. The capacity is used to pre-allocate space for up to c elements.

(gvector obj ...)

Returns a newly allocated growable vector whose elements contain the given arguments.

(gvector ’a ’b ’c)  ⇒  #g(a b c)

(list->gvector list)

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

(list->gvector ’(a b c))  ⇒  #g(a b c)

(vector->gvector vector)

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

(gvector-copy vector) (gvector-copy vector start) (gvector-copy vector start end)

Returns a newly allocated copy of the elements of the given growable 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.

(gvector-append vector ...)

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

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

(gvector-concatenate vector xs)

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

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

(gvector-map f vector1 vector2 ...)

Constructs a new growable 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.

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

(gvector-map/index f vector1 vector2 ...)

Constructs a new growable 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.

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

Iterating over vector elements

(gvector-for-each f vector1 vector2 ...)

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 ...)

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)

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

(gvector-ref vector k)

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

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

(gvector-set! vector k obj)

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

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

(gvector-add! vector obj ...)

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)

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)

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)

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) (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 ...)

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

(gvector-reverse! vector) (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 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 ...)

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 ...)

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) (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) (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)