NAME

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

SYNOPSIS

use List::Priority;

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

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

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

DESCRIPTION

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 pop(), or the lowest-priority item from the list using shift(). If two items have the same priority, they are returned in first-in, first-out order. New items are inserted using insert().

You can constrain the capacity of the list using the 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 shift and pop are linear in the number of priorities. Hence List::Priority is a good choice if one of the following conditions is true:

  • 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,

  • 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 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.

METHODS

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

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

  • capacity

    The maximum size of the list.

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

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

    A synonym for capacity, retained for backwards compatibility. If you specify both a SIZE and a capacity parameter, SIZE will be ignored.

    This option is deprecated, and may disappear in a future release.

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

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

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

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

pop
$object = $p_list->pop();

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

As an optional argument, takes the specific priority value to pop from, instead of the most important one.

# first-added object whose priority is 3
# NB: _not_ the first-added object whose priority is >= 3
$best_object_p3 = $list->pop(3);

In list context, returns the (priority, object) pair on sucesss, and undef on failure. In scalar context, returns the object on success, and undef on failure.

shift
$object = $p_list->shift();

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

As an optional argument, takes the specific priority value to shift from, instead of the least important one.

# first-added object whose priority is 3
# NB: _not_ the first-added object whose priority is <= 3
$worst_object_p3 = $list->shift(3);

In list context, returns the (priority, object) pair on sucesss, undef on failure. In scalar context, returns the object on success, undef on failure.

size
$num_elts = $p_list->size();

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

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 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.

EXPORT

None. All interfaces are OO.

TODO

More tests.

AUTHOR

Eyal Udassin, <eyaludassin@hotmail.com>

Currently maintained by Miles Gould, <miles@assyrian.org.uk>

Thanks to Maik Hentsche for bugfixes.

CONTRIBUTING

You can find the Git repository at http://github.com/pozorvlak/List-Priority.

SEE ALSO

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