partition.swift

extension Collection where Iterator.Element: Comparable {
    /// Returns an eagerly composed array of ordered elements
    /// split at each point where a user-supplied predicate
    /// evaluates to true.
    ///
    /// ```
    /// [1, 2, 2, 3, 3, 3, 1]
    ///   .partitioned(at: { $0 != $1.last! })
    /// // [[1], [2, 2], [3, 3, 3], [1]]
    ///
    /// [1, 2, 2, 3, 3, 3, 1]
    ///   .partitioned(at: { $0.count == 2 })
    /// // [[1 2], [2, 3], [3, 3], [1]]
    /// ```
    ///
    /// - Parameter predicate: a closure that tests whether a new element
    ///   should be added to the current partion
    /// - Parameter element: the element to be tested
    /// - Parameter currentPartition: a non-empty array, containing a
    ///   an ordered contiguous group of collection members
    ///
    /// - Returns: An array of partitioned collection elements
    public func partitioned(at predicate: (_ element: Iterator.Element, _ currentPartition: [Iterator.Element]) -> Bool ) -> [[Iterator.Element]] {
        var current: [Iterator.Element] = []
        var results: [[Iterator.Element]] = []
        for element in self {
            guard !current.isEmpty else { current = [element]; continue }
            switch predicate(element, current) {
            case true: results.append(current); current = [element]
            case false: current.append(element)
            }
        }
        guard !current.isEmpty else { return results }
        results.append(current)
        return results
    }
    
    /// Returns an eagerly composed array of ordered elements
    /// split at each point where a user-supplied predicate
    /// evaluates to true.
    ///
    /// ```
    /// [1, 2, 2, 3, 3, 3, 1]
    ///   .partitioned(where: !=)
    /// // [[1], [2, 2], [3, 3, 3], [1]]
    /// ```
    ///
    /// - Parameter predicate: a closure that tests whether a new element
    ///   should be added to the current partion
    /// - Parameter element: the element to be tested
    /// - Parameter mostRecent: the most recently included element
    ///
    /// - Returns: An array of partitioned collection elements
    public func partitioned(where predicate: @escaping (_ element: Iterator.Element, _ mostRecent: Iterator.Element) -> Bool ) -> [[Iterator.Element]] {
        // `partitioned(at:)` guarantees a non-empty array
        // as its second closure argument
        return self.partitioned(at: {
            return predicate($0, $1.last!)
        })
    }
}

let testArray = [1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 2, 3]

print(testArray.partitioned(at: { $0 != $1.last! }))
// [[1], [2, 2], [3, 3, 3], [1, 1, 1], [2, 2], [3]]

print(testArray.partitioned(where: !=))
// [[1], [2, 2], [3, 3, 3], [1, 1, 1], [2, 2], [3]]

print(testArray.partitioned(at: { $0 == $1.last! }))
// [[1, 2], [2, 3], [3], [3, 1], [1], [1, 2], [2, 3]]

print(testArray.partitioned(at: { $1.count == 5 }))
// [[1, 2, 2, 3, 3], [3, 1, 1, 1, 2], [2, 3]]

print([1, 2, 2, 3, 3, 3, 1].partitioned(at: { $1.count == 2 }))
// [[1, 2], [2, 3], [3, 3], [1]]

print("1223333111223"
    .characters
    .partitioned(at: { $0 != $1.last! })
    .map({ String($0) }))
// ["1", "22", "3333", "111", "22", "3"]

print("1223333111223"
    .characters
    .partitioned(where: !=)
    .map({ String($0) }))
// ["1", "22", "3333", "111", "22", "3"]

partitionSlices.swift

extension ArraySlice where Element: Comparable {
    /// Produces an array of slices representing the original
    /// slice split at each point where a user-supplied
    /// predicate evalutes to true.
    ///
    /// - Parameter predicate: a closure that tests whether a new element
    ///   should be added to the current partion
    /// - Parameter element: the element to be tested
    /// - Parameter nextElement: the successive element to be tested
    /// - Parameter maxPartitions: The maximum number of
    ///   subslices that can be produced
    ///
    /// - Returns: An array of array slices
    fileprivate func sliced(where predicate: (_ element: Element, _ nextElement: Element) -> Bool, maxPartitions: Int = .max ) -> [ArraySlice<Element>] {
        
        guard !isEmpty else { return [] }
        guard maxPartitions > 1, count > 1 else { return [self] }
        var (partitionIndex, nextPartitionIndex) = (startIndex, indices.index(after: startIndex))
        
        while nextPartitionIndex < endIndex, !predicate(self[partitionIndex], self[nextPartitionIndex]) {
            (partitionIndex, nextPartitionIndex) = (nextPartitionIndex, indices.index(after: nextPartitionIndex))
        }
        
        guard partitionIndex < endIndex else { return [self] }
        
        let (firstSlice, remainingSlice) = (self[startIndex ..<  nextPartitionIndex], self[nextPartitionIndex ..< endIndex])
        let rest = remainingSlice.sliced(where: predicate, maxPartitions: maxPartitions - 1)
        
        return [firstSlice] + rest
    }
}

extension Array where Element: Comparable {
    /// Produces an array of slices representing an
    /// array split at each point where a user-supplied
    /// predicate evalutes to true.
    ///
    /// ```
    /// [1, 2, 2, 3, 3, 3, 1]
    ///   .sliced(where: !=)
    /// // [ArraySlice([1]), ArraySlice([2, 2]), ArraySlice([3, 3, 3]), ArraySlice([1])]
    /// ```
    ///
    /// - Parameter predicate: a closure that tests whether a new element
    ///   should be added to the current partion
    /// - Parameter element: the element to be tested
    /// - Parameter nextElement: the successive element to be tested
    /// - Parameter maxPartitions: The maximum number of slices
    ///
    /// - Returns: An array of array slices
    public func sliced(where predicate: (_ element: Element, _ nextElement: Element) -> Bool, maxPartitions: Int = .max ) -> [ArraySlice<Element>] {
        return self[startIndex ..< endIndex].sliced(where: predicate, maxPartitions: maxPartitions)
    }
}

// Same value
let x = [1, 2, 2, 3, 3, 3, 1]
    .sliced(where: { $0 != $1 })
print(x)
// [ArraySlice([1]), ArraySlice([2, 2]), ArraySlice([3, 3, 3]), ArraySlice([1])]

// Run-length encoding
let xx = [1, 2, 2, 3, 3, 3, 3, 3, 1, 1, 2, 1, 1]
    .sliced(where: !=)
    .map { ($0.count, $0.first!) }
print(xx)
// [(1, 1), (2, 2), (5, 3), (2, 1), (1, 2), (2, 1)]

// Strings
let y = Array("aaaabbbbcccdef".characters)
    .sliced(where: !=)
    .map({ String($0) })
print(y)
// ["aaaa", "bbbb", "ccc", "d", "e", "f"]

// increasing subsequences
let z = [1, 2, 2, 1, 3, 3, 1].sliced(where: >)
print(z)
// [ArraySlice([1, 2, 2]), ArraySlice([1, 3, 3]), ArraySlice([1])]

// decreasing subsequences
let w = [1, 2, 2, 1, 3, 3, 1].sliced(where: <)
print(w)
// [ArraySlice([1]), ArraySlice([2, 2, 1]), ArraySlice([3, 3, 1])]

 extension Collection where Iterator.Element: Comparable, Index == Int {
    /// Returns an eagerly composed array of ordered elements
    /// split at each point where a user-supplied predicate
    /// evaluates to true.
    ///
    /// ```
    /// [1, 2, 2, 3, 3, 3, 1]
    ///   .partitioned(at: { $0 != $1.last! })
    /// // [[1], [2, 2], [3, 3, 3], [1]]
    /// ```
    ///
    /// - Parameter predicate: a closure that tests whether a partition
    ///   should be introduced between two elements
    /// - Parameter element: the first element to be tested
    /// - Parameter nextElement: the next element in the collection
    ///
    /// - Returns: An array of partitioned collection elements
    public func partitioned(at predicate: (_ element: Iterator.Element, _ nextElement: Iterator.Element) -> Bool ) -> [[Iterator.Element]] {
        var copy: [Iterator.Element?] = Array(self)
        indices.dropLast()
            .filter({ return predicate(self[$0], self[indices.index(after: $0)]) })
            .reversed()
            .forEach { copy.insert(nil, at: Int($0 + 1)) }
        return copy
            .split(whereSeparator: { $0 == nil })
            .map({ each in each.flatMap({ $0 }) })
    }
}

For @soroush @khanlou