Add extract method to Array

Evolution Discussion
,
1 
extension Array {
    
    // rough implementation
    public mutating func extract(where wants: (Element) throws -> Bool) rethrows -> [Element] {
        var extracted = [Element]()
        for i in self.indices.reversed() {
            if try wants(self[i]) {
                extracted.insert(self.remove(at: i), at: 0)
            }
        }
        return extracted
    }
}

var a = [1, 2, 3, 4, 5]
let b = a.extract { $0 % 2 == 0 }
a //[1, 3, 5]
b //[2, 4]

Hi:
During my development history, especially for my poker game, I have used extract method a lot. I think it should be very common util function for array. Unfortunately, it's not inside standard library. Anyone else have same requirement? How do you think about it?

2

This is probably something that could be done with stablePartition, which curiously enough isn't in the stdlib, even though it was used in a WWDC presentation.

Then you could write:

var a = [1,2,3,4,5]
var b = [Int]()
(a,b) = a.stablePartition(isSuffixElement: { $0 % 2 == 0 })

(if you really want to mutate the arrays)

3 Likes
3

stablePartition is mutating and returns the index where the suffix starts. So it's not the same as extract.

4

I think @yxckjhasdkjh's point is that stablePartition gives you a very similar result, where elements are grouped in a similar way to extract, just as the start/end of a single array, instead of two. One can then (relatively) efficiently mutate the array to convert it into two separate ones:

let index = a.stablePartition(isSuffixElement: { $0 % 2 == 0 })
let b = Array(a.suffix(from: index))
a.removeSubrange(index...)

This particular approach has the advantage over the rough implementation above in that it has no explicit loops, and instead is just composed of a few successive linear time operations, and so is linear time itself. In contrast, both the repeated remove(at: i)s and insert(... at: 0)s result in the loop in the rough extract being O(self.count2), that is, quadratic in the length of the array (both of these can be fixed "manually", but I suspect using stablePartition or similar will be the easiest to understand).

Additionally, depending what one is doing, it may even be okay to avoid the suffix copy, and instead just work directly with the sliced version.

(I'll also just reiterate the presentation that @yxckjhasdkjh links to: it's an enjoyable and informative session to watch when designing algorithms like this.)

9 Likes
5

I think it would be useful to have both an in-place and copying variant, so I don't think extract would work (because I can't think of the copying counterpart's name). Currently, I've been implementing this with Dictionary:

let a = [1, 2, 3, 4, 5]
let d = Dictionary(grouping: a, by: { $0 % 2 == 0 })
let (evens, odds) = (d[true] ?? [], d[false] ?? [])

print(evens, odds)

It's quick/dirty, has extra branching, memory allocation, etc., but it does in a pinch for now.

6

True, I misunderstood the algorithm. I would find a "stablePartition" variant that splits the array into two arrays more useful; in my code, I've implemented this as split(accordingTo: (Element) => Bool).