removeObjectsAtIndexes for Swift arrays

According to WWDC 2018 Session 223 – Embracing Algorithms an efficient solution is the half stable partition algorithm:

extension RangeReplaceableCollection where Self: MutableCollection, Index == Int {

    mutating func remove(at indexes : IndexSet) {
        guard var i = indexes.first, i < count else { return }
        var j = index(after: i)
        var k = indexes.integerGreaterThan(i) ?? endIndex
        while j != endIndex {
            if k != j { swapAt(i, j); formIndex(after: &i) }
            else { k = indexes.integerGreaterThan(k) ?? endIndex }
            formIndex(after: &j)
        }
        removeSubrange(i...)
    }
}

It moves all elements which are not in the index set to the end of the array just by swapping the elements. Half stable means the algorithm preserves the order of the left partition but doesn’t care about the order of the right side as the elements will be removed anyway. After the loop the variable i contains the first index of the items to be removed. The batch remove operation is inexpensive because no indexes will be shifted/rebuilt.

---

For example if you have an array

[0, 1, 2, 3, 4, 5, 6, 7]

and you want to remove the elements at index 2 and 4 the algorithm performs the following steps in the while loop (the initial value of the index j is the index after the first index to be removed):

• Index 3: Swap elements at index 2 and 3 → [0, 1, 3, 2, 4, 5, 6, 7]
• Index 4: No change
• Index 5: Swap elements at index 3 and 5 → [0, 1, 3, 5, 4, 2, 6, 7]
• Index 6: Swap elements at index 4 and 6 → [0, 1, 3, 5, 6, 2, 4, 7]

• Index 7: Swap elements at index 5 and 7 → [0, 1, 3, 5, 6, 7, 4, 2]

• Finally remove the elements at subrange 6...

---