Skip to content

Instantly share code, notes, and snippets.

@magurotuna
Last active December 4, 2023 03:55
Show Gist options
  • Save magurotuna/90335c8df3df00392d966156a371f4fa to your computer and use it in GitHub Desktop.
Save magurotuna/90335c8df3df00392d966156a371f4fa to your computer and use it in GitHub Desktop.
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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment