view release on metacpan or  search on metacpan

t/max_heap.t  view on Meta::CPAN

plan tests => (@test_tuples * 3)+15;
my @n= 1..10;
my $top;

$top= max_heapify(@n);
is($n[0],10,"max_heapify works");
is($top,10,"... and top looks ok");

$top= max_heap_push(@n,100);
is($n[0],100,"max_heap_push works");
is($top,100,"... and top looks ok");

$top= max_heap_push(@n,99);
is($n[0],100,"max_heap_push works");
is($top,100,"... and top looks ok");

$top= max_heap_shift(@n);
is($n[0],99,"max_heap_shift works");
is($top,100,"... and top looks ok");

$n[5]=1000;
$top= max_heap_adjust_item(@n,5);
is($n[0],1000,"max_heap_adjust_item works");
is($top,1000,"... and top looks ok");

$n[5]=-1;
$top= max_heap_adjust_item(@n,5);
is($n[0],1000,"max_heap_adjust_item works");
is($top,1000,"... and top looks ok");

$n[0]= 0;
$top= max_heap_adjust_top(@n);
is($n[0],99,"max_heap_adjust_top works");
is($top,99,"... and top looks ok");

my @expect= sort { $b<=>$a } @n;
my @got;
push @got, max_heap_shift(@n) while @n;
is("@got","@expect","and everything looks as expected at the end");


my @res;
foreach my $tuple (@test_tuples) {
    my $num_agents= $tuple->[0];
    my $num_jobs= $tuple->[1];

    my $agent_id= "AA";
    my @agents= map { $agent_id++ } 1 .. $num_agents;
    my $job_id= 1;
    my @jobs= map { $job_id++ } 1 .. $num_jobs;

    my %agent_array;
    my @arrays1;
    my @arrays2;
    my @sequence1;
    my @sequence2;
    foreach my $agent_id (@agents) {
        my @agent_jobs1;
        my @agent_jobs2;
        foreach my $job (@jobs) {
            my $j= bless [ int(rand(1000)), $job_id++ ], "OloadAry";
            push @agent_jobs1, $j;
            push @agent_jobs2, $j;

        }
        push @arrays1, bless \@agent_jobs1, "OloadAry";
        push @arrays2, bless \@agent_jobs2, "OloadAry";
        $agent_array{0+ $arrays1[-1]}= $agent_id;
        $agent_array{0+ $arrays2[-1]}= $agent_id;

    }

    my $max_heap_elapsed= 0 - time();
    {
        my $constructed_count;
        for (@arrays1) {
            max_heapify(@$_);
        }
        max_heapify(@arrays1);
        my %taken;
        while (@arrays1) {
            while (@arrays1 and $taken{$arrays1[0][0][1]}) {
                # note do { } means the condition fires after the statement
                do { max_heap_shift(@{$arrays1[0]}) } 
                    while (@{$arrays1[0]} and $taken{$arrays1[0][0][1]});

                if (@{$arrays1[0]}) {
                    max_heap_adjust_top(@arrays1);
                } else {
                    max_heap_shift(@arrays1);
                }
            }
            last unless @arrays1;

            my $best_ary= max_heap_shift(@arrays1);
            my $best_item= $best_ary->[0];
            my $job_id= $best_item->[1];
            my $agent= $agent_array{0+$best_ary};
            my $score= $best_item->[0];
            $taken{$job_id}++;
            push @sequence1, "$agent:$job_id";
        }
    }
    $max_heap_elapsed += time();
    my $max_heap_comparisons= OloadAry::reset_called_count();
    
    my $sort_elapsed= 0 - time();
    {
        @$_= sort { $b <=> $a } @$_ for @arrays2;
        @arrays2= sort { $b <=> $a } @arrays2;
        #die Data::Dumper::Dumper(\@arrays2);
        my %taken;
        while (@arrays2) {
            my $best_ary= shift @arrays2;
            last if !@$best_ary;
            my $best_item= shift @$best_ary;
            my $agent= $agent_array{0+$best_ary};
            my $score= $best_item->[0];
            my $job_id= $best_item->[1];
            push @sequence2, "$agent:$job_id";
            $taken{$job_id}++;
            foreach my $ary (@arrays2) {
                shift @$ary while @$ary and $taken{$ary->[0][1]};
            }
            @arrays2= sort { $b <=> $a } grep { 0+@$_ } @arrays2;
        }
    }