83 lines
2.5 KiB
Zig
83 lines
2.5 KiB
Zig
const std = @import("std");
|
|
const PriorityQueue = std.PriorityQueue;
|
|
const Allocator = std.mem.Allocator;
|
|
const testing = std.testing;
|
|
|
|
/// wrapper for the task - stores task priority
|
|
/// along with the task name
|
|
const Task = struct {
|
|
const Self = @This();
|
|
|
|
priority: i32,
|
|
name: []const u8,
|
|
|
|
pub fn init(priority: i32, name: []const u8) Self {
|
|
return Self{
|
|
.priority = priority,
|
|
.name = name,
|
|
};
|
|
}
|
|
};
|
|
|
|
/// Simple wrapper for the comparator function.
|
|
/// Each comparator function has the following signature:
|
|
///
|
|
/// fn(T, T) bool
|
|
const Comparator = struct {
|
|
fn maxCompare(_: void, a: Task, b: Task) std.math.Order {
|
|
return std.math.order(a.priority, b.priority);
|
|
}
|
|
|
|
fn minCompare(_: void, a: Task, b: Task) std.math.Order {
|
|
return std.math.order(a.priority, b.priority);
|
|
}
|
|
};
|
|
|
|
test "priority queue (max heap)" {
|
|
var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
|
|
defer arena.deinit();
|
|
const allocator = arena.allocator();
|
|
var pq = PriorityQueue(Task, void, Comparator.maxCompare).init(allocator, {});
|
|
defer pq.deinit();
|
|
|
|
try pq.add(Task.init(3, "Clear drains"));
|
|
try pq.add(Task.init(4, "Feed Cat"));
|
|
try pq.add(Task.init(5, "Make tea"));
|
|
try pq.add(Task.init(1, "Solve RC tasks"));
|
|
try pq.add(Task.init(2, "Tax returns"));
|
|
try testing.expectEqual(pq.count(), 5);
|
|
|
|
std.debug.print("\n", .{});
|
|
|
|
// execute the tasks in decreasing order of priority
|
|
while (pq.count() != 0) {
|
|
const task = pq.remove();
|
|
std.debug.print("Executing: {s} (priority {d})\n", .{ task.name, task.priority });
|
|
}
|
|
std.debug.print("\n", .{});
|
|
}
|
|
|
|
test "priority queue (min heap)" {
|
|
var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
|
|
defer arena.deinit();
|
|
const allocator = arena.allocator();
|
|
var pq = PriorityQueue(Task, void, Comparator.minCompare).init(allocator, {});
|
|
defer pq.deinit();
|
|
|
|
try pq.add(Task.init(3, "Clear drains"));
|
|
try pq.add(Task.init(4, "Feed Cat"));
|
|
try pq.add(Task.init(5, "Make tea"));
|
|
try pq.add(Task.init(1, "Solve RC tasks"));
|
|
try pq.add(Task.init(2, "Tax returns"));
|
|
try testing.expectEqual(pq.count(), 5);
|
|
|
|
std.debug.print("\n", .{});
|
|
|
|
// execute the tasks in increasing order of priority
|
|
while (pq.count() != 0) {
|
|
const task = pq.remove();
|
|
std.debug.print("Executing: {s} (priority {d})\n", .{ task.name, task.priority });
|
|
}
|
|
std.debug.print("\n", .{});
|
|
}
|