diff options
| -rwxr-xr-x | challenge-018/e-choroba/perl5/ch-2.pl | 50 |
1 files changed, 34 insertions, 16 deletions
diff --git a/challenge-018/e-choroba/perl5/ch-2.pl b/challenge-018/e-choroba/perl5/ch-2.pl index dfa59b0bd6..27c913ee38 100755 --- a/challenge-018/e-choroba/perl5/ch-2.pl +++ b/challenge-018/e-choroba/perl5/ch-2.pl @@ -30,15 +30,11 @@ use feature qw{ say }; my $i = 1; sub insert_with_priority { - my ($self, $element, $priority, $counter) = @_; - push @$self, [$element, $priority, ($counter // ++$i)]; + my ($self, $element, $priority) = @_; + push @$self, [$element, $priority, ++$i]; my $i = $#$self; my $p = int(($i - 1) / 2); - while ($p >= 0 - && ($self->[$p][PRIORITY] < $self->[$i][PRIORITY] - || ($self->[$p][PRIORITY] == $self->[$i][PRIORITY] - && $self->[$p][COUNTER] > $self->[$i][COUNTER])) - ) { + while ($p >= 0 && $self->_compare($p, $i)) { @$self[$i, $p] = @$self[$p, $i]; $i = $p; $p = int(($i - 1) / 2); @@ -48,11 +44,33 @@ use feature qw{ say }; sub pull_highest_priority_element { my ($self) = @_; my $element = shift(@$self)->[ELEMENT]; - my $new = ref($self)->new; - $new->insert_with_priority(@$_) for @$self; - $_[0] = $new; + unshift @$self, pop @$self if @$self; + $self->_adjust(0); return $element } + + sub _compare { + my ($self, $p1, $p2) = @_; + my $c = $self->[$p1][PRIORITY] <=> $self->[$p2][PRIORITY]; + return $c == -1 + || $c == 0 && $self->[$p1][COUNTER] > $self->[$p2][COUNTER] + } + + sub _adjust { + my ($self, $pos) = @_; + if (my @children + = sort { + ($self->[$a][PRIORITY] <=> $self->[$b][PRIORITY]) + || ($self->[$b][COUNTER] <=> $self->[$a][COUNTER]) + } grep defined $self->[$_], + 2 * $pos + 1, 2 * $pos + 2 + ) { + if ($self->_compare($pos, $children[-1])) { + @$self[$pos, $children[-1] ] = @$self[$children[-1], $pos]; + $self->_adjust($children[-1]); + } + } + } } use Test::More tests => 2 + 2 * 14; @@ -65,17 +83,17 @@ for my $class (qw(My::Queue::Priority::Array My::Queue::Priority::Heap)) { for [a => 10], [b => 4], [c => 2], [d=>8], [e => 4], [f => 3]; ok ! $q->is_empty; - is $q->pull_highest_priority_element, 'a', $class.$#$q; + is $q->pull_highest_priority_element, 'a'; ok ! $q->is_empty; - is $q->pull_highest_priority_element, 'd', $class.$#$q; + is $q->pull_highest_priority_element, 'd'; ok ! $q->is_empty; - is $q->pull_highest_priority_element, 'b', $class.$#$q; + is $q->pull_highest_priority_element, 'b'; ok ! $q->is_empty; - is $q->pull_highest_priority_element, 'e', $class.$#$q; + is $q->pull_highest_priority_element, 'e'; ok ! $q->is_empty; - is $q->pull_highest_priority_element, 'f', $class.$#$q; + is $q->pull_highest_priority_element, 'f'; ok ! $q->is_empty; - is $q->pull_highest_priority_element, 'c', $class.$#$q; + is $q->pull_highest_priority_element, 'c'; ok $q->is_empty; } |