Re: lists.texi

[Luc Teirlinck]

Richard Stallman wrote:

       (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)))

   Isn't that quadratically slow?  And it doesn't fix the bug.

Yes, it is quadratically slow.  Let us just forget about this one.
But it did fix the bug.

       !     (nconc lst (make-list (- (ring-length ring) (length lst)) nil))))

   What's the purpose of this?  It seems only to reintroduce the same bug
   that the delq fixes.

No.  The bug is that if the size of the ring is larger than the
length, the current version of `ring-elements' introduces fake `nil'
elements.  The delq gets rid of all nil's, fake ones and potentially
legitimate ones, because certain ring elements could _really_ be nil.
The nconc re-adds the correct number of legitimate nil's.  See the
ielm run below.

When testing the new function you have to be careful.  If you just do
C-M-x on it and then start experimenting, the bug _will_ still be
there.  Indeed, ring.el is not pre-loaded.  The experimentation loads
ring.el, overriding your C-M-x with the old definition.

The ielm run below uses the following function (the one in the second
patch I sent), which I propose to install:

(defun ring-elements (ring)
  "Return a list of the elements of RING, in no particular order."
  (let ((lst (delq nil (mapcar #'identity (cddr ring)))))
    (nconc lst (make-list (- (ring-length ring) (length lst)) nil))))

The original ring-elements would return three times
(nil nil nil nil nil nil) in the run below.  The function above
_without_ the nconc would return three times nil, which would only be
correct on the first call.

*** Welcome to IELM ***  Type (describe-mode) for help.
ELISP> (setq rr (make-ring 6))
(0 0 .
   [nil nil nil nil nil nil])

ELISP> (ring-elements rr)
nil
ELISP> (ring-insert rr nil) 
nil
ELISP> (ring-elements rr)
(nil)

ELISP> (ring-insert rr nil) 
nil
ELISP> (ring-elements rr)
(nil nil)

ELISP>