From 582bfc893c01cccec0aae7ea7eec18bcf97cd836 Mon Sep 17 00:00:00 2001 From: Julien Dessaux Date: Thu, 5 May 2022 22:28:07 +0200 Subject: Fixed a misunderstanding about allocations (I did too much go and nim!) --- src/field.zig | 120 ++++++++++++++++++++++++++++++++++++----------------- src/main.zig | 1 + src/stack.zig | 17 ++++---- src/stackStack.zig | 26 ++++++------ 4 files changed, 106 insertions(+), 58 deletions(-) diff --git a/src/field.zig b/src/field.zig index 85835cd..8066a65 100644 --- a/src/field.zig +++ b/src/field.zig @@ -1,6 +1,7 @@ const std = @import("std"); const Line = struct { + allocator: std.mem.Allocator, x: i64 = 0, data: std.ArrayList(i64), fn blank(l: *Line, x: i64) void { @@ -24,7 +25,7 @@ const Line = struct { } } test "blank" { - var l = Line.init(std.testing.allocator); + var l = try Line.init(std.testing.allocator); defer l.deinit(); const initial = [_]i64{ 'b', 'a', '@', 'c', 'd', 'e', 'f' }; try l.data.appendSlice(initial[0..]); @@ -62,16 +63,17 @@ const Line = struct { } fn deinit(self: *Line) void { self.data.deinit(); + self.allocator.destroy(self); } fn get(l: *Line, x: i64) i64 { if (x >= l.x and x < l.x + @intCast(i64, l.len())) return l.data.items[@intCast(usize, x - @intCast(i64, l.x))]; return ' '; } - fn init(allocator: std.mem.Allocator) Line { - const c = std.ArrayList(i64).init(allocator); - return Line{ - .data = c, - }; + fn init(allocator: std.mem.Allocator) !*Line { + var l = try allocator.create(Line); + l.allocator = allocator; + l.data = std.ArrayList(i64).init(allocator); + return l; } inline fn len(l: Line) usize { return l.data.items.len; @@ -107,7 +109,7 @@ const Line = struct { } } test "set" { - var l = Line.init(std.testing.allocator); + var l = try Line.init(std.testing.allocator); defer l.deinit(); try l.set(-1, '@'); const zero = [_]i64{'@'}; @@ -141,22 +143,22 @@ const Line = struct { } }; -const Field = struct { +pub const Field = struct { allocator: std.mem.Allocator, x: i64 = 0, y: i64 = 0, - lines: std.ArrayList(Line), + lines: std.ArrayList(*Line), lx: usize = 0, - pub fn blank(f: *Field, x: i64, y: i64) !void { + pub fn blank(f: *Field, x: i64, y: i64) void { const ly = @intCast(i64, f.lines.items.len); - if (ly == 0) return error.EmptyFieldError; + if (ly == 0) return; if (y < f.y or y >= f.y + ly) return; // outside the field - var l = &f.lines.items[@intCast(usize, y - f.y)]; + var l = f.lines.items[@intCast(usize, y - f.y)]; if (l.len() == 0) return; // the line is already empty l.blank(x); if (l.len() == 0) { if (ly == 1) { - return error.EmptyFieldError; + return; } else if (y == f.y) { // we need to remove leading lines l.deinit(); var i: usize = 1; @@ -164,7 +166,7 @@ const Field = struct { f.lines.items[i].deinit(); } f.y += @intCast(i64, i); - std.mem.copy(Line, f.lines.items[0 .. f.lines.items.len - i], f.lines.items[i..]); + std.mem.copy(*Line, f.lines.items[0 .. f.lines.items.len - i], f.lines.items[i..]); f.lines.items.len -= i; } else if (y == f.y + ly - 1) { // we need to remove trailing lines l.deinit(); @@ -189,62 +191,63 @@ const Field = struct { test "blank" { var f = try Field.init(std.testing.allocator); defer f.deinit(); - try std.testing.expectEqual(f.blank(1, 0), error.EmptyFieldError); - var moins2 = Line.init(std.testing.allocator); + var moins2 = try Line.init(std.testing.allocator); try moins2.set(-3, 'a'); - var moins1 = Line.init(std.testing.allocator); + var moins1 = try Line.init(std.testing.allocator); try moins1.set(6, 'b'); - var zero = Line.init(std.testing.allocator); + var zero = try Line.init(std.testing.allocator); try zero.set(-4, 'c'); - var un = Line.init(std.testing.allocator); + var un = try Line.init(std.testing.allocator); try un.set(-8, 'd'); - var deux = Line.init(std.testing.allocator); + var deux = try Line.init(std.testing.allocator); try deux.set(12, 'e'); - const initial = [_]Line{ moins2, moins1, zero, un, deux }; + const initial = [_]*Line{ moins2, moins1, zero, un, deux }; try f.lines.appendSlice(initial[0..]); f.x = -8; f.lx = 21; f.y = -2; - try f.blank(6, -1); + f.blank(6, -1); try std.testing.expectEqual(f.x, -8); try std.testing.expectEqual(f.lx, 21); try std.testing.expectEqual(f.y, -2); try std.testing.expectEqual(f.lines.items.len, 5); try std.testing.expectEqual(f.lines.items[1].len(), 0); - try f.blank(-3, -2); + f.blank(-3, -2); try std.testing.expectEqual(f.x, -8); try std.testing.expectEqual(f.lx, 21); try std.testing.expectEqual(f.y, 0); try std.testing.expectEqual(f.lines.items.len, 3); - try f.blank(-8, 1); + f.blank(-8, 1); try std.testing.expectEqual(f.x, -4); try std.testing.expectEqual(f.lx, 17); try std.testing.expectEqual(f.y, 0); try std.testing.expectEqual(f.lines.items.len, 3); try std.testing.expectEqual(f.lines.items[1].len(), 0); - try f.blank(12, 2); + f.blank(12, 2); try std.testing.expectEqual(f.x, -4); try std.testing.expectEqual(f.lx, 1); try std.testing.expectEqual(f.y, 0); try std.testing.expectEqual(f.lines.items.len, 1); - try std.testing.expectEqual(f.blank(-4, 0), error.EmptyFieldError); } pub fn deinit(self: *Field) void { for (self.lines.items) |*l| { - l.deinit(); + l.*.deinit(); } self.lines.deinit(); + self.allocator.destroy(self); } pub fn get(f: *Field, x: i64, y: i64) i64 { if (y >= f.y and y < f.y + @intCast(i64, f.lines.items.len)) return f.lines.items[@intCast(usize, y - @intCast(i64, f.y))].get(x); return ' '; } - pub fn init(allocator: std.mem.Allocator) !Field { - var lines = std.ArrayList(Line).init(allocator); - return Field{ - .allocator = allocator, - .lines = lines, - }; + pub fn init(allocator: std.mem.Allocator) !*Field { + var f = try allocator.create(Field); + f.allocator = allocator; + f.lines = std.ArrayList(*Line).init(allocator); + return f; + } + inline fn isIn(f: *Field, x: i64, y: i64) bool { + return x >= f.x and y >= f.y and x < f.x + @intCast(i64, f.lx) and y < f.y + @intCast(i64, f.lines.items.len); } pub fn load(f: *Field, reader: anytype) !void { if (f.lines.items.len > 0) return error.FIELD_NOT_EMPTY; @@ -252,10 +255,10 @@ const Field = struct { var x: i64 = 0; var y: i64 = 0; while (true) { - var i: usize = 0; var buffer: [4096]u8 = undefined; var l = try reader.read(buffer[0..]); if (l == 0) return; + var i: usize = 0; while (i < l) : (i += 1) { if (lastIsCR) { lastIsCR = false; @@ -303,6 +306,15 @@ const Field = struct { try std.testing.expectEqual(f2.load(cr2), error.GOT_CR_WITHOUT_LF); } pub fn set(f: *Field, x: i64, y: i64, v: i64) !void { + if (f.lines.items.len == 0) { + f.x = x; + f.y = y; + var l = try f.lines.addOne(); + l.* = try Line.init(f.allocator); + try l.*.set(x, v); + f.lx = 1; + return; + } if (v == ' ') return f.blank(x, y); if (y >= f.y) { if (y < f.y + @intCast(i64, f.lines.items.len)) { // the line exists @@ -310,9 +322,9 @@ const Field = struct { } else { // append lines var i: usize = f.lines.items.len; while (i < y - f.y) : (i += 1) { - try f.lines.append(Line.init(f.allocator)); + try f.lines.append(try Line.init(f.allocator)); } - var l = Line.init(f.allocator); + var l = try Line.init(f.allocator); try l.set(x, v); try f.lines.append(l); } @@ -320,13 +332,13 @@ const Field = struct { const oldLen = f.lines.items.len; f.lines.items.len += @intCast(usize, f.y - y); try f.lines.ensureUnusedCapacity(f.lines.items.len); - std.mem.copyBackwards(Line, f.lines.items[@intCast(usize, f.y - y)..], f.lines.items[0..oldLen]); - var l = Line.init(f.allocator); + std.mem.copyBackwards(*Line, f.lines.items[@intCast(usize, f.y - y)..], f.lines.items[0..oldLen]); + var l = try Line.init(f.allocator); try l.set(x, v); f.lines.items[0] = l; var i: usize = 1; while (i < @intCast(usize, f.y - y)) : (i += 1) { - f.lines.items[i] = Line.init(f.allocator); + f.lines.items[i] = try Line.init(f.allocator); } f.y = y; } @@ -371,6 +383,36 @@ const Field = struct { try std.testing.expectEqual(f.get(8, 2), '2'); try std.testing.expectEqual(f.get(9, 2), ' '); } + pub fn step(f: *Field, x: i64, y: i64, dx: i64, dy: i64) struct { x: i64, y: i64 } { + var a = x + dx; + var b = y + dy; + if (f.isIn(a, b)) return .{ .x = a, .y = b }; + // # We are stepping outside, we need to wrap the Lahey-space + a = x; + b = y; + while (true) { + var c = a - dx; + var d = b - dy; + if (!f.isIn(c, d)) return .{ .x = a, .y = b }; + a = c; + b = d; + } + } + test "step" { + const minimal = std.io.fixedBufferStream("@").reader(); + var f = try Field.init(std.testing.allocator); + defer f.deinit(); + try f.load(minimal); + try std.testing.expectEqual(f.step(0, 0, 0, 0), .{ .x = 0, .y = 0 }); + try std.testing.expectEqual(f.step(0, 0, 1, 0), .{ .x = 0, .y = 0 }); + const hello = std.io.fixedBufferStream("64+\"!dlroW ,olleH\">:#,_@\n").reader(); + var fHello = try Field.init(std.testing.allocator); + defer fHello.deinit(); + try fHello.load(hello); + try std.testing.expectEqual(fHello.step(3, 0, 0, 0), .{ .x = 3, .y = 0 }); + try std.testing.expectEqual(fHello.step(3, 0, 1, 0), .{ .x = 4, .y = 0 }); + try std.testing.expectEqual(fHello.step(0, 0, -1, 0), .{ .x = 23, .y = 0 }); + } }; test "all" { diff --git a/src/main.zig b/src/main.zig index 6f63b8d..14bada3 100644 --- a/src/main.zig +++ b/src/main.zig @@ -1,5 +1,6 @@ const std = @import("std"); const field = @import("field.zig"); +const pointer = @import("pointer.zig"); const stackStack = @import("stackStack.zig"); pub fn main() anyerror!void { diff --git a/src/stack.zig b/src/stack.zig index 6ba587b..ce70df0 100644 --- a/src/stack.zig +++ b/src/stack.zig @@ -2,12 +2,14 @@ const std = @import("std"); const vector = std.meta.Vector(2, i64); pub const Stack = struct { + allocator: std.mem.Allocator, data: std.ArrayList(i64), pub fn clear(self: *Stack) void { self.data.clearRetainingCapacity(); } pub fn deinit(self: *Stack) void { self.data.deinit(); + self.allocator.destroy(self); } pub fn duplicate(self: *Stack) !void { if (self.data.items.len > 0) { @@ -15,7 +17,7 @@ pub const Stack = struct { } } test "duplicate" { - var s = Stack.init(std.testing.allocator); + var s = try Stack.init(std.testing.allocator); defer s.deinit(); try s.duplicate(); try std.testing.expectEqual(s.popVector(), @as(vector, [2]i64{ 0, 0 })); @@ -25,10 +27,11 @@ pub const Stack = struct { try std.testing.expectEqual(s.popVector(), @as(vector, [2]i64{ 2, 2 })); try std.testing.expectEqual(s.popVector(), @as(vector, [2]i64{ 1, 2 })); } - pub fn init(allocator: std.mem.Allocator) Stack { - return Stack{ - .data = std.ArrayList(i64).init(allocator), - }; + pub fn init(allocator: std.mem.Allocator) !*Stack { + var s = try allocator.create(Stack); + s.allocator = allocator; + s.data = std.ArrayList(i64).init(allocator); + return s; } pub fn pop(self: *Stack) i64 { return if (self.data.popOrNull()) |v| v else 0; @@ -45,7 +48,7 @@ pub const Stack = struct { try self.data.appendSlice(v[0..]); } test "pushVector" { - var s = Stack.init(std.testing.allocator); + var s = try Stack.init(std.testing.allocator); defer s.deinit(); try s.pushVector([2]i64{ 1, -1 }); try s.pushVector([2]i64{ 2, -2 }); @@ -60,7 +63,7 @@ pub const Stack = struct { try self.pushVector([2]i64{ v[1], v[0] }); } test "swap" { - var s = Stack.init(std.testing.allocator); + var s = try Stack.init(std.testing.allocator); defer s.deinit(); try s.swap(); try std.testing.expectEqual(s.popVector(), @as(vector, [2]i64{ 0, 0 })); diff --git a/src/stackStack.zig b/src/stackStack.zig index 15578d3..717be3d 100644 --- a/src/stackStack.zig +++ b/src/stackStack.zig @@ -1,25 +1,27 @@ const std = @import("std"); const stack = @import("stack.zig"); -const vector = std.meta.Vector(2, i64); pub const StackStack = struct { - data: std.ArrayList(stack.Stack), + allocator: std.mem.Allocator, + data: std.ArrayList(*stack.Stack), toss: *stack.Stack, pub fn deinit(self: *StackStack) void { - for (self.data.items) |*s| { + for (self.data.items) |s| { s.deinit(); } self.data.deinit(); + self.allocator.destroy(self); } - pub fn init(allocator: std.mem.Allocator) !StackStack { - var ss = std.ArrayList(stack.Stack).init(allocator); - errdefer ss.deinit(); - var s = try ss.addOne(); - s.* = stack.Stack.init(allocator); - return StackStack{ - .data = ss, - .toss = s, - }; + pub fn init(allocator: std.mem.Allocator) !*StackStack { + var ss = try allocator.create(StackStack); + errdefer allocator.destroy(ss); + ss.allocator = allocator; + ss.data = std.ArrayList(*stack.Stack).init(allocator); + errdefer ss.data.deinit(); + var s = try ss.data.addOne(); + s.* = try stack.Stack.init(allocator); + ss.toss = s.*; + return ss; } pub inline fn toss(self: *StackStack) *stack.Stack { return self.toss; -- cgit v1.2.3