'by package' sorting of fully qualified functions

[Tassilo v. Parseval]

Hi there,

I was in the situation to come up with a kind of special sort routine.
The data to be sorted is a list of fully qualified function names as in

Pack1::subpack::func2
Pack1::subpack::func1
Pack1::func
__MAIN__
Pack2::bla
Pack1::subpack::another_subpack::func

which ultimately should be sorted like this:

Pack1::func
Pack1::subpack::func1
Pack1::subpack::func2
Pack1::subpack::another_subpack::func
Pack2::bla
__MAIN__

So essentially this should order these functions hierarchicly on their
package name and finally on their function name. '__MAIN__' should
always come as last element.

I had a hard time getting it right for a seemingly simple problem such
as this one. My solution:

@sorted = sort bypackage @functions;

sub bypackage {

# make sure that __MAIN__ is always last on output
return 1 if $a eq '__MAIN__';
return -1 if $b eq '__MAIN__';

my @a = split /::/, $a;
my @b = split /::/, $b;

my $s = '$a[0] cmp $b[0]';
if (@a == @b) {
$s .= "||\$a[$_] cmp \$b[$_]" for 1 .. $#a;
} else {
my $min = @a < @b ? $#a : $#b;
$s = '$a[0] cmp $b[0]';
$s .= "||\$a[$_] cmp \$b[$_]" for 1 .. $min-1;
$s .= "||\@a <=> \@b";
}
return eval $s;
}

I am not so much concerned with the dog-like slowness of the above. That
can be tolerated (the splits could be be cached to improve it a little).
I think the wordiness doesn't make this a very elegant solution measured
by Perl-standards.

How would others solve this task?

Bonus question: if speed was an issue, how could techniques such as
the Schwartzian or Guttman-Rosler Transform be applied here?

Tassilo

 

[Anno Siegel]

Hi there,

I was in the situation to come up with a kind of special sort routine.
The data to be sorted is a list of fully qualified function names as in

Pack1::subpack::func2
Pack1::subpack::func1
Pack1::func
__MAIN__
Pack2::bla
Pack1::subpack::another_subpack::func

which ultimately should be sorted like this:

Pack1::func
Pack1::subpack::func1
Pack1::subpack::func2
Pack1::subpack::another_subpack::func
Pack2::bla
__MAIN__

So essentially this should order these functions hierarchicly on their
package name and finally on their function name. '__MAIN__' should
always come as last element.

That last requirement will have to be dealt with in an ad-hoc manner.
Also, "__MAIN__" isn't a fully qualified function name. I'll ignore
it for now.

I had a hard time getting it right for a seemingly simple problem such
as this one. My solution:

@sorted = sort bypackage @functions;

sub bypackage {

# make sure that __MAIN__ is always last on output
return 1 if $a eq '__MAIN__';
return -1 if $b eq '__MAIN__';

my @a = split /::/, $a;
my @b = split /::/, $b;

my $s = '$a[0] cmp $b[0]';
if (@a == @b) {
$s .= "||\$a[$_] cmp \$b[$_]" for 1 .. $#a;
} else {
my $min = @a < @b ? $#a : $#b;
$s = '$a[0] cmp $b[0]';
$s .= "||\$a[$_] cmp \$b[$_]" for 1 .. $min-1;
$s .= "||\@a <=> \@b";
}
return eval $s;
}

Gee, I must be missing something. As far as I see, you only need to
split off the (final) function name. Sort the package parts, and within
these sort the function names. So:

sub bypackage {
my ( $apack, $aname) = $a =~ /(.+):.+)/;
my ( $bpack, $bname) = $b =~ /(.+):.+)/;
$apack cmp $bpack or $aname cmp $bname;
}

[...]

Bonus question: if speed was an issue, how could techniques such as
the Schwartzian or Guttman-Rosler Transform be applied here?

I don't need to explain how to apply the Schwartz transform to my
suggestion. The GRT doesn't seem to apply easily, as always when
different sort fields must be dealt with independently.

Anno

 

[Ben Morrow]

Hi there,

I was in the situation to come up with a kind of special sort routine.
The data to be sorted is a list of fully qualified function names as in

Pack1::subpack::func2
Pack1::subpack::func1
Pack1::func
__MAIN__
Pack2::bla
Pack1::subpack::another_subpack::func

which ultimately should be sorted like this:

Pack1::func
Pack1::subpack::func1
Pack1::subpack::func2
Pack1::subpack::another_subpack::func
Pack2::bla
__MAIN__

So essentially this should order these functions hierarchicly on their
package name and finally on their function name. '__MAIN__' should
always come as last element.

How would others solve this task?

#!/usr/bin/perl

$\ = $, = "\n";

use subs qw/hier_cmp bypackage/;

my @functions = qw/
Pack1::subpack::func2
Pack1::subpack::func1
Pack1::func
__MAIN__
Pack2::bla
Pack1::subpack::another_subpack::func
/;

sub hier_cmp {
my @x = @{$_[0]};
my @y = @{$_[1]};

my ($x, $y) = (shift @x, shift @y);

return $x cmp $y unless @x || @y;
return 1 unless @y;
return -1 unless @x;

return ($x cmp $y) || hier_cmp \@x, \@y;
}

sub bypackage {
return 1 if $a eq '__MAIN__';
return -1 if $b eq '__MAIN__';

my @a = split /::/, $a;
my @b = split /::/, $b;

return hier_cmp \@a, \@b;
}

print sort bypackage @functions;

__END__

I don't really like having '$x cmp $y' in there twice, but I can't see
how to get rid of it.

Ben

 

[Tassilo v. Parseval]

Also sprach Anno Siegel:

Hi there,

I was in the situation to come up with a kind of special sort routine.
The data to be sorted is a list of fully qualified function names as in

Pack1::subpack::func2
Pack1::subpack::func1
Pack1::func
__MAIN__
Pack2::bla
Pack1::subpack::another_subpack::func

which ultimately should be sorted like this:

Pack1::func
Pack1::subpack::func1
Pack1::subpack::func2
Pack1::subpack::another_subpack::func
Pack2::bla
__MAIN__

[...]

Gee, I must be missing something. As far as I see, you only need to
split off the (final) function name. Sort the package parts, and within
these sort the function names. So:

sub bypackage {
my ( $apack, $aname) = $a =~ /(.+):.+)/;
my ( $bpack, $bname) = $b =~ /(.+):.+)/;
$apack cmp $bpack or $aname cmp $bname;
}

Embarrassingly simple really. I initially was treating the function name
in a similar matter. But the major flaw in each of my attempts was that I
also split the package portion instead of just leaving it intact.

Alright, I'll retreat in shame.

I don't need to explain how to apply the Schwartz transform to my
suggestion.

Indeed not, thank you!

Tassilo

 

[Tassilo v. Parseval]

Also sprach Ben Morrow:

Hi there,

I was in the situation to come up with a kind of special sort routine.
The data to be sorted is a list of fully qualified function names as in

Pack1::subpack::func2
Pack1::subpack::func1
Pack1::func
__MAIN__
Pack2::bla
Pack1::subpack::another_subpack::func

which ultimately should be sorted like this:

Pack1::func
Pack1::subpack::func1
Pack1::subpack::func2
Pack1::subpack::another_subpack::func
Pack2::bla
__MAIN__

So essentially this should order these functions hierarchicly on their
package name and finally on their function name. '__MAIN__' should
always come as last element.

How would others solve this task?

#!/usr/bin/perl

$\ = $, = "\n";

use subs qw/hier_cmp bypackage/;

my @functions = qw/
Pack1::subpack::func2
Pack1::subpack::func1
Pack1::func
__MAIN__
Pack2::bla
Pack1::subpack::another_subpack::func
/;

sub hier_cmp {
my @x = @{$_[0]};
my @y = @{$_[1]};

my ($x, $y) = (shift @x, shift @y);

return $x cmp $y unless @x || @y;
return 1 unless @y;
return -1 unless @x;

return ($x cmp $y) || hier_cmp \@x, \@y;
}

sub bypackage {
return 1 if $a eq '__MAIN__';
return -1 if $b eq '__MAIN__';

my @a = split /::/, $a;
my @b = split /::/, $b;

return hier_cmp \@a, \@b;
}

print sort bypackage @functions;

__END__

I don't really like having '$x cmp $y' in there twice, but I can't see
how to get rid of it.

I kind of like that. It's the recursive implementation of what my
function did. Yet I assume that you would have come up with a solution
similar to Anno's if I hadn't provided my ridiculously complicated code
that probably distracted you.

Tassilo

 

[Bo Lindbergh]

How about this: split each fully qualified name into package name and
function name; use the package name as the key for a hash of arrays of
function names. This lets you sort the package names first and then
sort the function names within each package separately.

/Bo Lindbergh