Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
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"]
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])]
Owner

erica commented Aug 25, 2017

 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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment