Compress1
Remove irrelevant pairs from a 1-dimensional array
Example Form:
(compress1 'delta1 a)
General Form:
(compress1 name alist)
where name is a symbol and alist is a 1-dimensional array,
generally named name. See arrays for details. Logically
speaking, this function can remove irrelevant pairs from alist, possibly
shortening it. The function returns a new array, alist', with the same
header (including name and dimension) as alist, that, under
aref1, is everywhere equal to alist. That is, (aref1 name
alist' i) is (aref1 name alist i), for all legal indices i.
Alist' may be shorter than alist and the non-irrelevant pairs may
occur in a different order than in alist.
Practically speaking, this function plays an important role in the
efficient implementation of aref1. In addition to creating the new
array, alist', compress1 makes that array the ``semantic value'' of
name and allocates a raw lisp array to name. For each legal index,
i, that raw lisp array contains (aref1 name alist' i) in slot
i. Thus, subsequent aref1 operations can be executed in
virtually constant time provided they are given name and the alist'
returned by the most recently executed compress1 or aset1 on
name. See arrays.
In general, compress1 returns an alist whose cdr is an
association list whose keys are nonnegative integers in ascending order.
However, if the header specifies an :order of > then the
keys will occur in descending order; and if the :order is :none or
nil then the keys will not be sorted and the header may appear anywhere
(even more than once), i.e., compress1 is logically the identity
function (though it still attaches an array under the hood). Note however
that a compress1 call is replaced by a hard error if the header
specifies an :order of :none or nil and the array's length
exceeds the maximum-length field of its header.
We close with a remark concerning efficiency in the case that the
:ORDER specified by the given array's header is < or
> and the alist is properly ordered: header occurring only first, then
ascending (for :ORDER <) or descending (for :ORDER >) order of
indices, with no value in the alist equal to the :DEFAULT specified by
the header. In particular, this can cut the time to run compress1 on an
alist containing only the header by more than half.
Function: compress1
(defun compress1 (name l)
(declare (xargs :guard (array1p name l)))
(case (array-order (header name l))
(< (cons (header name l)
(compress11 name l 0 (car (dimensions name l))
(default name l))))
(> (cons (header name l)
(reverse (compress11 name l 0 (car (dimensions name l))
(default name l)))))
(t
(prog2$
(and
(> (length l) (maximum-length name l))
(hard-error
'compress1
"Attempted to compress a one-dimensional array named ~
~x0 whose header specifies :ORDER ~x1 and whose ~
length, ~x2, exceeds its maximum-length, ~x3."
(list (cons #\0 name)
(cons #\1 nil)
(cons #\2 (length l))
(cons #\3 (maximum-length name l)))))
l))))
