two-pass tree traversal via callcc (was: Re: Create a directories list with sub-directories)

On Wednesday 24 March 2004 13:32, Vadim Nasardinov wrote:
> X-Mail-Count: 95761
> Message-Id: <[e-mail]>
>
> On Wednesday 24 March 2004 03:44, Dirk Einecke wrote:
> > I have one question: With your code the files in a folder will be
> > print out at first. Is it possible to change this that the order
> > is inverted: at first the folders an after that the files?

I needed a variation of the above script that would print out, for
each directory, the number of files and subdirectories that it
contains directly and indirectly.  This turned out to be an
interesting opportunity for implementing a fairly simple backtracking
tree traversal via callcc.  This doesn't quite rise to the level of
inclusion in
http://blade.nagaokaut.ac.jp/~sinara/ruby/callcc-lib/
but may be interesting to some.

Here goes.


#!/usr/bin/ruby

# Author:  Vadim Nasardinov
# Since:   2004-03-24

# In a lesser language (how's that for a flamebait?), this would be
# coded by explicitly building a tree data structure in the first
# pass, and printing it out in the second pass.  This script avoids
# building the tree explicitly by exploiting the fact that the
# necessary tree structure is already maintained implicitly by the
# interpreter: the call tree of the file_tree_stats method mirrors the
# file tree that we want to print out.

def file_tree_stats(dir, indent)
    dirs =  []
    n_files = 0

    Dir.foreach(dir) do |ff|
        path = File.join(dir, ff)
        if File.directory?(path) and ff[0] != ?.
            dirs.push(path)
        elsif path[-3..-1] == '.rb'
            n_files = n_files.succ
        end
    end

    dirs.sort!
    dirs.reverse!

    conts = []

    first_pass = true
    n_total_dirs = dirs.length
    n_total_files = n_files
    dirs.each do |dd|
        cont, n_subdirs, n_subfiles = file_tree_stats(dd, indent + "  ")
        break if cont == nil
        n_total_dirs += n_subdirs
        n_total_files += n_subfiles
        conts.push(cont)
    end

    if first_pass
        first_pass = false
        callcc do |k|
            return k, n_total_dirs, n_total_files
        end
        puts "#{indent}#{File.basename(dir)}/"
        stats = "  #{indent}#{n_files} files"
        stats += " / #{n_total_files} total files" if n_files != n_total_files

        if dirs.length > 0
            stats += " / #{dirs.length} subdirs"
            if n_total_dirs > dirs.length
                stats += " / #{n_total_dirs} total subdirs"
            end
        end
        puts stats
    end

    if conts.length > 0
        conts.pop.call
    end
end

ARGV.each do |dd|
    k, n_dirs, n_files = file_tree_stats(dd, "")
    if k != nil
        puts dd
        puts "#{n_files} files / #{n_dirs} subdirectories"
        k.call
    end
end

# The end =================================



Example:

$ ./file_tree_stats.rb /usr/lib/ruby/1.8
/usr/lib/ruby/1.8
300 files / 41 subdirectories
1.8/
  77 files / 300 total files / 20 subdirs / 41 total subdirs
  bigdecimal/
    5 files
  cgi/
    1 files / 2 total files / 1 subdirs
    session/
      1 files
  date/
    1 files
  dl/
    4 files
  drb/
    9 files
  i386-linux-gnu/
    1 files / 3 subdirs
    digest/
      0 files
    io/
      0 files
    racc/
      0 files
  io/
    1 files
  irb/
    15 files / 31 total files / 3 subdirs / 4 total subdirs
    cmd/
      6 files
    ext/
      8 files
    lc/
      1 files / 2 total files / 1 subdirs
      ja/
        1 files
  net/
    11 files
  openssl/
    6 files
  optparse/
    4 files
  racc/
    1 files
  rexml/
    27 files / 53 total files / 4 subdirs
    dtd/
      5 files
    encodings/
      13 files
    light/
      1 files
    parsers/
      7 files
  runit/
    6 files / 7 total files / 1 subdirs
    cui/
      1 files
  shell/
    7 files
  test/
    1 files / 15 total files / 1 subdirs / 6 total subdirs
    unit/
      7 files / 14 total files / 2 subdirs / 5 total subdirs
      ui/
        2 files / 5 total files / 3 subdirs
        console/
          1 files
        fox/
          1 files
        gtk/
          1 files
      util/
        2 files
  uri/
    7 files
  webrick/
    19 files / 32 total files / 2 subdirs
    httpauth/
      7 files
    httpservlet/
      6 files
  xmlrpc/
    10 files
  yaml/
    16 files