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

[Dave Abrahams]

on Sun Jun 19 2016, Haravikk <swift-evolution at swift.org> wrote:

>> On 19 Jun 2016, at 11:12, Haravikk via swift-evolution <swift-evolution at swift.org> wrote:
>> 
>> I think the following should work for the generic case, and is pretty similar:
>> 
>> extension MutableCollection {
>> 	public mutating func remove(indices: Set<Index>) {
>> 		var index = self.startIndex
>> 		self = self.filter {
>> 			let result = indices.contains(index)
>> 			self.formIndex(after: &index)
>> 			return result
>> 		}
>> 	}
>> }
>
> Apologies for the double-post but I’m honour bound to follow up that my generic method is a load of nonsense at the moment; it’s missing some kind of constructor (I don’t recall if there’s a common option that will satisfy this), also, due to the way .filter {} currently works even in its lazy form it can end up calling the filter closure more than once per item, so advancing the index currently won’t work as expected (elements are skipped, children murdered, it’s just the worst).
>
> So yeah, best option to do this right now is with a proper loop over self.indices, but it still requires some kind constructor to build a new copy of the correct type.
>
> For arrays this is a bit simpler as you *can* safely remove indices in reverse order, since later indices cannot invalidate earlier ones, but this is reliant on the array’s indices being integers (reasonable enough, but not really correct in the strictest sense), so like so:
>
> 	extension Array {
> 		public mutating func remove(indices: Set<Index>) {
> 			for eachIndex in indices.sort(>) { // greater than should give descending order
> 				self.remove(at: eachIndex)
> 			}
> 		}
> 	}

This is still an O(N^2) algorithm.  You can do this in O(N) by taking
Dmitri's approach.

-- 
Dave