[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

adjusting displaced arrays

The following appears in Guy's list of `clarifications':

(*) 293 ...Add a function DISPLACED-ARRAY-P, which takes an array and
returns NIL and 0 if it is not displaced or the array displaced to and
the displaced-index-offset if it is displaced.  These allow certain code
efficiencies, and also allow array displacement to be explained in
terms of Lisp primitives:
	       (IF (NULL NEW-ARRAY)
					(+ INDEX OFFSET)))))
As a bow to efficiency, note the fact that if array A is displaced to B
with offset M, and B is displaced to C with offset N, and B is not
adjustable, then DISPLACED-ARRAY-P of A might return either array B with
offset M or array C with offset (+ M N).  This generalizes to chains
of non-adjustable arrays.

I would like to add an additional (and I think stronger) argument for
DISPLACED-ARRAY-P.  Someone in our group had the following type of
problem:  Given a very long string (representing, say, a long report),
he wanted to be able to displace a char. string of length N (call it
N-char-string) (where 1 <= N <= 80) to the beginning
of the very-long-string, do some parsing of the N-char-string, and
then ADJUST the N-char-string to start where it had previously ended
and to have a new length.  In other words, he wanted to slide this
variable length window over the very-long-string.  Without
DISPLACED-ARRAY-P, he is forced to wrap a structure around the
displaced-array to record the
original array the current offset, even though the displaced array
structure already contains this info!

I would suggest one minor change to DISPLACED-ARRAY-P, in the case
that it returns NIL, I suggest that it should return only that (and
not return the 0).  The zero provides no information and does not seem
to be of any use.

(*) 297 Here are the interactions of ADJUST-ARRAY with displacement.
Suppose we are adjusting array A, which is perhaps displaced
to B before adjustment and perhaps to C after adjustment.
(1) Not displaced before or after.  The dimensions of A are altered, and
the contents rearranged as appropriate.  Additional elements of A are
taken from the :initial-element.  The use of :initial-contents causes
all old contents to be discarded.
(2) Not displaced before, but displaced afterwards to C.  As already
specified, none of the original contents of A appears in A afterwards,
but rather the contents of C without any rearrangement of C.
(3) Displaced beforehand to B, and afterward to C.  As in case (2), no
contents of B appear in A afterward.  If :DISPLACED-INDEX-OFFSET is not
specified in this case, it defaults to zero; the old offset (into B) is
not retained.
(4) Displaced beforehand to B, but not displaced afterward.  A gets a
new "data region", and contents of B are copied into it as appropriate
to maintain the existing old contents; additional elements of A are
taken from the :initial-element.  However, the use of :initial-contents
causes all old contents to be discarded.
In case (3), what if (eq B C)?  (this would be the case in the sliding
window above).  Saying that "no contents of B appear in A afterward"
is not true.

	-- Nick