From a1cafa650d4ba64404f5db932a40c67b96ccfd1e Mon Sep 17 00:00:00 2001 From: Bas van den Berg Date: Fri, 13 Jul 2018 22:35:34 +0200 Subject: Improve ArrayList insert unit tests. --- std/array_list.zig | 21 +++++++++++++++++++-- 1 file changed, 19 insertions(+), 2 deletions(-) (limited to 'std/array_list.zig') diff --git a/std/array_list.zig b/std/array_list.zig index b71f5be6ab..c3e01a4637 100644 --- a/std/array_list.zig +++ b/std/array_list.zig @@ -266,19 +266,36 @@ test "insert ArrayList test" { defer list.deinit(); try list.append(1); + try list.append(2); + try list.append(3); try list.insert(0, 5); assert(list.items[0] == 5); assert(list.items[1] == 1); + assert(list.items[2] == 2); + assert(list.items[3] == 3); +} + +test "insertSlice ArrayList test" { + var list = ArrayList(i32).init(debug.global_allocator); + defer list.deinit(); + try list.append(1); + try list.append(2); + try list.append(3); + try list.append(4); try list.insertSlice(1, []const i32{ 9, 8, }); - assert(list.items[0] == 5); + assert(list.items[0] == 1); assert(list.items[1] == 9); assert(list.items[2] == 8); + assert(list.items[3] == 2); + assert(list.items[4] == 3); + assert(list.items[5] == 4); const items = []const i32{1}; try list.insertSlice(0, items[0..0]); - assert(list.items[0] == 5); + assert(list.len == 6); + assert(list.items[0] == 1); } -- cgit v1.2.3 From fe98a2da70cedaad47ea70d58399e04eb1c7ead2 Mon Sep 17 00:00:00 2001 From: Bas van den Berg Date: Fri, 13 Jul 2018 23:01:21 +0200 Subject: Add a copyBackwards to fix the broken insert methods for ArrayList. --- std/array_list.zig | 4 ++-- std/mem.zig | 18 ++++++++++++++++++ 2 files changed, 20 insertions(+), 2 deletions(-) (limited to 'std/array_list.zig') diff --git a/std/array_list.zig b/std/array_list.zig index c3e01a4637..5deb3c5fb1 100644 --- a/std/array_list.zig +++ b/std/array_list.zig @@ -85,7 +85,7 @@ pub fn AlignedArrayList(comptime T: type, comptime A: u29) type { try self.ensureCapacity(self.len + 1); self.len += 1; - mem.copy(T, self.items[n + 1 .. self.len], self.items[n .. self.len - 1]); + mem.copyBackwards(T, self.items[n + 1 .. self.len], self.items[n .. self.len - 1]); self.items[n] = item; } @@ -93,7 +93,7 @@ pub fn AlignedArrayList(comptime T: type, comptime A: u29) type { try self.ensureCapacity(self.len + items.len); self.len += items.len; - mem.copy(T, self.items[n + items.len .. self.len], self.items[n .. self.len - items.len]); + mem.copyBackwards(T, self.items[n + items.len .. self.len], self.items[n .. self.len - items.len]); mem.copy(T, self.items[n .. n + items.len], items); } diff --git a/std/mem.zig b/std/mem.zig index 555e1e249d..41c5d0c8a3 100644 --- a/std/mem.zig +++ b/std/mem.zig @@ -125,6 +125,7 @@ pub const Allocator = struct { /// Copy all of source into dest at position 0. /// dest.len must be >= source.len. +/// dest.ptr must be <= src.ptr. pub fn copy(comptime T: type, dest: []T, source: []const T) void { // TODO instead of manually doing this check for the whole array // and turning off runtime safety, the compiler should detect loops like @@ -135,6 +136,23 @@ pub fn copy(comptime T: type, dest: []T, source: []const T) void { dest[i] = s; } +/// Copy all of source into dest at position 0. +/// dest.len must be >= source.len. +/// dest.ptr must be >= src.ptr. +pub fn copyBackwards(comptime T: type, dest: []T, source: []const T) void { + // TODO instead of manually doing this check for the whole array + // and turning off runtime safety, the compiler should detect loops like + // this and automatically omit safety checks for loops + @setRuntimeSafety(false); + assert(dest.len >= source.len); + var i = source.len; + while(i > 0){ + i -= 1; + dest[i] = source[i]; + } +} + + pub fn set(comptime T: type, dest: []T, value: T) void { for (dest) |*d| d.* = value; -- cgit v1.2.3 From a0c1498e65d34e4f7d003ef1a804a87fa6c83ed3 Mon Sep 17 00:00:00 2001 From: tgschultz Date: Wed, 11 Jul 2018 12:52:30 -0500 Subject: Added `remove` to ArrayList --- std/array_list.zig | 48 +++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 47 insertions(+), 1 deletion(-) (limited to 'std/array_list.zig') diff --git a/std/array_list.zig b/std/array_list.zig index 5deb3c5fb1..dd9647f2d5 100644 --- a/std/array_list.zig +++ b/std/array_list.zig @@ -101,6 +101,25 @@ pub fn AlignedArrayList(comptime T: type, comptime A: u29) type { const new_item_ptr = try self.addOne(); new_item_ptr.* = item; } + + /// Removes the element at the specified index and returns it. + // The empty slot is filled from the end of the list. + pub fn remove(self: *Self, n: usize) T { + if(self.len - 1 == n) return self.pop(); + + var old_item = self.at(n); + self.set(n, self.pop()); + return old_item; + } + + pub fn removeOrError(self: *Self, n: usize) !T { + if(n >= self.len) return error.OutOfBounds; + if(self.len - 1 == n) return self.pop(); + + var old_item = self.at(n); + try self.setOrError(n, self.pop()); + return old_item; + } pub fn appendSlice(self: *Self, items: []align(A) const T) !void { try self.ensureCapacity(self.len + items.len); @@ -157,7 +176,7 @@ pub fn AlignedArrayList(comptime T: type, comptime A: u29) type { it.count += 1; return val; } - + pub fn reset(it: *Iterator) void { it.count = 0; } @@ -232,6 +251,33 @@ test "basic ArrayList test" { assert(list.pop() == 33); } +test "remove ArrayList test" { + var list = ArrayList(i32).init(debug.global_allocator); + defer list.deinit(); + + try list.append(1); + try list.append(2); + try list.append(3); + try list.append(4); + try list.append(5); + try list.append(6); + try list.append(7); + + //remove from middle + assert(list.remove(3) == 4); + assert(list.at(3) == 7); + assert(list.len == 6); + + //remove from end + assert(list.remove(5) == 6); + assert(list.len == 5); + + //remove from front + assert(list.remove(0) == 1); + assert(list.at(0) == 5); + assert(list.len == 4); +} + test "iterator ArrayList test" { var list = ArrayList(i32).init(debug.global_allocator); defer list.deinit(); -- cgit v1.2.3 From b44332f5a663c8e96e546d6a2b6071bf96ce9bcb Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Sat, 14 Jul 2018 10:01:45 -0400 Subject: std.ArrayList - rename remove to swapRemove --- std/array_list.zig | 43 ++++++++++++++++++++++--------------------- 1 file changed, 22 insertions(+), 21 deletions(-) (limited to 'std/array_list.zig') diff --git a/std/array_list.zig b/std/array_list.zig index dd9647f2d5..8d7bde46a1 100644 --- a/std/array_list.zig +++ b/std/array_list.zig @@ -41,8 +41,8 @@ pub fn AlignedArrayList(comptime T: type, comptime A: u29) type { return self.items[0..self.len]; } - pub fn at(self: Self, n: usize) T { - return self.toSliceConst()[n]; + pub fn at(self: Self, i: usize) T { + return self.toSliceConst()[i]; } /// Sets the value at index `i`, or returns `error.OutOfBounds` if @@ -101,21 +101,22 @@ pub fn AlignedArrayList(comptime T: type, comptime A: u29) type { const new_item_ptr = try self.addOne(); new_item_ptr.* = item; } - + /// Removes the element at the specified index and returns it. - // The empty slot is filled from the end of the list. - pub fn remove(self: *Self, n: usize) T { - if(self.len - 1 == n) return self.pop(); - - var old_item = self.at(n); - self.set(n, self.pop()); + /// The empty slot is filled from the end of the list. + pub fn swapRemove(self: *Self, i: usize) T { + if (self.len - 1 == i) return self.pop(); + + const slice = self.toSlice(); + const old_item = slice[i]; + slice[i] = self.pop(); return old_item; } - + pub fn removeOrError(self: *Self, n: usize) !T { - if(n >= self.len) return error.OutOfBounds; - if(self.len - 1 == n) return self.pop(); - + if (n >= self.len) return error.OutOfBounds; + if (self.len - 1 == n) return self.pop(); + var old_item = self.at(n); try self.setOrError(n, self.pop()); return old_item; @@ -176,7 +177,7 @@ pub fn AlignedArrayList(comptime T: type, comptime A: u29) type { it.count += 1; return val; } - + pub fn reset(it: *Iterator) void { it.count = 0; } @@ -251,7 +252,7 @@ test "basic ArrayList test" { assert(list.pop() == 33); } -test "remove ArrayList test" { +test "std.ArrayList.swapRemove" { var list = ArrayList(i32).init(debug.global_allocator); defer list.deinit(); @@ -262,18 +263,18 @@ test "remove ArrayList test" { try list.append(5); try list.append(6); try list.append(7); - + //remove from middle - assert(list.remove(3) == 4); + assert(list.swapRemove(3) == 4); assert(list.at(3) == 7); assert(list.len == 6); - + //remove from end - assert(list.remove(5) == 6); + assert(list.swapRemove(5) == 6); assert(list.len == 5); - + //remove from front - assert(list.remove(0) == 1); + assert(list.swapRemove(0) == 1); assert(list.at(0) == 5); assert(list.len == 4); } -- cgit v1.2.3