sort function, in non-standard cases

Discussion in 'Perl Misc' started by alexxx.magni@gmail.com, Jun 26, 2007.

  1. Guest

    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
     
    , Jun 26, 2007
    #1
    1. Advertising

  2. Joe Smith Guest

    wrote:
    > 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, Jun 26, 2007
    #2
    1. Advertising

  3. Joe Smith Guest

    Joe Smith wrote:

    > #!/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.
     
    Joe Smith, Jun 26, 2007
    #3
  4. -berlin.de Guest

    <> wrote in comp.lang.perl.misc:
    > 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
     
    -berlin.de, Jun 26, 2007
    #4
  5. -berlin.de Guest

    Joe Smith <> wrote in comp.lang.perl.misc:
    > wrote:
    > > 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";


    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
     
    -berlin.de, Jun 26, 2007
    #5
  6. On Tue, 26 Jun 2007 01:39:30 -0700, Joe Smith <> wrote:

    >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
    --
    {$_=pack'B8'x25,unpack'A8'x32,$a^=sub{pop^pop}->(map substr
    (($a||=join'',map--$|x$_,(unpack'w',unpack'u','G^<R<Y]*YB='
    ..'KYU;*EVH[.FHF2W+#"\Z*5TI/ER<Z`S(G.DZZ9OX0Z')=~/./g)x2,$_,
    256),7,249);s/[^\w,]/ /g;$ \=/^J/?$/:"\r";print,redo}#JAPH,
     
    Michele Dondi, Jun 26, 2007
    #6
  7. Joe Smith <> wrote:

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



    But `perldoc -q sort` does. :)


    --
    Tad McClellan
    email: perl -le "print scalar reverse qq/moc.noitatibaher\100cmdat/"
     
    Tad McClellan, Jun 26, 2007
    #7
  8. On Tue, 26 Jun 2007 12:12:01 +0200, Michele Dondi
    <> wrote:

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


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


    Michele
    --
    {$_=pack'B8'x25,unpack'A8'x32,$a^=sub{pop^pop}->(map substr
    (($a||=join'',map--$|x$_,(unpack'w',unpack'u','G^<R<Y]*YB='
    ..'KYU;*EVH[.FHF2W+#"\Z*5TI/ER<Z`S(G.DZZ9OX0Z')=~/./g)x2,$_,
    256),7,249);s/[^\w,]/ /g;$ \=/^J/?$/:"\r";print,redo}#JAPH,
     
    Michele Dondi, Jun 26, 2007
    #8
  9. Joe Smith wrote:
    > wrote:
    >> I need some hints on how to setup the sort function in a couple of
    >> cases that happened to me recently
    >>
    >> 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";


    You only need to stat the files once:

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



    John
    --
    Perl isn't a toolbox, but a small machine shop where you
    can special-order certain sorts of tools at low cost and
    in short order. -- Larry Wall
     
    John W. Krahn, Jun 26, 2007
    #9
  10. -berlin.de wrote:
    >
    > 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
    --
    Perl isn't a toolbox, but a small machine shop where you
    can special-order certain sorts of tools at low cost and
    in short order. -- Larry Wall
     
    John W. Krahn, Jun 26, 2007
    #10
  11. -berlin.de wrote:
    >
    > 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
    --
    Perl isn't a toolbox, but a small machine shop where you
    can special-order certain sorts of tools at low cost and
    in short order. -- Larry Wall
     
    John W. Krahn, Jun 26, 2007
    #11
  12. Uri Guttman Guest

    >>>>> "JS" == Joe Smith <> writes:

    JS> John W. Krahn wrote:
    >> That should be Guttman-Rosler.
    >> http://www.sysarch.com/Perl/sort_paper.html


    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

    --
    Uri Guttman ------ -------- http://www.stemsystems.com
    --Perl Consulting, Stem Development, Systems Architecture, Design and Coding-
    Search or Offer Perl Jobs ---------------------------- http://jobs.perl.org
     
    Uri Guttman, Jun 26, 2007
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Raghuram Devarakonda

    Connecting multiple test cases in a sort of pipe

    Raghuram Devarakonda, Jul 30, 2009, in forum: Python
    Replies:
    2
    Views:
    308
    Raghuram Devarakonda
    Jul 30, 2009
  2. Navin
    Replies:
    1
    Views:
    761
    Ken Schaefer
    Sep 9, 2003
  3. Sam Kong
    Replies:
    10
    Views:
    327
    Sam Kong
    Sep 20, 2006
  4. Terry Reedy

    Re: unittest - sort cases to be run

    Terry Reedy, Aug 21, 2012, in forum: Python
    Replies:
    2
    Views:
    184
    goon12
    Aug 21, 2012
  5. Peter Otten

    Re: unittest - sort cases to be run

    Peter Otten, Aug 21, 2012, in forum: Python
    Replies:
    0
    Views:
    164
    Peter Otten
    Aug 21, 2012
Loading...

Share This Page