177 lines
3.8 KiB
Zig
177 lines
3.8 KiB
Zig
const std = @import("std");
|
|
const Allocator = std.mem.Allocator;
|
|
const expect = std.testing.expect;
|
|
const testingAllocator = std.testing.allocator;
|
|
|
|
|
|
pub fn LList(comptime T: type) type {
|
|
return struct {
|
|
const Self = @This();
|
|
first: ?*Node(T),
|
|
alloc: Allocator,
|
|
counter: u64,
|
|
|
|
|
|
pub fn init(this: *Self, allocator: Allocator) void {
|
|
this.alloc = allocator;
|
|
this.first = null;
|
|
this.counter = 0;
|
|
}
|
|
|
|
pub fn deinit(this: *Self) void {
|
|
|
|
if (this.first == null) {
|
|
return;
|
|
}
|
|
|
|
var currentNode: *Node(T) = this.first orelse unreachable;
|
|
|
|
while (true) {
|
|
if (currentNode.next == null){
|
|
break;
|
|
}
|
|
|
|
const nextNode = currentNode.next orelse unreachable;
|
|
var breakNext = false;
|
|
|
|
if (nextNode.next == null) {
|
|
breakNext = true;
|
|
}
|
|
|
|
currentNode.deinit();
|
|
|
|
currentNode = nextNode;
|
|
|
|
if (breakNext == true) {
|
|
break;
|
|
}
|
|
}
|
|
currentNode.deinit();
|
|
this.counter = 0;
|
|
}
|
|
|
|
|
|
pub fn add(this: *Self, value: T ) !*Node(T){
|
|
|
|
const newNode: *Node(T) = try this.alloc.create(Node(T));
|
|
try newNode.init(this.alloc, value, this.first);
|
|
this.first = newNode;
|
|
|
|
this.counter = this.counter + 1;
|
|
|
|
return newNode;
|
|
}
|
|
|
|
pub fn size(this: *Self) u64{
|
|
|
|
return this.counter;
|
|
}
|
|
|
|
};
|
|
}
|
|
|
|
|
|
pub fn Node(comptime T: type) type {
|
|
return struct {
|
|
const Self = @This();
|
|
alloc: Allocator,
|
|
next: ?*Self,
|
|
value: *T,
|
|
|
|
pub fn init(this: *Self, allocator: Allocator, value: T, next: ?*Self) !void {
|
|
this.alloc = allocator;
|
|
this.next = next;
|
|
|
|
this.value = try this.alloc.create(T);
|
|
this.value.* = value;
|
|
}
|
|
|
|
|
|
pub fn deinit(this: *Self) void {
|
|
this.alloc.destroy(this.value);
|
|
this.alloc.destroy(this);
|
|
}
|
|
};
|
|
}
|
|
|
|
pub fn main() !void {
|
|
|
|
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
|
|
const allocator = gpa.allocator();
|
|
|
|
var testList: LList(u64) = undefined;
|
|
testList.init(allocator);
|
|
|
|
_ = try testList.add(10);
|
|
_ = try testList.add(20);
|
|
|
|
testList.deinit();
|
|
}
|
|
|
|
|
|
test "init()" {
|
|
|
|
var testList: LList(u64) = undefined;
|
|
testList.init(testingAllocator);
|
|
|
|
try expect(testList.first == null);
|
|
try expect(testList.counter == 0);
|
|
|
|
testList.deinit();
|
|
|
|
}
|
|
|
|
test "deinit()" {
|
|
|
|
var testList: LList(u64) = undefined;
|
|
testList.init(testingAllocator);
|
|
|
|
_ = try testList.add(1);
|
|
_ = try testList.add(2);
|
|
|
|
testList.deinit();
|
|
|
|
}
|
|
|
|
test "add()" {
|
|
|
|
var testList: LList(u64) = undefined;
|
|
testList.init(testingAllocator);
|
|
|
|
const firstNode = try testList.add(1);
|
|
const secondNode = try testList.add(2);
|
|
const thirdNode = try testList.add(3);
|
|
const fourthNode = try testList.add(4);
|
|
|
|
try expect(firstNode.value.* == 1);
|
|
try expect(secondNode.value.* == 2);
|
|
try expect(thirdNode.value.* == 3);
|
|
try expect(fourthNode.value.* == 4);
|
|
|
|
try expect(testList.first == fourthNode);
|
|
try expect(fourthNode.next == thirdNode);
|
|
try expect(thirdNode.next == secondNode);
|
|
try expect(secondNode.next == firstNode);
|
|
try expect(firstNode.next == null);
|
|
|
|
testList.deinit();
|
|
|
|
}
|
|
|
|
|
|
test "size()" {
|
|
|
|
var testList: LList(u64) = undefined;
|
|
testList.init(testingAllocator);
|
|
|
|
_ = try testList.add(1);
|
|
_ = try testList.add(2);
|
|
_ = try testList.add(3);
|
|
_ = try testList.add(4);
|
|
|
|
try expect(testList.size() == 4);
|
|
|
|
testList.deinit();
|
|
|
|
}
|