Custom operation to split sorted array into subarrays in Swift

Question

I want to write a custom operation on a sorted Array (or Collection or Sequence, whatever) that does the following:

Starting from the beginning, it looks at each adjacent pair of elements. If the condition is met among the two, move on to the next pair, otherwise split it. So in the end, I would have an array of arrays, where the condition is satisfied among the elements within the same subarray, but not between different subarrays. Is the following correct and efficient?

extension Array {
    public func splitSorted(by condition: (Element, Element)->(Bool)) -> [[Element]] {
        var result = [[Element]]()
        var start = 0
        var end = 0

        while end != self.count - 1 {
            while end < self.count && condition(self[start], self[end]) {
                end += 1
            }
            result.append(Array(self[start..<end]))
            start = end
        }

        return result
    }
}

edit your question and show your attempt – Leo Dabus Apr 19 '18 at 15:09 — Leo Dabus, Apr 19 '18 at 15:09

Martin R · Accepted Answer · 2018-04-19T17:14:59.843

Your code does not work correctly because:

You do not compare adjacent elements.
You start by comparing the first element with itself, this can lead to an never-terminating loop.
An empty array is not handled correctly.

Here is a working variation of your approach:

extension Array {
    public func splitSorted(by condition: (Element, Element)->(Bool)) -> [[Element]] {
        var result = [[Element]]()
        var start = startIndex
        while start != endIndex {
            var end = start
            repeat {
                end += 1
            } while end != endIndex && condition(self[end - 1], self[end])
            result.append(Array(self[start..<end]))
            start = end
        }
        return result
    }
}

Example:

let arr = [1, 2, 3, 2, 3, 4, 3, 4, 5]
let split = arr.splitSorted(by: <)
print(split) // [[1, 2, 3], [2, 3, 4], [3, 4, 5]]

A generalization to Sequence would be:

extension Sequence {
    public func splitSorted(by condition: (Element, Element)->(Bool)) -> [[Element]] {
        var it = makeIterator()
        guard var currentElem = it.next() else {
            return [] // Input sequence is empty
        }
        var result = [[Element]]()
        var currentSegment = [currentElem]
        while let nextElem = it.next() {
            if condition(currentElem, nextElem) {
                // Append to current segment:
                currentSegment.append(nextElem)
            } else {
                // Start new segment:
                result.append(currentSegment)
                currentSegment = [nextElem]
            }
            currentElem = nextElem
        }
        result.append(currentSegment)
        return result
    }
}

Example (group Fibonacci numbers by same parity):

// From https://stackoverflow.com/a/40203183/1187415
let fibs = sequence(state: (0, 1),
                    next: { (pair: inout (Int, Int)) -> Int? in
                        defer { pair = (pair.1, pair.0 + pair.1) }
                        return pair.1
                    })

print(fibs.prefix(12).splitSorted(by: { ($0 - $1) % 2 == 0 }))
// [[1, 1], [2], [3, 5], [8], [13, 21], [34], [55, 89], [144]]

Custom operation to split sorted array into subarrays in Swift

1 Answers1