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 aSIZE
and acapacity
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, andundef
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.