adjusting displaced arrays

[NGALL@G.BBN.COM]

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:
(DEFUN AREF (ORIGINAL-ARRAY &REST SUBSCRIPTS)
  (LABELS ((FOO (ARRAY INDEX)
	     (MULTIPLE-VALUE-BIND (NEW-ARRAY OFFSET) (DISPLACED-ARRAY-P ARRAY)
	       (IF (NULL NEW-ARRAY)
	           (ROW-MAJOR-AREF ARRAY INDEX)
		   (MULTIPLE-VALUE-CALL #'FOO
		                        NEW-ARRAY
					(+ INDEX OFFSET)))))
      (FOO ORIGINAL-ARRAY
	   (APPLY #'ARRAY-ROW-MAJOR-INDEX ORIGINAL-ARRAY SUBSCRIPTS))))
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