@c This file is part of the MIT/GNU Scheme Reference Manual.
@c $Id: vectors.texi,v 1.3 2008/01/30 20:06:12 cph Exp $

@c Copyright (C) 1986, 1987, 1988, 1989, 1990, 1991, 1992, 1993, 1994,
@c     1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004,
@c     2005, 2006, 2007, 2008 Massachusetts Institute of Technology
@c See file scheme.texinfo for copying conditions.

@node Vectors, Bit Strings, Lists, Top
@chapter Vectors

@cindex vector (defn)
@dfn{Vectors} are heterogenous structures whose elements are indexed by
exact non-negative integers.  A vector typically occupies less space
than a list of the same length, and the average time required to access
a randomly chosen element is typically less for the vector than for the
list.

@cindex length, of vector (defn)
@cindex index, of vector (defn)
@cindex valid index, of vector (defn)
@cindex vector length (defn)
@cindex vector index (defn)
The @dfn{length} of a vector is the number of elements that it contains.
This number is an exact non-negative integer that is fixed when the
vector is created.  The @dfn{valid indexes} of a 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 vector.

@cindex external representation, for vector
@cindex #( as external representation
@cindex parenthesis, as external representation
@findex #(
Vectors are written using the notation @code{#(@var{object} @dots{})}.
For example, a vector of length 3 containing the number zero in element
0, the list @code{(2 2 2 2)} in element 1, and the string @code{"Anna"}
in element 2 can be written as

@example
#(0 (2 2 2 2) "Anna")
@end example

@noindent
Note that this is the external representation of a vector, not an
expression evaluating to a vector.  Like list constants, vector
constants must be quoted:

@example
'#(0 (2 2 2 2) "Anna")          @result{}  #(0 (2 2 2 2) "Anna")
@end example

@cindex subvector (defn)
@cindex start, of subvector (defn)
@cindex end, of subvector (defn)
@cindex index, of subvector (defn)
@cindex valid index, of subvector (defn)
A number of the vector procedures operate on subvectors.  A
@dfn{subvector} is a segment of a vector that is specified by two exact
non-negative integers, @var{start} and @var{end}.  @var{Start} is the
index of the first element that is included in the subvector, and
@var{end} is one greater than the index of the last element that is
included in the subvector.  Thus if @var{start} and @var{end} are the
same, they refer to a null subvector, and if @var{start} is zero and
@var{end} is the length of the vector, they refer to the entire vector.
The @dfn{valid indexes} of a subvector are the exact integers between
@var{start} inclusive and @var{end} exclusive.

@menu
* Construction of Vectors::     
* Selecting Vector Components::  
* Cutting Vectors::             
* Modifying Vectors::           
@end menu

@node Construction of Vectors, Selecting Vector Components, Vectors, Vectors
@section Construction of Vectors
@cindex construction, of vector

@deffn {procedure} make-vector k [object]
Returns a newly allocated vector of @var{k} elements.  If @var{object}
is specified, @code{make-vector} initializes each element of the vector
to @var{object}.  Otherwise the initial elements of the result are
unspecified.
@end deffn

@deffn procedure vector object @dots{}
@findex list
Returns a newly allocated vector whose elements are the given arguments.
@code{vector} is analogous to @code{list}.

@example
(vector 'a 'b 'c)                       @result{}  #(a b c)
@end example
@end deffn

@deffn procedure vector-copy vector
@cindex copying, of vector
Returns a newly allocated vector that is a copy of @var{vector}.
@end deffn

@deffn procedure list->vector list
@cindex list, converting to vector
@findex vector->list
Returns a newly allocated vector initialized to the elements of
@var{list}.  The inverse of @code{list->vector} is @code{vector->list}.

@example
(list->vector '(dididit dah))           @result{}  #(dididit dah)
@end example
@end deffn

@deffn procedure make-initialized-vector k initialization
Similar to @code{make-vector}, except that the elements of the result
are determined by calling the procedure @var{initialization} on the
indices.  For example:

@example
@group
(make-initialized-vector 5 (lambda (x) (* x x)))
     @result{}  #(0 1 4 9 16)
@end group
@end example
@end deffn

@deffn procedure vector-grow vector k
@cindex growing, of vector
@var{K} must be greater than or equal to the length of @var{vector}.
Returns a newly allocated vector of length @var{k}.  The first
@code{(vector-length @var{vector})} elements of the result are
initialized from the corresponding elements of @var{vector}.  The
remaining elements of the result are unspecified.
@end deffn

@deffn procedure vector-map procedure vector
@cindex mapping, of vector
@var{Procedure} must be a procedure of one argument.  @code{vector-map}
applies @var{procedure} element-wise to the elements of @var{vector} and
returns a newly allocated vector of the results, in order from left to
right.  The dynamic order in which @var{procedure} is applied to the
elements of @var{vector} is unspecified.

@example
@group
(vector-map cadr '#((a b) (d e) (g h)))     @result{}  #(b e h)
(vector-map (lambda (n) (expt n n)) '#(1 2 3 4))
                                            @result{}  #(1 4 27 256)
(vector-map + '#(5 7 9))                    @result{}  #(5 7 9)
@end group
@end example
@end deffn

@node Selecting Vector Components, Cutting Vectors, Construction of Vectors, Vectors
@section Selecting Vector Components
@cindex selection, of vector component
@cindex component selection, of vector

@deffn procedure vector? object
@cindex type predicate, for vector
Returns @code{#t} if @var{object} is a vector; otherwise returns
@code{#f}.
@end deffn

@deffn procedure vector-length vector
Returns the number of elements in @var{vector}.
@end deffn

@deffn procedure vector-ref vector k
Returns the contents of element @var{k} of @var{vector}.  @var{K} must
be a valid index of @var{vector}.

@example
(vector-ref '#(1 1 2 3 5 8 13 21) 5)    @result{}  8
@end example
@end deffn

@deffn procedure vector-set! vector k object
Stores @var{object} in element @var{k} of @var{vector} and returns an
unspecified value.  @var{K} must be a valid index of
@var{vector}.

@example
@group
(let ((vec (vector 0 '(2 2 2 2) "Anna")))
  (vector-set! vec 1 '("Sue" "Sue"))
  vec)
     @result{}  #(0 ("Sue" "Sue") "Anna")
@end group
@end example
@end deffn

@deffn procedure vector-first vector
@deffnx procedure vector-second vector
@deffnx procedure vector-third vector
@deffnx procedure vector-fourth vector
@deffnx procedure vector-fifth vector
@deffnx procedure vector-sixth vector
@deffnx procedure vector-seventh vector
@deffnx procedure vector-eighth vector
These procedures access the first several elements of @var{vector} in
the obvious way.  It is an error if the implicit index of one of these
procedurs is not a valid index of @var{vector}.
@end deffn

@deffn procedure vector-binary-search vector key<? unwrap-key key
@cindex searching, of vector
Searches @var{vector} for an element with a key matching @var{key},
returning the element if one is found or @code{#f} if none.  The
search operation takes time proportional to the logarithm of the length
of @var{vector}.  @var{Unwrap-key} must be a procedure that maps each
element of @var{vector} to a key.  @var{Key<?} must be a procedure that
implements a total ordering on the keys of the elements.

@example
@group
(define (translate number)
  (vector-binary-search '#((1 . i)
                           (2 . ii)
                           (3 . iii)
                           (6 . vi))
                        < car number))
(translate 2)  @result{}  (2 . ii)
(translate 4)  @result{}  #F
@end group
@end example
@end deffn

@node Cutting Vectors, Modifying Vectors, Selecting Vector Components, Vectors
@section Cutting Vectors
@cindex cutting, of vector

@deffn procedure subvector vector start end
Returns a newly allocated vector that contains the elements of
@var{vector} between index @var{start} (inclusive) and @var{end}
(exclusive).
@end deffn

@deffn procedure vector-head vector end
Equivalent to

@example
(subvector @var{vector} 0 @var{end})
@end example
@end deffn

@deffn procedure vector-tail vector start
Equivalent to

@example
(subvector @var{vector} @var{start} (vector-length @var{vector}))
@end example
@end deffn

@node Modifying Vectors,  , Cutting Vectors, Vectors
@section Modifying Vectors
@cindex modification, of vector
@cindex filling, of vector
@cindex moving, of vector elements

@deffn {procedure} vector-fill! vector object
@deffnx procedure subvector-fill! vector start end object
Stores @var{object} in every element of the vector (subvector) and
returns an unspecified value.
@end deffn

@deffn procedure subvector-move-left! vector1 start1 end1 vector2 start2
@deffnx procedure subvector-move-right! vector1 start1 end1 vector2 start2
Destructively copies the elements of @var{vector1}, starting with index
@var{start1} (inclusive) and ending with @var{end1} (exclusive), into
@var{vector2} starting at index @var{start2} (inclusive).
@var{Vector1}, @var{start1}, and @var{end1} must specify a valid
subvector, and @var{start2} must be a valid index for @var{vector2}.
The length of the source subvector must not exceed the length of
@var{vector2} minus the index @var{start2}.

The elements are copied as follows (note that this is only important when
@var{vector1} and @var{vector2} are @code{eqv?}):

@table @code
@item subvector-move-left!
The copy starts at the left end and moves toward the right (from smaller
indices to larger).  Thus if @var{vector1} and @var{vector2} are the
same, this procedure moves the elements toward the left inside the
vector.

@item subvector-move-right!
The copy starts at the right end and moves toward the left (from larger
indices to smaller).  Thus if @var{vector1} and @var{vector2} are the
same, this procedure moves the elements toward the right inside the
vector.
@end table
@end deffn

@deffn procedure sort! vector procedure
@deffnx procedure merge-sort! vector procedure
@deffnx procedure quick-sort! vector procedure
@var{Procedure} must be a procedure of two arguments that defines a
@dfn{total ordering} on the elements of @var{vector}.  The elements of
@var{vector} are rearranged so that they are sorted in the order defined
by @var{procedure}.  The elements are rearranged in place, that is,
@var{vector} is destructively modified so that its elements are in the
new order.

@code{sort!} returns @var{vector} as its value.

Two sorting algorithms are implemented: @code{merge-sort!} and
@code{quick-sort!}.  The procedure @code{sort!} is an alias for
@code{merge-sort!}.

See also the definition of @code{sort}.
@end deffn
