Re: English Idiom in Unix: Directory Recursively

From	"Pascal J. Bourguignon" <pjb@informatimago.com>
Newsgroups	comp.lang.python, comp.lang.lisp
Subject	Re: English Idiom in Unix: Directory Recursively
Date	2011-05-18 20:57 +0200
Organization	Informatimago
Message-ID	<8762p7omzu.fsf@kuiper.lan.informatimago.com> (permalink)
References	(1 earlier) <iqvj9f$3ci$6@dont-email.me> <87aaekoab7.fsf@kuiper.lan.informatimago.com> <ymir57wldbn.fsf@blackcat.isi.edu> <jecca8-cmq.ln1@svn.schaathun.net> <ymik4do56hx.fsf@blackcat.isi.edu>

Cross-posted to 2 groups.

Show all headers | View raw

tar@sevak.isi.edu (Thomas A. Russ) writes:

> Well, unless you have a tree with backpointers, you have to keep the
> entire parent chain of nodes visited.  Otherwise, you won't be able to
> find the parent node when you need to backtrack.  A standard tree
> representation has only directional links.
>
> Consider:
>
> A--+---B----+---D
>    |        |
>    |        +---E
>    |        |
>    |        +---F
>    | 
>    +---C
>
> If all you keep is the current and previous node, then the only thing
> you have reference do when doing the depth-first traverse is:
>   1.  Current = A,  Previous = null
>   2.  Current = B.  Previous = A
>   3.  Current = D   Previous = B
>   4.  Current = E   Previous = D
>   5.  now what?  You can't get from E or D back to B.
>
>> By comparing the previous node (pointer or ID) to the
>> current node's parent and children one will know wherefrom the
>> current node was entered, and can choose the next child in the
>> list as the next node, or the parent if all children have been
>> visited.  A visit action may be added in any or all times the
>> node is visited.
>> 
>> This node requires no stack.  The only state space is constant,
>> regardless of the size of the tree, requiring just the two pointers
>> to previous and current.
>
> This will only work if there is a backpointer to the parent.

No, you don't need backpointers; some cases have been mentionned in the
other answer, but in general:

    (defun parent (tree node)
       (if (member node (children tree))
          tree
          (some (lambda (child) (parent child node)) (children tree))))

Yes, the question wasn't about time complexity.

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
A bad day in () is better than a good day in {}.

Thread

English Idiom in Unix: Directory Recursively Xah Lee <xahlee@gmail.com> - 2011-05-17 15:26 -0700
  Re: English Idiom in Unix: Directory Recursively Roland Hutchinson <my.spamtrap@verizon.net> - 2011-05-18 04:51 +0000
    Re: English Idiom in Unix: Directory Recursively "Pascal J. Bourguignon" <pjb@informatimago.com> - 2011-05-18 07:19 +0200
      Re: English Idiom in Unix: Directory Recursively tar@sevak.isi.edu (Thomas A. Russ) - 2011-05-17 23:42 -0700
        Re: English Idiom in Unix: Directory Recursively Hans Georg Schaathun <hg@schaathun.net> - 2011-05-18 09:26 +0100
          Re: English Idiom in Unix: Directory Recursively tar@sevak.isi.edu (Thomas A. Russ) - 2011-05-18 09:16 -0700
            Re: English Idiom in Unix: Directory Recursively Hans Georg Schaathun <hg@schaathun.net> - 2011-05-18 19:11 +0100
              Re: English Idiom in Unix: Directory Recursively Raymond Wiker <raw@RAWMBP-2.local> - 2011-05-18 20:20 +0200
                Re: English Idiom in Unix: Directory Recursively Hans Georg Schaathun <hg@schaathun.net> - 2011-05-18 19:39 +0100
                Re: English Idiom in Unix: Directory Recursively Raymond Wiker <raw@RAWMBP-2.local> - 2011-05-18 21:09 +0200
                Re: English Idiom in Unix: Directory Recursively Hans Georg Schaathun <hg@schaathun.net> - 2011-05-18 21:02 +0100
                Re: English Idiom in Unix: Directory Recursively Raymond Wiker <raw@RAWMBP-2.local> - 2011-05-18 22:40 +0200
                Re: English Idiom in Unix: Directory Recursively Hans Georg Schaathun <hg@schaathun.net> - 2011-05-19 05:56 +0100
                Re: English Idiom in Unix: Directory Recursively tar@sevak.isi.edu (Thomas A. Russ) - 2011-05-19 16:14 -0700
            Re: English Idiom in Unix: Directory Recursively "Pascal J. Bourguignon" <pjb@informatimago.com> - 2011-05-18 20:57 +0200
              Re: English Idiom in Unix: Directory Recursively tar@sevak.isi.edu (Thomas A. Russ) - 2011-05-19 16:17 -0700
                Re: English Idiom in Unix: Directory Recursively "Pascal J. Bourguignon" <pjb@informatimago.com> - 2011-05-20 02:38 +0200
                Re: English Idiom in Unix: Directory Recursively Antti J Ylikoski <antti.ylikoski@tkk.fi> - 2011-05-20 12:00 +0300
        Re: English Idiom in Unix: Directory Recursively Peter Moylan <invalid@peter.pmoylan.org.invalid> - 2011-05-18 22:09 +1000
          Re: English Idiom in Unix: Directory Recursively rusi <rustompmody@gmail.com> - 2011-05-18 06:14 -0700
            Re: English Idiom in Unix: Directory Recursively Peter Moylan <invalid@peter.pmoylan.org.invalid> - 2011-05-19 11:06 +1000
              Re: English Idiom in Unix: Directory Recursively Grant Edwards <invalid@invalid.invalid> - 2011-05-21 15:34 +0000
      Re: English Idiom in Unix: Directory Recursively Roland Hutchinson <my.spamtrap@verizon.net> - 2011-05-20 06:50 +0000
    Re: English Idiom in Unix: Directory Recursively rusi <rustompmody@gmail.com> - 2011-05-17 23:06 -0700
      Re: English Idiom in Unix: Directory Recursively Harrison Hill <harrishill@gmx.com> - 2011-05-17 23:50 -0700
        Re: English Idiom in Unix: Directory Recursively rusi <rustompmody@gmail.com> - 2011-05-18 00:16 -0700
        Re: English Idiom in Unix: Directory Recursively Peter Moylan <invalid@peter.pmoylan.org.invalid> - 2011-05-18 22:19 +1000
          Re: English Idiom in Unix: Directory Recursively rantingrick <rantingrick@gmail.com> - 2011-05-29 13:16 -0700
            Re: English Idiom in Unix: Directory Recursively Peter Moylan <invalid@peter.pmoylan.org.invalid> - 2011-05-30 22:58 +1000
        Re: English Idiom in Unix: Directory Recursively see@sig.for.address (Victor Eijkhout) - 2011-05-18 12:59 -0500
          Re: English Idiom in Unix: Directory Recursively Roland Hutchinson <my.spamtrap@verizon.net> - 2011-05-20 06:54 +0000
          Re: English Idiom in Unix: Directory Recursively rantingrick <rantingrick@gmail.com> - 2011-05-29 13:28 -0700
            Re: English Idiom in Unix: Directory Recursively Peter Moylan <invalid@peter.pmoylan.org.invalid> - 2011-05-30 23:02 +1000
          Re: English Idiom in Unix: Directory Recursively rantingrick <rantingrick@gmail.com> - 2011-05-29 13:28 -0700
        Re: English Idiom in Unix: Directory Recursively Glenn Knickerbocker <NotR@bestweb.net> - 2011-05-18 16:54 -0400
  Re: English Idiom in Unix: Directory Recursively Hans Georg Schaathun <hg@schaathun.net> - 2011-05-18 09:12 +0100
    Re: English Idiom in Unix: Directory Recursively Espen Vestre <espen@vestre.net> - 2011-05-18 10:20 +0200
    Re: English Idiom in Unix: Directory Recursively Rikishi42 <skunkworks@rikishi42.net> - 2011-05-19 23:21 +0200
  Re: English Idiom in Unix: Directory Recursively Captain Obvious <alex.mizrahi@gmail.com> - 2011-05-18 11:36 +0300
    Re: English Idiom in Unix: Directory Recursively Captain Obvious <alex.mizrahi@gmail.com> - 2011-05-18 11:46 +0300
  Re: English Idiom in Unix: Directory Recursively Mike Barnes <mikebarnes@bluebottle.com> - 2011-05-18 10:25 +0100
    Re: English Idiom in Unix: Directory Recursively Xah Lee <xahlee@gmail.com> - 2011-05-18 13:00 -0700
      Re: English Idiom in Unix: Directory Recursively Hans Georg Schaathun <hg@schaathun.net> - 2011-05-18 21:19 +0100
      Re: English Idiom in Unix: Directory Recursively Mike Barnes <mikebarnes@bluebottle.com> - 2011-05-18 22:00 +0100
      Re: English Idiom in Unix: Directory Recursively Jonathan de Boyne Pollard <J.deBoynePollard-newsgroups@NTLWorld.COM> - 2011-05-20 08:10 +0100
        Re: English Idiom in Unix: Directory Recursively Xah Lee <xahlee@gmail.com> - 2011-05-22 13:22 -0700
      Re: English Idiom in Unix: Directory Recursively rantingrick <rantingrick@gmail.com> - 2011-05-29 13:32 -0700
    Re: English Idiom in Unix: Directory Recursively Jonathan de Boyne Pollard <J.deBoynePollard-newsgroups@NTLWorld.COM> - 2011-05-20 08:07 +0100
  Re: English Idiom in Unix: Directory Recursively John Nagle <nagle@animats.com> - 2011-05-18 13:07 -0700
  Re: English Idiom in Unix: Directory Recursively Jonathan de Boyne Pollard <J.deBoynePollard-newsgroups@NTLWorld.COM> - 2011-05-20 08:00 +0100
    Re: English Idiom in Unix: Directory Recursively David Schwartz <davids@webmaster.com> - 2011-05-27 22:56 -0700

csiph-web