[swift-evolution] Sequence/Collection Enhancements

[Ben Cohen]

> On Feb 20, 2017, at 7:38 AM, Ole Begemann <ole at oleb.net> wrote:
> 
>> 
>> On 17 Feb 2017, at 01:39, Ben Cohen via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
>> 
>> Hi swift-evolution,
>> 
>> Following up on Ted’s post regarding the opening up of stage 2, I’m starting a thread to discuss additive algorithms for Sequence and Collection.
>> 
>> Here is a list of commonly requested algorithms to operate on Sequence or Collection:
>> 
>> In-place transformations:
>> transform elements in a MutableCollection using a closure i.e. in-place map
>> remove(where:) that takes a predicate i.e. in-place filter
>> remove(indices:) that takes a Sequence of Index
> Is it possible to implement this (efficiently) with RangeReplaceableCollection's current feature set?

In-place, I don’t think so, because of the shuffling-down-being-O(n) problem. 

It is possible with a combo of MutableCollection and RangeReplaceableCollection, because MutableCollection implies constant-time mutation of a single element:

extension MutableCollection where Self: RangeReplaceableCollection {
    mutating func remove(where predicate: (Iterator.Element) -> Bool) {
        guard var i = index(where: predicate) else { return }
        var j = index(after: i)
        while j != endIndex {
            let e = self[j]
            if !predicate(e) {
                // here's where you need MutableCollection...
                self[i] = e
                formIndex(after: &i)
            }
            formIndex(after: &j)
        }
        // and this is the part you need RRC for...
        removeSubrange(i..<endIndex)
    }
}

But if you tried to implement this with RRC alone, you’d hit the challenge of single-element replacement not necessarily being O(n). String is the poster child for this problem since the graphemes you might be wanting to remove are variable width.

Making this a full-fledged member of one of RangeReplaceableCollection would allow types that can’t offer constant-time single element replacement, but can implement an algorithm that slides down values over the top of others efficiently in one pass, to provide an efficient implementation. Additionally, types like Array or String that are backed by contiguous storage might be able to make use of lower-level memory operations. The default implementation could be to rebuild self from scratch using lazy filter, which while sub-optimal can at least be done in linear time.

> Since replaceSubrange(_:with:) potentially invalidates indices, you can't call it repeatedly and expect that the passed-in indices are still valid.
> 
> I suppose it's possible to create a new empty collection, then iterate over the existing collection's indices and append each element that doesn't match one of the indices to be removed, but that sounds a bit awkward to me. Is there a better solution?
> 
>> bulk operations (replace, remove, insert) on RangeReplaceableCollection for a Sequence of subranges
> This relates to my question above. Is there a better way to implement this than creating an new empty collection and iterating over the existing elements, replacing/skipping/inserting at the passed-in subranges?

In-place operations avoid having to allocate/free a whole new buffer, avoid copying the initial prefix of retained elements unnecessarily (a big deal if you are removing a small proportion of the whole, especially if you sometimes remove none), and also enable customized efficient implementations for specific types. Collections that didn’t implement them could just get a default that builds up from scratch like you describe.

If we had multi-range bulk remove, you could also implement remove(where:) using it, at the cost of having to do it in two passes.

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