sort-directory-order

#!/usr/bin/env perl

## Sorts the input lines by directory order:
##   first, every file in a given directory, in sorted order
##   then, process subdirectories recursively, in sorted order
## Example output order:
##   annotatenullable.txt
##   chicory.txt
##   varinfoaux.txt
##   varinfoname.txt
##   asm/asmfile.txt
##   asm/dsforest.txt
##   asm/pptfile.txt
##   asm/testredundantvars.txt
##   asm/x86instruction.txt
##   chicory/arrayinfo.txt
##   chicory/chicorypremain.txt
##   derive/derivation.txt
##   derive/derivationfactory.txt
##   derive/valueandmodified.txt
##   derive/binary/binaryderivation.txt
##   derive/binary/binaryderivationfactory.txt
##   derive/binary/sequencespredicatefactoryfloat.txt
##   derive/binary/sequencespredicatefloat.txt
##   derive/ternary/sequencefloatarbitrarysubsequence.txt
##   derive/ternary/sequencefloatarbitrarysubsequencefactory.txt
##   derive/ternary/ternaryderivation.txt
##   derive/ternary/ternaryderivationfactory.txt
##   derive/unary/sequenceinitial.txt
##   derive/unary/sequenceinitialfactory.txt
##   derive/unary/unaryderivation.txt
##   derive/unary/unaryderivationfactory.txt

## This can be used with "find" to put the results in sorted order.
## (find's default order has to do with where files happen to be stored on
## disk.)  Sorted order may be more sensible to a user, or may make other
## commands more deterministic.  (But for determinism alone, you might as
## well just use "sort", which is faster than this script.)
##
## For example, when making a TAGS file, instead of
##   etags `find . -iname '*.java' -print`
## do
##   etags `find . -iname '*.java' -print | sort-directory-order`

## Note a directory name will appear immediately before its contents if it
## ends with a slash (/), but a directory name that lacks a slash will
## appear with the contents of the parent directory.  If this is
## undesirable, then you want to use `sort` instead of this program.

## Mac OS X has a "-s" option to "find" that is similar (but not
## necessarily identical) to "find | sort".

my $debug = 0;
# $debug = 1;


my @lines = <>;
my @sorted_lines = sort cmp_parents_first @lines;
print @sorted_lines;
exit;




sub num_slashes ( $ ) {
  my ($tmp) = @_;
  return ($tmp =~ tr/\///);
}

sub longest_common_prefix {
  my $prefix = shift;
  for (@_) {
    chop $prefix while (! /^\Q$prefix\E/);
  }
  return $prefix;
}


# Crazily, if the first two lines of this routine are
#   sub cmp_parents_first ( $$ ) {
#     my ($a, $b) = @_;
# then it does not behave properly with sort even though it does
# behave properly when called directly.
# Perl's sort routine is messed up.

# Comparator that places entries in parent directories first.
sub cmp_parents_first {
  if ($debug) { print "cmp_parents_first($a, $b)\n"; }

  my $num_slashes_a = num_slashes($a);
  my $num_slashes_b = num_slashes($b);
  if ($debug) { print "slashes: $num_slashes_a $num_slashes_b\n"; }
  if ($num_slashes_a == $num_slashes_b) {
    return ($a cmp $b);
  }

  my $prefix = longest_common_prefix($a, $b);
  my $num_slashes_prefix = num_slashes($prefix);
  my $num_extra_slashes_a = $num_slashes_a - $num_slashes_prefix;
  my $num_extra_slashes_b = $num_slashes_b - $num_slashes_prefix;
  if ($debug) { print "prefix ($num_slashes_prefix slashes): $prefix\n"; }
  if ($debug) { print "num_extra_slashes $num_extra_slashes_a $num_extra_slashes_b\n"; }

  # If one of the directories contains all the slashes that the other does,
  # plus more, then the one with less slashes is a file in a parent
  # directory and should appear earlier in the sort order.
  if (($num_extra_slashes_a == 0) && ($num_extra_slashes_b != 0)) {
    return -1;
  } elsif (($num_extra_slashes_b == 0) && ($num_extra_slashes_a != 0)) {
    return 1;
  } else {
    return ($a cmp $b);
  }

}