[Python-Dev] os.path.walk() lacks 'depth first' option

andrew cooke andrew@acooke.org
Tue, 22 Apr 2003 21:12:05 -0400 (CLT)

I hesitate to post this because I'm out of my depth - I've never used
generators before, and I'm not 100% certain that this strange compromise
between imperative (the usual breadth/depth switch using queues) and a
functional (the usual pre/post switch using the call stack) algorithms is
ok.  However, it appears to work and may be useful - it's a simple
extension to Noah's code that allows the user to choose between breadth-
and depth-first traversal.  It is more expensive, using a list as either
fifo or lifo queue (depending on breadth/depth selection).

[Noah - I decided to post this rather than bother you again - hope that's OK]


from __future__ import generators # needed for Python 2.2
import os

def walktree(basepath=".", postorder=True, depthfirst=True,

    """Noah Spurrier's code, modified to allow depth/breadth-first
    traversal.  The recursion is there *only* to allow postorder
    processing as the stack rolls back - the rest of the algorithm is
    imperative and queue would be declared outside helper if I knew

    def helper(queue):

        if queue:

            if depthfirst: dir = queue.pop(-1)
            else: dir = queue.pop(0)

            children = os.listdir(dir)

            dirs, nondirs = [], []

            for name in children:
                fullpath = os.path.join(dir, name)
                if os.path.isdir(fullpath) and not \
                       (ignorelinks and os.path.islink(fullpath)):

            if not postorder:
                yield dir, dirs, nondirs

            for rest in helper(queue):
                yield rest

            if postorder:
                yield dir, dirs, nondirs

    return helper([basepath])

def test():
     for basepath, dirs, nondirs in \
             walktree(postorder=True, depthfirst=False):
         for name in dirs:
             print os.path.join(basepath, name)
         for name in nondirs:
             print os.path.join(basepath, name)

if __name__ == '__main__':