view release on metacpan or  search on metacpan

lib/List/Flat.pm  view on Meta::CPAN

package List::Flat;
use 5.008001;
use strict;
use warnings;

our $VERSION = "0.003";
$VERSION = eval $VERSION;

use Exporter 5.57 'import';
our @EXPORT_OK = qw/flat flat_r flat_f/;

# if PERL_LIST_FLAT_NO_REF_UTIL environment variable is set to a true
# value, or $List::Flat::NO_REF_UTIL is set to a true value,
# uses the pure-perl version of is_plain_arrayref.
# Otherwise, uses Ref::Util if it can be successfully loaded.

BEGIN {
    my $impl = $ENV{PERL_LIST_FLAT_NO_REF_UTIL}
      || our $NO_REF_UTIL;

    if ( !$impl && eval { require Ref::Util; 1 } ) {
        Ref::Util->import('is_plain_arrayref');
    }
    else {
        *is_plain_arrayref = sub { ref( $_[0] ) eq 'ARRAY' };
    }
}

{
    my $croak;

    sub flat {
        $croak = 1;
        goto &_flat;
        # call _flat with current @_
    }

    sub flat_r {
        undef $croak;
        goto &_flat;
        # call _flat with current @_
    }

    sub _flat {

        my @results;
        my @seens;

        # this uses @_ as the queue of items to process.
        # An item is plucked off the queue. If it's not an array ref,
        # put it in @results.

        # If it is an array ref, check to see if it's the same as any
        # of the arrayrefs we are currently in the middle of processing.
        # If it is, either croak if called as flat, or if called as
        # flat_r, don't do anything -- skip to the next one.
        # If it hasn't been seen before, put all the items it
        # contains back on the @_ queue.
        # Also, for each of the items, push a reference into @seens
        # that contains references to all the arrayrefs we are currently
        # in the middle of processing, plus this arrayref.
        # Note that @seens will be empty at the top level, so we must
        # handle both when it is empty and when it is not.

        while (@_) {

            if ( is_plain_arrayref( my $element = shift @_ ) ) {
                if ( !defined( my $seen_r = shift @seens ) ) {
                    unshift @_, @{$element};
                    unshift @seens, ( ( [$element] ) x scalar @{$element} );
                }
                ## no critic (ProhibitBooleanGrep)
                elsif ( !grep { $element == $_ } @$seen_r ) {
                    ## use critic
                   # until the recursion gets very deep, the overhead in calling
                   # List::Util::none seems to be taking more time than the
                   # additional comparisons required by grep
                    unshift @_, @{$element};
                    unshift @seens,
                      ( ( [ @$seen_r, $element ] ) x scalar @{$element} );
                }
                elsif ($croak) {

lib/List/Flat.pm  view on Meta::CPAN

throw an exception.

 my @list = (1, 2, 3);
 push @list, \@list;
 my @flat = flat(@list);
 # throws exception
 
But it will process it again if it's repeated but not circular.

 my @sublist = ( 4, 5, 6 );
 my @repeated = ( \@sublist, \@sublist, \@sublist);
 my @repeated_flat = flat (@repeated);
 # (4, 5, 6, 4, 5, 6, 4, 5, 6)

=item B<flat_r()>

This function takes its arguments and returns either a list (in
list context) or an array reference (in scalar context) that is
flat, so there are no (non-blessed) array references in the result.

If there are any circular references -- an array reference that has
an entry that points to itself, or an entry that points to another
array reference that refers to the first array reference -- it will
not descend infinitely. It skips any reference that it is currently
processing. So:

 my @list = (1, 2, 3);
 push @list, \@list;
 my @flat = flat(@list);
 # (1, 2, 3)
 
But it will process it again if it's repeated but not circular.

 my @sublist = ( 4, 5, 6 );
 my @repeated = ( \@sublist, \@sublist, \@sublist);
 my @repeated_flat = flat (@repeated);
 # (4, 5, 6, 4, 5, 6, 4, 5, 6)
 
=item B<flat_f()>

This function takes its arguments and returns either a list (in
list context) or an array reference (in scalar context) that is
flat, so there are no (non-blessed) array references in the result.

It does not check for circular references, and so will go into an 
infinite loop with something like

 @a = ( 1, 2, 3);
 push @a, \@a;
 @b = flat_f(\@a);

So don't do that. Use C<flat()> or C<flat_r()> instead.

When it is fed non-infinite lists, this function seems to be about 
twice as fast as C<flat()>.

=back

=head1 CONFIGURATION AND ENVIRONMENT

The functions will normally use Ref::Util to determine whether an
element is an array reference or not, but if the environment variable
$PERL_LIST_FLAT_NO_REF_UTIL is set to a true value, or the perl
variable List::Flat::NO_REF_UTIL is set to a true value before
importing it, it will use its internal pure-perl implementation.

=head1 DEPENDENCIES

It has one optional dependency, L<Ref::Util|Ref::Util>. 
If it is not present, a pure perl implementation is used instead.

=head1 SEE ALSO

There are several other modules on CPAN that do similar things.

=over

=item Array::DeepUtils

I have not tested this code, but it appears that its collapse()
routine does not handle circular references.  Also, it must be
passed an array reference rather than a list.

=item List::Flatten

List::Flatten flattens lists one level deep only, so

  1, 2, [ 3, [ 4 ] ]

is returned as 

  1, 2, 3, [ 4 ]

This might be, I suppose, useful in some circumstance or other.

=item List::Flatten::Recursive

The code from this module works well and does the same thing as
C<flat_r()>, but it seems to be somewhat slower than List::Flat (in
my testing; better testing welcome) due to its use of recursive
subroutine calls rather than using a queue of items to be processed.
Moreover, it is reliant on Exporter::Simple, which apparently does
not pass tests on perls newer than 5.10.

=item List::Flatten::XS

This is very fast and is worth using if one can accept its limitations.
These are, however, significant:

=over

=item *

It flattens blessed array references as well as unblessed ones,
which means that any array-based objects (for example,
L<Path::Tiny|Path::Tiny> objects) will be flattened as well.
Array-based objects aren't all that common, but that's not usually
what's desired.

=item *

Like all XS modules it requires a C compiler on the host system to be
installed, or some kind of special binary installation (e.g., ActiveState's 
ppm).

=item *

It goes into an infinite loop with circular references.