use Test::More;

my $r1 = {};
my $r2 = [];

my @tests = ( { in1 => [ 43, 43, 44 ],
                in2 => [ 43, 43 ],
                out => [ 44 ],
           },
              { 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 ],
           },
              { in1 => [ $r1, $r1, $r2 ],
                in2 => [ $r1, $r1 ],
                out => [ $r2 ],
           },
         );

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

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

while ( my ( $name, $code ) = each %solutions ) {
    my $n = 0;

    foreach my $t ( @tests ) {
        $n++;
        is_deeply( $code->( $t->{in1}, $t->{in2} ), $t->{out}, "$name $n" );
    }
}

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;
}

##</code><code>##

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

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

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