File Coverage

blib/lib/Hash/PriorityQueue.pm

Criterion	Covered	Total	%
statement	48	50	96.0
branch	14	18	77.7
condition	8	9	88.8
subroutine	7	7	100.0
pod	4	4	100.0
total	81	88	92.0

package Hash::PriorityQueue;

our $VERSION = '0.01';

use strict;
use warnings;

use List::Util qw(min);

sub new {
	return bless {
		queue => {},     # payloads by prio
		prios => {},     # prios by payload
		min_key => undef,
	}, shift();
}

sub delete {
	my ($self, $payload) = @_;
	my $op = $self->{prios}->{$payload};
	if (defined($op)) {
		$self->{queue}->{$op} = [ grep { $_ ne $payload } @{$self->{queue}->{$op}} ];
		if (!@{$self->{queue}->{$op}}) {
			delete($self->{queue}->{$op});
			if ($self->{min_key} == $op) {
				$self->{min_key} = min keys(%{$self->{queue}});
			}
		}
	}
}

sub pop {
	my ($self) = @_;
	if (!defined($self->{min_key})) {
		return undef;
	}

	my $elem = shift(@{$self->{queue}->{$self->{min_key}}});
	if (!@{$self->{queue}->{$self->{min_key}}}) {
		delete($self->{queue}->{$self->{min_key}});
		$self->{min_key} = min keys(%{$self->{queue}});
	}
	delete($self->{prios}->{$elem});
	return $elem;
}

sub update {
	my ($self, $payload, $priority) = @_;
	my $op = $self->{prios}->{$payload};
	if (defined($op)) {
		$self->{queue}->{$op} = [ grep { $_ ne $payload } @{$self->{queue}->{$op}} ];
		if (!@{$self->{queue}->{$op}}) {
			delete($self->{queue}->{$op});
		}
	}

	$self->{prios}->{$payload} = $priority;
	push(@{$self->{queue}->{$priority}}, $payload);
	if (!defined($self->{min_key}) or $priority < $self->{min_key}) {
		$self->{min_key} = $priority;
	} elsif ($priority > $self->{min_key} and (defined($op) and !defined($self->{queue}->{$op}))) {
		$self->{min_key} = min keys(%{$self->{queue}});
	}
}

*insert = \&update;

1;

__END__