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

[andrew cooke]

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]

#!/usr/bin/python2.2

from __future__ import generators # needed for Python 2.2
import os

def walktree(basepath=".", postorder=True, depthfirst=True,
             ignorelinks=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
    how."""

    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)):
                    dirs.append(name)
                    queue.append(fullpath)
                else:
                    nondirs.append(name)

            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__':
         test()


-- 
http://www.acooke.org/andrew