[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Gcl-devel] Re: more on nth

From: Camm Maguire
Subject: [Gcl-devel] Re: more on nth
Date: 06 Feb 2006 00:01:02 -0500
User-agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.2

Greetings, and thank you so much for pointing this out!  It is indeed
incorrect to neglect the circular list case.  So we will have to use
the code below in case of bignum args, and mod the arg by the circular
list length if found.  I'll try to get to this when I get back in 1
week.  We might be able to save the inlining, but defer to a function
call rather than simply return nil if the check for fixnum arg type

Take care,

Robert Boyer <address@hidden> writes:

> After thinking quite a bit more about how to code NTH, I have simply given
> up.
> I just don't know how to handle the circular list case as efficiently as
> possible.  Something like the suggested code for LIST-LENGTH might help, but
> I don't see how yet.  One could mark the list as in gbc, but I think that
> would not be tolerated by the users.  So what is a nondestructive but
> really fast way to tell where a circular list starts to circle?
> Bob
> -------------------------------------------------------------------------------
> >From the ANSI doc (and implemented this was in GCL I think):
>  (defun list-length (x)
>    (do ((n 0 (+ n 2))           ;Counter.
>         (fast x (cddr fast))    ;Fast pointer: leaps by 2.
>         (slow x (cdr slow)))    ;Slow pointer: leaps by 1.
>        (nil)
>      ;; If fast pointer hits the end, return the count.
>      (when (endp fast) (return n))
>      (when (endp (cdr fast)) (return (+ n 1)))
>      ;; If fast pointer eventually equals slow pointer,
>      ;;  then we must be stuck in a circular list.
>      ;; (A deeper property is the converse: if we are
>      ;;  stuck in a circular list, then eventually the
>      ;;  fast pointer will equal the slow pointer.
>      ;;  That fact justifies this implementation.)
>      (when (and (eq fast slow) (> n 0)) (return nil))))

Camm Maguire                                            address@hidden
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah

reply via email to

[Prev in Thread] Current Thread [Next in Thread]