id: ifbd0mau6agl312dgj4tfy4mtiuvvkq13rubvaptaxghlgn2
name: btreemap
main: src/btreemap.zig
license: MIT
description: BTreeMap implementation in Zig
dependencies:

const std = @import("std");
const meta = @import("meta.zig");
const Allocator = std.mem.Allocator;
const assert = std.debug.assert;
pub fn Node(comptime K: type, comptime V: type, comptime B: u32) type {
    return struct {
        const Self = @This();
        keys: [2 * B - 1]K,
        values: [2 * B - 1]V,
        len: usize,
        edges: [2 * B]?*Self,
        // Return Type for Node's search method.
        pub const SearchResult = struct {
            found: bool,
            index: usize,
        };
        pub const KV = struct {
            key: K,
            value: V,
        };
        const KVE = struct {
            key: K,
            value: V,
            edge: ?*Self,
        };
        const Entry = struct {
            key_ptr: *K,
            value_ptr: *V,
        };
        pub fn createEmpty(allocator: Allocator) !*Self {
            var out = try allocator.create(Self);
            out.* = Self{
                .keys = [_]K{undefined} ** (2 * B - 1),
                .values = [_]V{undefined} ** (2 * B - 1),
                .len = 0,
                .edges = [_]?*Self{null} ** (2 * B),
            };
            return out;
        }
        pub fn createFromKV(allocator: Allocator, key: K, value: V) !*Self {
            var out = try Self.createEmpty(allocator);
            out.keys[0] = key;
            out.values[0] = value;
            out.len = 1;
            return out;
        }
        /// Searches the node for a key. Returns a struct with two fields:
        /// 1) .found: bool -> Wether the key was found or not.
        /// 2) .index: usize -> The index of the found key or, if no key was found,
        /// the index of the edge where the search path continues.
        pub fn search(self: Self, key: K) SearchResult {
            var i: usize = 0;
            while (i < self.len) : (i += 1) {
                if (meta.eq(key, self.keys[i])) {
                    return SearchResult{
                        .found = true,
                        .index = i,
                    };
                } else if (meta.lt(key, self.keys[i])) {
                    return .{
                        .found = false,
                        .index = i,
                    };
                }
            }
            return .{
                .found = false,
                .index = self.len,
            };
        }
        /// Insert KVE if node has room. Return null in this case.
        /// If node is full, take out the median KV and split off the the right part
        /// into a new node and return this new node together with the median KV.
        pub fn insertOrSplit(
            self: *Self,
            allocator: Allocator,
            index: usize,
            key: K,
            value: V,
            edge: ?*Self,
        ) !?KVE {
            if (self.isFull()) {
                // Node is full. Split Node.
                var split_result = try self.split(allocator);
                if (index < B) {
                    // Insert KVE in original node.
                    self.insert(index, key, value, edge);
                } else {
                    // Insert KVE in the split off node.
                    split_result.edge.?.insert(index - B, key, value, edge);
                }
                return split_result;
            } else {
                // No split necessary.
                self.insert(index, key, value, edge);
                return null;
            }
        }
        /// Swap value at index.
        pub fn swapValue(self: *Self, index: usize, value: V) V {
            const out = self.values[index];
            self.values[index] = value;
            return out;
        }
        /// Swap KV at index.
        pub fn swapKV(self: *Self, index: usize, key: K, value: V) KV {
            const out = KV{
                .key = self.keys[index],
                .value = self.values[index],
            };
            self.values[index] = value;
            self.keys[index] = key;
            return out;
        }
        /// Remove and return KVE at index.
        /// The removed edge is right of the KV.
        pub fn remove(self: *Self, index: usize) KVE {
            const out = KVE{
                .key = self.keys[index],
                .value = self.values[index],
                .edge = self.edges[index + 1],
            };
            std.mem.copy(
                K,
                self.keys[index..],
                self.keys[index + 1 .. self.len],
            );
            std.mem.copy(
                V,
                self.values[index..],
                self.values[index + 1 .. self.len],
            );
            self.keys[self.len - 1] = undefined;
            self.values[self.len - 1] = undefined;
            if (!self.isLeaf()) {
                std.mem.copy(
                    ?*Self,
                    self.edges[index + 1 ..],
                    self.edges[index + 2 .. self.len + 1],
                );
                self.edges[self.len] = null;
            }
            self.len -= 1;
            return out;
        }
        /// Remove and return most right KVE.
        fn removeFromEnd(self: *Self) KVE {
            return self.remove(self.len - 1);
        }
        /// Remove and return most left KV and Edge.
        /// Contrary to the methods above, this removes the edge left of the KV.
        fn removeFromBeginning(self: *Self) KVE {
            const out = KVE{
                .key = self.keys[0],
                .value = self.values[0],
                .edge = self.edges[0],
            };
            std.mem.copy(
                K,
                self.keys[0..],
                self.keys[1..self.len],
            );
            std.mem.copy(
                V,
                self.values[0..],
                self.values[1..self.len],
            );
            self.keys[self.len - 1] = undefined;
            self.values[self.len - 1] = undefined;
            if (!self.isLeaf()) {
                std.mem.copy(
                    ?*Self,
                    self.edges[0..],
                    self.edges[1 .. self.len + 1],
                );
                self.edges[self.len] = null;
            }
            self.len -= 1;
            return out;
        }
        // Shifts the arrays right after index and inserts new KVE.
        // The new edge is right of the new KV.
        // Does not check if insertion is at the correct position/node has space.
        fn insert(self: *Self, index: usize, key: K, value: V, edge: ?*Self) void {
            std.mem.copyBackwards(
                K,
                self.keys[index + 1 .. self.len + 1],
                self.keys[index..self.len],
            );
            self.keys[index] = key;
            std.mem.copyBackwards(
                V,
                self.values[index + 1 .. self.len + 1],
                self.values[index..self.len],
            );
            self.values[index] = value;
            if (!self.isLeaf()) {
                std.mem.copyBackwards(
                    ?*Self,
                    self.edges[index + 2 .. self.len + 2],
                    self.edges[index + 1 .. self.len + 1],
                );
                self.edges[index + 1] = edge;
            }
            self.len += 1;
        }
        /// Does not check if insertion is at the correct position/node has space.
        fn insertAtEnd(self: *Self, key: K, value: V, edge: ?*Self) void {
            self.keys[self.len] = key;
            self.values[self.len] = value;
            self.edges[self.len + 1] = edge;
            self.len += 1;
        }
        /// This is different from the other inserts methods because it inserts the edge
        /// left of the KV. I.e. it also puts the edge in the first position.
        /// Does not check if insertion is at the correct position/node has space.
        fn insertAtBeginning(self: *Self, key: K, value: V, edge: ?*Self) void {
            std.mem.copyBackwards(
                K,
                self.keys[1 .. self.len + 1],
                self.keys[0..self.len],
            );
            self.keys[0] = key;
            std.mem.copyBackwards(
                V,
                self.values[1 .. self.len + 1],
                self.values[0..self.len],
            );
            self.values[0] = value;
            if (!self.isLeaf()) {
                std.mem.copyBackwards(
                    ?*Self,
                    self.edges[1 .. self.len + 2],
                    self.edges[0 .. self.len + 1],
                );
                self.edges[0] = edge;
            }
            self.len += 1;
        }
        /// The borrowing methods happen from the perspective of the parent.
        /// This means, the parent distributes from one edge to another.
        /// The edge at `index` is underflowed and needs compensation.
        /// Try to borrow from the edge at one side of `index` and rotate.
        /// Returns true on success, else false.
        pub fn borrowFromRight(self: *Self, index: usize) bool {
            // No edge right of index.
            if (index == self.len) return false;
            var giver = self.edges[index + 1].?;
            if (giver.len > B - 1) {
                // Right edge can spare one.
                var taker = self.edges[index].?;
                const from_giver: KVE = giver.removeFromBeginning();
                taker.insertAtEnd(self.keys[index], self.values[index], from_giver.edge);
                _ = self.swapKV(index, from_giver.key, from_giver.value);
                return true;
            } else return false;
        }
        /// The borrowing methods happen from the perspective of the parent.
        /// This means, the parent distributes from one edge to another.
        /// The edge at `index` is underflowed and needs compensation.
        /// Try to borrow from the edge at one side of `index` and rotate.
        /// Returns true on success, else false.
        pub fn borrowFromLeft(self: *Self, index: usize) bool {
            // No edge left of index.
            if (index == 0) return false;
            var giver = self.edges[index - 1].?;
            if (giver.len > B - 1) {
                // Right edge can spare one.
                var taker = self.edges[index].?;
                const from_giver: KVE = giver.removeFromEnd();
                taker.insertAtBeginning(self.keys[index - 1], self.values[index - 1], from_giver.edge);
                _ = self.swapKV(index - 1, from_giver.key, from_giver.value);
                return true;
            } else return false;
        }
        /// Merging happend from the perspective of the parent.
        /// It merges two edges together and puts the middle KV of the parent in between.
        /// The right node is merged into the left and the right is destroyed afterwards.
        pub fn mergeEdges(self: *Self, allocator: Allocator, left_edge_index: usize) void {
            var left = self.edges[left_edge_index].?;
            const removed = self.remove(left_edge_index);
            left.insertAtEnd(removed.key, removed.value, null);
            std.mem.copyBackwards(
                K,
                left.keys[left.len..],
                removed.edge.?.keys[0..removed.edge.?.len],
            );
            std.mem.copyBackwards(
                V,
                left.values[left.len..],
                removed.edge.?.values[0..removed.edge.?.len],
            );
            std.mem.copyBackwards(
                ?*Self,
                left.edges[left.len..],
                removed.edge.?.edges[0 .. removed.edge.?.len + 1],
            );
            left.len += removed.edge.?.len;
            allocator.destroy(removed.edge.?);
        }
        /// Split operation for a full node.
        /// Returns a struct with three fields:
        /// 1) and 2) -> Key and value of the median.
        /// 3) -> The right part of the median as a new node (pointer).
        /// These parts are erased from the original node.
        fn split(self: *Self, allocator: Allocator) !KVE {
            const median: usize = B - 1;
            var new_key = self.keys[median];
            var new_value = self.values[median];
            var new_node = try Self.createFromSlices(
                allocator,
                self.keys[median + 1 .. self.len],
                self.values[median + 1 .. self.len],
                self.edges[median + 1 .. self.len + 1],
            );
            // shrink original node
            std.mem.set(K, self.keys[median..], undefined);
            std.mem.set(V, self.values[median..], undefined);
            std.mem.set(?*Self, self.edges[median + 1 ..], null);
            self.len = median;
            return KVE{
                .key = new_key,
                .value = new_value,
                .edge = new_node,
            };
        }
        fn createFromSlices(allocator: Allocator, keys: []K, values: []V, edges: []?*Self) !*Self {
            var out = try Self.createEmpty(allocator);
            std.mem.copyBackwards(K, out.keys[0..], keys);
            std.mem.copyBackwards(V, out.values[0..], values);
            std.mem.copyBackwards(?*Self, out.edges[0..], edges);
            out.len = keys.len;
            return out;
        }
        pub fn isLeaf(self: Self) bool {
            return self.edges[0] == null;
        }
        pub fn isFull(self: Self) bool {
            return self.len == 2 * B - 1;
        }
        pub fn isLacking(self: Self) bool {
            return self.len < B - 1;
        }
        /// This is intended for testing and debugging.
        fn assertValidityExceptLength(self: *const Self) void {
            // Keys increasing
            for (self.keys[0 .. self.len - 1]) |_, i| {
                assert(meta.lt(self.keys[i], self.keys[i + 1]));
            }
            // Number of edges
            var count: u32 = 0;
            var encountered_null = false;
            for (self.edges) |edge| {
                if (edge) |_| {
                    assert(encountered_null == false);
                    count += 1;
                } else {
                    encountered_null = true;
                }
            }
            assert(count == self.len + 1 or count == 0);
            // If node is leaf we are done here.
            if (self.isLeaf()) return;
            // Edges left smaller and right larger
            for (self.keys[0..self.len]) |key, i| {
                const left_edge = self.edges[i].?;
                const imm_left_key = left_edge.keys[left_edge.len - 1];
                assert(meta.gt(key, imm_left_key));
                const right_edge = self.edges[i + 1].?;
                const imm_right_key = right_edge.keys[0];
                assert(meta.lt(key, imm_right_key));
            }
        }
        pub fn assertValidity(self: *const Self) void {
            // Length
            assert(self.len <= 2 * B - 1);
            assert(self.len >= B - 1);
            self.assertValidityExceptLength();
        }
        pub fn assertValidityRoot(self: *const Self) void {
            // Length
            assert(self.len <= 2 * B - 1);
            self.assertValidityExceptLength();
        }
    };
}

const std = @import("std");
const assert = std.debug.assert;
const expect = std.testing.expect;
/// Similiar to std.meta.eql but pointers are followed.
/// Also Unions and ErrorUnions are excluded.
pub fn eq(a: anytype, b: @TypeOf(a)) bool {
    const T = @TypeOf(a);
    switch (@typeInfo(T)) {
        .Int, .ComptimeInt, .Float, .ComptimeFloat => {
            return a == b;
        },
        .Struct => {
            if (!@hasDecl(T, "eq")) {
                @compileError("An 'eq' comparison method has to implemented for Type '" ++ @typeName(T) ++ "'");
            }
            return T.eq(a, b);
        },
        .Array => {
            for (a) |_, i|
                if (!eq(a[i], b[i])) return false;
            return true;
        },
        .Vector => |info| {
            var i: usize = 0;
            while (i < info.len) : (i += 1) {
                if (!eq(a[i], b[i])) return false;
            }
            return true;
        },
        .Pointer => |info| {
            switch (info.size) {
                .One => return eq(a.*, b.*),
                .Slice => {
                    if (a.len != b.len) return false;
                    for (a) |_, i|
                        if (!eq(a[i], b[i])) return false;
                    return true;
                },
                .Many => {
                    if (info.sentinel) {
                        if (std.mem.len(a) != std.mem.len(b)) return false;
                        var i: usize = 0;
                        while (i < std.mem.len(a)) : (i += 1)
                            if (!eq(a[i], b[i])) return false;
                        return true;
                    }
                    @compileError("Cannot compare many-item pointer to unknown number of items without sentinel value");
                },
                .C => @compileError("Cannot compare C pointers"),
            }
        },
        .Optional => {
            if (a == null and b == null) return true;
            if (a == null or b == null) return false;
            return eq(a.?, b.?);
        },
        else => {
            @compileError("Cannot compare type '" ++ @typeName(T) ++ "'");
        },
    }
}
pub fn lt(a: anytype, b: @TypeOf(a)) bool {
    const T = @TypeOf(a);
    switch (@typeInfo(T)) {
        .Int, .ComptimeInt, .Float, .ComptimeFloat => {
            return a < b;
        },
        .Struct => {
            if (!@hasDecl(T, "lt")) {
                @compileError("A 'lt' comparison method has to implemented for Type '" ++ @typeName(T) ++ "'");
            }
            return T.lt(a, b);
        },
        .Array => {
            for (a) |_, i| {
                if (lt(a[i], b[i])) {
                    return true;
                } else if (eq(a[i], b[i])) {
                    continue;
                } else {
                    return false;
                }
            }
            return false;
        },
        .Vector => |info| {
            var i: usize = 0;
            while (i < info.len) : (i += 1) {
                if (lt(a[i], b[i])) {
                    return true;
                } else if (eq(a[i], b[i])) {
                    continue;
                } else {
                    return false;
                }
            }
            return false;
        },
        .Pointer => |info| {
            switch (info.size) {
                .One => return lt(a.*, b.*),
                .Slice => {
                    const n = std.math.min(a.len, b.len);
                    for (a[0..n]) |_, i| {
                        if (lt(a[i], b[i])) {
                            return true;
                        } else if (eq(a[i], b[i])) {
                            continue;
                        } else {
                            return false;
                        }
                    }
                    return lt(a.len, b.len);
                },
                .Many => {
                    if (info.sentinel) {
                        const n = std.math.min(std.mem.len(a), std.mem.len(b));
                        var i: usize = 0;
                        while (i < n) : (i += 1) {
                            if (lt(a[i], b[i])) {
                                return true;
                            } else if (eq(a[i], b[i])) {
                                continue;
                            } else {
                                return false;
                            }
                        }
                        return lt(std.mem.len(a), std.mem.len(b));
                    }
                    @compileError("Cannot compare many-item pointer to unknown number of items without sentinel value");
                },
                .C => @compileError("Cannot compare C pointers"),
            }
        },
        .Optional => {
            if (a == null or b == null) return false;
            return lt(a.?, b.?);
        },
        else => {
            @compileError("Cannot compare type '" ++ @typeName(T) ++ "'");
        },
    }
}
pub fn le(a: anytype, b: @TypeOf(a)) bool {
    return lt(a, b) or eq(a, b);
}
pub fn gt(a: anytype, b: @TypeOf(a)) bool {
    return !lt(a, b) and !eq(a, b);
}
pub fn ge(a: anytype, b: @TypeOf(a)) bool {
    return !lt(a, b);
}
test "numerals" {
    try expect(eq(1.0, 1.0));
    try expect(!eq(1.0, 1.1));
    try expect(lt(1.0, 2.0));
    try expect(!lt(1, 1));
    try expect(!lt(2, 1));
}
test "Arrays" {
    try expect(eq("abc", "abc"));
    try expect(!eq("abc", "abb"));
    try expect(lt("ab", "ba"));
    try expect(lt("aaa", "aab"));
    try expect(!lt("aaa", "aaa"));
    try expect(!lt("aab", "aaa"));
}
test "structs" {
    const Car = struct {
        power: i32,
        pub fn lt(a: @This(), b: @This()) bool {
            return a.power < b.power;
        }
        pub fn eq(a: @This(), b: @This()) bool {
            return a.power == b.power;
        }
    };
    var car1 = Car{ .power = 100 };
    var car2 = Car{ .power = 200 };
    try expect(eq(car1, car1));
    try expect(!eq(car1, car2));
    try expect(lt(car1, car2));
    try expect(!lt(car1, car1));
}
test "Slices" {
    var o: usize = 0;
    assert(@TypeOf("abc"[o..]) == [:0]const u8);
    try expect(eq("abc"[o..], "abc"));
    try expect(!eq("abc"[o..], "abb"));
    try expect(lt("aba"[o..], "ba"));
    try expect(lt("aaa"[o..], "bb"));
    try expect(!lt("aba"[o..], "aa"));
    try expect(!lt("aaa"[o..], "aaa"));
    try expect(lt("aaa"[o..], "aaaa"));
    try expect(!lt("aaa"[o..], "aa"));
    try expect(lt("aab"[o..], "aaba"));
}
test "Optionals" {
    var x: ?i32 = 1;
    var y: ?i32 = 2;
    try expect(lt(x, y));
}
test "sentinel terminated pointers" {
    // TODO
}
test "Vectors" {
    // TODO
}

const std = @import("std");
const Allocator = std.mem.Allocator;
const assert = std.debug.assert;
const getNodeType = @import("node.zig").Node;
pub fn BTreeMap(comptime K: type, comptime V: type) type {
    return struct {
        const Self = @This();
        root: ?*Node,
        allocator: Allocator,
        const B = 6;
        const Node = getNodeType(K, V, B);
        const KV = Node.KV;
        const SearchResult = Node.SearchResult;
        const StackItem = struct {
            node: *Node,
            index: usize,
        };
        pub fn init(allocator: Allocator) Self {
            return Self{
                .allocator = allocator,
                .root = null,
            };
        }
        pub fn deinit(self: Self) !void {
            var stack = std.ArrayList(*Node).init(self.allocator);
            defer stack.deinit();
            if (self.root) |root| {
                try stack.append(root);
            } else return;
            while (stack.popOrNull()) |node| {
                if (!node.isLeaf()) {
                    var i: usize = 0;
                    while (i < node.len + 1) : (i += 1) {
                        try stack.append(node.edges[i].?);
                    }
                }
                self.allocator.destroy(node);
            }
        }
        pub fn isEmpty(self: *const Self) bool {
            if (self.root == null) return true;
            return self.root.?.len == 0;
        }
        /// Get value from a certain key.
        pub fn get(self: Self, key: K) ?V {
            var current = self.root;
            while (current) |node| {
                const result = node.search(key);
                if (result.found) {
                    return node.values[result.index];
                } else {
                    current = node.edges[result.index];
                }
            }
            return null;
        }
        /// Inserts key-value pair into the map. Swaps the values if already present
        /// and returns the old.
        /// This function has two stages. In the first stage, the tree
        /// is traversed to find the path to the relevant leaf node.
        /// This path is saved in a stack, containing the nodes itself
        /// and the indices of the children where the path continues.
        /// In the second phase, we try to insert and, if the node is full,
        /// split the node and hand the result of the split down the stack.
        /// Repeat this until insertion is successful or the root itself is split.
        pub fn fetchPut(self: *Self, key: K, value: V) !?V {
            // TODO: return KV like in std.HashMap
            if (self.root == null) {
                self.root = try Node.createFromKV(self.allocator, key, value);
                return null;
            }
            var stack = std.ArrayList(StackItem).init(self.allocator);
            defer stack.deinit();
            // Traverse tree until we find the key or hit bottom.
            // If we we find the key, swap new with old value and return the old.
            // Build a stack to remember the path
            var current = self.root;
            var search_result: SearchResult = undefined;
            while (current) |node| {
                search_result = node.search(key);
                if (search_result.found) {
                    return node.swapValue(search_result.index, value);
                }
                // Not found, go deeper.
                current = node.edges[search_result.index];
                try stack.append(.{
                    .node = node,
                    .index = search_result.index,
                });
            }
            // Pop top of stack (bottom of tree/leaf node).
            var stack_next: ?StackItem = stack.pop();
            // Try to insert to leaf node.
            var split_result = try stack_next.?.node.insertOrSplit(
                self.allocator,
                stack_next.?.index,
                key,
                value,
                null,
            );
            // No split was necessary -> insertion was successful. We're Done.
            if (split_result == null) {
                return null;
            }
            // Split was necessary -> move down on stack.
            // The current node in stack was incorporated in the tree and the SplitResult.
            stack_next = stack.popOrNull();
            // Repeat the process of splitting and inserting until insertion is
            // successful or we hit the root node, in which case the root node is split.
            while (split_result) |split_result_unwrapped| {
                if (stack_next) |stack_next_unwrapped| {
                    // Try to insert the in current stack item.
                    split_result = try stack_next_unwrapped.node.insertOrSplit(
                        self.allocator,
                        stack_next_unwrapped.index,
                        split_result_unwrapped.key,
                        split_result_unwrapped.value,
                        split_result_unwrapped.edge,
                    );
                    stack_next = stack.popOrNull();
                } else {
                    // We reached the root.
                    var new_root = try Node.createFromKV(
                        self.allocator,
                        split_result_unwrapped.key,
                        split_result_unwrapped.value,
                    );
                    new_root.edges[0] = self.root;
                    new_root.edges[1] = split_result_unwrapped.edge;
                    self.root = new_root;
                    return null;
                }
            } else return null;
        }
        /// Removes and returns a key-value-pair. Returns null if not found.
        pub fn fetchRemove(self: *Self, key: K) !?KV {
            var stack = std.ArrayList(StackItem).init(self.allocator);
            defer stack.deinit();
            // Traverse tree until we find the key or hit bottom.
            // Build a stack to remember the path
            var current = self.root;
            var search_result: SearchResult = undefined;
            var found_key_ptr: ?*K = null;
            var found_value_ptr: ?*V = null;
            while (current) |node| {
                search_result = node.search(key);
                if (search_result.found) {
                    // Found! Remember pointers to key and value to swap later.
                    found_key_ptr = &node.keys[search_result.index];
                    found_value_ptr = &node.values[search_result.index];
                    // If not reached leaf, increment index in order to find the
                    // found key's inorder successor when we continue down the tree.
                    if (!node.isLeaf()) search_result.index += 1;
                }
                try stack.append(.{
                    .node = node,
                    .index = search_result.index,
                });
                current = node.edges[search_result.index];
                if (search_result.found) break;
            } else {
                // Key not found.
                return null;
            }
            // Continue building the stack to the inorder successor of the found key.
            while (current) |node| {
                try stack.append(.{
                    .node = node,
                    .index = 0,
                });
                current = node.edges[0];
            }
            // Reached leaf node. Stack is complete.
            // Leaf node is on top of stack now.
            var current_stack = stack.pop();
            // Swap the KV for deletion with its inorder successor.
            var out: KV = .{ .key = found_key_ptr.?.*, .value = found_value_ptr.?.* };
            found_key_ptr.?.* = current_stack.node.keys[current_stack.index];
            found_value_ptr.?.* = current_stack.node.values[current_stack.index];
            // Now ew can remove the key-value pair in the leaf. This can result in an underflow,
            // which is handled below.
            _ = current_stack.node.remove(current_stack.index);
            // If our leaf is also the root, it cannot underflow.
            if (current_stack.node == self.root) return out;
            // Fix underflow and move down the stack until underflow is fixed.
            while (current_stack.node.isLacking()) {
                // We have an underflow in the current stack position. This is fixed
                // from the parent's erspective, so move down the stack.
                current_stack = stack.pop();
                // Try to borrow, first from right, then from left.
                if (current_stack.node.borrowFromRight(current_stack.index)) return out;
                if (current_stack.node.borrowFromLeft(current_stack.index)) return out;
                // Borrow was not possible, merge nodes.
                if (current_stack.index == current_stack.node.len) {
                    // the underflowed edge is the most right. Merge with left.
                    current_stack.node.mergeEdges(self.allocator, current_stack.index - 1);
                } else {
                    // Merge with right.
                    current_stack.node.mergeEdges(self.allocator, current_stack.index);
                }
                if (current_stack.node == self.root) {
                    // We reached the root.
                    if (self.root.?.len == 0) {
                        // If root is empty, replace with merged node.
                        const new_root = current_stack.node.edges[0].?;
                        self.allocator.destroy(self.root.?);
                        self.root.? = new_root;
                    }
                    break;
                }
            }
            return out;
        }
        pub fn iteratorInit(self: *const Self) !Iterator {
            var new_stack = std.ArrayList(StackItem).init(self.allocator);
            if (self.root) |root| {
                try new_stack.append(.{
                    .node = root,
                    .index = 0,
                });
            }
            return Iterator{
                .stack = new_stack,
                .backwards = false,
            };
        }
        const Iterator = struct {
            stack: std.ArrayList(StackItem),
            backwards: bool,
            pub fn deinit(it: Iterator) void {
                it.stack.deinit();
            }
            pub fn next(it: *Iterator) !?KV {
                while (it.topStackItem()) |item| {
                    if (!item.node.isLeaf() and !it.backwards) {
                        // Child exists at index or going forward, go deeper.
                        var child = item.node.edges[item.index].?;
                        try it.stack.append(StackItem{
                            .node = child,
                            .index = 0,
                        });
                    } else {
                        // No Child or coming backwards.
                        if (item.index < item.node.len) {
                            // Node is not yet exhausted.
                            // Return KV from Node and increment the node's index.
                            var out = KV{
                                .key = item.node.keys[item.index],
                                .value = item.node.values[item.index],
                            };
                            item.index += 1;
                            it.backwards = false;
                            return out;
                        } else {
                            // Node is exhausted.
                            // Set `backwards` so that this node is not entered again
                            // in the next iteration.
                            _ = it.stack.popOrNull();
                            it.backwards = true;
                        }
                    }
                } else return null;
            }
            fn topStackItem(it: *Iterator) ?*StackItem {
                if (it.stack.items.len == 0) {
                    return null;
                } else {
                    return &it.stack.items[it.stack.items.len - 1];
                }
            }
        };
        /// Intended for testing and debugging. Traverses whole tree and
        /// asserts the validity of every node. Also if every leaf has the
        /// same height. -> BTree itself is valid.
        fn assertValidity(self: *const Self) !void {
            if (self.root == null) return;
            var depth: ?usize = null;
            var backwards = false;
            var stack = std.ArrayList(StackItem).init(self.allocator);
            defer stack.deinit();
            try stack.append(StackItem{
                .node = self.root.?,
                .index = 0,
            });
            self.root.?.assertValidityRoot();
            var item: *StackItem = undefined;
            while (stack.items.len >= 1) {
                item = &stack.items[stack.items.len - 1];
                if (!item.node.isLeaf() and !backwards) {
                    // Go deeper.
                    var child = item.node.edges[item.index].?;
                    child.assertValidity();
                    try stack.append(StackItem{
                        .node = child,
                        .index = 0,
                    });
                } else {
                    // Reached leaf or moving backwards
                    // Assert tree depth
                    if (item.node.isLeaf()) {
                        if (depth == null) {
                            depth = stack.items.len;
                        } else {
                            assert(stack.items.len == depth.?);
                        }
                    }
                    if (item.index < item.node.len) {
                        // Node is not yet exhausted.
                        item.index += 1;
                        backwards = false;
                    } else {
                        // Node is exhausted.
                        // Set `backwards` so that this node is not entered again
                        // in the next iteration.
                        _ = stack.popOrNull();
                        backwards = true;
                    }
                }
            }
        }
    };
}
const testing = std.testing;
test {
    const n = 10000;
    var keys = std.ArrayList(i16).init(testing.allocator);
    defer keys.deinit();
    var prng = std.rand.DefaultPrng.init(0);
    const random = prng.random();
    var i: i16 = 0;
    while (i < n) : (i += 1) {
        keys.append(random.int(i16)) catch unreachable;
    }
    var tree = BTreeMap(i32, i32).init(testing.allocator);
    defer tree.deinit() catch unreachable;
    for (keys.items) |j| {
        _ = try tree.fetchPut(j, j);
    }
    _ = try tree.fetchPut(11111, 99999);
    _ = try tree.fetchPut(22222, 88888);
    //var it = try tree.iteratorInit();
    //defer it.deinit();
    //while (it.next() catch unreachable) |item| std.debug.print("{any}\n", .{item});
    try testing.expect((try tree.fetchPut(11111, 0)).? == 99999);
    try testing.expectEqual(
        (try tree.fetchRemove(22222)).?,
        @TypeOf(tree).Node.KV{
            .key = 22222,
            .value = 88888,
        },
    );
    try tree.assertValidity();
    random.shuffle(i16, keys.items);
    for (keys.items) |j| {
        const out = try tree.fetchRemove(j);
        if (out) |u| {
            try testing.expect(u.key == j);
            try testing.expect(u.value == j);
        }
    }
    _ = try tree.fetchRemove(11111);
    try testing.expect(tree.isEmpty());
}
test "structs as keys" {
    const Car = struct {
        power: i32,
        pub fn lt(a: @This(), b: @This()) bool {
            return a.power < b.power;
        }
        pub fn eq(a: @This(), b: @This()) bool {
            return a.power == b.power;
        }
    };
    const n = 50;
    var cars = std.ArrayList(Car).init(testing.allocator);
    defer cars.deinit();
    var prng = std.rand.DefaultPrng.init(0);
    const random = prng.random();
    var i: u32 = 0;
    while (i < n) : (i += 1) {
        var power: i32 = @intCast(i32, random.int(u8)) + 100;
        cars.append(Car{ .power = power }) catch unreachable;
    }
    var tree = BTreeMap(Car, bool).init(testing.allocator);
    defer tree.deinit() catch unreachable;
    for (cars.items) |j| {
        _ = try tree.fetchPut(j, true);
    }
    for (cars.items) |j| {
        _ = try tree.fetchRemove(j);
    }
}

const std = @import("std");
pub fn build(b: *std.build.Builder) void {
    // Standard release options allow the person running `zig build` to select
    // between Debug, ReleaseSafe, ReleaseFast, and ReleaseSmall.
    const mode = b.standardReleaseOptions();
    const lib = b.addStaticLibrary("zig-btreemap", "src/btreemap.zig");
    lib.setBuildMode(mode);
    lib.install();
    const main_tests = b.addTest("src/btreemap.zig");
    main_tests.setBuildMode(mode);
    const test_step = b.step("test", "Run library tests");
    test_step.dependOn(&main_tests.step);
}

This is for testing only, use [upstream version](https://github.com/pmkap/zig-btreemap)
# BTreeMap implementation in Zig
## Recources
* https://cglab.ca/~abeinges/blah/rust-btree-case/
* https://opendatastructures.org/ods-python/14_2_B_Trees.html

MIT License
Copyright (c) 2022 Peter Kaplan
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.