Version 16 of Directory recursion

Updated 2014-01-25 18:09:05 by pooryorick

AMG: This page gives some directory recursion scripts. Each prints the names of all subdirectories of the current directory, but of course you can change them to do whatever you need.


LV So what is breadth-first traversal vs depth-first traversal? Is this distinguishing between whether one sees the files of a directory first or last?

AMG: The following directory tree listing is generated using a depth-first traversal.

 /
 /a
 /a/1
 /a/2
 /b
 /b/1
 /b/2

Here's the same tree again generated using a breadth-first traversal.

 /
 /a
 /b
 /a/1
 /a/2
 /b/1
 /b/2

See the difference? Depth-first single-mindedly concentrates on one branch of the tree, and only after reaching a leaf node will it back up and try something else. Breadth-first takes turns following all branches it encounters. I'm aware that my explanation sucks, so instead I'll let XScreenSaver [L1 ] talk for me.

http://www.jwz.org/xscreensaver/screenshots/maze.jpg http://www.jwz.org/xscreensaver/screenshots/coral.jpg

Maze performs a depth-first traversal, and coral performs a breadth-first traversal.

Whether files are visited before, after, or intermingled with directories is a separate issue. It just depends on your code. Some relevant terms to explore are pre-order, in-order, and post-order.

The depth/breadth issue, on the other hand, is determined by whether a stack or a queue is used to keep track of the directories that have been discovered but not yet visited.

By the way, all these concepts are useful in expression parsing. I'd write more, but work is calling...


1. Iterative, breadth-first traversal, Tcl 8.5, [lappend]

 proc ftw_1 {{dirs .}} {
    while {[llength $dirs] != 0} {
       set dirs [lassign $dirs name]
       lappend dirs {*}[glob -nocomplain -directory $name -type d *]
       puts $name
    }
 }

2. Iterative, breadth-first traversal, Tcl 8.5, [list] + {*}

 proc ftw_2 {{dirs .}} {
    while {[llength $dirs] != 0} {
       set dirs [list {*}[lassign $dirs name] {*}[glob -nocomplain -directory $name -type d *]]
       puts $name
    }
 }

3. Iterative, breadth-first traversal, Tcl 8.4

 proc ftw_3 {{dirs .}} {
    while {[llength $dirs] != 0} {
       set name [lindex $dirs 0]
       set dirs [concat [lrange $dirs 1 end] [glob -nocomplain -directory [lindex $dirs 0] -type d *]]
       puts $name
    }
 }

4. Iterative, depth-first traversal, Tcl 8.5, [lassign]

 proc ftw_4 {{dirs .}} {
    while {[llength $dirs] != 0} {
       set dirs [lassign $dirs name]
       set dirs [list {*}[glob -nocomplain -directory $name -type d *] {*}$dirs]
       puts $name
    }
 }

5. Iterative, depth-first traversal, Tcl 8.5, [lreplace]

 proc ftw_5 {{dirs .}} {
    while {[llength $dirs] != 0} {
       set name [lindex $dirs 0]
       set dirs [lreplace $dirs 0 0 {*}[glob -nocomplain -directory [lindex $dirs 0] -type d *]]
       puts $name
    }
 }

6. Iterative, depth-first traversal, Tcl 8.5, [lrange]

 proc ftw_6 {{dirs .}} {
    while {[llength $dirs] != 0} {
       set name [lindex $dirs 0]
       set dirs [list {*}[glob -nocomplain -directory [lindex $dirs 0] -type d *] {*}[lrange $dirs 1 end]]
       puts $name
    }
 }

7. Iterative, depth-first traversal, Tcl 8.4

 proc ftw_7 {{dirs .}} {
    while {[llength $dirs] != 0} {
       set name [lindex $dirs 0]
       set dirs [concat [glob -nocomplain -directory [lindex $dirs 0] -type d *] [lrange $dirs 1 end]]
       puts $name
    }
 }

8. Recursive, depth-first traversal

 proc ftw_8 {{name .}} {
    puts $name
    foreach subdir [glob -nocomplain -directory $name -type d *] {
       ftw_8 $subdir
    }
 }

For this application, [linsert] is too clumsy because it errors when instructed to insert zero elements; therefore it would have to be wrapped with an [if] (or [catch], hehehe).

I [time]d the above procedures (sans [puts]) on a certain directory tree. Here are the results:

 % foreach p [info procs ftw_*] {puts "$p: [time $p 10]"}
 ftw_1: 519323.9 microseconds per iteration
 ftw_2: 512807.2 microseconds per iteration
 ftw_3: 665287.1 microseconds per iteration
 ftw_4: 518121.0 microseconds per iteration
 ftw_5: 515800.6 microseconds per iteration
 ftw_6: 515826.2 microseconds per iteration
 ftw_7: 595750.0 microseconds per iteration
 ftw_8: 515477.5 microseconds per iteration

And a bit of analysis:

  • The fastest two do the least amount of list and variable manipulation. By no means does recursion make ftw_8 slow.
  • The slowest two are the ones using [concat]. Yay {*}!
  • The fastest implementation is ftw_2, but breadth-first is an unconventional directory traversal.
  • The fastest depth-first implementation is ftw_8, since recursion apparently is quite fast.
  • I don't know why ftw_3 and ftw_7 have different execution times, but in repeated trials the difference is consistent.

See Matthias Hoffmann - Tcl-Code-Snippets - misc - globx


iu2 Tried package-Tclx's for_recursive_glob?

Reverse Traverse

Sometimes it's desirable to traverse a hierarchy backwards, such that deeper vertices are visited first. One example is when renaming all the directories and files in a tree. If parents are renamed before children, the newly-renamed directories might not get traversed. Using the example from the top of this page, here's what a reverse traversal would look like:

/a/1
/a/2
/a
/b/1
/b/2
/b
/

Here is a procedure that visits the contents in that order:

if 0 {
    this iterative depth-first directory traversal takes care apply $script to
    deeper paths first so that paths aren't invalidated by renaming before they
    can be processed
}
proc reverse_traverse_iter {path cmd} {
    set origpath $path 
    set cursor [list $path]
    while 1 {
        if {$cursor eq {}} {
            break
        }
        set path [join $cursor /] 
        set children [
            glob -nocomplain -tails -directory $path -types {d hidden} *]
        lappend children {*}[
            glob -nocomplain -tails -directory $path -type d *]
        foreach child $children[set children {}] {
            if {$child ni {. ..}} {
                dict set dirs {*}$cursor $child {}
                lappend children $child
            }
        }
        if {[llength $children]} {
            lappend cursor [lindex $children 0]
        } else {
            while 1 {
                set files [glob -nocomplain -directory $path -types hidden *]
                lappend files {*}[glob -nocomplain -directory $path *]
                foreach fname $files[set files {}] {
                    if {![file isdirectory $fname]} {
                        lappend files $fname
                    }
                }
                lappend files $path
                foreach fname $files {
                    {*}$cmd $fname
                }
                dict unset dirs {*}$cursor
                set cursor [lreplace $cursor end end]
                if {$cursor eq {}} {
                    break
                }
                set children [dict get $dirs {*}$cursor]
                set childnames [dict keys $children]
                if {[llength $childnames]} {
                    lappend cursor [lindex $childnames 0]
                    break
                } else {
                    set path [join $cursor /]
                }
            }
        }
    }
}

Example:

reverse_traverse_iter . {apply {fname {
    if {[file isdirectory $fname]} {
        puts "directory: $fname"
    } else {
        puts "file: $fname"
    }
}}} 

Of course, the recursive version is shorter, and the NRE of modern Tcl takes the stack pressure:

proc traverse_recurse {path cmd} {
        set myname [lindex [info level 0] 0]
        set children [glob -nocomplain -directory $path -types hidden *]
        lappend children {*}[glob -nocomplain -directory $path *]
        foreach child $children[set children {}] {
                if {$child in {. ..}} {
                        continue
                }
                if {[file isdirectory $child]} {
                        $myname $child $cmd
                }
                {*}$cmd $child
        }
}