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 capacity 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);

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.

Returns the highest-priority 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.

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

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.

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.

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.