https://zenn.dev/magurotuna/articles/zig-std-collections

zig_std_collections.zig

const std = @import("std");
const testing = std.testing;
const mem = std.mem;
const math = std.math;
const time = std.time;
const AutoHashMap = std.AutoHashMap;
const AutoArrayHashMap = std.AutoArrayHashMap;
const BufMap = std.BufMap;
const BufSet = std.BufSet;
const ArrayList = std.ArrayList;
const MultiArrayList = std.MultiArrayList;
const BoundedArray = std.BoundedArray;
const ComptimeStringMap = std.ComptimeStringMap;
const DynamicBitSet = std.DynamicBitSet;
const StaticBitSet = std.StaticBitSet;
const EnumArray = std.EnumArray;
const EnumMap = std.EnumMap;
const EnumSet = std.EnumSet;
const PriorityQueue = std.PriorityQueue;
const PriorityDequeue = std.PriorityDequeue;
const SegmentedList = std.SegmentedList;
const SinglyLinkedList = std.SinglyLinkedList;
const TailQueue = std.TailQueue;
const Treap = std.Treap;

test "AutoHashMap" {
    var map = AutoHashMap(u32, u8).init(testing.allocator);
    defer map.deinit();

    try map.put(0, 'a');
    try map.put(1, 'b');

    try testing.expectEqual(@as(u8, 'a'), map.get(0).?);
    try testing.expectEqual(@as(u8, 'b'), map.get(1).?);
    try testing.expect(map.get(2) == null);

    const prev = try map.fetchPut(0, 'x');
    try testing.expectEqual(@as(u32, 0), prev.?.key);
    try testing.expectEqual(@as(u8, 'a'), prev.?.value);
}

test "AutoArrayHashMap" {
    var map = AutoArrayHashMap(u32, u8).init(testing.allocator);
    defer map.deinit();

    try map.put(0, 'a');
    try map.put(1, 'b');

    var it = map.iterator();
    try testing.expectEqual(@as(u8, 'a'), it.next().?.value_ptr.*);
    try testing.expectEqual(@as(u8, 'b'), it.next().?.value_ptr.*);
    try testing.expect(it.next() == null);
}

test "BufMap" {
    var bufmap = BufMap.init(testing.allocator);
    defer bufmap.deinit();

    try bufmap.put("x", "1");
    try testing.expect(mem.eql(u8, bufmap.get("x").?, "1"));
    try testing.expect(1 == bufmap.count());

    try bufmap.put("x", "2");
    try testing.expect(mem.eql(u8, bufmap.get("x").?, "2"));
    try testing.expect(1 == bufmap.count());

    bufmap.remove("x");
    try testing.expect(0 == bufmap.count());
}

test "BufSet" {
    var bufset = BufSet.init(testing.allocator);
    defer bufset.deinit();

    try bufset.insert("x");
    try testing.expect(bufset.count() == 1);
    try testing.expect(bufset.contains("x"));
    bufset.remove("x");
    try testing.expect(bufset.count() == 0);
}

test "ArrayList" {
    var list = ArrayList(usize).init(std.testing.allocator);
    defer list.deinit();

    {
        var i: usize = 0;
        while (i < 10) : (i += 1) {
            try list.append(i);
        }
    }

    for (list.items) |v, i| {
        try testing.expectEqual(v, i);
    }

    try testing.expectEqual(@as(usize, 9), list.popOrNull().?);
    try testing.expectEqual(@as(usize, 9), list.items.len);
    try testing.expectEqual(@as(usize, 4), list.items[4]);
}

test "MultiArrayList" {
    const allocator = testing.allocator;

    const Foo = struct {
        field_one: u32,
        field_two: []const u8,
    };

    var list = MultiArrayList(Foo){};
    defer list.deinit(allocator);

    try testing.expectEqual(@as(usize, 0), list.items(.field_one).len);

    try list.append(allocator, .{
        .field_one = 1,
        .field_two = "foo",
    });
    try list.append(allocator, .{
        .field_one = 2,
        .field_two = "bar",
    });

    try testing.expectEqualSlices(u32, list.items(.field_one), &[_]u32{ 1, 2 });

    try testing.expectEqual(@as(usize, 2), list.items(.field_two).len);
    try testing.expectEqualStrings("foo", list.items(.field_two)[0]);
    try testing.expectEqualStrings("bar", list.items(.field_two)[1]);
}

test "BoundedArray" {
    const BoundedArrayMax4 = BoundedArray(u8, 4);

    try testing.expectError(error.Overflow, BoundedArrayMax4.init(8));

    var a = try BoundedArrayMax4.init(2);

    try testing.expectEqual(a.capacity(), 4);
    try testing.expectEqual(a.len, 2);
    try testing.expectEqual(a.slice().len, 2);
    try testing.expectEqual(a.constSlice().len, 2);

    try a.resize(4);
    try testing.expectEqual(a.len, 4);

    a.set(0, 42);
    try testing.expectEqual(a.get(0), 42);
}

test "ComptimeStringMap" {
    const KV = struct {
        @"0": []const u8,
        @"1": u32,
    };
    const map = ComptimeStringMap(u32, [_]KV{
        .{ .@"0" = "foo", .@"1" = 42 },
        .{ .@"0" = "barbaz", .@"1" = 99 },
    });

    try testing.expectEqual(@as(u32, 42), map.get("foo").?);
    try testing.expectEqual(@as(u32, 99), map.get("barbaz").?);
    try testing.expect(!map.has("hello"));
    try testing.expect(map.get("hello") == null);
}

test "StaticBitSet" {
    var bitset = StaticBitSet(4).initEmpty();

    try testing.expectEqual(@as(usize, 0), bitset.count());

    bitset.setValue(1, true);
    try testing.expectEqual(@as(usize, 1), bitset.count());
    try testing.expect(!bitset.isSet(0));
    try testing.expect(bitset.isSet(1));

    bitset.setRangeValue(.{ .start = 2, .end = 4 }, true);
    try testing.expectEqual(@as(usize, 3), bitset.count());
}

test "DynamicBitSet" {
    const size = @intCast(usize, time.timestamp()) % 60;

    var bitset = try DynamicBitSet.initEmpty(std.testing.allocator, size);
    defer bitset.deinit();

    try testing.expectEqual(@as(usize, 0), bitset.count());

    bitset.toggleAll();
    try testing.expectEqual(size, bitset.count());
}

test "EnumArray" {
    const A = EnumArray(enum {
        foo,
        bar,
    }, u32);
    try testing.expectEqual(@as(usize, 2), A.len);

    var a = A.initFill(42);
    try testing.expectEqual(@as(u32, 42), a.get(.foo));
    try testing.expectEqual(@as(u32, 42), a.get(.bar));
}

test "EnumMap" {
    const A = EnumMap(enum {
        foo,
        bar,
    }, u32);

    try testing.expectEqual(@as(usize, 2), A.len);

    var a = A{};
    try testing.expectEqual(@as(usize, 0), a.count());
    a.put(.foo, 42);
    try testing.expectEqual(@as(usize, 1), a.count());
    try testing.expect(a.contains(.foo));
    try testing.expect(!a.contains(.bar));
}

test "EnumSet" {
    const A = EnumSet(enum {
        foo,
        bar,
    });

    try testing.expectEqual(@as(usize, 2), A.len);

    var a = A{};
    try testing.expectEqual(@as(usize, 0), a.count());
    a.insert(.foo);
    try testing.expectEqual(@as(usize, 1), a.count());
    try testing.expect(a.contains(.foo));
    try testing.expect(!a.contains(.bar));

    a.remove(.foo);
    try testing.expectEqual(@as(usize, 0), a.count());
}

test "PriorityQueue" {
    {
        const MinHeap = PriorityQueue(u32, void, struct {
            fn lessThan(context: void, a: u32, b: u32) math.Order {
                _ = context;
                return math.order(a, b);
            }
        }.lessThan);
        var queue = MinHeap.init(testing.allocator, {});
        defer queue.deinit();

        try queue.add(12);
        try queue.add(7);
        try queue.add(23);
        try testing.expectEqual(@as(usize, 3), queue.len);
        try testing.expectEqual(@as(u32, 7), queue.remove());
        try testing.expectEqual(@as(u32, 12), queue.remove());
        try testing.expectEqual(@as(u32, 23), queue.remove());
    }

    {
        const MaxHeap = PriorityQueue(u32, void, struct {
            fn greaterThan(context: void, a: u32, b: u32) math.Order {
                _ = context;
                return math.order(a, b).invert();
            }
        }.greaterThan);
        var queue = MaxHeap.init(testing.allocator, {});
        defer queue.deinit();

        try queue.add(12);
        try queue.add(7);
        try queue.add(23);
        try testing.expectEqual(@as(usize, 3), queue.len);
        try testing.expectEqual(@as(u32, 23), queue.remove());
        try testing.expectEqual(@as(u32, 12), queue.remove());
        try testing.expectEqual(@as(u32, 7), queue.remove());
    }
}

test "PriorityDequeue" {
    const PQ = PriorityDequeue(u32, void, struct {
        fn lessThan(context: void, a: u32, b: u32) math.Order {
            _ = context;
            return math.order(a, b);
        }
    }.lessThan);
    var queue = PQ.init(testing.allocator, {});
    defer queue.deinit();

    try queue.add(12);
    try queue.add(7);
    try queue.add(23);
    try testing.expectEqual(@as(usize, 3), queue.len);
    try testing.expectEqual(@as(u32, 7), queue.removeMin());
    try testing.expectEqual(@as(u32, 23), queue.removeMax());
    try testing.expectEqual(@as(u32, 12), queue.removeMin());
}

test "SegmentedList" {
    const L = SegmentedList(u32, 2);
    var list = L{};
    defer list.deinit(testing.allocator);

    try list.append(testing.allocator, 1);
    try list.append(testing.allocator, 2);
    try list.append(testing.allocator, 3);
    try testing.expectEqual(@as(usize, 3), list.count());

    {
        var it = list.iterator(0);
        var s: u32 = 0;
        while (it.next()) |item| {
            s += item.*;
        }
        try testing.expectEqual(@as(u32, 6), s);
    }

    {
        var it = list.constIterator(0);
        var s: u32 = 0;
        while (it.next()) |item| {
            s += item.*;
        }
        try testing.expectEqual(@as(u32, 6), s);
    }
}

test "SinglyLinkedList" {
    const L = SinglyLinkedList(u32);
    var list = L{};

    try testing.expectEqual(@as(usize, 0), list.len());

    var one = L.Node{ .data = 1 };
    var two = L.Node{ .data = 2 };

    list.prepend(&two);
    list.prepend(&one);

    {
        var it = list.first;
        var val: u32 = 1;
        while (it) |node| : (it = node.next) {
            try testing.expectEqual(val, node.data);
            val += 1;
        }
    }

    try testing.expectEqual(@as(usize, 2), list.len());
    try testing.expectEqual(@as(u32, 1), list.first.?.data);
    try testing.expectEqual(@as(u32, 1), list.popFirst().?.data);
}

test "TailQueue" {
    const L = TailQueue(u32);
    var list = L{};

    try testing.expectEqual(@as(usize, 0), list.len);

    var one = L.Node{ .data = 1 };
    var two = L.Node{ .data = 2 };
    var three = L.Node{ .data = 3 };

    list.append(&two);
    list.append(&three);
    list.prepend(&one);
    try testing.expectEqual(@as(usize, 3), list.len);

    // 順方向イテレート
    {
        var it = list.first;
        var val: u32 = 1;
        while (it) |node| : (it = node.next) {
            try testing.expectEqual(val, node.data);
            val += 1;
        }
    }

    // 逆方向イテレート
    {
        var it = list.last;
        var val: u32 = 3;
        while (it) |node| : (it = node.prev) {
            try testing.expectEqual(val, node.data);
            val -= 1;
        }
    }
}

test "Treap" {
    const MyTreap = Treap(u32, math.order);
    const Node = MyTreap.Node;
    var treap = MyTreap{};
    var nodes: [10]Node = undefined;

    var i: u32 = 0;
    while (i < 10) : (i += 1) {
        var entry = treap.getEntryFor(i);
        try testing.expectEqual(i, entry.key);
        try testing.expect(entry.node == null);

        entry.set(&nodes[i]);
    }

    try testing.expectEqual(@as(u32, 9), treap.getMax().?.key);
    try testing.expectEqual(@as(u32, 0), treap.getMin().?.key);
}