1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311
|
@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
|