Niche Software

Following on from my 2016/2017 series on immutable types, this short series explores the implementation of an immutable priority queue.

What is a priority queue?

A regular queue preserves the order of items - they are removed from the end of the queue in the same sequence that they were admitted to the queue originally.

By introducing an ordering function, a priority queue reorders items so that the most important items are removed from the queue first. Effectively, some items are fast-tracked and reach the front of the queue quickly, while others are held aside for later.

Introducing the Priority Queue

Saturday, October 20 2018 priority-queues csharp

Recently, while working on a personal project, I needed a priority queue. Instead of slamming all of the items into a sorted list and making do, I decided to do the job properly and write a proper abstraction. To keep things interesting, it was an immutable implementation.

Designing the External API

Saturday, October 27 2018 priority-queues csharp

As we did previously with our regular immutable queue, we should start by considering the design of our external interface - our API. How do we want our users to create and interact with our priority queue?

Dequeuing Values

Saturday, November 03 2018 priority-queues csharp

Before we can start on the actual implementation of our immutable priority queue, we need to understand the algorithms we’re going to use. There are two different scenarios to consider - when we enqueue something onto the queue, and when we dequeue the head.

Enqueuing Values

Saturday, November 10 2018 priority-queues csharp

After exploring last time how to remove an item from a queue, let’s look at the slightly more complex case of adding items.

Simple Queues

Saturday, November 17 2018 priority-queues csharp

As we did with our original immutable queue, we’ll define dedicated implementations of IImmutablePriorityQueue<T> for handling empty and single item queues.

Two Dual Item Queues

Saturday, November 24 2018 priority-queues csharp

Once we have a priority queue containing a single item, how do we handle enqueuing the next item onto the queue? The answer, of course, is buried in the code from from last time: we introduce the DualItemImmutablePriorityQueue<T>.

Creating Branching Nodes

Saturday, December 01 2018 priority-queues csharp

For a queue exceeding two items, our existing implementations are insufficient. We need another - a BranchingImmutablePriorityQueue<T>. Each of these nodes will combine two existing sub-queues with a head item to form a tree structure.

Queue Testing

Saturday, December 08 2018 priority-queues csharp

It’s vital that our priority queue returns items in the correct order, so we should write some unit tests to ensure that items are returned in the order desired. Fortunately, we can test this fairly easy using property tests.

Queue Enumeration

Saturday, December 15 2018 priority-queues csharp

Sometimes our users might want to do something odd - like iterate the content of a queue without going to the hassle of dequeuing items one at a time. Fortunately, it’s not hard for us to support this.

Smarter Queue Enumeration

Saturday, December 22 2018 priority-queues csharp

I have a concern about the amount of debris created on the heap by the enumeration technique we used last time. Let’s explore an alternative approach and see how that compares.

Queue Equality

Saturday, December 29 2018 priority-queues csharp

As is always important, we need to implement hashing and equality. But what does equality mean for a queue?

The Problem with Equality

Saturday, January 05 2019 priority-queues csharp

Did you spot the problem with the implementation of queue equality that we developed last time? As with the other bug we’ve encountered, this one stems from the comparison function we use.

Generating Hash Codes

Saturday, January 12 2019 priority-queues csharp

Generating a hash code for an immutable priority queue introduces an unusual challenge: How do we generate a consistent hash code regardless of the order items are added to the queue?

Extension Methods

Saturday, January 19 2019 priority-queues csharp

Sometimes we’ll have an existing sequence of items that we want to prioritize - let’s explore a couple of simple extension methods that can make this easier.

Converting a List to a Queue

Saturday, February 23 2019 priority-queues csharp

While chatting with a friend about this series, he made a suggestion about a significantly more effective way to implement the ToImmutablePriorityQueue extension method.