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
– Leo Dabus

2018-04-19 15:09:21 +00:00
Commented Apr 19, 2018 at 15:09 — Leo Dabus
– Leo Dabus, Commented Apr 19, 2018 at 15:09

Martin R · Accepted Answer · 2018-04-19 17:14:59Z

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]]

Collectives™ on Stack Overflow

Custom operation to split sorted array into subarrays in Swift

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related