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

[Karl]

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 <raziel.im+swift-evo at gmail.com> 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 <saagarjha28 at gmail.com <mailto:saagarjha28 at gmail.com>> 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 <swift-evolution at swift.org <mailto: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>) {
>>                 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
>> swift-evolution at swift.org <mailto:swift-evolution at swift.org>
>> https://lists.swift.org/mailman/listinfo/swift-evolution <https://lists.swift.org/mailman/listinfo/swift-evolution>
>> -- 
>> -Saagar Jha
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160619/7bf791b0/attachment.html>