1//! Effectively a stack of u1 values implemented using ArrayList(u8).
 2
 3const BitStack = @This();
 4
 5const std = @import("std");
 6const Allocator = std.mem.Allocator;
 7const ArrayList = std.array_list.Managed;
 8
 9bytes: std.array_list.Managed(u8),
10bit_len: usize = 0,
11
12pub fn init(allocator: Allocator) @This() {
13    return .{
14        .bytes = std.array_list.Managed(u8).init(allocator),
15    };
16}
17
18pub fn deinit(self: *@This()) void {
19    self.bytes.deinit();
20    self.* = undefined;
21}
22
23pub fn ensureTotalCapacity(self: *@This(), bit_capacity: usize) Allocator.Error!void {
24    const byte_capacity = (bit_capacity + 7) >> 3;
25    try self.bytes.ensureTotalCapacity(byte_capacity);
26}
27
28pub fn push(self: *@This(), b: u1) Allocator.Error!void {
29    const byte_index = self.bit_len >> 3;
30    if (self.bytes.items.len <= byte_index) {
31        try self.bytes.append(0);
32    }
33
34    pushWithStateAssumeCapacity(self.bytes.items, &self.bit_len, b);
35}
36
37pub fn peek(self: *const @This()) u1 {
38    return peekWithState(self.bytes.items, self.bit_len);
39}
40
41pub fn pop(self: *@This()) u1 {
42    return popWithState(self.bytes.items, &self.bit_len);
43}
44
45/// Standalone function for working with a fixed-size buffer.
46pub fn pushWithStateAssumeCapacity(buf: []u8, bit_len: *usize, b: u1) void {
47    const byte_index = bit_len.* >> 3;
48    const bit_index = @as(u3, @intCast(bit_len.* & 7));
49
50    buf[byte_index] &= ~(@as(u8, 1) << bit_index);
51    buf[byte_index] |= @as(u8, b) << bit_index;
52
53    bit_len.* += 1;
54}
55
56/// Standalone function for working with a fixed-size buffer.
57pub fn peekWithState(buf: []const u8, bit_len: usize) u1 {
58    const byte_index = (bit_len - 1) >> 3;
59    const bit_index = @as(u3, @intCast((bit_len - 1) & 7));
60    return @as(u1, @intCast((buf[byte_index] >> bit_index) & 1));
61}
62
63/// Standalone function for working with a fixed-size buffer.
64pub fn popWithState(buf: []const u8, bit_len: *usize) u1 {
65    const b = peekWithState(buf, bit_len.*);
66    bit_len.* -= 1;
67    return b;
68}
69
70const testing = std.testing;
71test BitStack {
72    var stack = BitStack.init(testing.allocator);
73    defer stack.deinit();
74
75    try stack.push(1);
76    try stack.push(0);
77    try stack.push(0);
78    try stack.push(1);
79
80    try testing.expectEqual(@as(u1, 1), stack.peek());
81    try testing.expectEqual(@as(u1, 1), stack.pop());
82    try testing.expectEqual(@as(u1, 0), stack.peek());
83    try testing.expectEqual(@as(u1, 0), stack.pop());
84    try testing.expectEqual(@as(u1, 0), stack.pop());
85    try testing.expectEqual(@as(u1, 1), stack.pop());
86}