Re: lists.texi

[Luc Teirlinck]

Richard Stallman wrote:

   If you want to do a little work, I am sure you could write a single
   loop that produces the right elements in the right order.  Then you
   could rotate it properly with a single call to setcdr followed by
   nconc'ing the pieces in the opposite order.

Unless I am completely misunderstanding things, I believe I was a
little bit too quick to admit that my original function:

(defun ring-elements (ring)
  "Return a list of the elements of RING in order, newest first."
  (let (lst)
    (dotimes (var (ring-length ring))
      (push (ring-ref ring var) lst))
    (nreverse lst)))

was quadratic.  It essentially does ring-length times an aref in
_vector_, which unlike checking the element at an average position in
a _list_, would not appear to be linear in the size of the vector.

Anyway, I now propose the following which avoids the nreverse and
esentially "inlines" the `ring-ref' call, but in a way that avoids a
lot more overhead than a simple inlining.  So I believe that it should
be an improvement by a pretty good constant factor, which would not be
of too much help if it really is quadratic, but why is it?

(defun ring-elements (ring)
  "Return a list of the elements of RING, in order, newest first."
  (let ((start (car ring))
  (size (ring-size ring))
  (vect (cddr ring))
  lst)
    (dotimes (var (cadr ring) lst)
      (push (aref vect (mod (+ start var) size)) lst))))