const std = @import("std");
const SkipList = @import("lib.zig");
const MY_SIZE = 1000;
pub fn SkipQueue(comptime T: anytype) type {
    if (!@hasField(T, "key")) @compileError("must contain 'key' member");
    if (!@hasField(T, "value")) @compileError("must contain 'value' member");
    const K = blk: {
        switch (@typeInfo(T)) {
            .Struct => |str_info| {
                for (str_info.fields) |field| {
                    if (std.mem.eql(u8, field.name, "key")) {
                        break :blk field.field_type;
                    }
                }
            },
            else => unreachable,
        }
    };
    const V = blk: {
        switch (@typeInfo(T)) {
            .Struct => |str_info| {
                for (str_info.fields) |field| {
                    if (std.mem.eql(u8, field.name, "value")) {
                        break :blk field.field_type;
                    }
                }
            },
            else => unreachable,
        }
    };
    return struct {
        skiplist: SkipList.Lazy(K, V, {}, std.sort.asc(K)),
        pub fn init(allocator: std.mem.Allocator) !@This() {
            var sq: @This() = undefined;
            sq.skiplist = try SkipList.Lazy(K, V, {}, comptime std.sort.asc(K))
                .init(allocator, SkipList.DEFAULT_SKIP_SIZE, MY_SIZE);
            return sq;
        }
        pub fn deinit(self: @This()) void {
            self.skiplist.deinit();
        }
        pub fn add(self: *@This(), item: T) !void {
            _ = try self.skiplist.insert(item.key, item.value);
        }
        pub fn remove(self: *@This()) !?T {
            var ret: ?T = null;
            var curr = self.skiplist.head;
            while (curr.nexts[0]) |item| : (curr = curr.nexts[0].?) {
                const held = item.lock.acquire();
                defer held.release();
                // already marked for deletion
                if (item.marked) continue;
                item.marked = true;
                ret = .{ .key = item.key.?, .value = item.value };
                break;
            }
            if (ret != null) {
                _ = try self.skiplist.remove(ret.?.key);
            }
            return ret;
        }
    };
}

const SkipList = @import("lib.zig");

const SkipList = struct {
    pub usingnamespace @import("pugh.zig");
    pub usingnamespace @import("lazy.zig");
};

    try benchSkipQueue();

}
fn benchSkipQueue() !void {
    const QueueItem = struct {
        key: usize,
        value: usize,
    };
    var sq = try SkipList.SkipQueue(QueueItem).init(std.heap.page_allocator);
    defer sq.deinit();
    try sq.add(.{ .key = 1, .value = 1 });
    try sq.add(.{ .key = 2, .value = 2 });
    try sq.add(.{ .key = 3, .value = 3 });
    try sq.add(.{ .key = 0, .value = 4 });
    std.debug.assert((try sq.remove()).?.value == 4);
    std.debug.assert((try sq.remove()).?.value == 1);
    std.debug.assert((try sq.remove()).?.value == 2);
    std.debug.assert((try sq.remove()).?.value == 3);
    std.debug.assert((try sq.remove()) == null);

pub const DEFAULT_SKIP_SIZE = 4;
pub usingnamespace @import("pugh.zig");
pub usingnamespace @import("lazy.zig");
pub usingnamespace @import("skipqueue.zig");

        fn remove(self: @This(), remove_key: K) !bool {

        pub fn remove(self: @This(), remove_key: K) !bool {