NAME

List::GroupingPriorityQueue - priority queue with grouping

SYNOPSIS

  use List::GroupingPriorityQueue
    qw(grpriq_add grpriq_min_values);

  my $queue = [];
  grpriq_add($queue, 2, 'cat');
  grpriq_add($queue, 4, 'dog');
  grpriq_add($queue, 2, 'mlatu');
  grpriq_min_values($queue);        # ['cat', 'mlatu']

  # fast iteration ($queue must not be modified mid-loop)
  for my $entry (@{$queue}) {
      my ($payload_r, $priority) = @{$entry};
      ...
  }

  # OO
  my $pq = List::GroupingPriorityQueue->new;
  $pq->insert(2, 'cat');
  $pq->insert(4, 'dog');
  $pq->insert(2, 'mlatu');
  $pq->pop;                         # ['cat', 'mlatu']

  # slow iteration (but allows new items to be added)
  while (my $payload_r = $pq->pop) {
      ...
  }
  # or instead via
  $pq->each(
    sub {
        my ($payload_r, $priority) = @_;
        ...
    }
  );

DESCRIPTION

This priority queue implementation provides grouping of elements with the same priority. With a traditional priority queue multiple "pop" calls would need to be made until the priority value changes; worse, some implementations do not return the priority value. That information would need to be encoded into and decoded from the payload under such implementations. This module instead considers payloads with the same priority as belonging to the same set and returns them together as an array reference. The priority information is available to the caller, if need be.

FUNCTIONS

The following functions are available for export. An array reference qref is operated on. Modification of the qref in the calling code may break this module in unexpected ways.

grpriq_add qref priority payload ...

Adds the given payload(s) to the queue qref. There is no return value.

Note that the order of arguments differs from other priority queue modules; the difference allows multiple payload elements to be added with a single call.

The priority should probably be an integer; floating point values are more likely to run into compiler or platform wonkiness should the queue be saved to disk and reloaded elsewhere.

grpriq_min qref

Pulls the lowest priority [[payload,...],priority] array reference from qref, if any.

Use this if you need the priority value for some calculation.

grpriq_min_values qref

Pulls the lowest priority [payload,...] array reference from qref, if any. Equivalent to pop in the OO interface.

grpriq_max qref

Pulls the highest priority [[payload,...],priority] array reference from qref, if any.

grpriq_max_values qref

Pulls the highest priority [payload,...] array reference from qref, if any.

METHODS

A simple OO interface is also provided. This hides the qref but adds overhead.

each callback

Iterator that drains the queue by minimum value. The callback code reference is passed the payload array reference and priority value for each element in the queue.

new

Constructor.

insert priority payload ...

Adds the payload(s) to the priority queue.

Note that the order of arguments differs from other priority queue modules; the difference allows multiple payload elements to be added with a single call.

min

Returns the lowest priority [[payload],priority] array reference.

min_values

Returns the payload (or payloads) with the lowest priority as an array reference. Alias: pop.

max

Returns the lowest priority [[payload],priority] array reference.

max_values

Returns the payload (or payloads) with the highest priority as an array reference.

pop

Alias for min_values. Makes the interface similar to that of List::PriorityQueue.

BUGS

<https://github.com/thrig/List-GroupingPriorityQueue>

SEE ALSO

List::PriorityQueue - what I used in Game::PlatformsOfPeril, and what this module is based on. Other priority queue modules on CPAN have different features that may suit particular needs better, see e.g. Array::Queue::Priority, Hash::PriorityQueue, and Queue::Priority, among others.

Music::RhythmSet makes use of this module to record changes in beat patterns across multiple musical voices.

COPYRIGHT AND LICENSE

Copyright 2021 Jeremy Mates

This program is distributed under the (Revised) BSD License: https://opensource.org/licenses/BSD-3-Clause