package List::Priority;

use 5.006;
use strict;
use warnings;
use vars qw($VERSION);
use Carp;
use List::Util qw/min max/;

$VERSION = '0.05';

# Constructor. Enables Inheritance
sub new {
	my $this = shift;
	my $class = ref($this) || $this;
	my $self = {};
	bless $self, $class;
	if (@_) {
		my %options = @_;
		$self->{options} = \%options;
	$self->{size} = 0;
	return $self;

# Insert an element into the list
sub insert {
	# Arguments check
	croak 'List::Priority - Expected 3 arguments!' if (scalar(@_) != 3);
	# Argument assignment
	(my $self, my $priority, my $object) = @_;
	# Check that priority is numeric - Thanks Randel/Joseph!
	croak 'List::Priority - Priority must be numeric!'
		if ((~$priority & $priority) ne '0');
	# If the list is full
	if (defined($self->{options}{capacity}) and
		$self->{options}{capacity} <= $self->{size}) {
		my ($bottom_priority) = min(keys %{$self->{queues}});
		# And the object's priority is higher than the lowest on the list
		# - remove the lowest one to insert it
		if ($priority > $bottom_priority) {
		# Else, just return - the list is full.
		else {
			return 'List::Priority - Object denied, list is full';
	# Insert
	push(@{$self->{queues}{$priority}}, $object);
	return 1;

# Helper method for pop() and shift()
# If $priority is defined, return the first-in element with that priority.
# Otherwise, use $minmax() to find the best priority in the set, and
# extract the first element with that priority.
sub _extract {
	my ($self, $priority) = @_;
	return undef if ($self->{size} == 0);
	return undef unless (defined ($priority));
	# Remove the queue's first element
	my $object = CORE::shift (@{$self->{queues}{$priority}});
	# If the queue is now empty - delete it
	delete $self->{queues}{$priority}
		if (scalar(@{$self->{queues}{$priority}}) == 0);
	# Return the object I just shifted out of the queue
	return $object;

# Find out the extreme (top or bottom) priority
sub _extreme_priority {
	my ($self, $minmax) = @_;
	return $minmax->(keys %{$self->{queues}});

sub highest_priority {
	my $self = shift;
	return $self->_extreme_priority(\&max);

sub lowest_priority {
	my $self = shift;
	return $self->_extreme_priority(\&min);

sub pop {
	# Arguments check
	croak 'List::Priority - pop expected 1 argument' if (scalar(@_) != 1);
	my ($self) = @_;
	return $self->_extract($self->highest_priority);

sub shift {
	# Arguments check
	croak 'List::Priority - shift expected 1 argument' if (scalar(@_) != 1);
	my ($self) = @_;
	return $self->_extract($self->lowest_priority);

sub size {
	my ($self) = @_;
	return $self->{size};

sub capacity {
	my ($self, $new_capacity) = @_;
	if (@_ > 1) {
		$self->{options}{capacity} = $new_capacity;
		if (defined $new_capacity) { 
			while ($self->size > $new_capacity) {
	return $self->{options}{capacity};

# Documentation

=head1 NAME

List::Priority - Perl extension for a list that manipulates objects by their


  use List::Priority;

  # Create an instance
  my $list = List::Priority->new();

  # Insert some elements, each with a unique priority
  $list->insert(3,' ');

  # Print
  print $list->size()			# prints 3
  while (my $element = $list->pop()) {
  	  print $element;


If you want to handle multiple data items by their order of importance,
this one's for you.

You may retrieve the highest-priority item from the list using C<pop()>, or the
lowest-priority item from the list using C<shift()>. If two items have the same
priority, they are returned in first-in, first-out order. New items are
inserted using C<insert()>.

You can constrain the capacity of the list using the C<capacity> parameter.
Low-priority items are automatically evicted once the specified capacity is
exceeded. By default the list's capacity is unlimited.

Currently insertion (in ordered or random order) is constant-time, but C<shift>
and C<pop> are linear in the number of priorities. Hence List::Priority is a
good choice if one of the following conditions is true:


=item * you need one of its unusual features, like the ability to remove both
high- and low-priority items, or to constrain the list's capacity,

=item * you need to do a lot of inserting, but the list will never contain more
than a few thousand different priority levels.


If neither of these describes your use case, another priority queue
implementation like L<POE::XS::Queue::Array> may perform better.

I'd like to thank Joseph N. Hall and Randal L. Schwartz for their
excellent book "Effective Perl Programming" for one of the code hacks.

=head1 METHODS

=over 4

=item B<new>

  $p_list = List::Priority->new();

B<new> is the constructor for List::Priority objects. It accepts a key-value
list with the list attributes.


=item * B<capacity>

The maximum size of the list.

Inserting after the capacity is reached will result either in a no-op, or the
removal of the most recent lowest priority objects, according to the
C<insert()>'s priority.

  $list = List::Priority->new(capacity => 10);


=item B<insert>

  $result = $p_list->insert($priority, $scalar);

Inserts the scalar to the list. Time taken is approximately constant.

C<$priority> must be numeric. C<$scalar> can be any scalar, including
references (objects).

Returns 1 on success, and a string describing the error upon failure.

=item B<pop>

  $object = $p_list->pop();

Extracts the highest-priority scalar from the list.
Time taken is approximately linear in the number of I<priorities> already in
the list.

Returns the highest-priority object on success, and C<undef> on failure.

=item B<shift>

  $object = $p_list->shift();

Extracts the B<lowest>-priority scalar from the list.
Time taken is approximately linear in the number of I<priorities> already in
the list.

Returns the lowest-priority object on success, C<undef> on failure.

=item B<highest_priority>

  $priority = $p_list->highest_priority();

Returns the priority of the highest-priority item. Time taken is linear in the
number of priorities in the list.

=item B<lowest_priority>

  $priority = $p_list->lowest_priority();

Returns the priority of the lowest-priority item. Time taken is linear in the
number of priorities in the list.

=item B<size>

  $num_elts = $p_list->size();

Takes no arguments. Returns the number of elements in the priority queue.
Time taken is constant.

=item B<capacity>

  my $capacity = $l->capacity();  # get capacity
  $l->capacity($new_capacity);    # set capacity to $new_capacity
  $l->capacity(undef);            # set capacity to infinity

Get/set the list's capacity. If called with an argument, sets the capacity to
that value, discarding any excess low-priority items. To make the capacity
infinite (the default for new lists), call C<capacity()> with an explicit
undefined argument.
Time taken is O($old_capacity - $new_capacity) if $new_capacity <
$old_capacity, constant otherwise.

Returns the (new) capacity.


=head1 EXPORT

None. All interfaces are OO.

=head1 TODO

More tests.

=head1 AUTHOR

Eyal Udassin, <>

Currently maintained by Miles Gould, <>

Thanks to Maik Hentsche for bugfixes.


You can find the Git repository at L<>.

=head1 SEE ALSO

L<Heap::Priority>, L<List::PriorityQueue>, L<Hash::PriorityQueue>,
L<POE::Queue>, L<Timeout::Queue>, L<Data::PrioQ::SkewBinomial>.