queue.zig

const std = @import("std");
const Allocator = std.mem.Allocator;

/// Queue as ring buffer. There is one `T` of margin.
pub fn Queue(T: type, size: usize) type {
    return struct {
        buf: [size]T,
        head: usize,
        tail: usize,

        const Self = @This();

        pub fn enqueue(self: *Self, item: T) error{OutOfCapacity}!void {
            self.buf[self.head] = item;
            const head_next = (self.head + 1) % size;
            if (head_next == self.tail) return error.OutOfCapacity;
            self.head = head_next;
        }

        pub fn dequeue(self: *Self) ?T {
            if (self.tail == self.head) return null;
            const item = self.buf[self.tail];
            self.tail = (self.tail + 1) % size;
            return item;
        }

        pub fn init() Self {
            return Self{
                .buf = std.mem.zeroes([size]T),
                .head = 0,
                .tail = 0,
            };
        }
    };
}

const expect = std.testing.expect;
const expectError = std.testing.expectError;
test "enqueue" {
    var queue: Queue(u8, 100) = .init();
    try queue.enqueue(5);
    try queue.enqueue(6);
    try queue.enqueue(7);
    try queue.enqueue(8);

    try expect(queue.buf[0] == 5);
    try expect(queue.buf[3] == 8);
}

test "dequeue" {
    var queue: Queue(u8, 100) = .init();
    try queue.enqueue(5);
    try queue.enqueue(6);
    try queue.enqueue(7);
    try queue.enqueue(8);

    try expect(queue.dequeue().? == 5);
    try expect(queue.dequeue().? == 6);
    try expect(queue.dequeue().? == 7);
    try expect(queue.dequeue().? == 8);
    try expect(queue.dequeue() == null);
}

test "enqueue errors with not enough space" {
    var queue: Queue(u8, 8) = .init();

    for (0..7) |_| {
        try queue.enqueue(0);
    }

    try expectError(error.OutOfCapacity, queue.enqueue(0));
}

test "queue wraps" {
    var queue: Queue(u8, 4) = .init();
    try queue.enqueue(1);
    try queue.enqueue(2);
    try queue.enqueue(3);
    try expectError(error.OutOfCapacity, queue.enqueue(4));
    try expect(queue.dequeue().? == 1);
    try expect(queue.dequeue().? == 2);
    try queue.enqueue(5);
    try expect(queue.dequeue().? == 3);
    try expect(queue.dequeue().? == 5);
}