use Test::More;

my $r1 = { a => rand };
my $r2 = [ rand ];

my @tests = ( { in1 => [ 43, 43, 44 ],
                in2 => [ 43, 43 ],
                out => [ 44 ],
                name => 'OP example 1',
           },
              { in1 => [ 1,1,1,1,1,2,2,2,3,3,4,5,6 ],
                in2 => [ 1,2,3,4,5,6 ],
                out => [ 1,1,1,1,2,2,3 ],
                name => 'OP example 2',
           },
              { in1 => [ 1,2,3,4,5,6 ],
                in2 => [ 1,1,1,1,1,2,2,2,3,3,4,5,6 ],
                out => [ ],
                name => 'OP example 1 reversed',
           },
              { in1 => [ 43, 43 ],
                in2 => [ 43, 43, 44 ],
                out => [ ],
                name => 'OP example 2 reversed',
           },
              { in1 => [ $r1, $r1, $r2 ],
                in2 => [ $r1, $r1 ],
                out => [ $r2 ],
                name => 'references',
           },
         );

my %solutions = ( Skeeve      => \&skeeve,
#                  moritz      => \&moritz,
#                  moritz2     => \&moritz2,
                  ikegami     => \&ikegami,
                  pjotrik     => \&pjotrik,
                  kyle        => \&kyle,
                  betterworld => \&betterworld,
             );

plan 'tests' => scalar keys( %solutions ) * scalar @tests;

while ( my ( $name, $code ) = each %solutions ) {
    foreach my $t ( @tests ) {
        is_deeply( $code->( $t->{in1}, $t->{in2} ), $t->{out},
                   "$name - $t->{name}" );
    }
}

sub kyle {
    my ( $ref1, $ref2 ) = @_;

    my %h;
    $h{$_}++ for @{$ref1};
    $h{$_}-- for @{$ref2};

    my %x;
    return [ grep { $x{$_}++ < $h{$_} } @{$ref1} ];
}

sub skeeve {
    my ($a, $b)= @_;

    my %d;
    ++$d{$_} foreach @$a;
    --$d{$_} foreach @$b;

    my $d= ();
    return [ map { ($_) x abs $d{$_} } keys %d ];
}

sub moritz {
    my ( $ref1, $ref2 ) = @_;

    my @p = @{$ref1};
    my @q = @{$ref2};

    my ($px, $qx) = (0, 0);

    my @diff;
    while (1) {
        if ($qx >= @q){
            push @diff, @p[$px .. @p-1];
            last;
        } elsif ( $p[$px] == $q[$qx] ) {
            $px++;
            $qx++;
        } else {
            push @diff, $p[$px++];
        }
    }

    return \@diff;
}

sub moritz2 {
    my ( $ref1, $ref2 ) = @_;

    my @p = @{$ref1};
    my @q = @{$ref2};

    my ($px, $qx) = (0, 0);

    my @diff;
    while ($qx < @q) {
        if ( $p[$px] == $q[$qx] ) {
            $px++;
            $qx++;
        } else {
            push @diff, $p[$px++];
        }
    }
    push @diff, @p[$px .. @p-1];

    return \@diff;
}

sub betterworld {
    my ( $ref1, $ref2 ) = @_;

    my @p = @{$ref1};
    my @q = @{$ref2};

    my %q;
    $q{$_}++ for @q;

    my @r = grep {
        --$q{$_} < 0;
    } @p;

    return \@r;
}

sub ikegami {
    my ( $ref1, $ref2 ) = @_;

    my @a = sort { $a <=> $b } @{$ref1};
    my @b = sort { $a <=> $b } @{$ref2};

    my @c;

    while (@a && @b) {
        if ($a[0] < $b[0]) {
            push @c, pop @a;
        }
        elsif ($a[0] > $b[0]) {
            die "Bad data";
        }
        else {
            pop @a;
            pop @b;
        }
    }

    push @c, @a;

    return \@c;
}

sub pjotrik {
    my ($a, $b) = @_;
    my $i = 0;
    return [ map { if ($i < @$b && $_ == $$b[$i]) { $i++; () } else { $_ } } @$a ];
}