sort function, in non-standard cases

[alexxx.magni]

Hi everybody,
I need some hints on how to setup the sort function in a couple of
cases that happened to me recently

<disclaimer>I already did perldoc -f sort, yet I found mainly
discussed numerical/alphabetical cases</disclaimer>

The two sort problems I had - neither of which I was able to solve -
are the following:

1) given in @a a list of files/directories (e.g. returned by
File::Find), sort it directories first, then symlinks, then common
files.
The nearer I came was:

@a=sort {my $x= -d $a; my $y= -d $b; return $x
<=> $y} @a;

but it doesnt work.

2) sort @a, based on the existence/non-existence of the hash value
$c{$a}, where $a's are the elements of @a.

Both the problems are related to my difficulty of translating them in
some kind of comparison between two generic elements $a vs $b, as in
the typical $a<=>$b

Any hint is welcome!

Alessandro Magni

 

[Joe Smith]

Hi everybody,
I need some hints on how to setup the sort function in a couple of
cases that happened to me recently

<disclaimer>I already did perldoc -f sort, yet I found mainly
discussed numerical/alphabetical cases</disclaimer>

It is unfortunate that `perldoc -f sort` does not mention "Schwartzian Transform".
http://en.wikipedia.org/wiki/Schwartzian_transform

sort it directories first, then symlinks, then common files.

#!/usr/bin/perl
# Purpose: Outputs directory listing, dirs first, then symlinks, then rest
use strict; use warnings;

push @ARGV,(glob '*') unless @ARGV;
my @typed_names =
map {substr $_,1}
sort
map { -l $_ ? "l$_" : -d $_ ? "d$_" : "r$_"}
@ARGV;
print join("\n",@typed_names),"\n";

-Joe

 

[Joe Smith]

#!/usr/bin/perl
# Purpose: Outputs directory listing, dirs first, then symlinks, then rest
use strict; use warnings;

push @ARGV,(glob '*') unless @ARGV;
my @typed_names =
map {substr $_,1}
sort
map { -l $_ ? "l$_" : -d $_ ? "d$_" : "r$_"}
@ARGV;
print join("\n",@typed_names),"\n";

Another way:

sub sort_dir3 {
my %dir;
my @res;
foreach my $ent (@_) {
my $key = -l $ent ? 'Link' : -d $ent ? 'Directory' : 'Regular';
push @{$dir{$key}},$ent;
}
push @res, "\t\t$_\n",join("\n",sort @{$dir{$_}}),"\n\n" for sort keys %dir;
@res;
}

-Joe

P.S. The test for -l() before testing for -d() is deliberate. Unless you
want symlinks to directories to show up as directories instead of as symlinks.

 

[anno4000]

Hi everybody,
I need some hints on how to setup the sort function in a couple of
cases that happened to me recently

<disclaimer>I already did perldoc -f sort, yet I found mainly
discussed numerical/alphabetical cases</disclaimer>

The two sort problems I had - neither of which I was able to solve -
are the following:

1) given in @a a list of files/directories (e.g. returned by
File::Find), sort it directories first, then symlinks, then common
files.
The nearer I came was:

@a=sort {my $x= -d $a; my $y= -d $b; return $x
<=> $y} @a;

but it doesnt work.

That is a typical candidate for a Schwartz transform. To each file,
assign a rank of 0, 1, or 2 according as it is a directory, a symlink
or anything else. Then sort according to rank, breaking ties by
comparing the file names:

my @sorted_files = map $_->[ 0] =>
sort { $a->[ 1] <=> $b->[ 1] || $a->[ 0] cmp $b->[ 0] }
map {
my $rank = 2;
$rank = 0 if -d;
$rank = 1 if -l;
[ $_, $rank];
}
@files;

Anno

 

[anno4000]

It is unfortunate that `perldoc -f sort` does not mention "Schwartzian
Transform".
http://en.wikipedia.org/wiki/Schwartzian_transform


#!/usr/bin/perl
# Purpose: Outputs directory listing, dirs first, then symlinks, then rest
use strict; use warnings;

push @ARGV,(glob '*') unless @ARGV;
my @typed_names =
map {substr $_,1}
sort
map { -l $_ ? "l$_" : -d $_ ? "d$_" : "r$_"}
@ARGV;
print join("\n",@typed_names),"\n";

That's not strictly a Schwartz transform but a Guttman-Roesler
transform (GRT). A Schwartz transform builds a list of anonymous
arrays that hold the sort key(s) and the original elements and
uses a sort block to access the keys. A GRT (like your solution)
prepends a single sort key in string form and uses the default sort.

Anno

 

[Michele Dondi]

my @typed_names =
map {substr $_,1}
sort
map { -l $_ ? "l$_" : -d $_ ? "d$_" : "r$_"}
@ARGV;

++ x 10**3! Strictly speaking this is not an ST, which you mention,
but even a GRT, which is better in many respcts. I would have gone ST,
but your solution is more compact, elegant, and most probably fast.
Best code contribution I've seen in some time! FYI, I'm reporting it
elsewhere...


Michele

 

[Tad McClellan]

It is unfortunate that `perldoc -f sort` does not mention "Schwartzian Transform".

But `perldoc -q sort` does.

 

[Michele Dondi]

Best code contribution I've seen in some time! FYI, I'm reporting it
elsewhere...

Done: <http://perlmonks.org/?node_id=623356>.


Michele

 

[John W. Krahn]

#!/usr/bin/perl
# Purpose: Outputs directory listing, dirs first, then symlinks, then rest
use strict; use warnings;

push @ARGV,(glob '*') unless @ARGV;
my @typed_names =
map {substr $_,1}
sort
map { -l $_ ? "l$_" : -d $_ ? "d$_" : "r$_"}
@ARGV;
print join("\n",@typed_names),"\n";

You only need to stat the files once:

my @typed_names =
map {substr $_,1}
sort
map { -l $_ ? "l$_" : -d _ ? "d$_" : "r$_"}
@ARGV;



John

 

[John W. Krahn]

That is a typical candidate for a Schwartz transform. To each file,
assign a rank of 0, 1, or 2 according as it is a directory, a symlink
or anything else. Then sort according to rank, breaking ties by
comparing the file names:

my @sorted_files = map $_->[ 0] =>
sort { $a->[ 1] <=> $b->[ 1] || $a->[ 0] cmp $b->[ 0] }
map {
my $rank = 2;
$rank = 0 if -d;
$rank = 1 if -l;
[ $_, $rank];
}
@files;

You only need to stat the files once:

my @sorted_files = map $_->[ 0] =>
sort { $a->[ 1] <=> $b->[ 1] || $a->[ 0] cmp $b->[ 0] }
map {
my $rank = 2;
$rank = 0 if -d;
$rank = 1 if -l _;
[ $_, $rank];
}
@files;



John

 

[John W. Krahn]

That's not strictly a Schwartz transform

"Schwartzian Transform"

but a Guttman-Roesler transform (GRT).

That should be Guttman-Rosler.

http://www.sysarch.com/Perl/sort_paper.html



John

 

[Uri Guttman]

JS> Thanks for the link.

and Sort::Maker implements the GRT as well as the ST and other sort
styles. it will make sorts like yours much easier to create.

uri