--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/man/lispref/sequences.texi	Mon Aug 13 08:45:50 2007 +0200
@@ -0,0 +1,650 @@
+@c -*-texinfo-*-
+@c This is part of the XEmacs Lisp Reference Manual.
+@c Copyright (C) 1990, 1991, 1992, 1993, 1994 Free Software Foundation, Inc.
+@c Copyright (C) 1996 Ben Wing.
+@c See the file lispref.texi for copying conditions.
+@setfilename ../../info/sequences.info
+@node Sequences Arrays Vectors, Symbols, Lists, Top
+@chapter Sequences, Arrays, and Vectors
+@cindex sequence
+
+  Recall that the @dfn{sequence} type is the union of four other Lisp
+types: lists, vectors, bit vectors, and strings.  In other words, any
+list is a sequence, any vector is a sequence, any bit vector is a
+sequence, and any string is a sequence.  The common property that all
+sequences have is that each is an ordered collection of elements.
+
+  An @dfn{array} is a single primitive object that has a slot for each
+elements.  All the elements are accessible in constant time, but the
+length of an existing array cannot be changed.  Strings, vectors, and
+bit vectors are the three types of arrays.
+
+  A list is a sequence of elements, but it is not a single primitive
+object; it is made of cons cells, one cell per element.  Finding the
+@var{n}th element requires looking through @var{n} cons cells, so
+elements farther from the beginning of the list take longer to access.
+But it is possible to add elements to the list, or remove elements.
+
+  The following diagram shows the relationship between these types:
+
+@example
+@group
+          ___________________________________
+         |                                   |
+         |          Sequence                 |
+         |  ______   ______________________  |
+         | |      | |                      | |
+         | | List | |         Array        | |
+         | |      | |  ________   _______  | |
+         | |______| | |        | |       | | |
+         |          | | Vector | | String| | |
+         |          | |________| |_______| | |
+         |          |  __________________  | |
+         |          | |                  | | |
+         |          | |    Bit Vector    | | |
+         |          | |__________________| | |
+         |          |______________________| |
+         |___________________________________|
+@end group
+@end example
+
+  The elements of vectors and lists may be any Lisp objects.  The
+elements of strings are all characters.  The elements of bit vectors
+are the numbers 0 and 1.
+
+@menu
+* Sequence Functions::    Functions that accept any kind of sequence.
+* Arrays::                Characteristics of arrays in XEmacs Lisp.
+* Array Functions::       Functions specifically for arrays.
+* Vectors::               Special characteristics of XEmacs Lisp vectors.
+* Vector Functions::      Functions specifically for vectors.
+* Bit Vectors::           Special characteristics of XEmacs Lisp bit vectors.
+* Bit Vector Functions::  Functions specifically for bit vectors.
+@end menu
+
+@node Sequence Functions
+@section Sequences
+
+  In XEmacs Lisp, a @dfn{sequence} is either a list, a vector, a bit
+vector, or a string.  The common property that all sequences have is
+that each is an ordered collection of elements.  This section describes
+functions that accept any kind of sequence.
+
+@defun sequencep object
+Returns @code{t} if @var{object} is a list, vector, bit vector, or
+string, @code{nil} otherwise.
+@end defun
+
+@defun copy-sequence sequence
+@cindex copying sequences
+Returns a copy of @var{sequence}.  The copy is the same type of object
+as the original sequence, and it has the same elements in the same order.
+
+Storing a new element into the copy does not affect the original
+@var{sequence}, and vice versa.  However, the elements of the new
+sequence are not copies; they are identical (@code{eq}) to the elements
+of the original.  Therefore, changes made within these elements, as
+found via the copied sequence, are also visible in the original
+sequence.
+
+If the sequence is a string with extents or text properties, the extents
+and text properties in the copy are also copied, not shared with the
+original. (This means that modifying the extents or text properties of
+the original will not affect the copy.) However, the actual values of
+the properties are shared.  @xref{Extents}; @xref{Text Properties}.
+
+See also @code{append} in @ref{Building Lists}, @code{concat} in
+@ref{Creating Strings}, @code{vconcat} in @ref{Vectors}, and
+@code{bvconcat} in @ref{Bit Vectors}, for other ways to copy sequences.
+
+@example
+@group
+(setq bar '(1 2))
+     @result{} (1 2)
+@end group
+@group
+(setq x (vector 'foo bar))
+     @result{} [foo (1 2)]
+@end group
+@group
+(setq y (copy-sequence x))
+     @result{} [foo (1 2)]
+@end group
+
+@group
+(eq x y)
+     @result{} nil
+@end group
+@group
+(equal x y)
+     @result{} t
+@end group
+@group
+(eq (elt x 1) (elt y 1))
+     @result{} t
+@end group
+
+@group
+;; @r{Replacing an element of one sequence.}
+(aset x 0 'quux)
+x @result{} [quux (1 2)]
+y @result{} [foo (1 2)]
+@end group
+
+@group
+;; @r{Modifying the inside of a shared element.}
+(setcar (aref x 1) 69)
+x @result{} [quux (69 2)]
+y @result{} [foo (69 2)]
+@end group
+
+@group
+;; @r{Creating a bit vector.}
+(bit-vector 1 0 1 1 0 1 0 0)
+     @result{} #*10110100
+@end group
+@end example
+@end defun
+
+@defun length sequence
+@cindex string length
+@cindex list length
+@cindex vector length
+@cindex bit vector length
+@cindex sequence length
+Returns the number of elements in @var{sequence}.  If @var{sequence} is
+a cons cell that is not a list (because the final @sc{cdr} is not
+@code{nil}), a @code{wrong-type-argument} error is signaled.
+
+@example
+@group
+(length '(1 2 3))
+    @result{} 3
+@end group
+@group
+(length ())
+    @result{} 0
+@end group
+@group
+(length "foobar")
+    @result{} 6
+@end group
+@group
+(length [1 2 3])
+    @result{} 3
+@end group
+@group
+(length #*01101)
+    @result{} 5
+@end group
+@end example
+@end defun
+
+@defun elt sequence index
+@cindex elements of sequences
+This function returns the element of @var{sequence} indexed by
+@var{index}.  Legitimate values of @var{index} are integers ranging from
+0 up to one less than the length of @var{sequence}.  If @var{sequence}
+is a list, then out-of-range values of @var{index} return @code{nil};
+otherwise, they trigger an @code{args-out-of-range} error.
+
+@example
+@group
+(elt [1 2 3 4] 2)
+     @result{} 3
+@end group
+@group
+(elt '(1 2 3 4) 2)
+     @result{} 3
+@end group
+@group
+(char-to-string (elt "1234" 2))
+     @result{} "3"
+@end group
+@group
+(elt #*00010000 3)
+     @result{} 1
+@end group
+@group
+(elt [1 2 3 4] 4)
+     @error{}Args out of range: [1 2 3 4], 4
+@end group
+@group
+(elt [1 2 3 4] -1)
+     @error{}Args out of range: [1 2 3 4], -1
+@end group
+@end example
+
+This function generalizes @code{aref} (@pxref{Array Functions}) and
+@code{nth} (@pxref{List Elements}).
+@end defun
+
+@node Arrays
+@section Arrays
+@cindex array
+
+  An @dfn{array} object has slots that hold a number of other Lisp
+objects, called the elements of the array.  Any element of an array may
+be accessed in constant time.  In contrast, an element of a list
+requires access time that is proportional to the position of the element
+in the list.
+
+  When you create an array, you must specify how many elements it has.
+The amount of space allocated depends on the number of elements.
+Therefore, it is impossible to change the size of an array once it is
+created; you cannot add or remove elements.  However, you can replace an
+element with a different value.
+
+  XEmacs defines three types of array, all of which are one-dimensional:
+@dfn{strings}, @dfn{vectors}, and @dfn{bit vectors}.  A vector is a
+general array; its elements can be any Lisp objects.  A string is a
+specialized array; its elements must be characters.  A bit vector is
+another specialized array; its elements must be bits (an integer, either
+0 or 1).  Each type of array has its own read syntax.  @xref{String
+Type}, @ref{Vector Type}, and @ref{Bit Vector Type}.
+
+  All kinds of array share these characteristics:
+
+@itemize @bullet
+@item
+The first element of an array has index zero, the second element has
+index 1, and so on.  This is called @dfn{zero-origin} indexing.  For
+example, an array of four elements has indices 0, 1, 2, @w{and 3}.
+
+@item
+The elements of an array may be referenced or changed with the functions
+@code{aref} and @code{aset}, respectively (@pxref{Array Functions}).
+@end itemize
+
+  In principle, if you wish to have an array of text characters, you
+could use either a string or a vector.  In practice, we always choose
+strings for such applications, for four reasons:
+
+@itemize @bullet
+@item
+They usually occupy one-fourth the space of a vector of the same
+elements.  (This is one-eighth the space for 64-bit machines such as the
+DEC Alpha, and may also be different when @sc{MULE} support is compiled
+into XEmacs.)
+
+@item
+Strings are printed in a way that shows the contents more clearly
+as characters.
+
+@item
+Strings can hold extent and text properties.  @xref{Extents}; @xref{Text
+Properties}.
+
+@item
+Many of the specialized editing and I/O facilities of XEmacs accept only
+strings.  For example, you cannot insert a vector of characters into a
+buffer the way you can insert a string.  @xref{Strings and Characters}.
+@end itemize
+
+  By contrast, for an array of keyboard input characters (such as a key
+sequence), a vector may be necessary, because many keyboard input
+characters are non-printable and are represented with symbols rather than
+with characters.  @xref{Key Sequence Input}.
+
+  Similarly, when representing an array of bits, a bit vector has
+the following advantages over a regular vector:
+
+@itemize @bullet
+@item
+They occupy 1/32nd the space of a vector of the same elements.
+(1/64th on 64-bit machines such as the DEC Alpha.)
+
+@item
+Bit vectors are printed in a way that shows the contents more clearly
+as bits.
+@end itemize
+
+@node Array Functions
+@section Functions that Operate on Arrays
+
+  In this section, we describe the functions that accept both strings
+and vectors.
+
+@defun arrayp object
+This function returns @code{t} if @var{object} is an array (i.e., either a
+vector or a string).
+
+@example
+@group
+(arrayp [a])
+@result{} t
+(arrayp "asdf")
+@result{} t
+@end group
+@end example
+@end defun
+
+@defun aref array index
+@cindex array elements
+This function returns the @var{index}th element of @var{array}.  The
+first element is at index zero.
+
+@example
+@group
+(setq primes [2 3 5 7 11 13])
+     @result{} [2 3 5 7 11 13]
+(aref primes 4)
+     @result{} 11
+(elt primes 4)
+     @result{} 11
+@end group
+
+@group
+(aref "abcdefg" 1)
+     @result{} 98           ; @r{@samp{b} is @sc{ASCII} code 98.}
+@end group
+@end example
+
+See also the function @code{elt}, in @ref{Sequence Functions}.
+@end defun
+
+@defun aset array index object
+This function sets the @var{index}th element of @var{array} to be
+@var{object}.  It returns @var{object}.
+
+@example
+@group
+(setq w [foo bar baz])
+     @result{} [foo bar baz]
+(aset w 0 'fu)
+     @result{} fu
+w
+     @result{} [fu bar baz]
+@end group
+
+@group
+(setq x "asdfasfd")
+     @result{} "asdfasfd"
+(aset x 3 ?Z)
+     @result{} 90
+x
+     @result{} "asdZasfd"
+@end group
+@end example
+
+If @var{array} is a string and @var{object} is not a character, a
+@code{wrong-type-argument} error results.
+@end defun
+
+@defun fillarray array object
+This function fills the array @var{array} with @var{object}, so that
+each element of @var{array} is @var{object}.  It returns @var{array}.
+
+@example
+@group
+(setq a [a b c d e f g])
+     @result{} [a b c d e f g]
+(fillarray a 0)
+     @result{} [0 0 0 0 0 0 0]
+a
+     @result{} [0 0 0 0 0 0 0]
+@end group
+@group
+(setq s "When in the course")
+     @result{} "When in the course"
+(fillarray s ?-)
+     @result{} "------------------"
+@end group
+@end example
+
+If @var{array} is a string and @var{object} is not a character, a
+@code{wrong-type-argument} error results.
+@end defun
+
+The general sequence functions @code{copy-sequence} and @code{length}
+are often useful for objects known to be arrays.  @xref{Sequence Functions}.
+
+@node Vectors
+@section Vectors
+@cindex vector
+
+  Arrays in Lisp, like arrays in most languages, are blocks of memory
+whose elements can be accessed in constant time.  A @dfn{vector} is a
+general-purpose array; its elements can be any Lisp objects.  (The other
+kind of array in XEmacs Lisp is the @dfn{string}, whose elements must be
+characters.)  Vectors in XEmacs serve as obarrays (vectors of symbols),
+although this is a shortcoming that should be fixed.  They are also used
+internally as part of the representation of a byte-compiled function; if
+you print such a function, you will see a vector in it.
+
+  In XEmacs Lisp, the indices of the elements of a vector start from zero
+and count up from there.
+
+  Vectors are printed with square brackets surrounding the elements.
+Thus, a vector whose elements are the symbols @code{a}, @code{b} and
+@code{a} is printed as @code{[a b a]}.  You can write vectors in the
+same way in Lisp input.
+
+  A vector, like a string or a number, is considered a constant for
+evaluation: the result of evaluating it is the same vector.  This does
+not evaluate or even examine the elements of the vector.
+@xref{Self-Evaluating Forms}.
+
+  Here are examples of these principles:
+
+@example
+@group
+(setq avector [1 two '(three) "four" [five]])
+     @result{} [1 two (quote (three)) "four" [five]]
+(eval avector)
+     @result{} [1 two (quote (three)) "four" [five]]
+(eq avector (eval avector))
+     @result{} t
+@end group
+@end example
+
+@node Vector Functions
+@section Functions That Operate on Vectors
+
+  Here are some functions that relate to vectors:
+
+@defun vectorp object
+This function returns @code{t} if @var{object} is a vector.
+
+@example
+@group
+(vectorp [a])
+     @result{} t
+(vectorp "asdf")
+     @result{} nil
+@end group
+@end example
+@end defun
+
+@defun vector &rest objects
+This function creates and returns a vector whose elements are the
+arguments, @var{objects}.
+
+@example
+@group
+(vector 'foo 23 [bar baz] "rats")
+     @result{} [foo 23 [bar baz] "rats"]
+(vector)
+     @result{} []
+@end group
+@end example
+@end defun
+
+@defun make-vector length object
+This function returns a new vector consisting of @var{length} elements,
+each initialized to @var{object}.
+
+@example
+@group
+(setq sleepy (make-vector 9 'Z))
+     @result{} [Z Z Z Z Z Z Z Z Z]
+@end group
+@end example
+@end defun
+
+@defun vconcat &rest sequences
+@cindex copying vectors
+This function returns a new vector containing all the elements of the
+@var{sequences}.  The arguments @var{sequences} may be lists, vectors,
+or strings.  If no @var{sequences} are given, an empty vector is
+returned.
+
+The value is a newly constructed vector that is not @code{eq} to any
+existing vector.
+
+@example
+@group
+(setq a (vconcat '(A B C) '(D E F)))
+     @result{} [A B C D E F]
+(eq a (vconcat a))
+     @result{} nil
+@end group
+@group
+(vconcat)
+     @result{} []
+(vconcat [A B C] "aa" '(foo (6 7)))
+     @result{} [A B C 97 97 foo (6 7)]
+@end group
+@end example
+
+The @code{vconcat} function also allows integers as arguments.  It
+converts them to strings of digits, making up the decimal print
+representation of the integer, and then uses the strings instead of the
+original integers.  @strong{Don't use this feature; we plan to eliminate
+it.  If you already use this feature, change your programs now!}  The
+proper way to convert an integer to a decimal number in this way is with
+@code{format} (@pxref{Formatting Strings}) or @code{number-to-string}
+(@pxref{String Conversion}).
+
+For other concatenation functions, see @code{mapconcat} in @ref{Mapping
+Functions}, @code{concat} in @ref{Creating Strings}, @code{append}
+in @ref{Building Lists}, and @code{bvconcat} in @ref{Bit Vector Functions}.
+@end defun
+
+  The @code{append} function provides a way to convert a vector into a
+list with the same elements (@pxref{Building Lists}):
+
+@example
+@group
+(setq avector [1 two (quote (three)) "four" [five]])
+     @result{} [1 two (quote (three)) "four" [five]]
+(append avector nil)
+     @result{} (1 two (quote (three)) "four" [five])
+@end group
+@end example
+
+@node Bit Vectors
+@section Bit Vectors
+@cindex bit vector
+
+  Bit vectors are specialized vectors that can only represent arrays
+of 1's and 0's.  Bit vectors have a very efficient representation
+and are useful for representing sets of boolean (true or false) values.
+
+  There is no limit on the size of a bit vector.  You could, for example,
+create a bit vector with 100,000 elements if you really wanted to.
+
+  Bit vectors have a special printed representation consisting of
+@samp{#*} followed by the bits of the vector.  For example, a bit
+vector whose elements are 0, 1, 1, 0, and 1, respectively, is printed
+as
+
+@example
+#*01101
+@end example
+
+  Bit vectors are considered constants for evaluation, like vectors,
+strings, and numbers.  @xref{Self-Evaluating Forms}.
+
+@node Bit Vector Functions
+@section Functions That Operate on Bit Vectors
+
+  Here are some functions that relate to bit vectors:
+
+@defun bit-vector-p object
+This function returns @code{t} if @var{object} is a bit vector.
+
+@example
+@group
+(bit-vector-p #*01)
+     @result{} t
+(bit-vector-p [0 1])
+     @result{} nil
+(vectorp "asdf")
+     @result{} nil
+@end group
+@end example
+@end defun
+
+@defun bitp object
+This function returns @code{t} if @var{object} is either 0 or 1.
+@end defun
+
+@defun bit-vector &rest objects
+This function creates and returns a vector whose elements are the
+arguments, @var{objects}.  The elements must be either of the two
+integers 0 or 1.
+
+@example
+@group
+(bit-vector 0 0 0 1 0 0 0 0 1 0)
+     @result{} #*0001000010
+(vector)
+     @result{} #*
+@end group
+@end example
+@end defun
+
+@defun make-bit-vector length object
+This function returns a new bit vector consisting of @var{length} elements,
+each initialized to @var{object}.
+
+@example
+@group
+(setq sleepy (make-vector 9 1))
+     @result{} #*111111111
+@end group
+@end example
+@end defun
+
+@defun bvconcat &rest sequences
+@cindex copying bit vectors
+This function returns a new bit vector containing all the elements of the
+@var{sequences}.  The arguments @var{sequences} may be lists or vectors,
+all of whose elements are the integers 0 or 1.  If no @var{sequences} are
+given, an empty bit vector is returned.
+
+The value is a newly constructed bit vector that is not @code{eq} to any
+existing vector.
+
+@example
+@group
+(setq a (bvconcat '(1 1 0) '(0 0 1)))
+     @result{} #*110001
+(eq a (bvconcat a))
+     @result{} nil
+@end group
+@group
+(bvconcat)
+     @result{} #*
+(bvconcat [1 0 0 0 0] #*111 '(0 0 0 0 1))
+     @result{} #*1000011100001
+@end group
+@end example
+
+For other concatenation functions, see @code{mapconcat} in @ref{Mapping
+Functions}, @code{concat} in @ref{Creating Strings}, @code{vconcat} in
+@ref{Vector Functions}, and @code{append} in @ref{Building Lists}.
+@end defun
+
+  The @code{append} function provides a way to convert a bit vector into a
+list with the same elements (@pxref{Building Lists}):
+
+@example
+@group
+(setq avector #*00001110)
+     @result{} #*00001110
+(append avector nil)
+     @result{} (0 0 0 0 1 1 1 0)
+@end group
+@end example