[swift-evolution] [Pitch] remove(at: Set<Index>)

[Dmitri Gribenko]

On Sat, Jun 18, 2016 at 9:09 PM, Karl via swift-evolution
<swift-evolution at swift.org> wrote:
> So like most good pitches, this one comes about because of a bug I recently fixed which seems common and subtle enough that I think it would be nice to include in the standard library.
>
> Removing a collection of elements at once from a collection. You might want to do this in some kind of advanced filtering code. In my case, our code was merging adjacent elements in-place, and storing a list of indexes that were no longer required because they were now part of a merged element, and then we cleaned up the duplicates by removing those indexes.
>
> A näive implementation might look like this:
>
> for index in indexesToRemove {
>     myArray.remove(at: index)
> }
>
> However, as the array is mutated, those indexes won’t make sense any more. You’ll end up with invalid results - for example, if you have the array [0,1,2] and indexesToRemove is [0,1], your resulting array will actually be [1] (not [2], as expected). Actually removing a batch of indexes is subtly more complex. Here’s my generic implementation:
>
> extension RangeReplaceableCollection where Index:Hashable, Self:BidirectionalIndexable {
>
>         mutating func remove(at indexes: Set<Index>) {

Hi Karl,

This sounds like a good idea to me.  You can make this method even
more useful by making it generic over collections of appropriate
indices.  Then you can drop the Hashable requirement for indices.

>                 var removed : IndexDistance = 0
>                 for idx in indexes.sorted() {
>                         remove(at: index(idx, offsetBy: -removed))
>                         removed = removed.advanced(by: 1)

This implementation will not work correctly for all collections, since
removing an element at the beginning of the collection invalidates the
indices pointing at the tail.  Adjusting the index by "-removed" won't
help, the indices are invalidated already.  (Consider what happens in
a UnicodeScalar String view where indices have to jump over variable
number of code units in the underlying storage.)

You can make it correct (and work even faster, in O(n)) by walking
from the start, and moving the elements into place, and then
truncating the collection.  You will need to require
MutableCollection.

You can make a variant that works for collections that are not
MutableCollections, but then the runtime will be O(n^2).  You will
need to remove elements one by one walking from the end and shifting
the tail of the collection.

Dmitri

-- 
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr at gmail.com>*/