TL;DR

A basic priority queue in Raku.

In previous post Raku cglib: a priority queue we took a look at a priority queue implementation in Raku that can be overkill when something very easy is needed.

In particular, if all we need to store are numbers, whose value also represents their priority, and in addition we donâ€™t need to do fancy operations on the data structure (like removing a specific item), we can do with a simpler implementation that only has a handful of methods:

• `enqueue` to add items to the priority queue;
• `dequeue` to take the best item out of it;
• `is-empty` to do the obvious test;
• `elems`/`size` to see how many elements are still in the queue.

So enter BasicPriorityQueue.rakumod, a newcomer in the cglib-raku library!

It comes with an example of usage, showing that it does less than PriorityQueue.rakumod but itâ€™s still useful:

``````sub MAIN {
sub printall (BasicPriorityQueue \$pq) {
\$pq.dequeue.say while ! \$pq.is-empty;
put '-' x 10;
}
printall(BasicPriorityQueue.new(items => 1 .. 5));
printall(BasicPriorityQueue.new(items => 1 .. 5, before => {\$^b < \$^a}));
my \$pq = BasicPriorityQueue.new;
\$pq.enqueue(10);
put 'top is ', \$pq.top;
\$pq.enqueue(3);
put 'top is ', \$pq.top;
\$pq.enqueue(1);
put 'top is ', \$pq.top;
\$pq.enqueue(5);
put 'top is ', \$pq.top;
put 'queue has ', \$pq.size, ' elements';
put 'queue has ', \$pq.elems, ' elements';
printall(\$pq);
}
``````

Wellâ€¦ to be completely honest, itâ€™s possible to store more than numbers. As long as we can provide a `before` function that accepts two items and is capable of telling whether the first should come before the other, weâ€™re fine. E.g. to use letters/strings:

``````before => {\$^a leg \$^b}
``````

This, of course, allows storing also more complex data structures;

``````before => {\$^a<foo> leg \$^b<foo>}
``````

Soâ€¦ the thing that is actually lost is the possibility to refer to items by their identifier, and get rid of an item before itâ€™s extracted from the queue in the normal way. Whether or not we need these additional functionalitiesâ€¦ depends on the problem at hand.

I hope one day Iâ€™ll be able to use it in CodinGame!!!

Comments? Octodon, , GitHub, Reddit, or drop me a line!