Merge remote-tracking branch 'origin/master' into llvm7

1 files changed, 70 insertions, 6 deletions

diff --git a/std/array_list.zig b/std/array_list.zig
index b71f5be6ab..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
@@ -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);
         }
 
@@ -102,6 +102,26 @@ pub fn AlignedArrayList(comptime T: type, comptime A: u29) type {
             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 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();
+
+            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);
             mem.copy(T, self.items[self.len..], items);
@@ -232,6 +252,33 @@ test "basic ArrayList test" {
     assert(list.pop() == 33);
 }
 
+test "std.ArrayList.swapRemove" {
+    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.swapRemove(3) == 4);
+    assert(list.at(3) == 7);
+    assert(list.len == 6);
+
+    //remove from end
+    assert(list.swapRemove(5) == 6);
+    assert(list.len == 5);
+
+    //remove from front
+    assert(list.swapRemove(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();
@@ -266,19 +313,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);
 }