mirror of
https://github.com/apple/swift-algorithms
synced 2026-11-22 04:10:39 +00:00
Compare commits
1
Commits
| Author | SHA1 | Date | |
|---|---|---|---|
|
|
0bd7f4dcb1 |
No files matched your search
+10
-2
@@ -1,4 +1,4 @@
|
||||
// swift-tools-version:5.7
|
||||
// swift-tools-version:6.0
|
||||
//===----------------------------------------------------------------------===//
|
||||
//
|
||||
// This source file is part of the Swift Algorithms open source project
|
||||
@@ -12,6 +12,13 @@
|
||||
|
||||
import PackageDescription
|
||||
|
||||
let availabilityDefinition = PackageDescription.SwiftSetting.unsafeFlags([
|
||||
"-Xfrontend",
|
||||
"-define-availability",
|
||||
"-Xfrontend",
|
||||
"SwiftStdlib 5.7:macOS 13.0, iOS 16.0, watchOS 9.0, tvOS 16.0",
|
||||
])
|
||||
|
||||
let package = Package(
|
||||
name: "swift-algorithms",
|
||||
products: [
|
||||
@@ -27,7 +34,8 @@ let package = Package(
|
||||
name: "Algorithms",
|
||||
dependencies: [
|
||||
.product(name: "RealModule", package: "swift-numerics"),
|
||||
]),
|
||||
],
|
||||
swiftSettings: [availabilityDefinition]),
|
||||
.testTarget(
|
||||
name: "SwiftAlgorithmsTests",
|
||||
dependencies: ["Algorithms"]),
|
||||
|
||||
@@ -456,9 +456,9 @@ extension Collection {
|
||||
///
|
||||
/// - Complexity: O(*n*), where *n* is the length of this collection.
|
||||
@inlinable
|
||||
public func chunked(
|
||||
by belongInSameGroup: (Element, Element) throws -> Bool
|
||||
) rethrows -> [SubSequence] {
|
||||
public func chunked<E: Error>(
|
||||
by belongInSameGroup: (Element, Element) throws(E) -> Bool
|
||||
) throws(E) -> [SubSequence] {
|
||||
guard !isEmpty else { return [] }
|
||||
var result: [SubSequence] = []
|
||||
|
||||
@@ -489,9 +489,9 @@ extension Collection {
|
||||
///
|
||||
/// - Complexity: O(*n*), where *n* is the length of this collection.
|
||||
@inlinable
|
||||
public func chunked<Subject: Equatable>(
|
||||
on projection: (Element) throws -> Subject
|
||||
) rethrows -> [(Subject, SubSequence)] {
|
||||
public func chunked<Subject: Equatable, E: Error>(
|
||||
on projection: (Element) throws(E) -> Subject
|
||||
) throws(E) -> [(Subject, SubSequence)] {
|
||||
guard !isEmpty else { return [] }
|
||||
var result: [(Subject, SubSequence)] = []
|
||||
|
||||
|
||||
@@ -31,9 +31,9 @@ extension Sequence {
|
||||
/// - Complexity: O(*n*), where *n* is the number of elements at the start of
|
||||
/// the sequence that result in `nil` when applying the transformation.
|
||||
@inlinable
|
||||
public func firstNonNil<Result>(
|
||||
_ transform: (Element) throws -> Result?
|
||||
) rethrows -> Result? {
|
||||
public func firstNonNil<Result, E: Error>(
|
||||
_ transform: (Element) throws(E) -> Result?
|
||||
) throws(E) -> Result? {
|
||||
for value in self {
|
||||
if let value = try transform(value) {
|
||||
return value
|
||||
|
||||
@@ -19,7 +19,15 @@ extension Sequence {
|
||||
/// - Returns: A dictionary containing grouped elements of self, keyed by
|
||||
/// the keys derived by the `keyForValue` closure.
|
||||
@inlinable
|
||||
public func grouped<GroupKey>(by keyForValue: (Element) throws -> GroupKey) rethrows -> [GroupKey: [Element]] {
|
||||
try Dictionary(grouping: self, by: keyForValue)
|
||||
public func grouped<GroupKey, E: Error>(
|
||||
by keyForValue: (Element) throws(E) -> GroupKey
|
||||
) throws(E) -> [GroupKey: [Element]] {
|
||||
do {
|
||||
// This stdlib Dictionary initializer doesn't use typed errors,
|
||||
// so we need to catch and cast any thrown error to our expected type.
|
||||
return try Dictionary(grouping: self, by: keyForValue)
|
||||
} catch {
|
||||
throw error as! E
|
||||
}
|
||||
}
|
||||
}
|
||||
@@ -355,9 +355,9 @@ extension Sequence where Element: Sequence {
|
||||
}
|
||||
|
||||
@inlinable
|
||||
internal func _joined(
|
||||
by update: (inout [Element.Element], Element, Element) throws -> Void
|
||||
) rethrows -> [Element.Element] {
|
||||
internal func _joined<E: Error>(
|
||||
by update: (inout [Element.Element], Element, Element) throws(E) -> Void
|
||||
) throws(E) -> [Element.Element] {
|
||||
var iterator = makeIterator()
|
||||
guard let first = iterator.next() else { return [] }
|
||||
|
||||
@@ -381,10 +381,14 @@ extension Sequence where Element: Sequence {
|
||||
/// }
|
||||
/// // 1, 2, 6, 3, 4, 20, 5, 6
|
||||
@inlinable
|
||||
public func joined(
|
||||
by separator: (Element, Element) throws -> Element.Element
|
||||
) rethrows -> [Element.Element] {
|
||||
try _joined(by: { $0.append(try separator($1, $2)) })
|
||||
public func joined<E: Error>(
|
||||
by separator: (Element, Element) throws(E) -> Element.Element
|
||||
) throws(E) -> [Element.Element] {
|
||||
// An anonymous closure is inferred as `throws(any Error)`, so we give it
|
||||
// the correct type here.
|
||||
let joiner: (inout [Element.Element], Element, Element) throws(E) -> Void
|
||||
= { $0.append(try separator($1, $2)) }
|
||||
return try _joined(by: joiner)
|
||||
}
|
||||
|
||||
/// Returns the concatenation of the elements in this sequence of sequences,
|
||||
@@ -395,12 +399,16 @@ extension Sequence where Element: Sequence {
|
||||
/// }
|
||||
/// // 1, 2, 200, 300, 3, 4, 400, 500, 5, 6
|
||||
@inlinable
|
||||
public func joined<Separator>(
|
||||
by separator: (Element, Element) throws -> Separator
|
||||
) rethrows -> [Element.Element]
|
||||
public func joined<Separator, E: Error>(
|
||||
by separator: (Element, Element) throws(E) -> Separator
|
||||
) throws(E) -> [Element.Element]
|
||||
where Separator: Sequence, Separator.Element == Element.Element
|
||||
{
|
||||
try _joined(by: { $0.append(contentsOf: try separator($1, $2)) })
|
||||
// An anonymous closure is inferred as `throws(any Error)`, so we give it
|
||||
// the correct type here.
|
||||
let joiner: (inout [Element.Element], Element, Element) throws(E) -> Void
|
||||
= { $0.append(contentsOf: try separator($1, $2)) }
|
||||
return try _joined(by: joiner)
|
||||
}
|
||||
}
|
||||
|
||||
|
||||
@@ -19,10 +19,13 @@ extension Sequence {
|
||||
/// - Parameters:
|
||||
/// - keyForValue: A closure that returns a key for each element in `self`.
|
||||
@inlinable
|
||||
public func keyed<Key>(
|
||||
by keyForValue: (Element) throws -> Key
|
||||
) rethrows -> [Key: Element] {
|
||||
return try self.keyed(by: keyForValue, resolvingConflictsWith: { _, old, new in new })
|
||||
public func keyed<Key, E: Error>(
|
||||
by keyForValue: (Element) throws(E) -> Key
|
||||
) throws(E) -> [Key: Element] {
|
||||
// An anonymous closure is inferred as `throws(any Error)`, so we give it
|
||||
// the correct type here.
|
||||
let resolve: (Key, Element, Element) throws(E) -> Element = { _, _, new in new }
|
||||
return try self.keyed(by: keyForValue, resolvingConflictsWith: resolve)
|
||||
}
|
||||
|
||||
/// Creates a new Dictionary from the elements of `self`, keyed by the
|
||||
@@ -39,10 +42,10 @@ extension Sequence {
|
||||
/// keys that are encountered. The closure returns the desired value for
|
||||
/// the final dictionary.
|
||||
@inlinable
|
||||
public func keyed<Key>(
|
||||
by keyForValue: (Element) throws -> Key,
|
||||
resolvingConflictsWith resolve: (Key, Element, Element) throws -> Element
|
||||
) rethrows -> [Key: Element] {
|
||||
public func keyed<Key, E: Error>(
|
||||
by keyForValue: (Element) throws(E) -> Key,
|
||||
resolvingConflictsWith resolve: (Key, Element, Element) throws(E) -> Element
|
||||
) throws(E) -> [Key: Element] {
|
||||
var result = [Key: Element]()
|
||||
|
||||
for element in self {
|
||||
|
||||
@@ -12,10 +12,10 @@
|
||||
extension Sequence {
|
||||
/// Implementation for min(count:areInIncreasingOrder:)
|
||||
@inlinable
|
||||
internal func _minImplementation(
|
||||
internal func _minImplementation<E: Error>(
|
||||
count: Int,
|
||||
sortedBy areInIncreasingOrder: (Element, Element) throws -> Bool
|
||||
) rethrows -> [Element] {
|
||||
sortedBy areInIncreasingOrder: (Element, Element) throws(E) -> Bool
|
||||
) throws(E) -> [Element] {
|
||||
var iterator = makeIterator()
|
||||
|
||||
var result: [Element] = []
|
||||
@@ -23,14 +23,22 @@ extension Sequence {
|
||||
while result.count < count, let e = iterator.next() {
|
||||
result.append(e)
|
||||
}
|
||||
try result.sort(by: areInIncreasingOrder)
|
||||
do {
|
||||
// The stdlib `sort(by:)` method doesn't use typed errors,
|
||||
// so we need to catch and cast any thrown error to our expected type.
|
||||
try result.sort(by: areInIncreasingOrder)
|
||||
} catch {
|
||||
throw error as! E
|
||||
}
|
||||
|
||||
while let e = iterator.next() {
|
||||
// To be part of `result`, `e` must be strictly less than `result.last`.
|
||||
guard try areInIncreasingOrder(e, result.last!) else { continue }
|
||||
result.removeLast()
|
||||
let insertionIndex =
|
||||
try result.partitioningIndex { try areInIncreasingOrder(e, $0) }
|
||||
// An anonymous closure is inferred as `throws(any Error)`, so we give it
|
||||
// the correct type here.
|
||||
let pred: (Element) throws(E) -> Bool = { try areInIncreasingOrder(e, $0) }
|
||||
let insertionIndex = try result.partitioningIndex(where: pred)
|
||||
result.insert(e, at: insertionIndex)
|
||||
}
|
||||
|
||||
@@ -39,10 +47,10 @@ extension Sequence {
|
||||
|
||||
/// Implementation for max(count:areInIncreasingOrder:)
|
||||
@inlinable
|
||||
internal func _maxImplementation(
|
||||
internal func _maxImplementation<E: Error>(
|
||||
count: Int,
|
||||
sortedBy areInIncreasingOrder: (Element, Element) throws -> Bool
|
||||
) rethrows -> [Element] {
|
||||
sortedBy areInIncreasingOrder: (Element, Element) throws(E) -> Bool
|
||||
) throws(E) -> [Element] {
|
||||
var iterator = makeIterator()
|
||||
|
||||
var result: [Element] = []
|
||||
@@ -50,13 +58,21 @@ extension Sequence {
|
||||
while result.count < count, let e = iterator.next() {
|
||||
result.append(e)
|
||||
}
|
||||
try result.sort(by: areInIncreasingOrder)
|
||||
do {
|
||||
// The stdlib `sort(by:)` method doesn't use typed errors,
|
||||
// so we need to catch and cast any thrown error to our expected type.
|
||||
try result.sort(by: areInIncreasingOrder)
|
||||
} catch {
|
||||
throw error as! E
|
||||
}
|
||||
|
||||
while let e = iterator.next() {
|
||||
// To be part of `result`, `e` must be greater/equal to `result.first`.
|
||||
guard try !areInIncreasingOrder(e, result.first!) else { continue }
|
||||
let insertionIndex =
|
||||
try result.partitioningIndex { try areInIncreasingOrder(e, $0) }
|
||||
// An anonymous closure is inferred as `throws(any Error)`, so we give it
|
||||
// the correct type here.
|
||||
let pred: (Element) throws(E) -> Bool = { try areInIncreasingOrder(e, $0) }
|
||||
let insertionIndex = try result.partitioningIndex(where: pred)
|
||||
|
||||
assert(insertionIndex > 0)
|
||||
// Inserting `e` and then removing the first element (or vice versa)
|
||||
@@ -101,10 +117,10 @@ extension Sequence {
|
||||
/// - Complexity: O(*k* log *k* + *nk*), where *n* is the length of the
|
||||
/// sequence and *k* is `count`.
|
||||
@inlinable
|
||||
public func min(
|
||||
public func min<E: Error>(
|
||||
count: Int,
|
||||
sortedBy areInIncreasingOrder: (Element, Element) throws -> Bool
|
||||
) rethrows -> [Element] {
|
||||
sortedBy areInIncreasingOrder: (Element, Element) throws(E) -> Bool
|
||||
) throws(E) -> [Element] {
|
||||
precondition(count >= 0, """
|
||||
Cannot find a minimum with a negative count of elements!
|
||||
"""
|
||||
@@ -146,10 +162,10 @@ extension Sequence {
|
||||
/// - Complexity: O(*k* log *k* + *nk*), where *n* is the length of the
|
||||
/// sequence and *k* is `count`.
|
||||
@inlinable
|
||||
public func max(
|
||||
public func max<E: Error>(
|
||||
count: Int,
|
||||
sortedBy areInIncreasingOrder: (Element, Element) throws -> Bool
|
||||
) rethrows -> [Element] {
|
||||
sortedBy areInIncreasingOrder: (Element, Element) throws(E) -> Bool
|
||||
) throws(E) -> [Element] {
|
||||
precondition(count >= 0, """
|
||||
Cannot find a maximum with a negative count of elements!
|
||||
"""
|
||||
@@ -247,10 +263,10 @@ extension Collection {
|
||||
/// - Complexity: O(*k* log *k* + *nk*), where *n* is the length of the
|
||||
/// collection and *k* is `count`.
|
||||
@inlinable
|
||||
public func min(
|
||||
public func min<E: Error>(
|
||||
count: Int,
|
||||
sortedBy areInIncreasingOrder: (Element, Element) throws -> Bool
|
||||
) rethrows -> [Element] {
|
||||
sortedBy areInIncreasingOrder: (Element, Element) throws(E) -> Bool
|
||||
) throws(E) -> [Element] {
|
||||
precondition(count >= 0, """
|
||||
Cannot find a minimum with a negative count of elements!
|
||||
"""
|
||||
@@ -267,7 +283,13 @@ extension Collection {
|
||||
// If we're attempting to prefix more than 10% of the collection, it's
|
||||
// faster to sort everything.
|
||||
guard prefixCount < (self.count / 10) else {
|
||||
return Array(try sorted(by: areInIncreasingOrder).prefix(prefixCount))
|
||||
do {
|
||||
// The stdlib `sorted(by:)` method doesn't use typed errors,
|
||||
// so we need to catch and cast any thrown error to our expected type.
|
||||
return Array(try sorted(by: areInIncreasingOrder).prefix(prefixCount))
|
||||
} catch {
|
||||
throw error as! E
|
||||
}
|
||||
}
|
||||
|
||||
return try _minImplementation(count: count, sortedBy: areInIncreasingOrder)
|
||||
@@ -301,10 +323,10 @@ extension Collection {
|
||||
/// - Complexity: O(*k* log *k* + *nk*), where *n* is the length of the
|
||||
/// collection and *k* is `count`.
|
||||
@inlinable
|
||||
public func max(
|
||||
public func max<E: Error>(
|
||||
count: Int,
|
||||
sortedBy areInIncreasingOrder: (Element, Element) throws -> Bool
|
||||
) rethrows -> [Element] {
|
||||
sortedBy areInIncreasingOrder: (Element, Element) throws(E) -> Bool
|
||||
) throws(E) -> [Element] {
|
||||
precondition(count >= 0, """
|
||||
Cannot find a maximum with a negative count of elements!
|
||||
"""
|
||||
@@ -321,7 +343,13 @@ extension Collection {
|
||||
// If we're attempting to prefix more than 10% of the collection, it's
|
||||
// faster to sort everything.
|
||||
guard suffixCount < (self.count / 10) else {
|
||||
return Array(try sorted(by: areInIncreasingOrder).suffix(suffixCount))
|
||||
do {
|
||||
// The stdlib `sorted(by:)` method doesn't use typed errors,
|
||||
// so we need to catch and cast any thrown error to our expected type.
|
||||
return Array(try sorted(by: areInIncreasingOrder).suffix(suffixCount))
|
||||
} catch {
|
||||
throw error as! E
|
||||
}
|
||||
}
|
||||
|
||||
return try _maxImplementation(count: count, sortedBy: areInIncreasingOrder)
|
||||
@@ -427,9 +455,9 @@ extension Sequence {
|
||||
///
|
||||
/// - Complexity: O(*n*), where *n* is the length of the sequence.
|
||||
@inlinable
|
||||
public func minAndMax(
|
||||
by areInIncreasingOrder: (Element, Element) throws -> Bool
|
||||
) rethrows -> (min: Element, max: Element)? {
|
||||
public func minAndMax<E: Error>(
|
||||
by areInIncreasingOrder: (Element, Element) throws(E) -> Bool
|
||||
) throws(E) -> (min: Element, max: Element)? {
|
||||
// Check short sequences.
|
||||
var iterator = makeIterator()
|
||||
guard var lowest = iterator.next() else { return nil }
|
||||
|
||||
@@ -22,11 +22,11 @@ extension MutableCollection {
|
||||
/// - Precondition:
|
||||
/// `n == distance(from: range.lowerBound, to: range.upperBound)`
|
||||
@inlinable
|
||||
internal mutating func stablePartition(
|
||||
internal mutating func stablePartition<E: Error>(
|
||||
count n: Int,
|
||||
subrange: Range<Index>,
|
||||
by belongsInSecondPartition: (Element) throws -> Bool
|
||||
) rethrows -> Index {
|
||||
by belongsInSecondPartition: (Element) throws(E) -> Bool
|
||||
) throws(E) -> Index {
|
||||
if n == 0 { return subrange.lowerBound }
|
||||
if n == 1 {
|
||||
return try belongsInSecondPartition(self[subrange.lowerBound])
|
||||
@@ -58,10 +58,10 @@ extension MutableCollection {
|
||||
///
|
||||
/// - Complexity: O(*n* log *n*), where *n* is the length of this collection.
|
||||
@inlinable
|
||||
public mutating func stablePartition(
|
||||
public mutating func stablePartition<E: Error>(
|
||||
subrange: Range<Index>,
|
||||
by belongsInSecondPartition: (Element) throws-> Bool
|
||||
) rethrows -> Index {
|
||||
by belongsInSecondPartition: (Element) throws(E) -> Bool
|
||||
) throws(E) -> Index {
|
||||
try stablePartition(
|
||||
count: distance(from: subrange.lowerBound, to: subrange.upperBound),
|
||||
subrange: subrange,
|
||||
@@ -78,9 +78,9 @@ extension MutableCollection {
|
||||
///
|
||||
/// - Complexity: O(*n* log *n*), where *n* is the length of this collection.
|
||||
@inlinable
|
||||
public mutating func stablePartition(
|
||||
by belongsInSecondPartition: (Element) throws-> Bool
|
||||
) rethrows -> Index {
|
||||
public mutating func stablePartition<E: Error>(
|
||||
by belongsInSecondPartition: (Element) throws(E) -> Bool
|
||||
) throws(E) -> Index {
|
||||
try stablePartition(
|
||||
subrange: startIndex..<endIndex,
|
||||
by: belongsInSecondPartition)
|
||||
@@ -97,14 +97,22 @@ extension MutableCollection {
|
||||
///
|
||||
/// - Complexity: O(*n*) where n is the length of the collection.
|
||||
@inlinable
|
||||
public mutating func partition(
|
||||
public mutating func partition<E: Error>(
|
||||
subrange: Range<Index>,
|
||||
by belongsInSecondPartition: (Element) throws -> Bool
|
||||
) rethrows -> Index {
|
||||
by belongsInSecondPartition: (Element) throws(E) -> Bool
|
||||
) throws(E) -> Index {
|
||||
// This version of `partition(subrange:)` is half stable; the elements in
|
||||
// the first partition retain their original relative order.
|
||||
guard var i = try self[subrange].firstIndex(where: belongsInSecondPartition)
|
||||
else { return subrange.upperBound }
|
||||
var i: Index
|
||||
do {
|
||||
// The stdlib `firstIndex(where:)` method doesn't use typed errors,
|
||||
// so we need to catch and cast any thrown error to our expected type.
|
||||
guard let firstI = try self[subrange].firstIndex(where: belongsInSecondPartition)
|
||||
else { return subrange.upperBound }
|
||||
i = firstI
|
||||
} catch {
|
||||
throw error as! E
|
||||
}
|
||||
|
||||
var j = index(after: i)
|
||||
while j != subrange.upperBound {
|
||||
@@ -125,10 +133,10 @@ extension MutableCollection where Self: BidirectionalCollection {
|
||||
///
|
||||
/// - Complexity: O(*n*) where n is the length of the collection.
|
||||
@inlinable
|
||||
public mutating func partition(
|
||||
public mutating func partition<E: Error>(
|
||||
subrange: Range<Index>,
|
||||
by belongsInSecondPartition: (Element) throws -> Bool
|
||||
) rethrows -> Index {
|
||||
by belongsInSecondPartition: (Element) throws(E) -> Bool
|
||||
) throws(E) -> Index {
|
||||
var lo = subrange.lowerBound
|
||||
var hi = subrange.upperBound
|
||||
|
||||
@@ -185,9 +193,9 @@ extension Collection {
|
||||
/// - Complexity: O(log *n*), where *n* is the length of this collection if
|
||||
/// the collection conforms to `RandomAccessCollection`, otherwise O(*n*).
|
||||
@inlinable
|
||||
public func partitioningIndex(
|
||||
where belongsInSecondPartition: (Element) throws -> Bool
|
||||
) rethrows -> Index {
|
||||
public func partitioningIndex<E: Error>(
|
||||
where belongsInSecondPartition: (Element) throws(E) -> Bool
|
||||
) throws(E) -> Index {
|
||||
var n = count
|
||||
var l = startIndex
|
||||
|
||||
@@ -236,9 +244,9 @@ extension Sequence {
|
||||
///
|
||||
/// - Complexity: O(*n*), where *n* is the length of the sequence.
|
||||
@inlinable
|
||||
public func partitioned(
|
||||
by predicate: (Element) throws -> Bool
|
||||
) rethrows -> (falseElements: [Element], trueElements: [Element]) {
|
||||
public func partitioned<E: Error>(
|
||||
by predicate: (Element) throws(E) -> Bool
|
||||
) throws(E) -> (falseElements: [Element], trueElements: [Element]) {
|
||||
var lhs = [Element]()
|
||||
var rhs = [Element]()
|
||||
|
||||
@@ -281,9 +289,9 @@ extension Collection {
|
||||
///
|
||||
/// - Complexity: O(*n*), where *n* is the length of the collection.
|
||||
@inlinable
|
||||
public func partitioned(
|
||||
by predicate: (Element) throws -> Bool
|
||||
) rethrows -> (falseElements: [Element], trueElements: [Element]) {
|
||||
public func partitioned<E: Error>(
|
||||
by predicate: (Element) throws(E) -> Bool
|
||||
) throws(E) -> (falseElements: [Element], trueElements: [Element]) {
|
||||
guard !self.isEmpty else {
|
||||
return ([], [])
|
||||
}
|
||||
@@ -300,40 +308,47 @@ extension Collection {
|
||||
// We will use this to partition the single array into two.
|
||||
var midPoint: Int = 0
|
||||
|
||||
let elements = try [Element](
|
||||
unsafeUninitializedCapacity: count,
|
||||
initializingWith: { buffer, initializedCount in
|
||||
var lhs = buffer.baseAddress!
|
||||
var rhs = lhs + buffer.count
|
||||
do {
|
||||
for element in self {
|
||||
if try predicate(element) {
|
||||
rhs -= 1
|
||||
rhs.initialize(to: element)
|
||||
} else {
|
||||
lhs.initialize(to: element)
|
||||
lhs += 1
|
||||
let elements: [Element]
|
||||
do {
|
||||
// This stdlib `Array` initializer doesn't use typed errors,
|
||||
// so we need to catch and cast any thrown error to our expected type.
|
||||
elements = try Array(
|
||||
unsafeUninitializedCapacity: count,
|
||||
initializingWith: { buffer, initializedCount in
|
||||
var lhs = buffer.baseAddress!
|
||||
var rhs = lhs + buffer.count
|
||||
do {
|
||||
for element in self {
|
||||
if try predicate(element) {
|
||||
rhs -= 1
|
||||
rhs.initialize(to: element)
|
||||
} else {
|
||||
lhs.initialize(to: element)
|
||||
lhs += 1
|
||||
}
|
||||
}
|
||||
|
||||
precondition(lhs == rhs, """
|
||||
Collection's `count` differed from the number of elements iterated.
|
||||
"""
|
||||
)
|
||||
|
||||
let rhsIndex = rhs - buffer.baseAddress!
|
||||
buffer[rhsIndex...].reverse()
|
||||
initializedCount = buffer.count
|
||||
|
||||
midPoint = rhsIndex
|
||||
} catch {
|
||||
let lhsCount = lhs - buffer.baseAddress!
|
||||
let rhsCount = (buffer.baseAddress! + buffer.count) - rhs
|
||||
buffer.baseAddress!.deinitialize(count: lhsCount)
|
||||
rhs.deinitialize(count: rhsCount)
|
||||
throw error
|
||||
}
|
||||
|
||||
precondition(lhs == rhs, """
|
||||
Collection's `count` differed from the number of elements iterated.
|
||||
"""
|
||||
)
|
||||
|
||||
let rhsIndex = rhs - buffer.baseAddress!
|
||||
buffer[rhsIndex...].reverse()
|
||||
initializedCount = buffer.count
|
||||
|
||||
midPoint = rhsIndex
|
||||
} catch {
|
||||
let lhsCount = lhs - buffer.baseAddress!
|
||||
let rhsCount = (buffer.baseAddress! + buffer.count) - rhs
|
||||
buffer.baseAddress!.deinitialize(count: lhsCount)
|
||||
rhs.deinitialize(count: rhsCount)
|
||||
throw error
|
||||
}
|
||||
})
|
||||
})
|
||||
} catch {
|
||||
throw error as! E
|
||||
}
|
||||
|
||||
let lhs = elements[..<midPoint]
|
||||
let rhs = elements[midPoint...]
|
||||
|
||||
@@ -112,13 +112,16 @@ extension Sequence {
|
||||
///
|
||||
/// - Complexity: O(_n_), where _n_ is the length of the sequence.
|
||||
@inlinable
|
||||
public func reductions<Result>(
|
||||
public func reductions<Result, E: Error>(
|
||||
_ initial: Result,
|
||||
_ transform: (Result, Element) throws -> Result
|
||||
) rethrows -> [Result] {
|
||||
try reductions(into: initial) { result, element in
|
||||
_ transform: (Result, Element) throws(E) -> Result
|
||||
) throws(E) -> [Result] {
|
||||
// An anonymous closure is inferred as `throws(any Error)`, so we give it
|
||||
// the correct type here.
|
||||
let reducer: (inout Result, Element) throws(E) -> Void = { result, element in
|
||||
result = try transform(result, element)
|
||||
}
|
||||
return try reductions(into: initial, reducer)
|
||||
}
|
||||
|
||||
/// Returns an array containing the accumulated results of combining the
|
||||
@@ -156,11 +159,10 @@ extension Sequence {
|
||||
///
|
||||
/// - Complexity: O(_n_), where _n_ is the length of the sequence.
|
||||
@inlinable
|
||||
public func reductions<Result>(
|
||||
public func reductions<Result, E: Error>(
|
||||
into initial: Result,
|
||||
_ transform: (inout Result, Element) throws -> Void
|
||||
) rethrows -> [Result] {
|
||||
|
||||
_ transform: (inout Result, Element) throws(E) -> Void
|
||||
) throws(E) -> [Result] {
|
||||
var output = [Result]()
|
||||
output.reserveCapacity(underestimatedCount + 1)
|
||||
output.append(initial)
|
||||
@@ -415,9 +417,9 @@ extension Sequence {
|
||||
///
|
||||
/// - Complexity: O(_n_), where _n_ is the length of the sequence.
|
||||
@inlinable
|
||||
public func reductions(
|
||||
_ transform: (Element, Element) throws -> Element
|
||||
) rethrows -> [Element] {
|
||||
public func reductions<E: Error>(
|
||||
_ transform: (Element, Element) throws(E) -> Element
|
||||
) throws(E) -> [Element] {
|
||||
var iterator = makeIterator()
|
||||
guard let initial = iterator.next() else { return [] }
|
||||
return try IteratorSequence(iterator).reductions(initial, transform)
|
||||
@@ -582,19 +584,19 @@ extension LazySequenceProtocol {
|
||||
extension Sequence {
|
||||
@available(*, deprecated, message: "Use reductions(_:_:) instead.")
|
||||
@inlinable
|
||||
public func scan<Result>(
|
||||
public func scan<Result, E: Error>(
|
||||
_ initial: Result,
|
||||
_ transform: (Result, Element) throws -> Result
|
||||
) rethrows -> [Result] {
|
||||
_ transform: (Result, Element) throws(E) -> Result
|
||||
) throws(E) -> [Result] {
|
||||
try reductions(initial, transform)
|
||||
}
|
||||
|
||||
@available(*, deprecated, message: "Use reductions(into:_:) instead.")
|
||||
@inlinable
|
||||
public func scan<Result>(
|
||||
public func scan<Result, E: Error>(
|
||||
into initial: Result,
|
||||
_ transform: (inout Result, Element) throws -> Void
|
||||
) rethrows -> [Result] {
|
||||
_ transform: (inout Result, Element) throws(E) -> Void
|
||||
) throws(E) -> [Result] {
|
||||
try reductions(into: initial, transform)
|
||||
}
|
||||
}
|
||||
@@ -612,9 +614,9 @@ extension LazySequenceProtocol {
|
||||
extension Sequence {
|
||||
@available(*, deprecated, message: "Use reductions(_:) instead.")
|
||||
@inlinable
|
||||
public func scan(
|
||||
_ transform: (Element, Element) throws -> Element
|
||||
) rethrows -> [Element] {
|
||||
public func scan<E: Error>(
|
||||
_ transform: (Element, Element) throws(E) -> Element
|
||||
) throws(E) -> [Element] {
|
||||
try reductions(transform)
|
||||
}
|
||||
}
|
||||
@@ -24,9 +24,9 @@ extension BidirectionalCollection {
|
||||
///
|
||||
/// - Complexity: O(*n*), where *n* is the length of the collection.
|
||||
@inlinable
|
||||
public func suffix(
|
||||
while predicate: (Element) throws -> Bool
|
||||
) rethrows -> SubSequence {
|
||||
public func suffix<E: Error>(
|
||||
while predicate: (Element) throws(E) -> Bool
|
||||
) throws(E) -> SubSequence {
|
||||
try self[startOfSuffix(while: predicate)...]
|
||||
}
|
||||
}
|
||||
@@ -46,11 +46,11 @@ extension Collection {
|
||||
///
|
||||
/// - Complexity: O(*n*), where *n* is the length of the collection.
|
||||
@inlinable
|
||||
public func endOfPrefix(
|
||||
while predicate: (Element) throws -> Bool
|
||||
) rethrows -> Index {
|
||||
public func endOfPrefix<E: Error>(
|
||||
while predicate: (Element) throws(E) -> Bool
|
||||
) throws(E) -> Index {
|
||||
var index = startIndex
|
||||
while try index != endIndex && predicate(self[index]) {
|
||||
while index != endIndex, try predicate(self[index]) {
|
||||
formIndex(after: &index)
|
||||
}
|
||||
return index
|
||||
@@ -72,9 +72,9 @@ extension BidirectionalCollection {
|
||||
///
|
||||
/// - Complexity: O(*n*), where *n* is the length of the collection.
|
||||
@inlinable
|
||||
public func startOfSuffix(
|
||||
while predicate: (Element) throws -> Bool
|
||||
) rethrows -> Index {
|
||||
public func startOfSuffix<E: Error>(
|
||||
while predicate: (Element) throws(E) -> Bool
|
||||
) throws(E) -> Index {
|
||||
var index = endIndex
|
||||
while index != startIndex {
|
||||
let after = index
|
||||
|
||||
@@ -26,11 +26,10 @@ extension Collection {
|
||||
/// omitted from the resulting slice.
|
||||
///
|
||||
/// - Complexity: O(*n*), where *n* is the length of this collection.
|
||||
///
|
||||
@inlinable
|
||||
public func trimmingPrefix(
|
||||
while predicate: (Element) throws -> Bool
|
||||
) rethrows -> SubSequence {
|
||||
public func trimmingPrefix<E: Error>(
|
||||
while predicate: (Element) throws(E) -> Bool
|
||||
) throws(E) -> SubSequence {
|
||||
let start = try endOfPrefix(while: predicate)
|
||||
return self[start..<endIndex]
|
||||
}
|
||||
@@ -55,12 +54,11 @@ extension Collection where Self: RangeReplaceableCollection {
|
||||
/// removed from the string.
|
||||
///
|
||||
/// - Complexity: O(*n*), where *n* is the length of this collection.
|
||||
///
|
||||
@inlinable
|
||||
@_disfavoredOverload
|
||||
public mutating func trimPrefix(
|
||||
while predicate: (Element) throws -> Bool
|
||||
) rethrows {
|
||||
public mutating func trimPrefix<E: Error>(
|
||||
while predicate: (Element) throws(E) -> Bool
|
||||
) throws(E) {
|
||||
let startOfResult = try endOfPrefix(while: predicate)
|
||||
removeSubrange(startIndex..<startOfResult)
|
||||
}
|
||||
@@ -81,12 +79,12 @@ extension Collection where Self == Self.SubSequence {
|
||||
/// be removed from the string.
|
||||
///
|
||||
/// - Complexity: O(*n*), where *n* is the length of this collection.
|
||||
///
|
||||
@inlinable
|
||||
public mutating func trimPrefix(
|
||||
while predicate: (Element) throws -> Bool
|
||||
) rethrows {
|
||||
self = try trimmingPrefix(while: predicate)
|
||||
public mutating func trimPrefix<E: Error>(
|
||||
while predicate: (Element) throws(E) -> Bool
|
||||
) throws(E) {
|
||||
let start = try endOfPrefix(while: predicate)
|
||||
self = self[start..<endIndex]
|
||||
}
|
||||
}
|
||||
|
||||
@@ -108,12 +106,12 @@ extension BidirectionalCollection {
|
||||
/// omitted from the resulting slice.
|
||||
///
|
||||
/// - Complexity: O(*n*), where *n* is the length of this collection.
|
||||
///
|
||||
@inlinable
|
||||
public func trimming(
|
||||
while predicate: (Element) throws -> Bool
|
||||
) rethrows -> SubSequence {
|
||||
try trimmingPrefix(while: predicate).trimmingSuffix(while: predicate)
|
||||
public func trimming<E: Error>(
|
||||
while predicate: (Element) throws(E) -> Bool
|
||||
) throws(E) -> SubSequence {
|
||||
let start = try endOfPrefix(while: predicate)
|
||||
return try self[start..<endIndex].trimmingSuffix(while: predicate)
|
||||
}
|
||||
|
||||
/// Returns a `SubSequence` formed by discarding all elements at the end of
|
||||
@@ -129,11 +127,10 @@ extension BidirectionalCollection {
|
||||
/// omitted from the resulting slice.
|
||||
///
|
||||
/// - Complexity: O(*n*), where *n* is the length of this collection.
|
||||
///
|
||||
@inlinable
|
||||
public func trimmingSuffix(
|
||||
while predicate: (Element) throws -> Bool
|
||||
) rethrows -> SubSequence {
|
||||
public func trimmingSuffix<E: Error>(
|
||||
while predicate: (Element) throws(E) -> Bool
|
||||
) throws(E) -> SubSequence {
|
||||
let end = try startOfSuffix(while: predicate)
|
||||
return self[startIndex..<end]
|
||||
}
|
||||
@@ -158,14 +155,14 @@ extension BidirectionalCollection where Self: RangeReplaceableCollection {
|
||||
/// removed from the string.
|
||||
///
|
||||
/// - Complexity: O(*n*), where *n* is the length of this collection.
|
||||
///
|
||||
@inlinable
|
||||
@_disfavoredOverload
|
||||
public mutating func trim(
|
||||
while predicate: (Element) throws -> Bool
|
||||
) rethrows {
|
||||
public mutating func trim<E: Error>(
|
||||
while predicate: (Element) throws(E) -> Bool
|
||||
) throws(E) {
|
||||
let start = try endOfPrefix(while: predicate)
|
||||
self.removeSubrange(startIndex..<start)
|
||||
try trimSuffix(while: predicate)
|
||||
try trimPrefix(while: predicate)
|
||||
}
|
||||
|
||||
/// Mutates a `BidirectionalCollection` by discarding all elements at the end
|
||||
@@ -182,12 +179,11 @@ extension BidirectionalCollection where Self: RangeReplaceableCollection {
|
||||
/// removed from the string.
|
||||
///
|
||||
/// - Complexity: O(*n*), where *n* is the length of this collection.
|
||||
///
|
||||
@inlinable
|
||||
@_disfavoredOverload
|
||||
public mutating func trimSuffix(
|
||||
while predicate: (Element) throws -> Bool
|
||||
) rethrows {
|
||||
public mutating func trimSuffix<E: Error>(
|
||||
while predicate: (Element) throws(E) -> Bool
|
||||
) throws(E) {
|
||||
let endOfResult = try startOfSuffix(while: predicate)
|
||||
removeSubrange(endOfResult..<endIndex)
|
||||
}
|
||||
@@ -208,11 +204,10 @@ extension BidirectionalCollection where Self == Self.SubSequence {
|
||||
/// removed from the string.
|
||||
///
|
||||
/// - Complexity: O(*n*), where *n* is the length of this collection.
|
||||
///
|
||||
@inlinable
|
||||
public mutating func trim(
|
||||
while predicate: (Element) throws -> Bool
|
||||
) rethrows {
|
||||
public mutating func trim<E: Error>(
|
||||
while predicate: (Element) throws(E) -> Bool
|
||||
) throws(E) {
|
||||
self = try trimming(while: predicate)
|
||||
}
|
||||
|
||||
@@ -230,11 +225,10 @@ extension BidirectionalCollection where Self == Self.SubSequence {
|
||||
/// removed from the string.
|
||||
///
|
||||
/// - Complexity: O(*n*), where *n* is the length of this collection.
|
||||
///
|
||||
@inlinable
|
||||
public mutating func trimSuffix(
|
||||
while predicate: (Element) throws -> Bool
|
||||
) rethrows {
|
||||
public mutating func trimSuffix<E: Error>(
|
||||
while predicate: (Element) throws(E) -> Bool
|
||||
) throws(E) {
|
||||
self = try trimmingSuffix(while: predicate)
|
||||
}
|
||||
}
|
||||
@@ -112,9 +112,9 @@ extension Sequence {
|
||||
///
|
||||
/// - Complexity: O(*n*), where *n* is the length of the sequence.
|
||||
@inlinable
|
||||
public func uniqued<Subject: Hashable>(
|
||||
on projection: (Element) throws -> Subject
|
||||
) rethrows -> [Element] {
|
||||
public func uniqued<Subject: Hashable, E: Error>(
|
||||
on projection: (Element) throws(E) -> Subject
|
||||
) throws(E) -> [Element] {
|
||||
var seen: Set<Subject> = []
|
||||
var result: [Element] = []
|
||||
for element in self {
|
||||
|
||||
@@ -13,7 +13,7 @@ import XCTest
|
||||
import Algorithms
|
||||
|
||||
final class GroupedTests: XCTestCase {
|
||||
private class SampleError: Error {}
|
||||
private final class SampleError: Error {}
|
||||
|
||||
// Based on https://github.com/apple/swift/blob/4d1d8a9de5ebc132a17aee9fc267461facf89bf8/validation-test/stdlib/Dictionary.swift#L1974-L1988
|
||||
|
||||
|
||||
@@ -13,7 +13,7 @@ import XCTest
|
||||
import Algorithms
|
||||
|
||||
final class KeyedTests: XCTestCase {
|
||||
private class SampleError: Error {}
|
||||
private final class SampleError: Error {}
|
||||
|
||||
func testUniqueKeys() {
|
||||
let d = ["Apple", "Banana", "Cherry"].keyed(by: { $0.first! })
|
||||
|
||||
@@ -75,9 +75,10 @@ final class TrimTests: XCTestCase {
|
||||
}
|
||||
|
||||
// Self == Self.Subsequence
|
||||
func testTrimPrefixNoAmbiguity() {
|
||||
func testTrimPrefixNoAmbiguity() throws {
|
||||
var values = [2, 10, 12, 15, 20, 100] as ArraySlice
|
||||
values.trimPrefix { $0.isMultiple(of: 2) }
|
||||
// FIXME: `trimPrefix` in the _StringProcessing module always `throws`
|
||||
try values.trimPrefix { $0.isMultiple(of: 2) }
|
||||
XCTAssertEqual(values, [15, 20, 100])
|
||||
}
|
||||
|
||||
|
||||
Reference in new issue
Block a user