summaryrefslogtreecommitdiff
path: root/src/sketch/list.zig
blob: 8040a5d7f2b65cf73450d17b4aad88c072c093da (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
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);
}