const std = @import("std");

fn Queue(comptime T: type) type {
    const QueueNode = struct {
        const Self = @This();
        value: T,
        next: ?*Self,
    };

    return struct {
        const Self = @This();
        head: ?*QueueNode,
        tail: ?*QueueNode,
        alloc: std.mem.Allocator,

        fn new(alloc: std.mem.Allocator) Self {
            return .{
                .alloc = alloc,
                .head = null,
                .tail = null,
            };
        }

        fn enqueue(self: *Self, value: T) !void {
            var node = try self.alloc.create(QueueNode);
            node.value = value;
            node.next = null;

            if (self.head == null) {
                self.head = node;
                self.tail = node;
            }

            if (self.tail) |t_node| {
                var next = t_node;
                next.next = node;
            }
            self.tail = node;
        }

        fn dequeue(self: *Self) ?T {
            if (self.head) |t_head| {
                self.head = t_head.next;
                const value = t_head.value;
                self.alloc.destroy(t_head);
                return value;
            }
            return null;
        }

        fn print(self: *Self) void {
            var curr = self.head;
            std.log.info("queue", .{});

            while (curr) |node| {
                std.log.info("-> {d}", .{node.value});
                curr = node.next;
            }
        }
    };
}

const IntQueue = Queue(i32);

const Data = struct { val: usize };
const StructQueue = Queue(*Data);

pub fn main() !void {
    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();

    const allocator = arena.allocator();

    var q = IntQueue.new(allocator);
    try q.enqueue(32);
    try q.enqueue(45);
    try q.enqueue(33);
    q.print();
    std.log.info("-----", .{});

    const x = q.dequeue();
    _ = x;
    q.print();
}

test "filled queue" {
    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();

    const allocator = arena.allocator();

    var q = IntQueue.new(allocator);
    try q.enqueue(20);
    try q.enqueue(30);
    if (q.dequeue()) |value| {
        std.testing.expect(value == 20) catch {
            std.debug.print("filled queue: got error: 20=={}", .{value});
        };
    }
}

test "struct* queue" {
    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();

    const allocator = arena.allocator();

    var q = StructQueue.new(allocator);
    for (0..5) |idx| {
        var d = Data{ .val = idx };
        try q.enqueue(&d);
    }
    if (q.dequeue()) |value| {
        std.testing.expect(value.*.val == 0) catch {
            std.debug.print("struct* queue: got error: 0=={}", .{value.*.val});
        };
    }
}

test "empty queue" {
    const arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();

    const allocator = arena.allocator();

    var q = IntQueue.new(allocator);
    const x = q.dequeue();
    try std.testing.expect(x == null);
}