view release on metacpan or  search on metacpan

lib/Array/Heap/ModifiablePriorityQueue.pm  view on Meta::CPAN

package Array::Heap::ModifiablePriorityQueue;
use strict;
use warnings;
use vars qw( $VERSION );
$VERSION = '1.10';
use Array::Heap qw( adjust_heap_idx make_heap_idx pop_heap_idx push_heap_idx
   splice_heap_idx );

=head1 NAME

Array::Heap::ModifiablePriorityQueue - Modifiable priority queue

=head1 SYNOPSIS

   use Array::Heap::ModifiablePriorityQueue;
   my $pq = Array::Heap::ModifiablePriorityQueue->new();
   $pq->add('fish', 42);
   $pq->add('banana', 27);
   print $pq->peek(), "\n"; # banana
   $pq->remove('banana');
   print $pq->get(), "\n"; # fish

=head1 DESCRIPTION

This module implements a priority queue, which is a data structure that can
efficiently locate the item with the lowest weight at any time. This is useful
for writing cost-minimizing and shortest-path algorithms.

Why another priority queue module? First, unlike many similar modules, this one
allows you to modify the queue. Items can be removed from the queue or have
their weight changed after they are added.

Second, it simple to use. Items in the queue don't have to implement any
specific interface. Just throw them in there along with a weight value and
the module will keep track of everything.

Finally, it has good performance on large datasets. This is because it is
based on a partially-ordered heap data structure. Many other priority
queue modules are based on fully sorted lists (even ones that claim to be
heaps). Keeping the items only partially sorted saves time when there are
are a large number of them (several thousand or so).

This module is a Perl wrapper around L<Array::Heap>, a lightweight and fast
heap management module implemented in XS.

=head1 FUNCTIONS

=over 4

=item Array::Heap::ModifiablePriorityQueue->new()

Create a new, empty priority queue.

=cut

sub new {
   my ($class) = @_;
   return bless { heap => [], items => {} } => $class;
}

=item $pq->add($item, $weight)

Add an item to the priority queue with the given weight. If the item is
already present in the queue, modify its weight. Weight must be numeric.

=cut

sub add {
   my ($self, $item, $weight) = @_;
   if (my $node = $self->{items}{$item}) {
      $node->[0] = $weight;
      adjust_heap_idx @{$self->{heap}}, $node->[1];
   }
   else {
      $node = [ $weight, 0, $item ];
      $self->{items}{$item} = $node;
      push_heap_idx @{$self->{heap}}, $node;
   }
}

=item $pq->peek()

Return the first (numerically lowest weight) item from the queue.
Does not modify the queue. Returns undef if the queue is empty.

=cut

sub peek {
   my ($self) = @_;
   my $node = $self->{heap}[0] or return;
   return $node->[2];
}

=item $pq->get()

Removes the first item from the priority queue and returns it.
Returns undef if the queue is empty. If two items in the queue
have equal weight, this module makes no guarantee as to which
one will be returned first.

=cut

sub get {
   my ($self) = @_;
   my $node = pop_heap_idx @{$self->{heap}} or return;
   my $item = $node->[2];
   delete $self->{items}{$item};
   return $item;
}

=item $pq->remove($item)

Removes the given item from the priority queue. If item is not present
in the queue, does nothing.

=cut

sub remove {