Arguments to "make_sorter"

Arguments fall into four categories: selecting the style of the sort, key descriptions, setting defaults for key description attributes, and setting general flags and values. The following sections will describe the categories and their associated arguments.

Sort Style

        plain
        orcish
        ST
        GRT

        # Make a plain sorter
        my $plain_sorter = make_sorter( qw( plain ) ... ) ;

        # Make an orcish manouevre sorter
        my $orcish_sorter = make_sorter( orcish => 1 ... ) ;

        # Make a Schwartzian Transform sorter
        my $st_sorter = make_sorter( 'ST', 1, ... ) ;

        # Make a GRT sort
        my $GRT = make_sorter( 'GRT', ... ) ;

Key Attribute Defaults

        ascending       (default)
        descending

        case            (default)
        no_case

        signed
        unsigned
        signed_float    (default)
        unsigned_float

        fixed
        varying

General Options

"name"

This is a value option which exports the generated sort sub to that name. The call to "make_sorter" must be run to install the named named function before it is called. You should still check the result of "make_sorter" to see if an error occurred (it returns undef).

        my $sorter = make_sorter( name => 'sort_func', ... ) ;
        die "make_sorter: $@" unless $sorter ;

        ...

        @sorted = sort_func @unsorted ;

"ref_in/ref_out"

This boolean arguments specifies that the input to and output from the sort sub will be array references. "ref_in" makes the sorter only take as input a single array reference (which contains the unsorted records). "ref_out" makes the sorter only return a single array reference (which contains the sorted records). You can set both of these options in a sorter.

Note: This does not affect key extraction code which still gets each record in $_. It only modifies the I/O of the generated sorter.

        # input records are in an array reference
        my $sorter = make_sorter( qw( ref_in ), ... ) ;
        @sorted_array = $sorter->( \@unsorted_input ) ;

        # sorted output records are in an array reference
        my $sorter = make_sorter( ref_out => 1, ... ) ;
        $sorted_array_ref = $sorter->( @unsorted_input ) ;

        # input and output records are in array references
        my $sorter = make_sorter( qw( ref_in ref_out ), ... ) ;
        $sorted_array_ref = $sorter->( \@unsorted_input ) ;

"string_data"

This boolean argument specifies that the input records will be plain text strings with no null (0x0) bytes in them. It is only valid for use with the GRT and it is ignored for the other sort styles. It tells the GRT that it can put the record directly into the string cache and it will be separated from the packed keys with a null byte (hence that restriction). This is an optimization that can run slightly faster than the normal index sorting done with the GRT. Run this to see the benchmark results.

        perl t/string_data.t -bench

"init_code"

This value argument is code that will be put into the beginning of the generated sorter subroutine. It is meant to be used to declare lexical variables that the extraction code can use. Normally different extraction code have no way to share common code. By declaring lexicals with the "init_code" option, some key extraction code can save data there for use by another key. This is useful if you have two (or more) keys that share a complex piece of code such as accessing a deep value in a record tree.

For example, suppose the input record is an array of arrays of hashes of strings and the string has 2 keys that need to be grabbed by a regex. The string is a string key, a ':' and a number key. So the common part of the key extraction is:

        $_->[0][0]{a}

And the make_sorter call is:

        my $sorter = make_sorter( 
                'ST',
                init_code => 'my( $str, $num ) ;',
                string => 'do{( $str, $num ) =
                        $_->[0][0]{a} =~ /^(\w+):(\d+)$/; $str}',
                number => '$num'
        ) ;

In the above code both keys are extracted in the first key extraction code and the number key is saved in $num. The second key extraction code just uses that saved value.

Note that "init_code" is only useful in the ST and GRT sort styles as they process all the keys of a record at one time and can use variables declared in "init_code" to transfer data to later keys. The plain and orcish sorts may not process a later key at the same time as an earlier key (that only happens when the earlier key is compared to an equal key). Also for "init_code" to be a win, the data set must be large enough and the work to extract the keys must be hard enough for the savings to be noticed. The test init_code.t shows some examples and you can see the speedup when you run:

        perl t/init_code.t -bench

Key Description Arguments

The generated sorter will sort the records according to the order of the key arguments. The first key is used to compare a pair of records and if they are deemed equal, then the next key is examined. This happens until the records are given an ordering or you run out of keys and the records are deemed equal in sort order. Key descriptions can be mixed with the other arguments which can appear in any order and anywhere in the argument list, but the keys themselves must be in the desired order.

A key argument is either 'string' or 'number' followed by optional attributes. The key type sets the way that the key is compared (e.g. using 'cmp' or '<=>'). All key attributes can be set from the default values in the global arguments or set in each individual key description.

There are 4 ways to provide attributes to a key:

No attributes

A key argument which is either at the end of the argument list or is followed by a valid keyword token has no explict attributes. This key will use the default attributes. In both of these examples, a default attribute was set and used by the key description which is just a single key argument.

        # sort the record as a single number in descending order
        my $sorter = make_sorter( qw( plain number descending ) ) ;

        # sort the record as a case sensitive string
        my $sorter = make_sorter( qw( plain case string ) ) ;

        # sort the record as a single number in ascending order
        my $sorter = make_sorter( qw( ST number ) ) ;

Only Code as a Value

A key argument which is followed by a scalar value which is not a valid keyword token, will use that scalar value as its key extraction code. See below for more on key extraction code.

        # sort by the first (optionally signed) number matched
        my $sorter = make_sorter( qw( plain number /([+-]?\d+)/ ) ) ;

        # string sort by the 3rd field in the input records (array refs)
        my $sorter = make_sorter( 'ST', string => '$_->[2]' ) ;

An Array Reference

A key argument which is followed by an array reference will parse that array for its description attributes. As with the general boolean arguments, any boolean attribute can be optionally followed by a '1'. Value attributes must be followed by their value.

        # another way to specify the same sort as above
        # sort by the first (optionally signed) number matched

        my $sorter = make_sorter(
                qw( plain ),
                number => [
                        code => '/(\d+)/',
                        'descending',
                ],
        ) ;

        # same sort but for the GRT which uses the 'unsigned'
        # attribute to optimize the sort.

        my $sorter = make_sorter(
                qw( GRT ),
                number => [
                        qw( descending unsigned ),
                        code => '/(\d+)/',
                ],
        ) ;

A Hash Reference

A key argument which is followed a hash reference will use that hash as its description attributes. Any boolean attribute in the hash must have a value of '1'. Value attributes must be followed by their value.

        # another way to specify the same sort as above
        # sort by the first (optionally signed) number matched

        my $sorter = make_sorter(
                qw( plain ),
                number => {
                        code => '/(\d+)/',
                        descending => 1,
                },
        ) ;

        # a multi-key sort. the first key is a descending unsigned
        # integer and the second is a string padded to 10 characters

        my $sorter = make_sorter(
                qw( GRT ),
                number => {
                        code => '/(\d+)/',
                        descending => 1,
                        unsigned => 1,
                },
                string => {
                        code => '/FOO<(\w+)>/',
                        fixed => 10,
                },
        ) ;

Key Description Attributes

"code"

This value attribute is the code that will be used to extract a key from the input record. It can be a string of Perl code, a qr// regular expression (Regexp reference) or an anonymous sub (CODE reference) that operates on $_ and extracts a value. The code will be wrapped in a do{} block and called in a list context so that regular expressions can just use () to grab a key value. The code defaults to $_ which means the entire record is used for this key. You can't set the default for code (unlike all the other key attributes). See the section on Extraction Code for more.

        # make an ST sort of the first number grabbed in descending order

        my $sorter = make_sorter(
                qw( ST ),
                number => {
                        code    => '/(\d+)/',
                        descending => 1,
                },
        ) ;

"ascending/descending"

These two Boolean attributes control the sorting order for this key. If a key is marked as "ascending" (which is the initial default for all keys), then lower keys will sort before higher keys. "descending" sorts have the higher keys sort before the lower keys. It is illegal to have both set in the defaults or in any key.

        # sort by descending order of the first grabbed number
        # and then sort in ascending order the first grabbed <word>

        my $sorter = make_sorter(
                qw( ST descending ),
                number => {
                        code    => '/(\d+)/',
                },
                string => {
                        code    => '/<(\w+)>/',
                        ascending => 1,
                },
        ) ;

        # this will return undef and store an error in $@. 
        # you can't have both 'ascending' and 'descending' as defaults

        my $sorter = make_sorter(
                qw( ST ascending descending ),
                number => {
                        code    => '/(\d+)/',
                        descending => 1,
                },
        ) ;

        # this will return undef and store an error in $@. 
        # you can't have both 'ascending' and 'descending' in a key

        my $sorter = make_sorter(
                qw( ST )
                number => {
                        code    => '/(\d+)/',
                        descending => 1,
                        ascending => 1,
                },
        ) ;

"case/no_case"

These two Boolean attributes control how 'string' keys handle case sensitivity. If a key is marked as "case" (which is the initial default for all keys), then keys will treat upper and lower case letters as different. If the key is marked as "no_case" then they are treated as equal. It is illegal to have both set in the defaults or in any key. Internally this uses the uc() function so you can use locale settings to affect string sorts.

        # sort by the first grabbed word with no case
        # and then sort the grabbed <word> with case

        my $sorter = make_sorter(
                qw( ST no_case ),
                string => {
                        code    => '/(\w+)/',
                },
                string => {
                        code    => '/<(\w+)>/',
                        case => 1,
                },
        ) ;

        # this will return undef and store an error in $@. 
        # you can't have both 'case' and 'no_case' as defaults

        my $sorter = make_sorter(
                qw( ST no_case case ),
                string => {
                        code    => '/(\w+)/',
                },
        ) ;

        # this will return undef and store an error in $@. 
        # you can't have both 'case' and 'no_case' in a key

        my $sorter = make_sorter(
                qw( ST )
                string => {
                        code    => '/(\w+)/',
                        no_case => 1,
                        case    => 1,
                },
        ) ;

"closure"

This Boolean attribute causes this key to use call its CODE reference to extract its value. This is useful if you need to access a lexical variable during the key extraction. A typical use would be if you have a sorting order stored in a lexical and need to access that from the extraction code. If you didn't set the "closure" attribute for this key, the generated source (see Key Extraction) would not be able to see that lexical which will trigger a Perl compiling error in make_sorter.

        my @months = qw( 
                January February March April May June 
                July August September October November December ) ;
        my @month_jumble = qw(
                February June October March January April
                July November August December May September ) ;

        my %month_to_num ;
        @month_to_num{ @months } = 1 .. @months ;

# this will fail to generate a sorter if 'closure' is removed # as %month_to_num will not be in scope to the eval inside sort_maker.

        my $sorter = make_sorter(
                'closure',
                number => sub { $month_to_num{$_} },
        ) ;

        my @sorted = $sorter->( @month_jumble ) ;

"signed/unsigned/signed_float/unsigned_float" (GRT only)

These Boolean attributes are only used by the GRT sort style. They are meant to describe the type of a number key so that the GRT can best process and cache the key's value. It is illegal to have more than one of them set in the defaults or in any key. See the section on GRT sorting for more.

The "signed" and "unsigned" attributes mark this number key as an integer. The GRT does the least amount of work processing an unsigned integer and only slightly more work for a signed integer. It is worth using these attributes if a sort key is restricted to integers.

The "signed_float" (which is the normal default for all keys) and "unsigned_float" attributes mark this number key as a float. The GRT does the less work processing an unsigned float then a signed float. It is worth using the "unsigned_float" attribute if a sort key is restricted to non-negative values. The "signed_float" attribute is supported to allow overriding defaults and to make it easier to auto-generate sorts.

"fixed/varying" (GRT only)

These attributes are only used by the GRT sort style. They are used to describe the type of a string key so that the GRT can properly process and cache the key's value. It is illegal to have more than one of them set in the defaults or in any key. See the section on GRT sorting for more.

"fixed" is a value attribute that marks this string key as always being this length. The extracted value will either be padded with null (0x0) bytes or truncated to the specified length (the value of "fixed"). The data in this key may have embedded null bytes (0x0) and may be sorted in descending order.

"varying" is a Boolean attribute marks this string key as being of varying lengths. The GRT sorter will do a scan of all of this key's values to find the maximum string length and then it pads all the extracted values to that length. The data in this key may have embedded null bytes (0x0) and may be sorted in descending order.

Key Extraction Code

Code can be either a string, a qr// object (Regexp reference) or an anonymous sub (CODE reference).

If qr// is used, the actual generated code will be m($qr) which works because qr// will interpolate to its string representation. The advantage of qr// over a string is that the qr// will be syntax checked at compile time while the string only later when the generated sorter is compiled by an eval.

If a CODE reference is found, it is used to extract the key in the generated sorter. As with qr//, the advantage is that the extraction code is syntax checked at compile time and not runtime. Also the deparsed code is wrapped in a "do{}" block so you may use complex code to extract the key. In the default case a CODE reference will be deparsed by the B::Deparse module into Perl source. If the key has the "closure" attribute set, the code will be called to extract the key.

The following will generate sorters with exact same behavior:

        $sorter = make_sorter( 'ST', string => '/(\w+)/' ) ;
        $sorter = make_sorter( 'ST', string => qr/(\w+)/ ) ;
        $sorter = make_sorter( 'ST', string => sub { /(\w+)/ } ) ;
        $sorter = make_sorter( 'ST', 'closure', string => sub { /(\w+)/ } ) ;

Extraction code for a key can be set in one of three ways.

No explicit code

If you don't pass any extraction code to a key, it will default to $_ which is the entire record. This is useful in certain cases such as in simple sorts where you are sorting the entire record.

        # sort numerically and in reverse order
        my $sorter = make_sorter( qw( plain number descending ) ;

        # sort with case folding
        my $sorter = make_sorter( qw( plain no_case string ) ;

        # sort by file time stamp and then by name
        my $sorter = make_sorter( 'ST', number => '-M', 'string' ) ;

Code is the only key attribute

In many cases you don't need to specify any specific key attributes (the normal or globally set defaults are fine) but you need extraction code. If the argument that follows a key type ( 'string' or 'number' ) is not a valid keyword, it will be assumed to be the extraction code for that key.

        # grab the first number string as the key
        my $sorter = make_sorter( qw( plain number /(\d+)/ ) ) ;

        # no_case string sort on the 3rd-5th chars of the 2nd array element
        my $sorter = make_sorter(
                plain   => 1,
                no_case => 1,
                string  => 'substr( $_->[1], 2, 3)'
        ) ;

Key needs specific attributes

When the key needs to have its own specific attributes other than its code, you need to pass them in an ARRAY or HASH reference. This is mostly needed when there are multiple keys and the defaults are not correct for all the keys.

        # string sort by the first 3 elements of the array record with
        # different case requirements
        
        my $sorter = make_sorter(
                ST      => 1,
                string  => {
                        code    => '$_->[0]',
                        no_case => 1,
                },
                string  => '$_->[1]',
                string  => {
                        code    => '$_->[2]',
                        no_case => 1,
                },
        ) ;

        # GRT sort with multiple unsigned integers and padded strings
        # note that some keys use a hash ref and some an array ref
        # the record is marked with key\d: sections
        my $sorter = make_sorter(
                GRT     => 1,
                descending => 1,
                number  => {
                        code    => 'key1:(\d+)',
                        unsigned => 1,
                },
                number  => [
                        code    => 'key2:([+-]?\d+)',
                        qw( signed ascending ),
                ],
                string  => [
                        code    => 'key3:(\w{10})',
                        fixed => 1,
                        ascending => 1,
                ],
                # pad the extracted keys to 8 chars
                string  => {
                        code    => 'key4:([A-Z]+)',
                        pad => 8,
                },
        ) ;

"plain"

"orcish"

        $cache{$a} ||= CODE($a) ;

CODE is the extract code and it operates on a record in $a. If we have never seen this record before then the cache entry will be undef and the ||= operator will assign the extracted key to that hash slot. The next time this record is seen in a comparison, the saved extracted key will be found in the hash and used. The name orcish comes from OR-cache.

"ST"

        map [ $_, CODE1( $_ ), CODE2( $_ ) ], @input

The CODE's extract the set of keys from the record but only once per record so it is O(N). Now the sort function can just do the comparisons and it returns a list of sorted anonymous arrays.

        sort {
                $a->[1] cmp $b->[1]
                        ||
                $a->[2] cmp $b->[2]
        }

Finally, we need to get back the original records which are in the first slot of the anonymous array:

        map $_->[0]

This is why the ST is known as a map/sort/map technique.

"GRT"

The GRT gains its speed by using a single byte string to cache all of the extracted keys from a given input record. Packing keys into a string such that it will lexically sort the correct way requires some deep mojo and data munging. But that is why this module was written - to hide all that from the coder. Below are descriptions of how the various key types are packed and how to best use the GRT specific key attributes. Note: you can only use one of the GRT number or string attributes for any key. Setting more than one in either the defaults or in any given key is an error (a key's attribute can override a default choice).

"unsigned"

The 'unsigned' Boolean attribute tells the GRT that this number key is a non-negative integer. This allows the GRT to just pack it into 4 bytes using the N format (network order - big endian). An integer packed this way will have its most significant bytes compared before its least signifigant bytes. This involves the least amount of key munging and so it is the most efficient way to sort numbers in the GRT.

If you want this key to sort in descending order, then the key value is negated and normalized (see the 'signed' attribute) so there is no advantage to using 'unsigned'.

"signed"

The 'signed' Boolean attribute tells the GRT that this number key is an integer. This allows the GRT to just pack it into 4 bytes using the N format (network order - big endian). The key value must first be normalized which will convert it to an unsigned integer but with the same ordering as a signed integer. This is simply done by inverting the sign (highest order) bit of the integer. As mentioned above, when sorting this key in descending order, the GRT just negates the key value.

NOTE: In the GRT the signed and unsigned integer attributes only work on perl built with 32 bit integers. This is due to using the N format of pack which is specified to be 32 bits. A future version may support 64 bit integers (anyone want to help?).

"unsigned_float"

The 'unsigned_float' Boolean attribute tells the GRT that this number key is a non-negative floating point number. This allows the GRT to pack it into 8 bytes using the 'd' format. A float packed this way will have its most significant bytes compared before its least signifigant bytes.

"signed_float"

The "signed_float" Boolean attribute (which is the default for all number keys when using the GRT) tells the GRT that this number key is a floating point number. This allows the GRT to pack it into 8 bytes using the 'd' format. A float packed this way will have its most significant bytes compared before its least signifigant bytes. When processed this key will be normalized to an unsigned float similar to to the "signed" to "unsigned" conversion mentioned above.

NOTE: The GRT only works with floats that are in the IEEE format for doubles. This includes most modern architectures including x86, sparc, powerpc, mips, etc. If the cpu doesn't have IEEE floats you can either use the integer attributes or select another sort style (all the others have no restriction on float formats).

simple string.

If a string key is being sorted in ascending order with the GRT and it doesn't have one of the GRT string attributes, it will be packed without any munging and a null (0x0) byte will be appended to it. This byte enables a shorter string to sort before longer ones that start with the shorter string.

NOTE: You cannot sort strings in descending order in the GRT unless the key has either the 'fixed' or 'varying' attributes set. Also, if a string is being sorted in ascending order but has any null (0x0) bytes in it, the key must have one of those attributes set.

"fixed"

This value attribute tells the GRT to pack this key value as a fixed length string. The extracted value will either be padded with null (0x0) bytes or truncated to the specified length (the value of the "fixed" attribute). This means it can be packed into the cache string with no padding and no trailing null byte is needed. The key can contain any data including null (0x0) bytes. Data munging happens only if the key's sort order is descending. Then the key value is xor'ed with a same length string of 0xff bytes. This toggles each bit which allows for a lexical comparison but in the reverse order. This same bit inversion is used for descending varying strings.

"varying"

This Boolean attribute tells the GRT that this key value is a varying length string and has no predetermined padding length. A prescan is done to determine the maximum string length for this key and that is used as the padding length. The rest is the same as with the 'fixed' attribute.

"sorter_source"

        my $sorter = make_sorter( ... ) ;
        print sorter_source( $sorter ) ;

        make_sorter( name => 'my_sorter', ... ) ;
        print sorter_source( \&my_sorter ) ;

        my $sorter = make_sorter( ... ) 
                or die "make_sorter error: $@\n", sorter_source();

If all you want is the generated source you can just do:

        print sorter_source make_sorter( ... ) ;

Error Handling