{"header":{"message":"Test","description":null,"timestamp":"2022-03-10T21:56:13.351870229Z","authors":[{}]},"hash":"IVB35HSRN2QH6LCGYHEWNDH7XVSYYSMA4OCI7Z24L52LH3X5AODQC","authors":[{"login":"voroskoi","key":"Guf8VYJNUiWAqxwLxDSKxmvvtY65ht2zK2q4h6VhxrcZ"}],"deps":{"hashes":[["IVB35HSRN2QH6LCGYHEWNDH7XVSYYSMA4OCI7Z24L52LH3X5AODQC","Test"],["AA",null],["5X4EO2QKQZJ7HTGO5RN3AZPTOGH5NYGCXM4INQBYIR37JVC6HTKAC",""]],"deps":["5X4EO2QKQZJ7HTGO5RN3AZPTOGH5NYGCXM4INQBYIR37JVC6HTKAC"],"known":[]},"hunks":[{"FileAdd":{"meta":{"basename":"zigmod.yml","metadata":0},"context":[{"change":2,"pos":1}],"contents":[{"Add":"id: ifbd0mau6agl312dgj4tfy4mtiuvvkq13rubvaptaxghlgn2"},{"Add":"name: btreemap"},{"Add":"main: src/btreemap.zig"},{"Add":"license: MIT"},{"Add":"description: BTreeMap implementation in Zig"},{"Add":"dependencies:"}]}},{"FileAdd":{"meta":{"basename":"src","metadata":576},"context":[{"change":2,"pos":1}],"contents":[]}},{"FileAdd":{"meta":{"basename":"node.zig","metadata":0},"context":[{"change":0,"pos":214}],"contents":[{"Add":"const std = @import(\"std\");"},{"Add":""},{"Add":"const meta = @import(\"meta.zig\");"},{"Add":""},{"Add":"const Allocator = std.mem.Allocator;"},{"Add":"const assert = std.debug.assert;"},{"Add":""},{"Add":"pub fn Node(comptime K: type, comptime V: type, comptime B: u32) type {"},{"Add":" return struct {"},{"Add":" const Self = @This();"},{"Add":""},{"Add":" keys: [2 * B - 1]K,"},{"Add":" values: [2 * B - 1]V,"},{"Add":" len: usize,"},{"Add":" edges: [2 * B]?*Self,"},{"Add":""},{"Add":" // Return Type for Node's search method."},{"Add":" pub const SearchResult = struct {"},{"Add":" found: bool,"},{"Add":" index: usize,"},{"Add":" };"},{"Add":""},{"Add":" pub const KV = struct {"},{"Add":" key: K,"},{"Add":" value: V,"},{"Add":" };"},{"Add":""},{"Add":" const KVE = struct {"},{"Add":" key: K,"},{"Add":" value: V,"},{"Add":" edge: ?*Self,"},{"Add":" };"},{"Add":""},{"Add":" const Entry = struct {"},{"Add":" key_ptr: *K,"},{"Add":" value_ptr: *V,"},{"Add":" };"},{"Add":""},{"Add":" pub fn createEmpty(allocator: Allocator) !*Self {"},{"Add":" var out = try allocator.create(Self);"},{"Add":" out.* = Self{"},{"Add":" .keys = [_]K{undefined} ** (2 * B - 1),"},{"Add":" .values = [_]V{undefined} ** (2 * B - 1),"},{"Add":" .len = 0,"},{"Add":" .edges = [_]?*Self{null} ** (2 * B),"},{"Add":" };"},{"Add":" return out;"},{"Add":" }"},{"Add":""},{"Add":" pub fn createFromKV(allocator: Allocator, key: K, value: V) !*Self {"},{"Add":" var out = try Self.createEmpty(allocator);"},{"Add":" out.keys[0] = key;"},{"Add":" out.values[0] = value;"},{"Add":" out.len = 1;"},{"Add":" return out;"},{"Add":" }"},{"Add":""},{"Add":" /// Searches the node for a key. Returns a struct with two fields:"},{"Add":" /// 1) .found: bool -> Wether the key was found or not."},{"Add":" /// 2) .index: usize -> The index of the found key or, if no key was found,"},{"Add":" /// the index of the edge where the search path continues."},{"Add":" pub fn search(self: Self, key: K) SearchResult {"},{"Add":" var i: usize = 0;"},{"Add":" while (i < self.len) : (i += 1) {"},{"Add":" if (meta.eq(key, self.keys[i])) {"},{"Add":" return SearchResult{"},{"Add":" .found = true,"},{"Add":" .index = i,"},{"Add":" };"},{"Add":" } else if (meta.lt(key, self.keys[i])) {"},{"Add":" return .{"},{"Add":" .found = false,"},{"Add":" .index = i,"},{"Add":" };"},{"Add":" }"},{"Add":" }"},{"Add":" return .{"},{"Add":" .found = false,"},{"Add":" .index = self.len,"},{"Add":" };"},{"Add":" }"},{"Add":""},{"Add":" /// Insert KVE if node has room. Return null in this case."},{"Add":" /// If node is full, take out the median KV and split off the the right part"},{"Add":" /// into a new node and return this new node together with the median KV."},{"Add":" pub fn insertOrSplit("},{"Add":" self: *Self,"},{"Add":" allocator: Allocator,"},{"Add":" index: usize,"},{"Add":" key: K,"},{"Add":" value: V,"},{"Add":" edge: ?*Self,"},{"Add":" ) !?KVE {"},{"Add":" if (self.isFull()) {"},{"Add":" // Node is full. Split Node."},{"Add":" var split_result = try self.split(allocator);"},{"Add":" if (index < B) {"},{"Add":" // Insert KVE in original node."},{"Add":" self.insert(index, key, value, edge);"},{"Add":" } else {"},{"Add":" // Insert KVE in the split off node."},{"Add":" split_result.edge.?.insert(index - B, key, value, edge);"},{"Add":" }"},{"Add":" return split_result;"},{"Add":" } else {"},{"Add":" // No split necessary."},{"Add":" self.insert(index, key, value, edge);"},{"Add":" return null;"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" /// Swap value at index."},{"Add":" pub fn swapValue(self: *Self, index: usize, value: V) V {"},{"Add":" const out = self.values[index];"},{"Add":" self.values[index] = value;"},{"Add":" return out;"},{"Add":" }"},{"Add":""},{"Add":" /// Swap KV at index."},{"Add":" pub fn swapKV(self: *Self, index: usize, key: K, value: V) KV {"},{"Add":" const out = KV{"},{"Add":" .key = self.keys[index],"},{"Add":" .value = self.values[index],"},{"Add":" };"},{"Add":" self.values[index] = value;"},{"Add":" self.keys[index] = key;"},{"Add":" return out;"},{"Add":" }"},{"Add":""},{"Add":" /// Remove and return KVE at index."},{"Add":" /// The removed edge is right of the KV."},{"Add":" pub fn remove(self: *Self, index: usize) KVE {"},{"Add":" const out = KVE{"},{"Add":" .key = self.keys[index],"},{"Add":" .value = self.values[index],"},{"Add":" .edge = self.edges[index + 1],"},{"Add":" };"},{"Add":""},{"Add":" std.mem.copy("},{"Add":" K,"},{"Add":" self.keys[index..],"},{"Add":" self.keys[index + 1 .. self.len],"},{"Add":" );"},{"Add":" std.mem.copy("},{"Add":" V,"},{"Add":" self.values[index..],"},{"Add":" self.values[index + 1 .. self.len],"},{"Add":" );"},{"Add":""},{"Add":" self.keys[self.len - 1] = undefined;"},{"Add":" self.values[self.len - 1] = undefined;"},{"Add":""},{"Add":" if (!self.isLeaf()) {"},{"Add":" std.mem.copy("},{"Add":" ?*Self,"},{"Add":" self.edges[index + 1 ..],"},{"Add":" self.edges[index + 2 .. self.len + 1],"},{"Add":" );"},{"Add":" self.edges[self.len] = null;"},{"Add":" }"},{"Add":""},{"Add":" self.len -= 1;"},{"Add":" return out;"},{"Add":" }"},{"Add":""},{"Add":" /// Remove and return most right KVE."},{"Add":" fn removeFromEnd(self: *Self) KVE {"},{"Add":" return self.remove(self.len - 1);"},{"Add":" }"},{"Add":""},{"Add":" /// Remove and return most left KV and Edge."},{"Add":" /// Contrary to the methods above, this removes the edge left of the KV."},{"Add":" fn removeFromBeginning(self: *Self) KVE {"},{"Add":" const out = KVE{"},{"Add":" .key = self.keys[0],"},{"Add":" .value = self.values[0],"},{"Add":" .edge = self.edges[0],"},{"Add":" };"},{"Add":""},{"Add":" std.mem.copy("},{"Add":" K,"},{"Add":" self.keys[0..],"},{"Add":" self.keys[1..self.len],"},{"Add":" );"},{"Add":" std.mem.copy("},{"Add":" V,"},{"Add":" self.values[0..],"},{"Add":" self.values[1..self.len],"},{"Add":" );"},{"Add":""},{"Add":" self.keys[self.len - 1] = undefined;"},{"Add":" self.values[self.len - 1] = undefined;"},{"Add":""},{"Add":" if (!self.isLeaf()) {"},{"Add":" std.mem.copy("},{"Add":" ?*Self,"},{"Add":" self.edges[0..],"},{"Add":" self.edges[1 .. self.len + 1],"},{"Add":" );"},{"Add":" self.edges[self.len] = null;"},{"Add":" }"},{"Add":" self.len -= 1;"},{"Add":" return out;"},{"Add":" }"},{"Add":""},{"Add":" // Shifts the arrays right after index and inserts new KVE."},{"Add":" // The new edge is right of the new KV."},{"Add":" // Does not check if insertion is at the correct position/node has space."},{"Add":" fn insert(self: *Self, index: usize, key: K, value: V, edge: ?*Self) void {"},{"Add":" std.mem.copyBackwards("},{"Add":" K,"},{"Add":" self.keys[index + 1 .. self.len + 1],"},{"Add":" self.keys[index..self.len],"},{"Add":" );"},{"Add":" self.keys[index] = key;"},{"Add":""},{"Add":" std.mem.copyBackwards("},{"Add":" V,"},{"Add":" self.values[index + 1 .. self.len + 1],"},{"Add":" self.values[index..self.len],"},{"Add":" );"},{"Add":" self.values[index] = value;"},{"Add":""},{"Add":" if (!self.isLeaf()) {"},{"Add":" std.mem.copyBackwards("},{"Add":" ?*Self,"},{"Add":" self.edges[index + 2 .. self.len + 2],"},{"Add":" self.edges[index + 1 .. self.len + 1],"},{"Add":" );"},{"Add":" self.edges[index + 1] = edge;"},{"Add":" }"},{"Add":""},{"Add":" self.len += 1;"},{"Add":" }"},{"Add":""},{"Add":" /// Does not check if insertion is at the correct position/node has space."},{"Add":" fn insertAtEnd(self: *Self, key: K, value: V, edge: ?*Self) void {"},{"Add":" self.keys[self.len] = key;"},{"Add":" self.values[self.len] = value;"},{"Add":" self.edges[self.len + 1] = edge;"},{"Add":" self.len += 1;"},{"Add":" }"},{"Add":""},{"Add":" /// This is different from the other inserts methods because it inserts the edge"},{"Add":" /// left of the KV. I.e. it also puts the edge in the first position."},{"Add":" /// Does not check if insertion is at the correct position/node has space."},{"Add":" fn insertAtBeginning(self: *Self, key: K, value: V, edge: ?*Self) void {"},{"Add":" std.mem.copyBackwards("},{"Add":" K,"},{"Add":" self.keys[1 .. self.len + 1],"},{"Add":" self.keys[0..self.len],"},{"Add":" );"},{"Add":" self.keys[0] = key;"},{"Add":""},{"Add":" std.mem.copyBackwards("},{"Add":" V,"},{"Add":" self.values[1 .. self.len + 1],"},{"Add":" self.values[0..self.len],"},{"Add":" );"},{"Add":" self.values[0] = value;"},{"Add":""},{"Add":" if (!self.isLeaf()) {"},{"Add":" std.mem.copyBackwards("},{"Add":" ?*Self,"},{"Add":" self.edges[1 .. self.len + 2],"},{"Add":" self.edges[0 .. self.len + 1],"},{"Add":" );"},{"Add":" self.edges[0] = edge;"},{"Add":" }"},{"Add":""},{"Add":" self.len += 1;"},{"Add":" }"},{"Add":""},{"Add":" /// The borrowing methods happen from the perspective of the parent."},{"Add":" /// This means, the parent distributes from one edge to another."},{"Add":" /// The edge at `index` is underflowed and needs compensation."},{"Add":" /// Try to borrow from the edge at one side of `index` and rotate."},{"Add":" /// Returns true on success, else false."},{"Add":" pub fn borrowFromRight(self: *Self, index: usize) bool {"},{"Add":" // No edge right of index."},{"Add":" if (index == self.len) return false;"},{"Add":""},{"Add":" var giver = self.edges[index + 1].?;"},{"Add":""},{"Add":" if (giver.len > B - 1) {"},{"Add":" // Right edge can spare one."},{"Add":" var taker = self.edges[index].?;"},{"Add":""},{"Add":" const from_giver: KVE = giver.removeFromBeginning();"},{"Add":" taker.insertAtEnd(self.keys[index], self.values[index], from_giver.edge);"},{"Add":" _ = self.swapKV(index, from_giver.key, from_giver.value);"},{"Add":" return true;"},{"Add":" } else return false;"},{"Add":" }"},{"Add":""},{"Add":" /// The borrowing methods happen from the perspective of the parent."},{"Add":" /// This means, the parent distributes from one edge to another."},{"Add":" /// The edge at `index` is underflowed and needs compensation."},{"Add":" /// Try to borrow from the edge at one side of `index` and rotate."},{"Add":" /// Returns true on success, else false."},{"Add":" pub fn borrowFromLeft(self: *Self, index: usize) bool {"},{"Add":" // No edge left of index."},{"Add":" if (index == 0) return false;"},{"Add":""},{"Add":" var giver = self.edges[index - 1].?;"},{"Add":""},{"Add":" if (giver.len > B - 1) {"},{"Add":" // Right edge can spare one."},{"Add":" var taker = self.edges[index].?;"},{"Add":""},{"Add":" const from_giver: KVE = giver.removeFromEnd();"},{"Add":" taker.insertAtBeginning(self.keys[index - 1], self.values[index - 1], from_giver.edge);"},{"Add":" _ = self.swapKV(index - 1, from_giver.key, from_giver.value);"},{"Add":" return true;"},{"Add":" } else return false;"},{"Add":" }"},{"Add":""},{"Add":" /// Merging happend from the perspective of the parent."},{"Add":" /// It merges two edges together and puts the middle KV of the parent in between."},{"Add":" /// The right node is merged into the left and the right is destroyed afterwards."},{"Add":" pub fn mergeEdges(self: *Self, allocator: Allocator, left_edge_index: usize) void {"},{"Add":" var left = self.edges[left_edge_index].?;"},{"Add":" const removed = self.remove(left_edge_index);"},{"Add":""},{"Add":" left.insertAtEnd(removed.key, removed.value, null);"},{"Add":""},{"Add":" std.mem.copyBackwards("},{"Add":" K,"},{"Add":" left.keys[left.len..],"},{"Add":" removed.edge.?.keys[0..removed.edge.?.len],"},{"Add":" );"},{"Add":" std.mem.copyBackwards("},{"Add":" V,"},{"Add":" left.values[left.len..],"},{"Add":" removed.edge.?.values[0..removed.edge.?.len],"},{"Add":" );"},{"Add":" std.mem.copyBackwards("},{"Add":" ?*Self,"},{"Add":" left.edges[left.len..],"},{"Add":" removed.edge.?.edges[0 .. removed.edge.?.len + 1],"},{"Add":" );"},{"Add":""},{"Add":" left.len += removed.edge.?.len;"},{"Add":""},{"Add":" allocator.destroy(removed.edge.?);"},{"Add":" }"},{"Add":""},{"Add":" /// Split operation for a full node."},{"Add":" /// Returns a struct with three fields:"},{"Add":" /// 1) and 2) -> Key and value of the median."},{"Add":" /// 3) -> The right part of the median as a new node (pointer)."},{"Add":" /// These parts are erased from the original node."},{"Add":" fn split(self: *Self, allocator: Allocator) !KVE {"},{"Add":" const median: usize = B - 1;"},{"Add":" var new_key = self.keys[median];"},{"Add":" var new_value = self.values[median];"},{"Add":""},{"Add":" var new_node = try Self.createFromSlices("},{"Add":" allocator,"},{"Add":" self.keys[median + 1 .. self.len],"},{"Add":" self.values[median + 1 .. self.len],"},{"Add":" self.edges[median + 1 .. self.len + 1],"},{"Add":" );"},{"Add":""},{"Add":" // shrink original node"},{"Add":" std.mem.set(K, self.keys[median..], undefined);"},{"Add":" std.mem.set(V, self.values[median..], undefined);"},{"Add":" std.mem.set(?*Self, self.edges[median + 1 ..], null);"},{"Add":" self.len = median;"},{"Add":""},{"Add":" return KVE{"},{"Add":" .key = new_key,"},{"Add":" .value = new_value,"},{"Add":" .edge = new_node,"},{"Add":" };"},{"Add":" }"},{"Add":""},{"Add":" fn createFromSlices(allocator: Allocator, keys: []K, values: []V, edges: []?*Self) !*Self {"},{"Add":" var out = try Self.createEmpty(allocator);"},{"Add":" std.mem.copyBackwards(K, out.keys[0..], keys);"},{"Add":" std.mem.copyBackwards(V, out.values[0..], values);"},{"Add":" std.mem.copyBackwards(?*Self, out.edges[0..], edges);"},{"Add":" out.len = keys.len;"},{"Add":" return out;"},{"Add":" }"},{"Add":""},{"Add":" pub fn isLeaf(self: Self) bool {"},{"Add":" return self.edges[0] == null;"},{"Add":" }"},{"Add":""},{"Add":" pub fn isFull(self: Self) bool {"},{"Add":" return self.len == 2 * B - 1;"},{"Add":" }"},{"Add":""},{"Add":" pub fn isLacking(self: Self) bool {"},{"Add":" return self.len < B - 1;"},{"Add":" }"},{"Add":""},{"Add":" /// This is intended for testing and debugging."},{"Add":" fn assertValidityExceptLength(self: *const Self) void {"},{"Add":" // Keys increasing"},{"Add":" for (self.keys[0 .. self.len - 1]) |_, i| {"},{"Add":" assert(meta.lt(self.keys[i], self.keys[i + 1]));"},{"Add":" }"},{"Add":""},{"Add":" // Number of edges"},{"Add":" var count: u32 = 0;"},{"Add":" var encountered_null = false;"},{"Add":" for (self.edges) |edge| {"},{"Add":" if (edge) |_| {"},{"Add":" assert(encountered_null == false);"},{"Add":" count += 1;"},{"Add":" } else {"},{"Add":" encountered_null = true;"},{"Add":" }"},{"Add":" }"},{"Add":" assert(count == self.len + 1 or count == 0);"},{"Add":""},{"Add":" // If node is leaf we are done here."},{"Add":" if (self.isLeaf()) return;"},{"Add":""},{"Add":" // Edges left smaller and right larger"},{"Add":" for (self.keys[0..self.len]) |key, i| {"},{"Add":" const left_edge = self.edges[i].?;"},{"Add":" const imm_left_key = left_edge.keys[left_edge.len - 1];"},{"Add":" assert(meta.gt(key, imm_left_key));"},{"Add":""},{"Add":" const right_edge = self.edges[i + 1].?;"},{"Add":" const imm_right_key = right_edge.keys[0];"},{"Add":" assert(meta.lt(key, imm_right_key));"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" pub fn assertValidity(self: *const Self) void {"},{"Add":" // Length"},{"Add":" assert(self.len <= 2 * B - 1);"},{"Add":" assert(self.len >= B - 1);"},{"Add":""},{"Add":" self.assertValidityExceptLength();"},{"Add":" }"},{"Add":""},{"Add":" pub fn assertValidityRoot(self: *const Self) void {"},{"Add":" // Length"},{"Add":" assert(self.len <= 2 * B - 1);"},{"Add":""},{"Add":" self.assertValidityExceptLength();"},{"Add":" }"},{"Add":" };"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"meta.zig","metadata":0},"context":[{"change":0,"pos":214}],"contents":[{"Add":"const std = @import(\"std\");"},{"Add":"const assert = std.debug.assert;"},{"Add":"const expect = std.testing.expect;"},{"Add":""},{"Add":"/// Similiar to std.meta.eql but pointers are followed."},{"Add":"/// Also Unions and ErrorUnions are excluded."},{"Add":"pub fn eq(a: anytype, b: @TypeOf(a)) bool {"},{"Add":" const T = @TypeOf(a);"},{"Add":""},{"Add":" switch (@typeInfo(T)) {"},{"Add":" .Int, .ComptimeInt, .Float, .ComptimeFloat => {"},{"Add":" return a == b;"},{"Add":" },"},{"Add":" .Struct => {"},{"Add":" if (!@hasDecl(T, \"eq\")) {"},{"Add":" @compileError(\"An 'eq' comparison method has to implemented for Type '\" ++ @typeName(T) ++ \"'\");"},{"Add":" }"},{"Add":" return T.eq(a, b);"},{"Add":" },"},{"Add":" .Array => {"},{"Add":" for (a) |_, i|"},{"Add":" if (!eq(a[i], b[i])) return false;"},{"Add":" return true;"},{"Add":" },"},{"Add":" .Vector => |info| {"},{"Add":" var i: usize = 0;"},{"Add":" while (i < info.len) : (i += 1) {"},{"Add":" if (!eq(a[i], b[i])) return false;"},{"Add":" }"},{"Add":" return true;"},{"Add":" },"},{"Add":" .Pointer => |info| {"},{"Add":" switch (info.size) {"},{"Add":" .One => return eq(a.*, b.*),"},{"Add":" .Slice => {"},{"Add":" if (a.len != b.len) return false;"},{"Add":" for (a) |_, i|"},{"Add":" if (!eq(a[i], b[i])) return false;"},{"Add":" return true;"},{"Add":" },"},{"Add":" .Many => {"},{"Add":" if (info.sentinel) {"},{"Add":" if (std.mem.len(a) != std.mem.len(b)) return false;"},{"Add":" var i: usize = 0;"},{"Add":" while (i < std.mem.len(a)) : (i += 1)"},{"Add":" if (!eq(a[i], b[i])) return false;"},{"Add":" return true;"},{"Add":" }"},{"Add":" @compileError(\"Cannot compare many-item pointer to unknown number of items without sentinel value\");"},{"Add":" },"},{"Add":" .C => @compileError(\"Cannot compare C pointers\"),"},{"Add":" }"},{"Add":" },"},{"Add":" .Optional => {"},{"Add":" if (a == null and b == null) return true;"},{"Add":" if (a == null or b == null) return false;"},{"Add":" return eq(a.?, b.?);"},{"Add":" },"},{"Add":" else => {"},{"Add":" @compileError(\"Cannot compare type '\" ++ @typeName(T) ++ \"'\");"},{"Add":" },"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"pub fn lt(a: anytype, b: @TypeOf(a)) bool {"},{"Add":" const T = @TypeOf(a);"},{"Add":""},{"Add":" switch (@typeInfo(T)) {"},{"Add":" .Int, .ComptimeInt, .Float, .ComptimeFloat => {"},{"Add":" return a < b;"},{"Add":" },"},{"Add":" .Struct => {"},{"Add":" if (!@hasDecl(T, \"lt\")) {"},{"Add":" @compileError(\"A 'lt' comparison method has to implemented for Type '\" ++ @typeName(T) ++ \"'\");"},{"Add":" }"},{"Add":" return T.lt(a, b);"},{"Add":" },"},{"Add":" .Array => {"},{"Add":" for (a) |_, i| {"},{"Add":" if (lt(a[i], b[i])) {"},{"Add":" return true;"},{"Add":" } else if (eq(a[i], b[i])) {"},{"Add":" continue;"},{"Add":" } else {"},{"Add":" return false;"},{"Add":" }"},{"Add":" }"},{"Add":" return false;"},{"Add":" },"},{"Add":" .Vector => |info| {"},{"Add":" var i: usize = 0;"},{"Add":" while (i < info.len) : (i += 1) {"},{"Add":" if (lt(a[i], b[i])) {"},{"Add":" return true;"},{"Add":" } else if (eq(a[i], b[i])) {"},{"Add":" continue;"},{"Add":" } else {"},{"Add":" return false;"},{"Add":" }"},{"Add":" }"},{"Add":" return false;"},{"Add":" },"},{"Add":" .Pointer => |info| {"},{"Add":" switch (info.size) {"},{"Add":" .One => return lt(a.*, b.*),"},{"Add":" .Slice => {"},{"Add":" const n = std.math.min(a.len, b.len);"},{"Add":" for (a[0..n]) |_, i| {"},{"Add":" if (lt(a[i], b[i])) {"},{"Add":" return true;"},{"Add":" } else if (eq(a[i], b[i])) {"},{"Add":" continue;"},{"Add":" } else {"},{"Add":" return false;"},{"Add":" }"},{"Add":" }"},{"Add":" return lt(a.len, b.len);"},{"Add":" },"},{"Add":" .Many => {"},{"Add":" if (info.sentinel) {"},{"Add":" const n = std.math.min(std.mem.len(a), std.mem.len(b));"},{"Add":" var i: usize = 0;"},{"Add":" while (i < n) : (i += 1) {"},{"Add":" if (lt(a[i], b[i])) {"},{"Add":" return true;"},{"Add":" } else if (eq(a[i], b[i])) {"},{"Add":" continue;"},{"Add":" } else {"},{"Add":" return false;"},{"Add":" }"},{"Add":" }"},{"Add":" return lt(std.mem.len(a), std.mem.len(b));"},{"Add":" }"},{"Add":" @compileError(\"Cannot compare many-item pointer to unknown number of items without sentinel value\");"},{"Add":" },"},{"Add":" .C => @compileError(\"Cannot compare C pointers\"),"},{"Add":" }"},{"Add":" },"},{"Add":" .Optional => {"},{"Add":" if (a == null or b == null) return false;"},{"Add":" return lt(a.?, b.?);"},{"Add":" },"},{"Add":" else => {"},{"Add":" @compileError(\"Cannot compare type '\" ++ @typeName(T) ++ \"'\");"},{"Add":" },"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"pub fn le(a: anytype, b: @TypeOf(a)) bool {"},{"Add":" return lt(a, b) or eq(a, b);"},{"Add":"}"},{"Add":""},{"Add":"pub fn gt(a: anytype, b: @TypeOf(a)) bool {"},{"Add":" return !lt(a, b) and !eq(a, b);"},{"Add":"}"},{"Add":""},{"Add":"pub fn ge(a: anytype, b: @TypeOf(a)) bool {"},{"Add":" return !lt(a, b);"},{"Add":"}"},{"Add":""},{"Add":"test \"numerals\" {"},{"Add":" try expect(eq(1.0, 1.0));"},{"Add":" try expect(!eq(1.0, 1.1));"},{"Add":""},{"Add":" try expect(lt(1.0, 2.0));"},{"Add":" try expect(!lt(1, 1));"},{"Add":" try expect(!lt(2, 1));"},{"Add":"}"},{"Add":""},{"Add":"test \"Arrays\" {"},{"Add":" try expect(eq(\"abc\", \"abc\"));"},{"Add":" try expect(!eq(\"abc\", \"abb\"));"},{"Add":""},{"Add":" try expect(lt(\"ab\", \"ba\"));"},{"Add":" try expect(lt(\"aaa\", \"aab\"));"},{"Add":" try expect(!lt(\"aaa\", \"aaa\"));"},{"Add":" try expect(!lt(\"aab\", \"aaa\"));"},{"Add":"}"},{"Add":""},{"Add":"test \"structs\" {"},{"Add":" const Car = struct {"},{"Add":" power: i32,"},{"Add":" pub fn lt(a: @This(), b: @This()) bool {"},{"Add":" return a.power < b.power;"},{"Add":" }"},{"Add":" pub fn eq(a: @This(), b: @This()) bool {"},{"Add":" return a.power == b.power;"},{"Add":" }"},{"Add":" };"},{"Add":""},{"Add":" var car1 = Car{ .power = 100 };"},{"Add":" var car2 = Car{ .power = 200 };"},{"Add":""},{"Add":" try expect(eq(car1, car1));"},{"Add":" try expect(!eq(car1, car2));"},{"Add":""},{"Add":" try expect(lt(car1, car2));"},{"Add":" try expect(!lt(car1, car1));"},{"Add":"}"},{"Add":""},{"Add":"test \"Slices\" {"},{"Add":" var o: usize = 0;"},{"Add":" assert(@TypeOf(\"abc\"[o..]) == [:0]const u8);"},{"Add":""},{"Add":" try expect(eq(\"abc\"[o..], \"abc\"));"},{"Add":" try expect(!eq(\"abc\"[o..], \"abb\"));"},{"Add":""},{"Add":" try expect(lt(\"aba\"[o..], \"ba\"));"},{"Add":" try expect(lt(\"aaa\"[o..], \"bb\"));"},{"Add":" try expect(!lt(\"aba\"[o..], \"aa\"));"},{"Add":" try expect(!lt(\"aaa\"[o..], \"aaa\"));"},{"Add":" try expect(lt(\"aaa\"[o..], \"aaaa\"));"},{"Add":" try expect(!lt(\"aaa\"[o..], \"aa\"));"},{"Add":" try expect(lt(\"aab\"[o..], \"aaba\"));"},{"Add":"}"},{"Add":""},{"Add":"test \"Optionals\" {"},{"Add":" var x: ?i32 = 1;"},{"Add":" var y: ?i32 = 2;"},{"Add":" try expect(lt(x, y));"},{"Add":"}"},{"Add":""},{"Add":"test \"sentinel terminated pointers\" {"},{"Add":" // TODO"},{"Add":"}"},{"Add":""},{"Add":"test \"Vectors\" {"},{"Add":" // TODO"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"btreemap.zig","metadata":0},"context":[{"change":0,"pos":214}],"contents":[{"Add":"const std = @import(\"std\");"},{"Add":"const Allocator = std.mem.Allocator;"},{"Add":"const assert = std.debug.assert;"},{"Add":""},{"Add":"const getNodeType = @import(\"node.zig\").Node;"},{"Add":""},{"Add":"pub fn BTreeMap(comptime K: type, comptime V: type) type {"},{"Add":" return struct {"},{"Add":" const Self = @This();"},{"Add":""},{"Add":" root: ?*Node,"},{"Add":" allocator: Allocator,"},{"Add":""},{"Add":" const B = 6;"},{"Add":" const Node = getNodeType(K, V, B);"},{"Add":" const KV = Node.KV;"},{"Add":" const SearchResult = Node.SearchResult;"},{"Add":""},{"Add":" const StackItem = struct {"},{"Add":" node: *Node,"},{"Add":" index: usize,"},{"Add":" };"},{"Add":""},{"Add":" pub fn init(allocator: Allocator) Self {"},{"Add":" return Self{"},{"Add":" .allocator = allocator,"},{"Add":" .root = null,"},{"Add":" };"},{"Add":" }"},{"Add":""},{"Add":" pub fn deinit(self: Self) !void {"},{"Add":" var stack = std.ArrayList(*Node).init(self.allocator);"},{"Add":" defer stack.deinit();"},{"Add":""},{"Add":" if (self.root) |root| {"},{"Add":" try stack.append(root);"},{"Add":" } else return;"},{"Add":""},{"Add":" while (stack.popOrNull()) |node| {"},{"Add":" if (!node.isLeaf()) {"},{"Add":" var i: usize = 0;"},{"Add":" while (i < node.len + 1) : (i += 1) {"},{"Add":" try stack.append(node.edges[i].?);"},{"Add":" }"},{"Add":" }"},{"Add":" self.allocator.destroy(node);"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" pub fn isEmpty(self: *const Self) bool {"},{"Add":" if (self.root == null) return true;"},{"Add":" return self.root.?.len == 0;"},{"Add":" }"},{"Add":""},{"Add":" /// Get value from a certain key."},{"Add":" pub fn get(self: Self, key: K) ?V {"},{"Add":" var current = self.root;"},{"Add":" while (current) |node| {"},{"Add":" const result = node.search(key);"},{"Add":" if (result.found) {"},{"Add":" return node.values[result.index];"},{"Add":" } else {"},{"Add":" current = node.edges[result.index];"},{"Add":" }"},{"Add":" }"},{"Add":" return null;"},{"Add":" }"},{"Add":""},{"Add":" /// Inserts key-value pair into the map. Swaps the values if already present"},{"Add":" /// and returns the old."},{"Add":" /// This function has two stages. In the first stage, the tree"},{"Add":" /// is traversed to find the path to the relevant leaf node."},{"Add":" /// This path is saved in a stack, containing the nodes itself"},{"Add":" /// and the indices of the children where the path continues."},{"Add":" /// In the second phase, we try to insert and, if the node is full,"},{"Add":" /// split the node and hand the result of the split down the stack."},{"Add":" /// Repeat this until insertion is successful or the root itself is split."},{"Add":" pub fn fetchPut(self: *Self, key: K, value: V) !?V {"},{"Add":" // TODO: return KV like in std.HashMap"},{"Add":" if (self.root == null) {"},{"Add":" self.root = try Node.createFromKV(self.allocator, key, value);"},{"Add":" return null;"},{"Add":" }"},{"Add":""},{"Add":" var stack = std.ArrayList(StackItem).init(self.allocator);"},{"Add":" defer stack.deinit();"},{"Add":""},{"Add":" // Traverse tree until we find the key or hit bottom."},{"Add":" // If we we find the key, swap new with old value and return the old."},{"Add":" // Build a stack to remember the path"},{"Add":" var current = self.root;"},{"Add":" var search_result: SearchResult = undefined;"},{"Add":" while (current) |node| {"},{"Add":" search_result = node.search(key);"},{"Add":" if (search_result.found) {"},{"Add":" return node.swapValue(search_result.index, value);"},{"Add":" }"},{"Add":" // Not found, go deeper."},{"Add":" current = node.edges[search_result.index];"},{"Add":" try stack.append(.{"},{"Add":" .node = node,"},{"Add":" .index = search_result.index,"},{"Add":" });"},{"Add":" }"},{"Add":""},{"Add":" // Pop top of stack (bottom of tree/leaf node)."},{"Add":" var stack_next: ?StackItem = stack.pop();"},{"Add":""},{"Add":" // Try to insert to leaf node."},{"Add":" var split_result = try stack_next.?.node.insertOrSplit("},{"Add":" self.allocator,"},{"Add":" stack_next.?.index,"},{"Add":" key,"},{"Add":" value,"},{"Add":" null,"},{"Add":" );"},{"Add":""},{"Add":" // No split was necessary -> insertion was successful. We're Done."},{"Add":" if (split_result == null) {"},{"Add":" return null;"},{"Add":" }"},{"Add":""},{"Add":" // Split was necessary -> move down on stack."},{"Add":" // The current node in stack was incorporated in the tree and the SplitResult."},{"Add":" stack_next = stack.popOrNull();"},{"Add":""},{"Add":" // Repeat the process of splitting and inserting until insertion is"},{"Add":" // successful or we hit the root node, in which case the root node is split."},{"Add":" while (split_result) |split_result_unwrapped| {"},{"Add":" if (stack_next) |stack_next_unwrapped| {"},{"Add":" // Try to insert the in current stack item."},{"Add":" split_result = try stack_next_unwrapped.node.insertOrSplit("},{"Add":" self.allocator,"},{"Add":" stack_next_unwrapped.index,"},{"Add":" split_result_unwrapped.key,"},{"Add":" split_result_unwrapped.value,"},{"Add":" split_result_unwrapped.edge,"},{"Add":" );"},{"Add":" stack_next = stack.popOrNull();"},{"Add":" } else {"},{"Add":" // We reached the root."},{"Add":" var new_root = try Node.createFromKV("},{"Add":" self.allocator,"},{"Add":" split_result_unwrapped.key,"},{"Add":" split_result_unwrapped.value,"},{"Add":" );"},{"Add":" new_root.edges[0] = self.root;"},{"Add":" new_root.edges[1] = split_result_unwrapped.edge;"},{"Add":" self.root = new_root;"},{"Add":" return null;"},{"Add":" }"},{"Add":" } else return null;"},{"Add":" }"},{"Add":""},{"Add":" /// Removes and returns a key-value-pair. Returns null if not found."},{"Add":" pub fn fetchRemove(self: *Self, key: K) !?KV {"},{"Add":" var stack = std.ArrayList(StackItem).init(self.allocator);"},{"Add":" defer stack.deinit();"},{"Add":""},{"Add":" // Traverse tree until we find the key or hit bottom."},{"Add":" // Build a stack to remember the path"},{"Add":" var current = self.root;"},{"Add":" var search_result: SearchResult = undefined;"},{"Add":" var found_key_ptr: ?*K = null;"},{"Add":" var found_value_ptr: ?*V = null;"},{"Add":" while (current) |node| {"},{"Add":" search_result = node.search(key);"},{"Add":" if (search_result.found) {"},{"Add":" // Found! Remember pointers to key and value to swap later."},{"Add":" found_key_ptr = &node.keys[search_result.index];"},{"Add":" found_value_ptr = &node.values[search_result.index];"},{"Add":" // If not reached leaf, increment index in order to find the"},{"Add":" // found key's inorder successor when we continue down the tree."},{"Add":" if (!node.isLeaf()) search_result.index += 1;"},{"Add":" }"},{"Add":" try stack.append(.{"},{"Add":" .node = node,"},{"Add":" .index = search_result.index,"},{"Add":" });"},{"Add":" current = node.edges[search_result.index];"},{"Add":" if (search_result.found) break;"},{"Add":" } else {"},{"Add":" // Key not found."},{"Add":" return null;"},{"Add":" }"},{"Add":""},{"Add":" // Continue building the stack to the inorder successor of the found key."},{"Add":" while (current) |node| {"},{"Add":" try stack.append(.{"},{"Add":" .node = node,"},{"Add":" .index = 0,"},{"Add":" });"},{"Add":" current = node.edges[0];"},{"Add":" }"},{"Add":" // Reached leaf node. Stack is complete."},{"Add":""},{"Add":" // Leaf node is on top of stack now."},{"Add":" var current_stack = stack.pop();"},{"Add":""},{"Add":" // Swap the KV for deletion with its inorder successor."},{"Add":" var out: KV = .{ .key = found_key_ptr.?.*, .value = found_value_ptr.?.* };"},{"Add":" found_key_ptr.?.* = current_stack.node.keys[current_stack.index];"},{"Add":" found_value_ptr.?.* = current_stack.node.values[current_stack.index];"},{"Add":""},{"Add":" // Now ew can remove the key-value pair in the leaf. This can result in an underflow,"},{"Add":" // which is handled below."},{"Add":" _ = current_stack.node.remove(current_stack.index);"},{"Add":""},{"Add":" // If our leaf is also the root, it cannot underflow."},{"Add":" if (current_stack.node == self.root) return out;"},{"Add":""},{"Add":" // Fix underflow and move down the stack until underflow is fixed."},{"Add":" while (current_stack.node.isLacking()) {"},{"Add":" // We have an underflow in the current stack position. This is fixed"},{"Add":" // from the parent's erspective, so move down the stack."},{"Add":" current_stack = stack.pop();"},{"Add":""},{"Add":" // Try to borrow, first from right, then from left."},{"Add":" if (current_stack.node.borrowFromRight(current_stack.index)) return out;"},{"Add":" if (current_stack.node.borrowFromLeft(current_stack.index)) return out;"},{"Add":""},{"Add":" // Borrow was not possible, merge nodes."},{"Add":" if (current_stack.index == current_stack.node.len) {"},{"Add":" // the underflowed edge is the most right. Merge with left."},{"Add":" current_stack.node.mergeEdges(self.allocator, current_stack.index - 1);"},{"Add":" } else {"},{"Add":" // Merge with right."},{"Add":" current_stack.node.mergeEdges(self.allocator, current_stack.index);"},{"Add":" }"},{"Add":""},{"Add":" if (current_stack.node == self.root) {"},{"Add":" // We reached the root."},{"Add":" if (self.root.?.len == 0) {"},{"Add":" // If root is empty, replace with merged node."},{"Add":" const new_root = current_stack.node.edges[0].?;"},{"Add":" self.allocator.destroy(self.root.?);"},{"Add":" self.root.? = new_root;"},{"Add":" }"},{"Add":" break;"},{"Add":" }"},{"Add":" }"},{"Add":" return out;"},{"Add":" }"},{"Add":""},{"Add":" pub fn iteratorInit(self: *const Self) !Iterator {"},{"Add":" var new_stack = std.ArrayList(StackItem).init(self.allocator);"},{"Add":" if (self.root) |root| {"},{"Add":" try new_stack.append(.{"},{"Add":" .node = root,"},{"Add":" .index = 0,"},{"Add":" });"},{"Add":" }"},{"Add":" return Iterator{"},{"Add":" .stack = new_stack,"},{"Add":" .backwards = false,"},{"Add":" };"},{"Add":" }"},{"Add":""},{"Add":" const Iterator = struct {"},{"Add":" stack: std.ArrayList(StackItem),"},{"Add":" backwards: bool,"},{"Add":""},{"Add":" pub fn deinit(it: Iterator) void {"},{"Add":" it.stack.deinit();"},{"Add":" }"},{"Add":""},{"Add":" pub fn next(it: *Iterator) !?KV {"},{"Add":" while (it.topStackItem()) |item| {"},{"Add":" if (!item.node.isLeaf() and !it.backwards) {"},{"Add":" // Child exists at index or going forward, go deeper."},{"Add":" var child = item.node.edges[item.index].?;"},{"Add":" try it.stack.append(StackItem{"},{"Add":" .node = child,"},{"Add":" .index = 0,"},{"Add":" });"},{"Add":" } else {"},{"Add":" // No Child or coming backwards."},{"Add":" if (item.index < item.node.len) {"},{"Add":" // Node is not yet exhausted."},{"Add":" // Return KV from Node and increment the node's index."},{"Add":" var out = KV{"},{"Add":" .key = item.node.keys[item.index],"},{"Add":" .value = item.node.values[item.index],"},{"Add":" };"},{"Add":" item.index += 1;"},{"Add":" it.backwards = false;"},{"Add":" return out;"},{"Add":" } else {"},{"Add":" // Node is exhausted."},{"Add":" // Set `backwards` so that this node is not entered again"},{"Add":" // in the next iteration."},{"Add":" _ = it.stack.popOrNull();"},{"Add":" it.backwards = true;"},{"Add":" }"},{"Add":" }"},{"Add":" } else return null;"},{"Add":" }"},{"Add":""},{"Add":" fn topStackItem(it: *Iterator) ?*StackItem {"},{"Add":" if (it.stack.items.len == 0) {"},{"Add":" return null;"},{"Add":" } else {"},{"Add":" return &it.stack.items[it.stack.items.len - 1];"},{"Add":" }"},{"Add":" }"},{"Add":" };"},{"Add":""},{"Add":" /// Intended for testing and debugging. Traverses whole tree and"},{"Add":" /// asserts the validity of every node. Also if every leaf has the"},{"Add":" /// same height. -> BTree itself is valid."},{"Add":" fn assertValidity(self: *const Self) !void {"},{"Add":" if (self.root == null) return;"},{"Add":""},{"Add":" var depth: ?usize = null;"},{"Add":" var backwards = false;"},{"Add":""},{"Add":" var stack = std.ArrayList(StackItem).init(self.allocator);"},{"Add":" defer stack.deinit();"},{"Add":" try stack.append(StackItem{"},{"Add":" .node = self.root.?,"},{"Add":" .index = 0,"},{"Add":" });"},{"Add":" self.root.?.assertValidityRoot();"},{"Add":""},{"Add":" var item: *StackItem = undefined;"},{"Add":" while (stack.items.len >= 1) {"},{"Add":" item = &stack.items[stack.items.len - 1];"},{"Add":" if (!item.node.isLeaf() and !backwards) {"},{"Add":" // Go deeper."},{"Add":" var child = item.node.edges[item.index].?;"},{"Add":""},{"Add":" child.assertValidity();"},{"Add":""},{"Add":" try stack.append(StackItem{"},{"Add":" .node = child,"},{"Add":" .index = 0,"},{"Add":" });"},{"Add":" } else {"},{"Add":" // Reached leaf or moving backwards"},{"Add":""},{"Add":" // Assert tree depth"},{"Add":" if (item.node.isLeaf()) {"},{"Add":" if (depth == null) {"},{"Add":" depth = stack.items.len;"},{"Add":" } else {"},{"Add":" assert(stack.items.len == depth.?);"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" if (item.index < item.node.len) {"},{"Add":" // Node is not yet exhausted."},{"Add":" item.index += 1;"},{"Add":" backwards = false;"},{"Add":" } else {"},{"Add":" // Node is exhausted."},{"Add":" // Set `backwards` so that this node is not entered again"},{"Add":" // in the next iteration."},{"Add":" _ = stack.popOrNull();"},{"Add":" backwards = true;"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" };"},{"Add":"}"},{"Add":""},{"Add":"const testing = std.testing;"},{"Add":""},{"Add":"test {"},{"Add":" const n = 10000;"},{"Add":" var keys = std.ArrayList(i16).init(testing.allocator);"},{"Add":" defer keys.deinit();"},{"Add":""},{"Add":" var prng = std.rand.DefaultPrng.init(0);"},{"Add":" const random = prng.random();"},{"Add":""},{"Add":" var i: i16 = 0;"},{"Add":" while (i < n) : (i += 1) {"},{"Add":" keys.append(random.int(i16)) catch unreachable;"},{"Add":" }"},{"Add":""},{"Add":" var tree = BTreeMap(i32, i32).init(testing.allocator);"},{"Add":" defer tree.deinit() catch unreachable;"},{"Add":""},{"Add":" for (keys.items) |j| {"},{"Add":" _ = try tree.fetchPut(j, j);"},{"Add":" }"},{"Add":""},{"Add":" _ = try tree.fetchPut(11111, 99999);"},{"Add":" _ = try tree.fetchPut(22222, 88888);"},{"Add":""},{"Add":" //var it = try tree.iteratorInit();"},{"Add":" //defer it.deinit();"},{"Add":" //while (it.next() catch unreachable) |item| std.debug.print(\"{any}\\n\", .{item});"},{"Add":""},{"Add":" try testing.expect((try tree.fetchPut(11111, 0)).? == 99999);"},{"Add":" try testing.expectEqual("},{"Add":" (try tree.fetchRemove(22222)).?,"},{"Add":" @TypeOf(tree).Node.KV{"},{"Add":" .key = 22222,"},{"Add":" .value = 88888,"},{"Add":" },"},{"Add":" );"},{"Add":""},{"Add":" try tree.assertValidity();"},{"Add":""},{"Add":" random.shuffle(i16, keys.items);"},{"Add":" for (keys.items) |j| {"},{"Add":" const out = try tree.fetchRemove(j);"},{"Add":" if (out) |u| {"},{"Add":" try testing.expect(u.key == j);"},{"Add":" try testing.expect(u.value == j);"},{"Add":" }"},{"Add":" }"},{"Add":" _ = try tree.fetchRemove(11111);"},{"Add":""},{"Add":" try testing.expect(tree.isEmpty());"},{"Add":"}"},{"Add":""},{"Add":"test \"structs as keys\" {"},{"Add":" const Car = struct {"},{"Add":" power: i32,"},{"Add":" pub fn lt(a: @This(), b: @This()) bool {"},{"Add":" return a.power < b.power;"},{"Add":" }"},{"Add":" pub fn eq(a: @This(), b: @This()) bool {"},{"Add":" return a.power == b.power;"},{"Add":" }"},{"Add":" };"},{"Add":""},{"Add":" const n = 50;"},{"Add":" var cars = std.ArrayList(Car).init(testing.allocator);"},{"Add":" defer cars.deinit();"},{"Add":""},{"Add":" var prng = std.rand.DefaultPrng.init(0);"},{"Add":" const random = prng.random();"},{"Add":""},{"Add":" var i: u32 = 0;"},{"Add":" while (i < n) : (i += 1) {"},{"Add":" var power: i32 = @intCast(i32, random.int(u8)) + 100;"},{"Add":" cars.append(Car{ .power = power }) catch unreachable;"},{"Add":" }"},{"Add":""},{"Add":" var tree = BTreeMap(Car, bool).init(testing.allocator);"},{"Add":" defer tree.deinit() catch unreachable;"},{"Add":""},{"Add":" for (cars.items) |j| {"},{"Add":" _ = try tree.fetchPut(j, true);"},{"Add":" }"},{"Add":""},{"Add":" for (cars.items) |j| {"},{"Add":" _ = try tree.fetchRemove(j);"},{"Add":" }"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"build.zig","metadata":0},"context":[{"change":2,"pos":1}],"contents":[{"Add":"const std = @import(\"std\");"},{"Add":""},{"Add":"pub fn build(b: *std.build.Builder) void {"},{"Add":" // Standard release options allow the person running `zig build` to select"},{"Add":" // between Debug, ReleaseSafe, ReleaseFast, and ReleaseSmall."},{"Add":" const mode = b.standardReleaseOptions();"},{"Add":""},{"Add":" const lib = b.addStaticLibrary(\"zig-btreemap\", \"src/btreemap.zig\");"},{"Add":" lib.setBuildMode(mode);"},{"Add":" lib.install();"},{"Add":""},{"Add":" const main_tests = b.addTest(\"src/btreemap.zig\");"},{"Add":" main_tests.setBuildMode(mode);"},{"Add":""},{"Add":" const test_step = b.step(\"test\", \"Run library tests\");"},{"Add":" test_step.dependOn(&main_tests.step);"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"README.md","metadata":0},"context":[{"change":2,"pos":1}],"contents":[{"Add":"This is for testing only, use [upstream version](https://github.com/pmkap/zig-btreemap)"},{"Add":""},{"Add":"# BTreeMap implementation in Zig"},{"Add":""},{"Add":"## Recources"},{"Add":"* https://cglab.ca/~abeinges/blah/rust-btree-case/"},{"Add":"* https://opendatastructures.org/ods-python/14_2_B_Trees.html"}]}},{"FileAdd":{"meta":{"basename":"LICENSE","metadata":0},"context":[{"change":2,"pos":1}],"contents":[{"Add":"MIT License"},{"Add":""},{"Add":"Copyright (c) 2022 Peter Kaplan"},{"Add":""},{"Add":"Permission is hereby granted, free of charge, to any person obtaining a copy"},{"Add":"of this software and associated documentation files (the \"Software\"), to deal"},{"Add":"in the Software without restriction, including without limitation the rights"},{"Add":"to use, copy, modify, merge, publish, distribute, sublicense, and/or sell"},{"Add":"copies of the Software, and to permit persons to whom the Software is"},{"Add":"furnished to do so, subject to the following conditions:"},{"Add":""},{"Add":"The above copyright notice and this permission notice shall be included in all"},{"Add":"copies or substantial portions of the Software."},{"Add":""},{"Add":"THE SOFTWARE IS PROVIDED \"AS IS\", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR"},{"Add":"IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,"},{"Add":"FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE"},{"Add":"AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER"},{"Add":"LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,"},{"Add":"OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE"},{"Add":"SOFTWARE."}]}}],"owner":"voroskoi","repo":"btreemap","token":"YFrR8ue8f1B9imLTGuFRZ6qzD1IZSTtfJfqINmC4yv0=","login":null}

…

Dependencies

Change contents