How does a PriorityQueue context work?

Explain
1

I’m going through this example of using context in a priority queue, but dont understand any of the expectEqual test cases.

A regular lessThan function would make the queue behave like a min heap - in which 0 will have the highest priority and will be popped / removed first, followed by 2, 3, etc.

How does contextLessThan work ?

2

It lets you define custom priorities via the context slice, even at runtime.

2 Likes
3

Edit: another answer above was posted while I was typing this :smile: Hopefully it’ll be helpful if you feel you need more explanation.

PriorityQueue takes three arguments:

pub fn PriorityQueue(comptime T: type, comptime Context: type, comptime compareFn: fn (context: Context, a: T, b: T) Order) type

The first argument is the type of data stored in the queue, and the third argument is the function used to compare elements. The simplest initial design would be to just have these be the only arguments:

pub fn PriorityQueue(comptime T: type, comptime compareFn: fn (a: T, b: T) Order) type

so that you just fill in some function which compares two elements to determine their relative priority. The problem with this initial design is that it’s not very flexible: the compareFn only gets the two values to compare, and can’t use any other information (except global variables) in the decision.

For example, maybe you’re writing a task scheduling system, and you want to have parameters controlling how tasks are scheduled (e.g. “prioritize tasks with attribute A over those with attribute B”). You could store the parameters in global variables and use those from the compareFn, but then you’d be limited to a single queue in your application. You could also write different functions for every possible combination of parameters, but that would get tedious.

The solution is the second argument of the PriorityQueue function: the Context argument. It lets you add any other value to your queue as context (e.g. some parameters for how values should be ordered) which will be passed to compareFn as the first argument.

So, breaking down the example you’re looking at: contextLessThan takes a context of type []const u32 (the first argument) and compares two usize values. It compares the values by using them as indexes into context, so in other words, context is defining the priority order of the possible values in the queue (a value of 0 in the queue is mapped to a priority of 5, 1 is mapped to 3, etc.).

The queue type used in the test is just an alias for PriorityQueue with all the necessary types/functions filled in:

const CPQlt = PriorityQueue(usize, []const u32, contextLessThan);

Then, the specific context value is provided for the queue being used, defining the priority as outlined above:

const context = [_]u32{ 5, 3, 4, 2, 2, 8, 0 };

var queue = CPQlt.init(testing.allocator, context[0..]);
10 Likes
4

Thanks for going the distance Ian !

1 Like