Scratch that: it should still be a Set and Index should still be Hashable.
Otherwise the order of the indexes could be important and there may be
duplicates. That’s a level of sophistication where you should know how about
index invalidation while mutating and can do it manually.
extension RangeReplaceableCollection where Index : Hashable {
mutating func remove(at indexes: Set<Index>) {
for idx in indexes.sorted(isOrderedBefore: >) {
remove(at: idx)
}
}
}
It’s not actually O(n^2) - it’s O(m*n), where m is never larger than n, and
likely much smaller if n is large. Otherwise, you should probably use an
inclusive filter and create a new instance, rather than than removing most of
your large numbers of elements in-place.
So it’s probably better to loop over m. Given that, I’m not sure how we’d
improve on the O(n) remove-at-index. That said, I’m seeing lots of weirdness in
Xcode 8 (which may just be my machine), so I’m not really certain what
MutableCollection even provides — apparently it supports in-place ’sort’ (via
CMD+click), but it’s not in auto-complete and trying to use it is a compile
error.
Karl
> On 19 Jun 2016, at 07:59, Karl <[email protected]> wrote:
>
> 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]
>> <mailto:[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
