fn SkipList(

/// Pugh creates a SkipList which implementation details match the original paper from William Pugh.
pub fn Pugh(
    /// K is the key type of the SkipList.

    /// V is the stored value type of the SkipList.

    /// lessThan returns if `lhs` parameter key is less than `rhs` key.

        P: f32,
        max_level: usize,

        /// Determines average skip size for each level of SkipList. Equals `1/P`.
        skip_size: f32,
        /// Maximum number of levels in the SkipList.
        max_level: usize = undefined,
        /// Current maximum level of the SkipList.

        /// Starting Node pointer of the SkipList.

        const Node = struct {

        pub const Node = struct {

        fn init(allocator: std.mem.Allocator, max_level: usize, P: f32) !@This() {

        fn getMaxLevel(self: @This(), n: usize) usize {
            return @floatToInt(usize, std.math.log(f32, self.skip_size, @intToFloat(f32, n)));
        }
        pub fn init(
            /// Allocator to use when creating SkipList and its Node items.
            allocator: std.mem.Allocator,
            /// Number of items to skip with each level. Probabilistic!
            comptime skip_size: f32,
            /// Maximum number of items to be stored in the SkipList.
            /// This is not a hard limit, but SkipList performance will degrade when badly choosen.
            comptime n_max: usize,
        ) !@This() {
            if (skip_size <= 1) @compileError("`skip_size must be > 1`");

                .max_level = max_level,
                .P = P,

                .skip_size = skip_size,

            sl.head = Node.init(sl.allocator, 0, max_level) catch unreachable;

            sl.max_level = sl.getMaxLevel(n_max);
            // XXX: removing `catch` causing segfault
            sl.head = Node.init(sl.allocator, 0, sl.max_level) catch unreachable;

            // XXX: this version causing segfault
            // sl.head = try Node.init(sl.allocator, -1, max_level);

        fn deinit(self: @This()) void {

        pub fn deinit(self: @This()) void {

        fn search(self: @This(), search_key: K) ?*Node {

        pub fn search(self: @This(), search_key: K) ?*Node {

            while (self.rnd.float(f32) < self.P and level < self.max_level) level += 1;

            // while (self.rnd.float(f32) < (1.0 / self.skip_size) and
            //     level < self.max_level) level += 1;
            while (level < self.max_level) {
                const r = self.rnd.float(f32);
                // FIXME: strange r values...
                std.debug.print("r: {d}\n", .{r});
                if (r < 1 / self.skip_size) level += 1 else break;
            }
            std.debug.print("{d}\n", .{level});

        fn insert(self: *@This(), insert_key: K, insert_value: V) !void {

        pub fn insert(self: *@This(), insert_key: K, insert_value: V) !void {

        fn display(self: @This()) void {
            std.debug.print("SkipList structure:\n", .{});

        pub fn display(self: @This()) void {
            std.debug.print("SkipList structure - P:{d}, max_level: {d}\n", .{ 1 / self.skip_size, self.max_level });

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

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

test "SkipList" {
    const KeyType = usize;
    const SL = SkipList(KeyType, void, {}, comptime std.sort.asc(KeyType));
    var sl = try SL.init(std.testing.allocator, 3, 1 / std.math.e);
    defer sl.deinit();
    try sl.insert(3, {});
    try sl.insert(6, {});
    try sl.insert(7, {});
    try sl.insert(9, {});
    try sl.insert(0, {});
    try sl.insert(std.math.minInt(KeyType), {});
    try sl.insert(12, {});
    try sl.insert(12, {}); // does nothing
    try sl.insert(12, {}); // does nothing
    try sl.insert(19, {});
    try sl.insert(17, {});
    try sl.insert(26, {});
    try sl.insert(21, {});
    try sl.insert(25, {});
    try std.testing.expectEqual(@as(KeyType, 12), sl.search(12).?.key.?);
    try std.testing.expectEqual(@as(KeyType, 26), sl.search(26).?.key.?);
    try std.testing.expectEqual(@as(?*SL.Node, null), sl.search(13));
    try std.testing.expectEqual(true, try sl.remove(12));
    try std.testing.expectEqual(false, try sl.remove(12));
    _ = try sl.remove(std.math.minInt(KeyType));
    sl.display();
}