# SE-0270 (Review #2): Add Collection Operations on Noncontiguous Elements

**URL:** <https://forums.swift.org/t/se-0270-review-2-add-collection-operations-on-noncontiguous-elements/31653>\
**Category:** Proposal Reviews\
**Created:** [December 13, 2019, 6:22pm UTC](https://forums.swift.org/t/se-0270-review-2-add-collection-operations-on-noncontiguous-elements/31653 "2019-12-13T18:22:30Z")\
**Posts on this page:** 1\
**Showing post:** 31

<div class="post-metadata">

**Author:** ![dabrahams](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/dabrahams/32/9815_2.png) [@dabrahams](https://forums.swift.org/u/dabrahams)\
**Post date:** [December 18, 2019, 3:20am UTC](https://forums.swift.org/t/se-0270-review-2-add-collection-operations-on-noncontiguous-elements/31653/31 "2019-12-18T03:20:39Z")

</div>

# `gather` Should Be Independent of `RangeSet`

_[I have a few issues with the proposal that I'll be raising in separate posts.]_

One of the issues I had with the previous proposal was that it failed to separate independent concerns. The most glaring examples—the methods that mutate a `RangeSet` based on a `Collection`—were removed from in this proposal, but one still remains: there's an overload of `gather` that takes a `RangeSet` argument.

To review, the proposed `gather` methods are as follows:

```swift
extension MutableCollection {
    /// Collects the elements at the given indices just before the element at 
    /// the specified index.
    @discardableResult
    public mutating func gather(
        _ indices: RangeSet<Index>, at insertionPoint: Index
    ) -> Range<Index>

    /// Collects the elements that satisfy the given predicate just before
    /// the element at the specified index.
    @discardableResult
    public mutating func gather(
        at insertionPoint: Index, where predicate: (Element) -> Bool
    ) -> Range<Index>
}

```

Why is the first method's first parameter a `RangeSet`? Its _algorithm_ will work with any representation of a set of a collection's indices. In fact, all it needs is a predicate that tells us whether the element at a given index should be gathered. If someone is already working with a `Set<Index>`, or already has a predicate that answers the question, we should not force them to reconstitute it as a `RangeSet<Index>`. That code looks like this:

```swift
let s = someSetOfIndices()

// O(a.count), plus an allocation
let rs = RangeSet(
        a.indices.lazy
            .filter { i in s.contains(i) }
            .map { i in i..<a.index(after: i))

a.gather(rs, at: destination)

```

Actually, that's pretty fancy code. It's more likely they'd end up with this, which performs worse:

```swift
let s = someSetOfIndices()

// Same big-O, but probably many allocations
var rs = RangeSet<A.Index>()
for i in a.indices where s.contains(i) {
   rs.insert(contentsOf: i..<a.index(after: i))
}

a.gather(rs, at: destination)

```

and I doubt most people would be aware of the difference.

The second `gather` overload is _almost_ what we'd need to solve the problem, but its predicate works on elements, rather than indices. With a `gather` method that takes a predicate over indices, the user could just write:

```swift
let s = someSetOfIndices()
a.gather(at: destination) { i in s.contains(i) }

```

That version of `gather` could be declared as follows (but see below for a problem):

```swift
    /// Collects the elements at positions satisfying the given predicate
    /// just before the element at the specified index, preserving their
    /// relative order.
    @discardableResult
    public mutating func gather(
        at insertionPoint: Index, where predicate: (Index) -> Bool
    ) -> Range<Index>

```

## The One True `gather`

It's tempting to think we could use this new gather method to do the work of the second overload:

```swift
a.gather(at: destination) { i in somePredicateOverElements(a[i]) }

```

The problem is that the closure captures `a`, which will force the first mutation made by `gather` to copy `a`'s storage, even if it was otherwise uniquely-referenced.

It's also problematic to add this new gather method as an overload, because there are common cases where the `Index` type is the same as that of the `Element` (e.g. `Array<Int>`), which would make invoking the method ambiguous.

So, if we are going to solve this problem with one method taking a predicate argument, it should be a binary predicate over elements and indices:

```swift
    /// Collects the elements satisfying the given predicate over their
    /// values and positions just before the element at the specified index,
    /// preserving their relative order.
    @discardableResult
    public mutating func gather(
        at gatheringPlace: Index, 
        where predicate: (Element, Index) -> Bool
    ) -> Range<Index>

```

Using it with a `RangeSet` or a `Set<Index>` would be equally simple:

```swift
a.gather(at: gatheringPlace) { _, i in someSetOfIndices.contains(i) }

```

Once you have this method, it seems to me that the second overload buys very little; you get to drop “`, _`” from

```swift
a.gather(at: gatheringPlace) { e, _ in somePredicate(e) }

```

## The Generic Approach

Another way of making `gather` independent of `RangeSet` would be to

- introduce a primitive set protocol that only supports containment testing
- make the first `gather` overload generic over the set type
- preserve the second `gather` overload

But this seems to add lots of complexity with little benefit. You still need two overloads. That primitive set protocol is, semantically, nothing more than a predicate function that answers the containment question. Also, if what you're starting with is a predicate over indices, you'd have to build a conforming wrapper type just to use it, which would interrupt the flow of code.

## Conclusion

`gather` should be a single method taking a binary predicate as suggested above. The simplicity of the result, both for the library and for its users, is telling us that's the right design. I hope we'll listen.

-Dave

---

_[View the full topic](https://forums.swift.org/t/se-0270-review-2-add-collection-operations-on-noncontiguous-elements/31653)._
