Implementing a Collection.removingIndices(_:)

Be careful that if the Collection indices is not 0..<count, the operation might not mean the same thing.

1 Like

In Foundation. There’s no reason I can perceive it shouldn’t be in the standard library — apart from the evolution slog, that is.

You can do this algorithm in place. It turns out that the classic stable partition algorithm only visits each element once, before it is moved, so you can partition the elements based on their indices. That's probably true of the simpler half-stable partition as well, but I haven't checked.

Actually it looks like @vadian may have posted this answer above.

1 Like

Aren't these all O(N²) algorithms?

Yes indeed, in fact all of them have big trouble dealing with arrays with more than 1000 elements.
The only faster implementations are @nnnnnnnn version:

Iterative copying
extension Collection {
    func removingIndices<S: Sequence>(_ indicesToRemove: S) -> [Element]
        where S.Element == Index
    {
        var result: [Element] = []
        var low = startIndex
        for high in indicesToRemove {
            result.append(contentsOf: self[low..<high])
            low = index(after: high)
        }
        result.append(contentsOf: self[low...])
        return result
    }
}

and @vadian version:

It's all about partitions
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...)
    }
}

@dabrahams the "Iterative copying" version is not O(n²), isn't it? If it is, then I don't understand how it is much faster than the other (bad) implementations.
Thank you for your amazing WWDC presentation :ok_hand:

Does the constraint “MutableCollection & RangeReplaceableCollection” provide sufficient guarantees of index stability for this?

Here's someone saying that the new method actually appears on the Standard Library documentation: RangeReplaceableCollection

The specific addition that the documentation says to have been made is remove(atOffsets offsets: IndexSet). There also is a new method: applying(_ difference: CollectionDifference<Self.Element>) -> Self?. These changes were made in Catalina Beta 5.

The question raised on the other thread is whether these changes actually are changes to the Standard Library, as the documentation indicates, or whether they might be extensions made within the SwiftUI framework.

I can't find the implementation of the method in the stdlib code though (unless its yet to be committed publicly).

remove(atOffsets:) is implemented in SwiftUI as an extension. I don't know why the list page miscategorises it, but if you click through and look at the sidebar, it says 'Framework: SwiftUI'.

applying(_:) is correctly grouped in the standard library domain and was introduced in the collection diffing proposal.

I started a proposal for this a while ago but didn't have the time to take it forwards. If anyone want to take it on you are quite welcome: [Pre-pitch] removeAll(at:)

Actually, with a little more digging, it appears the remove(atOffsets:) method is implemented in the Foundation framework.

And, as you indicate, applying(_:) is anticipated to be included in the Standard Library, but has not yet been accepted.

I observe these bare facts, here. I'll post discussion in the other thread.

It was accepted.

When working with RRCs, you're constrained in what you can do — whenever you call a mutating RRC method you invalidate all existing indices (though some concrete collections, like array, won't have problems).

If you constrain to both MutableCollection and RRC, you can use swapAt (which doesn't invalidate indices) to rearrange as much as necessary, and then remove a single batch of elements at the end of your algorithm, once you don't need to access any other indices.

5 Likes

Right. Back in January it was accepted.

I've been referencing the most recent thread, which was a re-review on account of an amendment. The proposal itself is still listed as being in Active Review (June 19 - 25 2019).

Where is it guaranteed? I couldn't find it in the doc.

1 Like

That guarantee belongs to the protocol, but it doesn't appear to be documented explicitly. The closest we get is in the Conforming to the MutableCollection Protocol section of the protocol docs, but even that doesn't spell out that other indices must also be unaffected by changes to the value at a particular position.

1 Like

It could be heavily implied, but I think we should still be conservative on this.

We don't need to be conservative on this — it's core to the main function of the MutableCollection protocol. Without that guarantee, none of the in-place algorithms that MutableCollection is intended to enable (partition, reverse, sort, rotate, etc) would be possible. We just need improved docs!

7 Likes

I agree, that the discrepancy should be resolved. Either to remove the assumption that appeared else where, or include it into the doc.

Terms of Service

Privacy Policy

Cookie Policy