What exactly are the guarantees for index safety across mutations? Both
Collection and Indexable stop short of making any kind of guarantees about what
happens to indexes after you mutate. For example, popFirst() has the potential
to invalidate all stored indexes, but you wouldn’t know that if you were just
working in terms of Collection.
If we can guarantee tail-end removal is safe, a minimalist’s solution could be:
extension RangeReplaceableCollection {
mutating func remove<S:Sequence where S.Iterator.Element == Index>(at
indexes: S) {
for idx in indexes.sorted(isOrderedBefore: >) {
remove(at: idx)
}
}
}
Maybe with Array having a more optimal implementation if those sorted indexes
form a continuous range.
Karl
> On 19 Jun 2016, at 06:58, Saagar Jha <[email protected]> wrote:
>
> This isn’t actually that complex, especially if you ditch the “C-style” for
> loop algorithm and switch it to, as you mentioned, “filtering code”. filter,
> enumerated (to get indices), and map (to go back to elements) are more than
> up to the task. Plus, this is much more efficient.
>
> var myArray = [0, 1, 2]
> let indices: Set = [0, 1]
> myArray = myArray.enumerated().filter {
> return !indices.contains($0.offset)
> }.map {
> return $0.element // to get the elements back
> }
> print(myArray) // prints “[2]"
> Adding it to the standard library might be useful, but it’s not as hard as it
> looks.
>
>
>
> On Sat, Jun 18, 2016 at 9:09 PM Karl via swift-evolution
> <[email protected] <mailto:[email protected]>> 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>) {
> var removed : IndexDistance = 0
> for idx in indexes.sorted() {
> remove(at: index(idx, offsetBy: -removed))
> removed = removed.advanced(by: 1)
> }
> }
> }
>
> I think it would be nice to have this in the standard library. I think it’s a
> reasonably common problem and it’d be nice to make it easier for people.
>
> Karl
>
>
> _______________________________________________
> swift-evolution mailing list
> [email protected] <mailto:[email protected]>
> https://lists.swift.org/mailman/listinfo/swift-evolution
> <https://lists.swift.org/mailman/listinfo/swift-evolution>
> --
> -Saagar Jha
_______________________________________________
swift-evolution mailing list
[email protected]
https://lists.swift.org/mailman/listinfo/swift-evolution
