[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
adjusting displaced arrays
- To: common-lisp@SU-AI.ARPA
- Subject: adjusting displaced arrays
- From: NGALL@G.BBN.COM
- Date: Thu, 15 May 1986 23:26:00 -0000
- Sender: 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)
(+ INDEX OFFSET)))))
(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
(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.