diff options
Diffstat (limited to 'src/sketch/list.zig')
| -rw-r--r-- | src/sketch/list.zig | 109 |
1 files changed, 109 insertions, 0 deletions
diff --git a/src/sketch/list.zig b/src/sketch/list.zig new file mode 100644 index 0000000..8040a5d --- /dev/null +++ b/src/sketch/list.zig @@ -0,0 +1,109 @@ +//! 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); +} |
