std: introduce orderedRemoveMany

This algorithm is non-trivial and makes sense for any data structure
that acts as an array list, so I thought it would make sense as a
method.

I have a real world case for this in a music player application
(deleting queue items).

Adds the method to:
* ArrayList
* ArrayHashMap
* MultiArrayList

1 files changed, 62 insertions, 0 deletions

diff --git a/lib/std/multi_array_list.zig b/lib/std/multi_array_list.zig
index 160a9f2fba..e4eb60bd93 100644
--- a/lib/std/multi_array_list.zig
+++ b/lib/std/multi_array_list.zig
@@ -350,6 +350,42 @@ pub fn MultiArrayList(comptime T: type) type {
             self.len -= 1;
         }
 
+        /// Remove the elements indexed by `sorted_indexes`. The indexes to be
+        /// removed correspond to the array list before deletion.
+        ///
+        /// Asserts:
+        /// * Each index to be removed is in bounds.
+        /// * The indexes to be removed are sorted ascending.
+        ///
+        /// Duplicates in `sorted_indexes` are allowed.
+        ///
+        /// This operation is O(N).
+        ///
+        /// Invalidates element pointers beyond the first deleted index.
+        pub fn orderedRemoveMany(self: *Self, sorted_indexes: []const usize) void {
+            if (sorted_indexes.len == 0) return;
+            const slices = self.slice();
+            var shift: usize = 1;
+            for (sorted_indexes[0 .. sorted_indexes.len - 1], sorted_indexes[1..]) |removed, end| {
+                if (removed == end) continue; // allows duplicates in `sorted_indexes`
+                const start = removed + 1;
+                const len = end - start; // safety checks `sorted_indexes` are sorted
+                inline for (fields, 0..) |_, field_index| {
+                    const field_slice = slices.items(@enumFromInt(field_index));
+                    @memmove(field_slice[start - shift ..][0..len], field_slice[start..][0..len]); // safety checks initial `sorted_indexes` are in range
+                }
+                shift += 1;
+            }
+            const start = sorted_indexes[sorted_indexes.len - 1] + 1;
+            const end = self.len;
+            const len = end - start; // safety checks final `sorted_indexes` are in range
+            inline for (fields, 0..) |_, field_index| {
+                const field_slice = slices.items(@enumFromInt(field_index));
+                @memmove(field_slice[start - shift ..][0..len], field_slice[start..][0..len]);
+            }
+            self.len = end - shift;
+        }
+
         /// Adjust the list's length to `new_len`.
         /// Does not initialize added items, if any.
         pub fn resize(self: *Self, gpa: Allocator, new_len: usize) !void {
@@ -1025,3 +1061,29 @@ test "struct with many fields" {
     try ManyFields.doTest(testing.allocator, 100);
     try ManyFields.doTest(testing.allocator, 200);
 }
+
+test "orderedRemoveMany" {
+    const gpa = testing.allocator;
+
+    var list: MultiArrayList(struct { x: usize }) = .empty;
+    defer list.deinit(gpa);
+
+    for (0..10) |n| {
+        try list.append(gpa, .{ .x = n });
+    }
+
+    list.orderedRemoveMany(&.{ 1, 5, 5, 7, 9 });
+    try testing.expectEqualSlices(usize, &.{ 0, 2, 3, 4, 6, 8 }, list.items(.x));
+
+    list.orderedRemoveMany(&.{0});
+    try testing.expectEqualSlices(usize, &.{ 2, 3, 4, 6, 8 }, list.items(.x));
+
+    list.orderedRemoveMany(&.{});
+    try testing.expectEqualSlices(usize, &.{ 2, 3, 4, 6, 8 }, list.items(.x));
+
+    list.orderedRemoveMany(&.{ 1, 2, 3, 4 });
+    try testing.expectEqualSlices(usize, &.{2}, list.items(.x));
+
+    list.orderedRemoveMany(&.{0});
+    try testing.expectEqualSlices(usize, &.{}, list.items(.x));
+}