in reply to Re: flattening a list-of-lists
in thread flattening a list-of-lists

Hi Limbic~Region, in response to your question in the CB I wrote the following code. It handles the issues you mention in your update as well as the fact that you are doing the wrong kind of traversal. 

#!/usr/bin/perl
use strict;
use warnings;
use Scalar::Util qw(reftype refaddr);

my @array1 = ( 1 .. 10 );
my @array2 = ( qw(a b c) , [ 28, 42, 84 ] , 'foo bar' );

push @array1 , \@array2;
push @array2 , \@array1;
my %hash=(
            foo=>[qw(bar baz)],
            bar=>{ foo=>1, baz=>2},
            baz=>\@array1,
            bop=>\@array2
         );

print "   flatten:",join(', ' , flatten(\@array1 , \@array2)),"\n";
print "lr_flatten:",join(', ' , lr_flatten(\@array1 , \@array2)),"\n";
print "*  flatten:",join(', ' , flatten(\%hash)),"\n";

sub flatten {
   my @context;
   my @flat;
   my %seen;

   push @context,[0,\@_]; # index, array ref
   
   #@context could be simpler if we didnt care about 
   #destroying the arrays that we are  flattening.

   while (@context and $context[-1][0]<@{$context[-1][1]}) {
        my $item=$context[-1][1][$context[-1][0]++]; 
        my $type=reftype $item;
        unless ($type) {
            push @flat,$item;
        } elsif ($type eq 'ARRAY') {
            push @context,[0,$item]
                unless $seen{refaddr $item}++;
        } elsif ($type eq 'HASH') {
            push @context,[0,[map { $_ => $item->{$_} } 
                              sort {$a cmp $b} keys %$item]]
                unless $seen{refaddr $item}++;
        } else {
            Carp::confess "Error! can only flatten scalars, ARRAYs and
+ HASHes,".
                          " got a $type instead\n";
        }
        pop @context unless $context[-1][0]<@{$context[-1][1]};
   }
   return wantarray ? @flat : \@flat;
}

[download]

The output I get for the two variants is below. 

   flatten:1, 2, 3, 4, 5, 6, 7, 8, 9, 10, a, b, c, 28, 42, 84, foo bar
lr_flatten:1, 2, 3, 4, 5, 6, 7, 8, 9, 10, a, b, c, foo bar, 28, 42, 84
*  flatten:bar, baz, 2, foo, 1, baz, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, a,
+ b, c, 28, 42, 84, foo bar

[download]

The star result is from dumping a hash, something I added in just for the hell of it. :-)

Cheers,


---
demerphq

    First they ignore you, then they laugh at you, then they fight you, then you win.
    -- Gandhi

Replies are listed 'Best First'.
Re^3: flattening a list-of-lists (simpler)
by tye (Sage) on Nov 19, 2003 at 20:14 UTC

    Updated: It now includes checking for cycles.

    That seems way complicated. I went with: 

    *isa = \&UNIVERSAL::isa;

sub flatten
{
    my @stack= reverse @_;
    my %seen;
    my @out;
    while(  @stack  ) {
        my $value= pop(@stack);
        if(  !ref($value)  ||  !isa($value,"ARRAY")  ) {
            push @out, $value;
        } elsif(  ! $seen{0+$value}++  ) {
            push @stack, reverse @$value;
        }
    }
    return @out;
}

sub flatten2
{
    my @out;
    my %seen;
    while(  @_  ) {
        my $value= shift(@_);
        if(  !ref($value)  ||  !isa($value,"ARRAY")  ) {
            push @out, $value;
        } elsif(  ! $seen{0+$value}++  ) {
            unshift @_, @$value;
        }
    }
    return @out;
}

my @list = ( 1, [ 2, 3 ], 4, [ [ 5, 6 ], 7, [ 8 ] ] );
print join " ", flatten( @list, @list );
print $/;
print join " ", flatten2( @list, @list );
print $/;

    [download]
    which outputs: 
    1 2 3 4 5 6 7 8 1 4
1 2 3 4 5 6 7 8 1 4

    [download]

                    - tye
[reply]
[d/l]
[select]

      I think its arguable that mine is closer to what (I see) is the spirit of L~R's original intention. That being to minimize the amount overhead especially that associated with the stack. I thought of using this approach, but decided against on the grounds that it involved an unreasonable amount of copying and stack manipulation. Heh. Whatever. In real life I would just use recursion on this most likely. :-)

      Caveats about using is() and 0+$ref in the algorithm of course. Better to use Scalar::Util or parse overload::StrVal(). But you knew that, and its beside the point here isnt it. :-)


      ---
      demerphq

        First they ignore you, then they laugh at you, then they fight you, then you win.
        -- Gandhi

[reply]
[d/l]

In Section Seekers of Perl Wisdom