//! A list with its capacity in its type: plain data, so it can live in //! State (no pointers) and migrate there element by element. const std = @import("std"); /// `buffer` and `len` are public fields, so the host's console and scripts /// reach elements by path (`boids.buffer[3].pos[0]`, `boids.len`). /// /// Every method clamps `len` to the capacity: after a reload that shrinks /// the capacity, a saved `len` may be larger than the new buffer, and the /// list then holds `capacity` elements rather than indexing out of bounds. /// The names and errors are std's (`ArrayList`'s bounded methods). pub fn List(comptime T: type, comptime cap: u32) type { return struct { const Self = @This(); pub const capacity = cap; buffer: [cap]T = default_buffer, len: u32 = 0, /// T's own defaults when it has them for every field, zeroes for /// numbers, the first tag for enums; otherwise undefined. Never /// `std.mem.zeroes`, which fails on enums with no 0 tag. const default_buffer: [cap]T = if (defaultOf(T)) |d| @splat(d) else undefined; pub fn slice(l: *Self) []T { return l.buffer[0..l.count()]; } pub fn constSlice(l: *const Self) []const T { return l.buffer[0..l.count()]; } /// `len`, clamped to the capacity. pub fn count(l: *const Self) u32 { return @min(l.len, cap); } pub fn appendBounded(l: *Self, item: T) error{OutOfMemory}!void { const n = l.count(); if (n == cap) return error.OutOfMemory; l.buffer[n] = item; l.len = n + 1; } /// Removes the element at `i`, keeping the order of the rest. pub fn orderedRemove(l: *Self, i: u32) T { const n = l.count(); const item = l.buffer[i]; std.mem.copyForwards(T, l.buffer[i .. n - 1], l.buffer[i + 1 .. n]); l.len = n - 1; return item; } /// Removes the element at `i`, moving the last one into its place. pub fn swapRemove(l: *Self, i: u32) T { const n = l.count(); const item = l.buffer[i]; l.buffer[i] = l.buffer[n - 1]; l.len = n - 1; return item; } pub fn clear(l: *Self) void { l.len = 0; } }; } fn defaultOf(comptime T: type) ?T { return switch (@typeInfo(T)) { .int, .float, .vector => std.mem.zeroes(T), .bool => false, .optional => null, .array => |a| if (defaultOf(a.child)) |d| @splat(d) else null, .@"enum" => |e| if (e.mode == .exhaustive) @field(T, e.field_names[0]) else @enumFromInt(0), .@"struct" => |s| { for (s.field_attrs) |attrs| if (attrs.default_value_ptr == null) return null; return .{}; }, else => null, }; } test "append, remove, clamp after a capacity shrink" { const Kind = enum(u8) { a = 1, b = 2 }; const Item = struct { kind: Kind = .b, x: f32 = 1 }; var l: List(Item, 4) = .{}; try std.testing.expectEqual(Kind.b, l.buffer[3].kind); for (0..4) |i| try l.appendBounded(.{ .x = @floatFromInt(i) }); try std.testing.expectError(error.OutOfMemory, l.appendBounded(.{})); try std.testing.expectEqual(@as(f32, 1), l.orderedRemove(1).x); try std.testing.expectEqual(@as(f32, 2), l.constSlice()[1].x); try std.testing.expectEqual(@as(f32, 0), l.swapRemove(0).x); try std.testing.expectEqual(@as(f32, 3), l.slice()[0].x); try std.testing.expectEqual(@as(usize, 2), l.slice().len); // A saved len from a bigger list. l.len = 10; try std.testing.expectEqual(@as(usize, 4), l.constSlice().len); try std.testing.expectError(error.OutOfMemory, l.appendBounded(.{})); _ = l.swapRemove(0); try std.testing.expectEqual(@as(u32, 3), l.len); } test "defaults for element types without struct defaults" { const E = enum(u8) { one = 1, two = 2 }; const a: List(E, 3) = .{}; try std.testing.expectEqual(E.one, a.buffer[2]); const b: List(f32, 3) = .{}; try std.testing.expectEqual(@as(f32, 0), b.buffer[1]); const c: List(@Vector(2, f32), 2) = .{}; try std.testing.expectEqual(@as(f32, 0), c.buffer[1][0]); const NoDefault = struct { x: f32 }; const d: List(NoDefault, 2) = .{}; try std.testing.expectEqual(@as(u32, 0), d.len); }