.c	Wednesday  June 1,1983  22:00  FM+6D.4H.42M.43S.  -*- Bolio -*-

.chapter "Arrays"
.setq array-section-page section-page

Arrays in lan{nil} encompass a large number of varied objects which
share certain features and aspects of usage.  lan{Nil} arrays may
'cindex array rank
'cindex rank, array
'cindex array
range in rank (number of dimensions) from 0 to about 250.
All array indices in lan{nil} are zero origined.  One-dimensional
arrays are term_i{vector}s, are of the type 3vector*, and may be
used by the various sequence functions (in chapter
(sequence-chapter-number)).  Restrictions on the types of the
elements of an array (its term_i{element type}) can result in
special storage and access strategies.
The data in multidimensional arrays is
always stored in row-major order;  this is compatible with
lan{maclisp}, although normally it does not matter.

.section "Array Creation, Access, and Attributes"

.defun make-array dimensions &key element-type displaced-to displaced-index-offset adjustable fill-pointer
This is the general array creation function.  2dimensions* may be
an integer, in which case the rank of the created array will be one
(it will be a vector), or a list of integers which are the sizes of
the corresponding dimensions of the array.

The array will be created to hold objects of type 2element-type*.
If this is not supplied, 3t* is assumed, and the created array
will be able to hold any lisp objects.  The most common types, aside
from 3t*, are 3bit* (which creates a bit-array), and
3string-char* (which creates a string-char-array).  The special
types which lan{nil} supports, and their consequences, are discussed
in (array-element-type-section-page).

If 2fill-pointer* is not null, then the array must be
one-dimensional (a vector).  It will be created with a fill pointer
initialized to 2fill-pointer*, which must be between zero
and the size of the array (inclusive).  Fill pointers are discussed in
(array-fill-pointer-section-page).

Normally, the size of an array may not be changed (other than by
modification of its fill pointer if it has one).  This allows the
implementation some leeway to provide for more efficient access and
storage.  However, if 2adjustable* is specified and not 3nil*,
then the array will be created in such a way that its size (and its
displacement attributes) can be modified later by 3adjust-array*.
Modification of array size and attributes is discussed in
(array-adjustment-section-page).

The 2displaced-to* and 2displaced-index-offset* arguments
control term_i{array displacement};
'cindex displacing arrays
that is where one array can "point into" another.  This is discussed
in (array-displacement-section-page).
.end_defun

.defun aref array &rest indices
Returns the element of 2array* addressed by the 2indices*.
The number of indices must match the rank of the array, and each index
must lie between zero (inclusive) and the size of the corresponding
dimension of the array (exclusive).

If the array is one dimensional (i.e., a vector) and has a fill
pointer, the fill pointer is 2not* used to decide the range of the
array which may be validly referenced;  3aref* may be used to
access 2all* elements of such an array.  In this, it differs from
3elt* ((elt-fun)).

An array element may be set by using 3setf* with 3aref*.
.end_defun

.defun array-rank array
Returns the rank of 2array*.
.end_defun

.defun array-dimension array dimension-number
Returns the size of the dimension 2dimension-number* of
2array*.  The dimension number must be between zero (inclusive)
and the rank of the array (exclusive).
.end_defun

.defun array-dimensions array
Returns a list of the sizes of the dimensions of the array.
.end_defun

.defun array-element-type array
Returns the element-type of 2array*.  This is not necessarily the
same as what was given as the 2element-type* argument to
3make-array*;  rather, it is the actual element-type used to
2implement* the array, which will be a supertype of the originally
specified element-type.  This is discussed further below.
.end_defun


.section "Array Element Types"
.setq array-element-type-section-page section-page

Arrays may be restricted to contain only a certain type of element;
this restriction is the term_i{element type} of the array.  Some
element-types are distinguished in that the arrays will then be of a
particular distinguishable type.  For instance, arrays with
element-type of 3string-char* are 3string-char-array*s, and
one-dimensional arrays of element-type 3string-char* (which are
therefore also vectors) are of type 3string*.  Similarly, the
types 3bit-array* and 3bit-vector* are distinguished.  There
are other type restrictions (most of which result in special storage
strategies for the data) which do not result in the array itself being of a
particular type;  nevertheless, the element-type of an array may be
obtained with the 3array-element-type* function
((array-element-type-fun)).

When an array is created with a particular element type, the system
chooses the most specific element type it offers which can satisfy the
requirement.  For instance, if an array is requested of element type
3(double-float 0.0 1.0)* (double-floats between zero and one), a
double-float array will be created.  Similarly, for an array with
element-type 3symbol*, the element-type 3t* will be used.
3array-element-type* returns the type actually used;  the
requested element-type is forgotten.

There are several array types currently defined by lan{nil}.  Most
of them are not particularly useful right now, because lan{nil} does
not yet have a smart enough compiler to cause declarations about array
element types to do anything smart with the array accessing.

.table 3 250 250
.item bit
The array can only hold bits (the integers 0 and 1).  A
one-dimensional array of element-type 3bit* is of the type
3bit-vector*.  If it not adjustable, not displaced, and has no
fill pointer, then it will be a 3simple-bit-vector*, and is
specially implemented (less storage overhead, and faster access), and
can be accessed efficiently with 3sbit* ((sbit-fun)).
Many lan{nil} complex datastructures, including the current
implementation of bignums and more complex arrays which hold bits,
small bytes, and binary data (such as double-floats), are built from
simple bit vectors.  Because of their
utility, bit arrays are discussed further in (bit-array-section-page).
.item string-char
The array can only hold characters which satisfy the predicate
3string-char-p* ((string-char-p-fun)).  A one-dimensional array of
this element-type is of type 3string*.  A string that is not
adjustable, not displaced, and has no fill pointer is of the type
3simple-string*;  this is implemented more efficiently than a more
general string, and can be efficiently accessed with the 3schar*
function ((schar-fun)).  Chapter (string-chapter-number) is
devoted to strings.
.item character
The array can hold only characters (but they may be any type of
characters).  This provides no advantage over the element-type 3t*
in the current implementation;  in a later lan{nil}, vectors of
element-type 3character* will be acceptable to the string
functions (chapter (string-chapter-number)).
.item (unsigned-byte 8)
.item1 (signed-byte 8)
.item1 (unsigned-byte 16)
.item1 (signed-byte 16)
Store those integers which are representable in the respective fields.
.item double-float
The 3double-float*s are stored packed in machine representation.
Until the compiler has sufficient power to specially handle accesses
to arrays of this type, there is no particular benefit to their use,
because a generic array reference to a double-float array will have to
cons the number to return it.
.item t
An array of element-type 3t* can hold any lisp object.  If such an
array is one-dimensional, not adjustable, not displaced, and has no
fill pointer, then it is a simple vector (of the type
3simple-vector*).  Such a vector is especially efficient,
and may be accessed with the 3svref* function ((svref-fun)).
.end_table


.section "Fill Pointers"
.setq array-fill-pointer-section-page section-page

The 3:fill-pointer* option to 3make-array* allows one to
create a vector of varying length.  It is only applicable to
one-dimensional arrays.  The fill pointer of a vector is an integer
which may range from 0
to the size of the vector.  It is used as the length of the vector;
the value of the fill pointer will be returned by 3length*
((length-fun)), and used as the length by all sequence and string
functions;  in fact, by everything except for 3aref* (and its
variants such as 3char* and 3bit*).  The contents of the array
at and beyond the fill pointer are still considered valid; they just
are not considered when the array is viewed as a sequence.

A string with a fill pointer is reputed to be similar to a lan{pl/i}
varying string, although such a comparison is beyond the realm of this
author's knowledge.

To find the actual allocated length of a vector which has a fill
pointer, use 3array-dimension* with a dimension number of 30*.
3array-dimension* always returns the allocated length.

.defun array-has-fill-pointer-p array
This returns 3t* if 2array* has a fill pointer (implying that
it is a vector), 3nil* otherwise.  It is an error for 2array*
to not be an array.
.end_defun

.defun fill-pointer vector
This returns the fill pointer of 2vector*, which 2must* be a
vector with a fill pointer.  This may be used with 3setf*.
.end_defun

.defun vector-push vector object
2vector* must be a vector with a fill pointer.  If the fill
pointer is a valid index into the vector (that is, its value is less
than the allocated length of the vector), then 3vector-push*
stores 2object* into that slot, increments the fill pointer, and
returns the original (unincremented) fill pointer (which addresses
where the object was stored).  If the fill pointer is the same as the
allocated length (the only other valid situation), then
3vector-push* returns 3nil*.

Note that the argument order to 3vector-push* differs from that of
the 3push* macro ((push-fun)).  This will be incompatibly
changed in the future, at which time 3vector-push* will contrive
to figure out which argument is which from their types.
.end_defun

.defun vector-push-extend vector object &optional extension
This is like 3vector-push*, but whereas 3vector-push* will
return 3nil* if the vector is "full", 3vector-push-extend*
will instead call 3adjust-array* to increase the size of
2vector* in order that it might do the push.  Thus, it never
returns 3nil*.  If 2extension* is supplied and not 3nil*,
then that is the amount by which the size of 2vector* is
incremented by 3adjust-array*, if necessary;  otherwise, some
random guess based on the current size is used.

In order for 3adjust-array* to succeed in increasing the size of
2vector*, 2vector* must have been created with the
3:adjustable* option to 3make-array*;  see
(array-adjustment-section-page).

The ordering of the arguments 2vector* and 2object* will be
reversed in the future;  see 3vector-push*, above.
.end_defun

.defun vector-pop vector
This is the inverse of 2vector-push*.  The fill pointer of
2vector* is decremented, and the object addressed by that index is
returned.  The fill pointer must not already be zero.
.end_defun

.defun reset-fill-pointer vector &optional (index 0)
Resets the fill pointer of 2vector*, which must have one.  If
2index* is not specified, 30* is assumed.

This function is obsoleted by the use of 3fill-pointer* with
3setf*.
.end_defun

One common use of vectors with fill pointers is as buffers.  For
example, the lan{nil} compiler uses a vector with a fill pointer for
allocating a table of value cell indices to be referenced by the code it
is compiling.  It creates a vector with 3make-array*, specifying
that the array is adjustable, and giving it an initial fill pointer of
30*.  Then, it uses 3vector-push-extend* to add a new entry,
and the value that returns is the index into this table.
3vector-push-extend* takes care of increasing the size of the
vector if the initial guess as to its size was too small.

This same technique can be used for generating text, if the vector is
a string (that is, 3make-array* was given 3string-char* as the
3:element-type* keyword).  This is how some string accumulating
primitives work.

With 3vector-pop*, vectors with fill pointers can also be used as
stacks.

.section "Displaced Arrays"
.setq array-displacement-section-page section-page

Arrays may be created which do not have data of their own, but in fact
"share" data with some other array.  These are term_i{displaced
arrays}.  The uses for displaced arrays vary.  One might want to
access the elements of a multi-dimensional array as if it were a
vector;  this could be done by
.lisp
(make-array 2size* :displaced-to 2other-array*)
.end_lisp
which returns a vector which will access the elements of
2other-array* in row-major-order.
With displacement, a term_i{displaced index offset}
may also be specified.  Conceptually, when an array is accessed, a
single index is computed from the indices and dimensions of the array;
this is the index into the row-major-order data.  This index
then has the displaced-index-offset added to it, to get the index into
the data for the array being displaced to.

Another potential use for displaced arrays is to reference some
"substructure" of an array which implicitly has some "structure".
This causes modification of the displaced array to modify the
referenced subpart of the original array.  In general, however, it is
not appropriate to use array displacement as a substitute for a
3subseq* operation ((subseq-fun));  it is intended for cases
where modification of one must implicitly modify the other, although
if the subsequence is large it may be worthwhile.

Efficiency note:  displaced arrays which are displaced to
non-adjustable arrays access at just about the same speed as normal
arrays (not counting those which are especially efficient, namely
simple vectors, simple strings, and simple bit vectors).  Arrays
displaced to adjustable arrays are a touch slower.  At this time, the
lan{nil} compiler does not know how to inline code any non-vector
array access, however, so 3aref* (or use of it with 3setf*)
will produce general function call unless there is exactly one index.

.section "Modifying Array Sizes and Characteristics"
.setq array-adjustment-section-page section-page

Normally, an array may not have the size of its dimensions or other
attributes changed once it is created (other than modification of its
fill pointer; (array-fill-pointer-section-page)).  If a non-null
3:adjustable* option is given to 3make-array*, however, the
array will be created such that this is possible.

.defun adjust-array array dimensions &key displaced-to displaced-index-offset element-type fill-pointer
3adjust-array* interprets 2dimensions* just as
3make-array* does.  The array is modified to have the new
dimensions;  however, its rank may 2not* be changed.

If 2fill-pointer* is specified, then 2array* must have
originally been created with a fill pointer;  the value of
2fill-pointer* is used as the new one.

The remaining options will not be detailed at this time.
3adjust-array* currently only works on one-dimensional arrays,
so although not generally useful yet, it has enough to keep
3vector-push-extend* happy.
.end_defun

.section "Special Vector Primitives"

These functions are around in lan{nil} for historical reasons.  They
should generally not be used in new code, for reasons which will
become clear from reading the descriptions.  They are documented
because they are used all over the place in lan{nil} itself still,
and 3vref* in particular is generated internal by the compiler
from the use of 3aref*.

.defun vref vector index
This is 2absolutely identical* to 3aref* when 3aref* is
given a vector and a single index.  3aref* is the preferred
function to use in code;  the lan{nil} compiler compiles 3aref*
of a single index as a call to this internal vector-referencing
subroutine.

Because this is the same as 3aref* on a one-dimensional array, it
is interesting to note that (for a vector with a fill pointer)
3vref* does not use the 3vector-length* to check if the index
is in range.
.end_defun

.defun vector-length vector
For historical reasons, this is the same as 3length* but only
accepts a vector as an argument.  If the vector has a fill pointer,
this is not the same as 3(array-dimension 2vector* 0)*, which
is the quantity used by 3vref* for bounds checking.
.end_defun

.section "Simple Vectors"

Vectors of element-type 3t* which are not adjustable and have no
fill pointer are implemented as the primitive data type
3simple-vector*.  (This was called 3simple-general-vector* in
the previous lan{nil} release.  Do 2not* misinterpret the name
3simple-vector* to mean one encompassing vectors of other element
types.)  This type is extensively used in lan{nil} as a building
block for more complicated datastructures in lan{nil}, including
less simple arrays.  There are special routines for creating and
manipulating them, which are coded efficiently by the lan{nil} compiler.

Vectors of this type may be checked for with 3typep*, of course.

.defun make-vector size &key initial-contents initial-element
Makes a vector of element-type 3t*, 2size* long.  Because no
complicated array options can be specified, this will always be a
simple vector.

This may be called 3make-simple-vector* in the future, but the
name 3make-vector* will be preserved indefinitely.
.end_defun

.defun vector &rest elements
This makes a simple vector whose elements are initialized to
2elements*.   That is,
.lisp
(vector 1 2 3)	=>  #(1 2 3)
.end_lisp
.end_defun

.defun svref simple-vector index
References a simple vector.  This routine is entirely
open-coded by the compiler, with no error checking;  to retain runtime
type and bounds checking, 3aref* must be used.

3svref* may be used with 3setf*.

This function used to be called fun_i{sgvref};  that name is still around.
.end_defun

.defun simple-vector-length vector
Returns the length of the simple vector 2vector*.

This used to be called fun_i{simple-general-vector-length} (yow!);
that name is still around.
.end_defun


.section "Bit Arrays"
.setq bit-array-section-page section-page

Arrays which contain only bits, which can be used to represent boolean
2true* and 2false*, are useful in various applications.  There
are several functions which perform boolean operations on arrays of
this element type.

Bit arrays may be more or less appropriate for a particular
application than integers used to represent a sequence of bits.  Bit
arrays (or bit-vectors) may be side-effected;  integers may not.
Integers however may be used to represent infinite sets, because they
are virtually extended with their sign;  see also
(logical-operations-on-numbers-section-page).  Bit arrays, of
course, may be multi-dimensional.

.defun bit bit-array &rest subscripts
Just like 3aref* ((aref-fun)), but only works on arrays of
element-type 3bit*.

3setf* may be used with 3bit*.
.end_defun

.defun bit-and bit-array-1 bit-array-2 &optional result-bit-array
.defun1 bit-ior bit-array-1 bit-array-2 &optional result-bit-array
.defun1 bit-xor bit-array-1 bit-array-2 &optional result-bit-array
.defun1 bit-eqv bit-array-1 bit-array-2 &optional result-bit-array
.defun1 bit-nand bit-array-1 bit-array-2 &optional result-bit-array
.defun1 bit-nor bit-array-1 bit-array-2 &optional result-bit-array
.defun1 bit-andc1 bit-array-1 bit-array-2 &optional result-bit-array
.defun1 bit-andc2 bit-array-1 bit-array-2 &optional result-bit-array
.defun1 bit-orc1 bit-array-1 bit-array-2 &optional result-bit-array
.defun1 bit-orc2 bit-array-1 bit-array-2 &optional result-bit-array
These crunch together 2bit-array-1* and 2bit-array-2*,
performing the appropriate bitwise logical operation.
2bit-array-1* and 2bit-array-2* must have the same rank and
dimensions.  If 2result-bit-array* is 3nil* or not specified,
then the result is a freshly created bit array of the same rank and
dimensions.  If it is 3t*, then the results are stored in
2bit-array-1*.  Otherwise, it must be a bit array of the same rank
and dimensions as the other two, and the results are stored into it.
.end_defun


.defun bit-not bit-array &optional result-bit-array
Performs a bitwise logical negation on the contents of
2bit-array*.  If 2result-bit-array* is 3nil* or not
specified, then the result is returned as a freshly created bit array
of the same rank and dimensions as 2bit-array*.  If
2result-bit-array* is 3t*, then 2bit-array* is
side-effected with the results.  Otherwise, 2result-bit-array*
should be the a bit array of the same rank and dimensions as
2bit-array*, and will have the results stored into it.
.end_defun

.subsection "Simple Bit Vectors"

In lan{nil}, a one-dimensional bit array which is not adjustable,
not displaced, and has no fill pointer, is represented as the
primitive type 3simple-bit-vector*, which is represented more
efficiently than a more general bit array.  Simple bit vectors are
used as building blocks for more complicated structures which contain
binary data, such as the more complicated bit arrays, and even arrays
of element-type 3double-float*.  There are primitives for
accessing variable length fields from them as (possibly sign-extended)
fixnums (but 2not* general integers, yet), and primitives for treating
them as if they were sequences of eight-bit bytes.

Once upon a time the name for this type was 3bits*.  This name
still lingers in places, but is being replaced by
3simple-bit-vector*.

.defun make-bit-vector size &key initial-element initial-contents
Creates a simple-bit-vector 2size* long.  If neither
2initial-element* nor 2initial-contents* are specified, the
contents of the created bit-vector are undefined.  The current
implementation of lan{nil} storage allocation requires that all
allocated datastructure be initialized, so in fact the bit-vector will
always be initialized to zeros, but this could change in the future.

If 2initial-element* is specified, it must be either 30* or
31*, and the elements of the bit vector are initialized to that.

If 2initial-contents* is specified, then it should be a bit
vector, and the created bit vector is initialized to the contents of
2initial-contents*.  If 2initial-contents* is longer than
2size*, the extra elements are ignored;  if it is shorter, then
the contents of the remaining elements of the created bit vector are
undefined (just as they are if neither 3:initial-element* nor
3:initial-contents* are specified).  It is an error to specify
both 2initial-element* and 2initial-contents*.
.end_defun

.defun simple-bit-vector-length simple-bit-vector
Returns the length of 2simple-bit-vector*.
.end_defun

.defun nibble simple-bit-vector skip take
Returns the sequence of bits 2take* long from
2simple-bit-vector*, starting at 2skip*, as a fixnum.
2take* may range from zero to the number of bits representable in
a fixnum (30);  however,  if the last, the result will include
the sign bit so may be unacceptable for certain applications.  The
result is zero-extended.

3setf* may be used with 3nibble* to replace the field.
.end_defun

.defun nibble-2c simple-bit-vector skip take
Like 3nibble*, but the result is sign-extended.  That is, the
result is interpreted as a signed binary value from the referenced
field.

3setf* may be used with 3nibble-2c* to replace the field.
.end_defun

.defun get-a-byte simple-bit-vector byte-index
Interprets 2simple-bit-vector* as a sequence of type
3(unsigned-byte 8)*, and returns the 2byte-index*th byte.

3setf* may be used with 3get-a-byte*.
.end_defun

.defun get-a-byte-2c simple-bit-vector byte-index
Interprets 2simple-bit-vector* as a sequence of type
3(signed-byte 8)*, and returns the 2byte-index*th byte.

3setf* may be used with 3get-a-byte-2c*.
.end_defun

