Compare commits

..
Author SHA1 Message Date
Nate Cook bcd4f369ac Update changelog for 1.1.0 release (#206) 2023-10-05 14:45:17 -05:00
Nate Cook 4f53c9cf40 Finish sub-page documentation updates (#204)
* Finish sub-page documentation updates

Some of these pages could use introductions, but the current state is
ready for publication.

* Add SPI yaml file for building docs
2023-10-05 13:10:03 -05:00
Nate Cook 0d6f943832 Increase the package version to 5.4 (#205)
The latest Swift versions appear to have a problem with the
LinuxMain.swift again, which we haven't needed for quite some time.
Linux test autodiscovery has been enabled since 5.4, so we can
update to that version and drop the file.
2023-10-05 13:03:25 -05:00
Nate Cook fc8fdfd4dc Curate documentation for Algorithms module (#201) 2023-08-24 14:17:38 -05:00
Matt Zanchelli bfcaaa8758 Correct Chunked documentation (#182)
* Clarify that the determining factor for being grouped is equality (`Equatable`), which doesn’t necessarily mean the _same_ value (identity)
* Correct algorithmic complexity documentation on the lazy Chunked functions
* Document `belongInSameGroup` and `projection`
2023-08-02 10:18:17 -05:00
Nate Cook 0f81ef4a70 Chunked type / documentation cleanup (#200)
This change improves the documentation for `evenlyChunked(in:)` and
`chunks(ofCount:)` and renames `EvenChunksCollection` to
`EvenlyChunkedCollection` to follow the pattern of wrapper type
names matching their producing functions.
2023-07-26 13:15:35 -05:00
Tim VermeulenandTim Vermeulen de3efbc567 Evenly divide a collection into chunks (#96)
Adds `evenlyChunked(in:)` as a `Collection` method that divides a
collection into a specific number of chunks as evenly as possible.

Co-authored-by: Tim Vermeulen <tvermeulen@apple.com>
2023-07-26 11:17:25 -05:00
Gwynne Raskind df51f1780b Specify dependency URL in consistent fashion (#194) 2023-07-03 15:15:33 -05:00
Matt Dickoff 288d8b00f2 Merge pull request #191 from dickoff/dickoff/fix-max-code-documentation
Corrects variable name in documentation for max functions to better reflect usage
2022-12-07 13:27:05 -06:00
Matt Dickoff aa6349dea0 Corrects variable name in max functions to better reflect usage
The variable smallestThree should really be named largestThree. Looks
like this was originally a copy paste error from the min documentation.
2022-12-01 11:37:32 -06:00
28 changed files with 953 additions and 211 deletions

No files matched your search

+5
View File
@@ -0,0 +1,5 @@
version: 1
builder:
configs:
- documentation_targets: [Algorithms]
+51 -2
View File
@@ -12,6 +12,49 @@ This project follows semantic versioning.
---
## [1.1.0] - 2023-08-24
### Additions
- New nonmutating `partitioned(by:)` methods that return both the failing and passing elements of a sequence or collection in separate arrays. ([#152])
```swift
let cast = ["Vivien", "Marlon", "Kim", "Karl"]
let (longNames, shortNames) = cast.partitioned(by: { $0.count < 5 })
print(longNames)
// Prints "["Vivien", "Marlon"]"
print(shortNames)
// Prints "["Kim", "Karl"]"
```
- A new `evenlyChunked(in:)` method that chunks a sequence or collection into the specified number of evenly-sized subsequences. ([#96])
```swift
let numbers = Array(0..<10)
for chunk in numbers.evenlyChunked(in: 4) {
print(chunk)
}
// Prints:
// [0, 1, 2]
// [3, 4, 5]
// [6, 7]
// [8, 9]
```
### Changes
- The package now has a minimum Swift version of Swift 5.4.
### Fixes
- Improvements to documentation, including a new DocC-based documentation structure.
The 1.1.0 release includes contributions from [dickoff], [gwynne], [mdznr], [natecook1000], [ole], [stephentyrone], and [timvermeulen].
Thank you!
---
## [1.0.0] - 2021-09-08
### Changes
@@ -269,7 +312,8 @@ This changelog's format is based on [Keep a Changelog](https://keepachangelog.co
<!-- Link references for releases -->
[Unreleased]: https://github.com/apple/swift-algorithms/compare/1.0.0...HEAD
[Unreleased]: https://github.com/apple/swift-algorithms/compare/1.1.0...HEAD
[1.1.0]: https://github.com/apple/swift-algorithms/compare/1.0.0...1.1.0
[1.0.0]: https://github.com/apple/swift-algorithms/compare/0.2.1...1.0.0
[0.2.1]: https://github.com/apple/swift-algorithms/compare/0.2.0...0.2.1
[0.2.0]: https://github.com/apple/swift-algorithms/compare/0.1.1...0.2.0
@@ -299,6 +343,7 @@ This changelog's format is based on [Keep a Changelog](https://keepachangelog.co
[#85]: https://github.com/apple/swift-algorithms/pull/85
[#90]: https://github.com/apple/swift-algorithms/pull/90
[#91]: https://github.com/apple/swift-algorithms/pull/91
[#96]: https://github.com/apple/swift-algorithms/pull/96
[#104]: https://github.com/apple/swift-algorithms/pull/104
[#106]: https://github.com/apple/swift-algorithms/pull/106
[#112]: https://github.com/apple/swift-algorithms/pull/112
@@ -307,6 +352,7 @@ This changelog's format is based on [Keep a Changelog](https://keepachangelog.co
[#125]: https://github.com/apple/swift-algorithms/pull/125
[#130]: https://github.com/apple/swift-algorithms/pull/130
[#138]: https://github.com/apple/swift-algorithms/pull/138
[#152]: https://github.com/apple/swift-algorithms/pull/152
[#162]: https://github.com/apple/swift-algorithms/pull/162
<!-- Link references for contributors -->
@@ -317,11 +363,13 @@ This changelog's format is based on [Keep a Changelog](https://keepachangelog.co
[CTMacUser]: https://github.com/apple/swift-algorithms/commits?author=CTMacUser
[danielctull]: https://github.com/apple/swift-algorithms/commits?author=danielctull
[dhruvshah8]: https://github.com/apple/swift-algorithms/commits?author=dhruvshah8
[dickoff]: https://github.com/apple/swift-algorithms/commits?author=dickoff
[egorzhdan]: https://github.com/apple/swift-algorithms/commits?author=egorzhdan
[fedeci]: https://github.com/apple/swift-algorithms/commits?author=fedeci
[gwynne]: https://github.com/apple/swift-algorithms/commits?author=gwynne
[hashemi]: https://github.com/apple/swift-algorithms/commits?author=hashemi
[IanKeen]: https://github.com/apple/swift-algorithms/commits?author=IanKeen
[iainsmith]: https://github.com/apple/swift-algorithms/commits?author=iainsmith
[IanKeen]: https://github.com/apple/swift-algorithms/commits?author=IanKeen
[iSame7]: https://github.com/apple/swift-algorithms/commits?author=iSame7
[karwa]: https://github.com/apple/swift-algorithms/commits?author=karwa
[kylemacomber]: https://github.com/apple/swift-algorithms/commits?author=kylemacomber
@@ -333,6 +381,7 @@ This changelog's format is based on [Keep a Changelog](https://keepachangelog.co
[mpangburn]: https://github.com/apple/swift-algorithms/commits?author=mpangburn
[natecook1000]: https://github.com/apple/swift-algorithms/commits?author=natecook1000
[nordicio]: https://github.com/apple/swift-algorithms/commits?author=nordicio
[ole]: https://github.com/apple/swift-algorithms/commits?author=ole
[ollieatkinson]: https://github.com/apple/swift-algorithms/commits?author=ollieatkinson
[pmtao]: https://github.com/apple/swift-algorithms/commits?author=pmtao
[Qata]: https://github.com/apple/swift-algorithms/commits?author=Qata
+56 -39
View File
@@ -3,16 +3,16 @@
[[Source](https://github.com/apple/swift-algorithms/blob/main/Sources/Algorithms/Chunked.swift) |
[Tests](https://github.com/apple/swift-algorithms/blob/main/Tests/SwiftAlgorithmsTests/ChunkedTests.swift)]
Break a collection into subsequences where consecutive elements pass a binary
predicate, or where all elements in each chunk project to the same value.
Break a collection into nonoverlapping subsequences:
Also includes a `chunks(ofCount:)` that breaks a collection into subsequences
of a given `count`.
* `chunked(by:)` forms chunks of consecutive elements that pass a binary predicate,
* `chunked(on:)` forms chunks of consecutive elements that project to equal values,
* `chunks(ofCount:)` forms chunks of a given size, and
* `evenlyChunked(in:)` forms a given number of equally-sized chunks.
There are two variations of the `chunked` method: `chunked(by:)` and
`chunked(on:)`. `chunked(by:)` uses a binary predicate to test consecutive
elements, separating chunks where the predicate returns `false`. For example,
you can chunk a collection into ascending sequences using this method:
`chunked(by:)` uses a binary predicate to test consecutive elements, separating
chunks where the predicate returns `false`. For example, you can chunk a
collection into ascending sequences using this method:
```swift
let numbers = [10, 20, 30, 10, 40, 40, 10, 20]
@@ -31,11 +31,10 @@ let chunks = names.chunked(on: \.first!)
// [("D", ["David"]), ("K", ["Kyle", "Karoy"]), ("N", ["Nate"])]
```
The `chunks(ofCount:)` method takes a `count` parameter (greater than zero)
and separates the collection into chunks of this given count. If the `count`
parameter is evenly divided by the count of the base `Collection`, all the
chunks will have a count equal to the parameter. Otherwise, the last chunk will
contain the remaining elements.
The `chunks(ofCount:)` method takes a `count` parameter (required to be > 0) and
separates the collection into chunks of this given count. If the length of the
collection is a multiple of the `count` parameter, all chunks will have the
a count equal to the parameter. Otherwise, the last chunk will contain the remaining elements.
```swift
let names = ["David", "Kyle", "Karoy", "Nate"]
@@ -46,11 +45,26 @@ let remaining = names.chunks(ofCount: 3)
// equivalent to [["David", "Kyle", "Karoy"], ["Nate"]]
```
The `chunks(ofCount:)` is the subject of an [existing SE proposal][proposal].
The `chunks(ofCount:)` method was previously [proposed](proposal) for inclusion
in the standard library.
The `evenlyChunked(in:)` method takes a `count` parameter and divides the
collection into `count` number of equally-sized chunks. If the length of the
collection is not a multiple of the `count` parameter, the chunks at the start
will be longer than the chunks at the end.
```swift
let evenChunks = (0..<15).evenlyChunked(in: 3)
// equivalent to [0..<5, 5..<10, 10..<15]
let nearlyEvenChunks = (0..<15).evenlyChunked(in: 4)
// equivalent to [0..<4, 4..<8, 8..<12, 12..<15]
```
When "chunking" a collection, the entire collection is included in the result,
unlike the `split` family of methods, where separators are dropped.
Joining the result of a chunking method call recreates the original collection.
Joining the result of a chunking method call results in a collection equivalent
to the original.
```swift
c.elementsEqual(c.chunked(...).joined())
@@ -61,42 +75,45 @@ c.elementsEqual(c.chunked(...).joined())
## Detailed Design
The three methods are added as extension to `Collection`. `chunked(by:)` and
`chunked(on:)` are eager by default, both with a matching version that return a
lazy wrapper added to `LazySequenceProtocol`.
The four methods are added to `Collection`, with matching versions of
`chunked(by:)` and `chunked(on:)` that return a lazy wrapper added to
`LazyCollectionProtocol`.
```swift
extension Collection {
public func chunked(
by belongInSameGroup: (Element, Element) -> Bool
) -> [SubSequence]
public func chunked(
by belongInSameGroup: (Element, Element) -> Bool
) -> [SubSequence]
public func chunked<Subject: Equatable>(
public func chunked<Subject: Equatable>(
on projection: (Element) -> Subject
) -> [(Subject, SubSequence)]
public func chunks(ofCount count: Int) -> ChunksOfCountCollection<Self>
) -> [SubSequence]
public func chunks(ofCount count: Int) -> ChunkedByCount<Self>
public func evenlyChunked(in count: Int) -> EvenlyChunkedCollection<Self>
}
extension LazySequenceProtocol where Self: Collection, Elements: Collection {
public func chunked(
by belongInSameGroup: @escaping (Element, Element) -> Bool
) -> ChunkedByCollection<Elements, Element>
extension LazyCollectionProtocol {
public func chunked(
by belongInSameGroup: @escaping (Element, Element) -> Bool
) -> ChunkedByCollection<Elements>
public func chunked<Subject: Equatable>(
on projection: @escaping (Element) -> Subject
) -> ChunkedOnCollection<Elements, Subject>
public func chunked<Subject: Equatable>(
on projection: @escaping (Element) -> Subject
) -> ChunkedOnCollection<Elements, Subject>
}
```
The `ChunkedByCollection`, `ChunkedOnCollection`, and `ChunksOfCountCollection`
types are bidirectional when the wrapped collection is bidirectional.
`ChunksOfCountCollection` also conforms to `LazySequenceProtocol` when the base
collection conforms.
Each of the "chunked" collection types are bidirectional when the wrapped
collection is bidirectional. `ChunksOfCountCollection` and
`EvenlyChunkedCollection` also conform to `RandomAccessCollection` and
`LazySequenceProtocol` when their base collections conform.
### Complexity
The eager methods are O(_n_), the lazy methods are O(_1_).
The eager methods are O(_n_) where _n_ is the number of elements in the
collection. The lazy methods are O(_n_) because the start index is pre-computed.
### Naming
@@ -120,5 +137,5 @@ into potentially overlapping subsequences.
**Ruby:** Ruby’s `Enumerable` class defines `chunk_while` and `chunk`, which map
to the proposed `chunked(by:)` and `chunked(on:)` methods.
**Rust:** Rust defines a variety of size-based `chunks` methods, but doesn’t
include any with the functionality described here.
**Rust:** Rust defines a variety of size-based `chunks` methods, of which the
standard version corresponds to the `chunks(ofCount:)` method defined here.
+2 -2
View File
@@ -1,4 +1,4 @@
// swift-tools-version:5.1
// swift-tools-version:5.4
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Algorithms open source project
@@ -20,7 +20,7 @@ let package = Package(
targets: ["Algorithms"]),
],
dependencies: [
.package(url: "https://github.com/apple/swift-numerics", from: "1.0.0"),
.package(url: "https://github.com/apple/swift-numerics.git", from: "1.0.0"),
],
targets: [
.target(
+13 -2
View File
@@ -10,7 +10,8 @@
//===----------------------------------------------------------------------===//
extension Sequence {
/// Creates a sequence of adjacent pairs of elements from this sequence.
/// Returns a sequence of overlapping adjacent pairs of the elements of this
/// sequence.
///
/// In the `AdjacentPairsSequence` returned by this method, the elements of
/// the *i*th pair are the *i*th and *(i+1)*th elements of the underlying
@@ -24,6 +25,11 @@ extension Sequence {
/// // Prints "(2, 3)"
/// // Prints "(3, 4)"
/// // Prints "(4, 5)"
///
/// The resulting sequence is empty when called on an empty or single-element
/// sequence.
///
/// - Complexity: O(1)
@inlinable
public func adjacentPairs() -> AdjacentPairsSequence<Self> {
AdjacentPairsSequence(base: self)
@@ -31,7 +37,7 @@ extension Sequence {
}
extension Collection {
/// A collection of adjacent pairs of elements built from an underlying
/// Returns a collection of overlapping adjacent pairs of the elements of this
/// collection.
///
/// In an `AdjacentPairsCollection`, the elements of the *i*th pair are the
@@ -46,6 +52,11 @@ extension Collection {
/// // Prints "(2, 3)"
/// // Prints "(3, 4)"
/// // Prints "(4, 5)"
///
/// The resulting collection is empty when called on an empty or
/// single-element collection.
///
/// - Complexity: O(1)
@inlinable
public func adjacentPairs() -> AdjacentPairsCollection<Self> {
AdjacentPairsCollection(base: self)
+302 -15
View File
@@ -198,6 +198,210 @@ extension ChunkedOnCollection: BidirectionalCollection
extension ChunkedOnCollection: LazyCollectionProtocol {}
/// A collection wrapper that evenly breaks a collection into a given number of
/// chunks.
public struct EvenlyChunkedCollection<Base: Collection> {
/// The base collection.
@usableFromInline
internal let base: Base
/// The number of equal chunks the base collection is divided into.
@usableFromInline
internal let numberOfChunks: Int
/// The count of the base collection.
@usableFromInline
internal let baseCount: Int
/// The upper bound of the first chunk.
@usableFromInline
internal var firstUpperBound: Base.Index
@inlinable
internal init(base: Base, numberOfChunks: Int) {
self.base = base
self.numberOfChunks = numberOfChunks
self.baseCount = base.count
self.firstUpperBound = base.startIndex
if numberOfChunks > 0 {
firstUpperBound = endOfChunk(startingAt: base.startIndex, offset: 0)
}
}
}
extension EvenlyChunkedCollection {
/// Returns the number of chunks with size `smallChunkSize + 1` at the start
/// of this collection.
@inlinable
internal var numberOfLargeChunks: Int {
baseCount % numberOfChunks
}
/// Returns the size of a chunk at a given offset.
@inlinable
internal func sizeOfChunk(offset: Int) -> Int {
let isLargeChunk = offset < numberOfLargeChunks
return baseCount / numberOfChunks + (isLargeChunk ? 1 : 0)
}
/// Returns the index in the base collection of the end of the chunk starting
/// at the given index.
@inlinable
internal func endOfChunk(startingAt start: Base.Index, offset: Int) -> Base.Index {
base.index(start, offsetBy: sizeOfChunk(offset: offset))
}
/// Returns the index in the base collection of the start of the chunk ending
/// at the given index.
@inlinable
internal func startOfChunk(endingAt end: Base.Index, offset: Int) -> Base.Index {
base.index(end, offsetBy: -sizeOfChunk(offset: offset))
}
/// Returns the index that corresponds to the chunk that starts at the given
/// base index.
@inlinable
internal func indexOfChunk(startingAt start: Base.Index, offset: Int) -> Index {
guard offset != numberOfChunks else { return endIndex }
let end = endOfChunk(startingAt: start, offset: offset)
return Index(start..<end, offset: offset)
}
/// Returns the index that corresponds to the chunk that ends at the given
/// base index.
@inlinable
internal func indexOfChunk(endingAt end: Base.Index, offset: Int) -> Index {
let start = startOfChunk(endingAt: end, offset: offset)
return Index(start..<end, offset: offset)
}
}
extension EvenlyChunkedCollection: Collection {
public struct Index: Comparable {
/// The range corresponding to the chunk at this position.
@usableFromInline
internal var baseRange: Range<Base.Index>
/// The offset corresponding to the chunk at this position. The first chunk
/// has offset `0` and all other chunks have an offset `1` greater than the
/// previous.
@usableFromInline
internal var offset: Int
@inlinable
internal init(_ baseRange: Range<Base.Index>, offset: Int) {
self.baseRange = baseRange
self.offset = offset
}
@inlinable
public static func == (lhs: Self, rhs: Self) -> Bool {
lhs.offset == rhs.offset
}
@inlinable
public static func < (lhs: Self, rhs: Self) -> Bool {
lhs.offset < rhs.offset
}
}
public typealias Element = Base.SubSequence
@inlinable
public var startIndex: Index {
Index(base.startIndex..<firstUpperBound, offset: 0)
}
@inlinable
public var endIndex: Index {
Index(base.endIndex..<base.endIndex, offset: numberOfChunks)
}
@inlinable
public func index(after i: Index) -> Index {
precondition(i != endIndex, "Can't advance past endIndex")
let start = i.baseRange.upperBound
return indexOfChunk(startingAt: start, offset: i.offset + 1)
}
@inlinable
public subscript(position: Index) -> Element {
precondition(position != endIndex)
return base[position.baseRange]
}
@inlinable
public func index(_ i: Index, offsetBy distance: Int) -> Index {
/// Returns the base distance between two `EvenChunksCollection` indices
/// from the end of one to the start of the other, when given their offsets.
func baseDistance(from offsetA: Int, to offsetB: Int) -> Int {
let smallChunkSize = baseCount / numberOfChunks
let numberOfChunks = (offsetB - offsetA) - 1
let largeChunksEnd = Swift.min(self.numberOfLargeChunks, offsetB)
let largeChunksStart = Swift.min(self.numberOfLargeChunks, offsetA + 1)
let numberOfLargeChunks = largeChunksEnd - largeChunksStart
return smallChunkSize * numberOfChunks + numberOfLargeChunks
}
if distance == 0 {
return i
} else if distance > 0 {
let offset = i.offset + distance
let baseOffset = baseDistance(from: i.offset, to: offset)
let start = base.index(i.baseRange.upperBound, offsetBy: baseOffset)
return indexOfChunk(startingAt: start, offset: offset)
} else {
let offset = i.offset + distance
let baseOffset = baseDistance(from: offset, to: i.offset)
let end = base.index(i.baseRange.lowerBound, offsetBy: -baseOffset)
return indexOfChunk(endingAt: end, offset: offset)
}
}
@inlinable
public func index(_ i: Index, offsetBy distance: Int, limitedBy limit: Index) -> Index? {
if distance >= 0 {
if (0..<distance).contains(self.distance(from: i, to: limit)) {
return nil
}
} else {
if (0..<(-distance)).contains(self.distance(from: limit, to: i)) {
return nil
}
}
return index(i, offsetBy: distance)
}
@inlinable
public func distance(from start: Index, to end: Index) -> Int {
end.offset - start.offset
}
}
extension EvenlyChunkedCollection.Index: Hashable where Base.Index: Hashable {}
extension EvenlyChunkedCollection: BidirectionalCollection
where Base: BidirectionalCollection
{
@inlinable
public func index(before i: Index) -> Index {
precondition(i != startIndex, "Can't advance before startIndex")
return indexOfChunk(endingAt: i.baseRange.lowerBound, offset: i.offset - 1)
}
}
extension EvenlyChunkedCollection: RandomAccessCollection
where Base: RandomAccessCollection {}
extension EvenlyChunkedCollection: LazySequenceProtocol
where Base: LazySequenceProtocol {}
extension EvenlyChunkedCollection: LazyCollectionProtocol
where Base: LazyCollectionProtocol {}
//===----------------------------------------------------------------------===//
// lazy.chunked(by:) / lazy.chunked(on:)
//===----------------------------------------------------------------------===//
@@ -206,6 +410,9 @@ extension LazySequenceProtocol where Self: Collection, Elements: Collection {
/// Returns a lazy collection of subsequences of this collection, chunked by
/// the given predicate.
///
/// - Parameter belongInSameGroup: A closure that takes two adjacent elements
/// of the sequence and returns whether or not they belong in the same group.
///
/// - Complexity: O(*n*), because the start index is pre-computed.
@inlinable
public func chunked(
@@ -218,7 +425,11 @@ extension LazySequenceProtocol where Self: Collection, Elements: Collection {
}
/// Returns a lazy collection of subsequences of this collection, chunked by
/// grouping elements that project to the same value.
/// grouping elements that project to equal values.
///
/// - Parameter projection: A closure that takes an element in the sequence
/// and returns an `Equatable` value that can be used to determine if adjacent
/// elements belong in the same group.
///
/// - Complexity: O(*n*), because the start index is pre-computed.
@inlinable
@@ -239,6 +450,10 @@ extension Collection {
/// Returns a collection of subsequences of this collection, chunked by the
/// given predicate.
///
/// - Parameter belongInSameGroup: A closure that takes two adjacent elements
/// of the collection and returns whether or not they belong in the same
/// group.
///
/// - Complexity: O(*n*), where *n* is the length of this collection.
@inlinable
public func chunked(
@@ -266,7 +481,11 @@ extension Collection {
}
/// Returns a collection of subsequences of this collection, chunked by
/// grouping elements that project to the same value.
/// grouping elements that project to equal values.
///
/// - Parameter projection: A closure that takes an element in the collection
/// and returns an `Equatable` value that can be used to determine if adjacent
/// elements belong in the same group.
///
/// - Complexity: O(*n*), where *n* is the length of this collection.
@inlinable
@@ -558,22 +777,37 @@ extension ChunksOfCountCollection {
}
extension Collection {
/// Returns a `ChunksOfCountCollection<Self>` view presenting the elements in
/// chunks with count of the given count parameter.
/// Returns a collection of subsequences, each with up to the specified
/// length.
///
/// - Parameter count: The size of the chunks. If the `count` parameter is
/// evenly divided by the count of the base `Collection` all the chunks will
/// have the count equals to size. Otherwise, the last chunk will contain
/// the remaining elements.
/// If the number of elements in the collection is evenly divided by `count`,
/// then every chunk will have a length equal to `count`. Otherwise, every
/// chunk but the last will have a length equal to `count`, with the
/// remaining elements in the last chunk.
///
/// let c = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
/// print(c.chunks(ofCount: 5).map(Array.init))
/// // [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10]]
/// let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
/// for chunk in numbers.chunks(ofCount: 5) {
/// print(chunk)
/// }
/// // [1, 2, 3, 4, 5]
/// // [6, 7, 8, 9, 10]
///
/// print(c.chunks(ofCount: 3).map(Array.init))
/// // [[1, 2, 3], [4, 5, 6], [7, 8, 9], [10]]
/// for chunk in numbers.chunks(ofCount: 3) {
/// print(chunk)
/// }
/// // [1, 2, 3]
/// // [4, 5, 5]
/// // [7, 8, 9]
/// // [10]
///
/// - Parameter count: The desired size of each chunk.
/// - Returns: A collection of consescutive, non-overlapping subseqeunces of
/// this collection, where each subsequence (except possibly the last) has
/// the length `count`.
///
/// - Complexity: O(1) if the collection conforms to `RandomAccessCollection`;
/// otherwise, O(*k*), where *k* is equal to `count`.
///
/// - Complexity: O(*n*), because the start index is pre-computed.
@inlinable
public func chunks(ofCount count: Int) -> ChunksOfCountCollection<Self> {
precondition(count > 0, "Cannot chunk with count <= 0!")
@@ -583,5 +817,58 @@ extension Collection {
extension ChunksOfCountCollection.Index: Hashable where Base.Index: Hashable {}
extension ChunksOfCountCollection: LazySequenceProtocol, LazyCollectionProtocol
extension ChunksOfCountCollection: LazySequenceProtocol
where Base: LazySequenceProtocol {}
extension ChunksOfCountCollection: LazyCollectionProtocol
where Base: LazyCollectionProtocol {}
//===----------------------------------------------------------------------===//
// evenlyChunked(in:)
//===----------------------------------------------------------------------===//
extension Collection {
/// Returns a collection of evenly divided consecutive subsequences of this
/// collection.
///
/// This method divides the collection into a given number of evenly sized
/// chunks. If the length of the collection is not divisible by `count`, the
/// chunks at the start will be longer than the chunks at the end, like in
/// this example:
///
/// for chunk in "Hello, world!".evenlyChunked(in: 5) {
/// print(chunk)
/// }
/// // "Hel"
/// // "lo,"
/// // " wo"
/// // "rl"
/// // "d!"
///
/// If the number passed as `count` is greater than the number of elements in
/// the collection, the result will include one or more empty subsequences.
///
/// for chunk in "Hi!".evenlyChunked(in: 5) {
/// print(chunk)
/// }
/// // "H"
/// // "i"
/// // "!"
/// // ""
/// // ""
///
/// - Parameter count: The number of chunks to evenly divide this collection
/// into. If this collection is non-empty, `count` must be greater than
/// zero; otherwise, `count` may be zero or greater.
/// - Returns: A collection of `count` subsequences of this collection,
/// divided as evenly as possible.
///
/// - Complexity: O(1) if the collection conforms to `RandomAccessCollection`;
/// otherwise, O(*n*), where *n* is the length of the collection.
@inlinable
public func evenlyChunked(in count: Int) -> EvenlyChunkedCollection<Self> {
precondition(count >= 0, "Can't divide into a negative number of chunks")
precondition(count > 0 || isEmpty, "Can't divide a non-empty collection into 0 chunks")
return EvenlyChunkedCollection(base: self, numberOfChunks: count)
}
}
+2 -2
View File
@@ -289,8 +289,8 @@ extension Collection {
/// - Parameter k: The number of elements to include in each combination.
///
/// - Complexity: O(1) for random-access base collections. O(*n*) where *n*
/// is the number of elements in the base collection, since
/// `CombinationsSequence` accesses the `count` of the base collection.
/// is the number of elements in the base collection, since
/// `CombinationsSequence` accesses the `count` of the base collection.
@inlinable
public func combinations(ofCount k: Int) -> CombinationsSequence<Self> {
precondition(k >= 0, "Can't have combinations with a negative number of elements.")
@@ -0,0 +1,41 @@
# ``Algorithms``
**Swift Algorithms** is an open-source package of sequence and collection algorithms,
along with their related types.
## Overview
The Algorithms package provides a variety of sequence and collection operations, letting you cycle over a collection's elements, find combinations and permutations, create a random sample, and more.
For example, the package includes a group of "chunking" methods, each of which breaks a collection into consecutive subsequences. One version tests adjacent elements to find the breaking point between chunks — you can use it to quickly separate an array into ascending runs:
```swift
let numbers = [10, 20, 30, 10, 40, 40, 10, 20]
let chunks = numbers.chunked(by: { $0 <= $1 })
// [[10, 20, 30], [10, 40, 40], [10, 20]]
```
Another version looks for a change in the transformation of each successive value. You can use that to separate a list of names into groups by the first character:
```swift
let names = ["Cassie", "Chloe", "Jasmine", "Jordan", "Taylor"]
let chunks = names.chunked(on: \.first)
// [["Cassie", "Chloe"], ["Jasmine", "Jordan"], ["Taylor"]]
```
Explore more chunking methods and the remainder of the Algorithms package, grouped in the following topics.
## Topics
- <doc:CombinationsPermutations>
- <doc:SlicingSplitting>
- <doc:Chunking>
- <doc:Joining>
- <doc:Extending>
- <doc:Trimming>
- <doc:Sampling>
- <doc:MinAndMax>
- <doc:Selecting>
- <doc:Filtering>
- <doc:Reductions>
- <doc:Partitioning>
@@ -0,0 +1,40 @@
# Chunking
Break collections into consecutive chunks by length, count, or based on closure-based logic.
## Overview
_Chunking_ is the process of breaking a collection into consecutive subsequences, without dropping or duplicating any of the collection's elements. After chunking a collection, joining the resulting subsequences produces the original collection of elements, unlike _splitting_, which consumes the separator element(s).
```swift
let names = ["Ji-sun", "Jin-su", "Min-jae", "Young-ho"]
let evenlyChunked = names.chunks(ofCount: 2)
// ~ [["Ji-sun", "Jin-su"], ["Min-jae", "Young-ho"]]
let chunkedByFirstLetter = names.chunked(on: \.first)
// equivalent to [("J", ["Ji-sun", "Jin-su"]), ("M", ["Min-jae"]), ("Y", ["Young-ho"])]
```
## Topics
### Chunking a Collection by Count
- ``Swift/Collection/chunks(ofCount:)``
- ``Swift/Collection/evenlyChunked(in:)``
### Chunking a Collection by Predicate
- ``Swift/Collection/chunked(by:)``
- ``Swift/LazySequenceProtocol/chunked(by:)``
### Chunking a Collection by Subject
- ``Swift/Collection/chunked(on:)``
- ``Swift/LazySequenceProtocol/chunked(on:)``
### Supporting Types
- ``ChunkedByCollection``
- ``ChunkedOnCollection``
- ``ChunksOfCountCollection``
- ``EvenlyChunkedCollection``
@@ -0,0 +1,32 @@
# Combinations and Permutations
Find the combinations and permutations of any collection's elements,
or the product of two different collections.
## Topics
### Combinations
- ``Swift/Collection/combinations(ofCount:)-26o4x``
- ``Swift/Collection/combinations(ofCount:)-53jql``
### Permutations
- ``Swift/Collection/permutations(ofCount:)-7rc99``
- ``Swift/Collection/permutations(ofCount:)-5zvhn``
### Unique Permutations
- ``Swift/Collection/uniquePermutations(ofCount:)-2extq``
- ``Swift/Collection/uniquePermutations(ofCount:)-48r1k``
### Product
- ``product(_:_:)``
### Supporting Types
- ``CombinationsSequence``
- ``PermutationsSequence``
- ``UniquePermutationsSequence``
- ``Product2Sequence``
@@ -0,0 +1,14 @@
# DeprecatedScan
These methods are deprecated; use the `reductions` family of methods instead.
See: <doc:Reductions>
## Topics
- ``Swift/Sequence/scan(_:)``
- ``Swift/Sequence/scan(_:_:)``
- ``Swift/Sequence/scan(into:_:)``
- ``Swift/LazySequenceProtocol/scan(_:)``
- ``Swift/LazySequenceProtocol/scan(_:_:)``
- ``Swift/LazySequenceProtocol/scan(into:_:)``
@@ -0,0 +1,42 @@
# Extending
Chain two collections end-to-end,
or repeat a collection forever or a specific number of times.
## Overview
_Chaining_ two collections
```swift
let letters = chain("abcd", "EFGH")
// String(letters) == "abcdEFGH"
for (num, letter) in zip((1...3).cycled(), letters) {
print(num, letter)
}
// 1 a
// 2 b
// 3 c
// 1 d
// 2 E
// 3 F
// 1 G
// 2 H
```
## Topics
### Chaining Two Collections
- ``chain(_:_:)``
### Cycling a Collection
- ``Swift/Collection/cycled()``
- ``Swift/Collection/cycled(times:)``
### Supporting Types
- ``Chain2Sequence``
- ``CycledSequence``
- ``CycledTimesCollection``
@@ -0,0 +1,41 @@
# Filtering
Remove duplicated elements or strip the `nil` values from a sequence or collection.
## Overview
Use the _uniquing_ methods to remove duplicates from a sequence or collection, or to remove elements that have a duplicated property.
```swift
let numbers = [1, 2, 3, 3, 2, 3, 3, 2, 2, 2, 1]
let unique = numbers.uniqued()
// Array(unique) == [1, 2, 3]
```
The `compacted()` method removes all `nil` values from a sequence or collection of optionals:
```swift
let array: [Int?] = [10, nil, 30, nil, 2, 3, nil, 5]
let withNoNils = array.compacted()
// Array(withNoNils) == [10, 30, 2, 3, 5]
```
## Topics
### Uniquing Elements
- ``Swift/Sequence/uniqued()``
- ``Swift/Sequence/uniqued(on:)``
- ``Swift/LazySequenceProtocol/uniqued(on:)``
### Filtering out `nil` Elements
- ``Swift/Collection/compacted()``
- ``Swift/Sequence/compacted()``
### Supporting Types
- ``UniquedSequence``
- ``CompactedSequence``
- ``CompactedCollection``
@@ -0,0 +1,35 @@
# Joining
Join the parts of a collection of collections,
providing a connecting element or collection,
or a closure that produces the connector.
## Topics
### Joining by an Element
- ``Swift/Sequence/joined(by:)-6mrf9``
- ``Swift/Sequence/joined(by:)-9hyaf``
- ``Swift/Collection/joined(by:)-430ue``
- ``Swift/LazySequenceProtocol/joined(by:)-3yjw0``
- ``Swift/LazySequenceProtocol/joined(by:)-47xvy``
### Joining by a Collection
- ``Swift/Sequence/joined(by:)-62j1h``
- ``Swift/Sequence/joined(by:)-9b108``
- ``Swift/Collection/joined(by:)-28n3b``
- ``Swift/LazySequenceProtocol/joined(by:)-4neii``
- ``Swift/LazySequenceProtocol/joined(by:)-49xws``
### Interspersing Elements
- ``Swift/Sequence/interspersed(with:)``
### Supporting Types
- ``JoinedBySequence``
- ``JoinedByCollection``
- ``JoinedByClosureSequence``
- ``JoinedByClosureCollection``
- ``InterspersedSequence``
@@ -0,0 +1,23 @@
# Finding the Minimum and Maximum
Find the minimum and maximum elements simultaneously,
or a specific number of elements at the minimum and maximum.
## Topics
### Finding Minimum or Maximum Elements
- ``Swift/Sequence/min(count:)``
- ``Swift/Collection/min(count:)``
- ``Swift/Sequence/min(count:sortedBy:)``
- ``Swift/Collection/min(count:sortedBy:)``
- ``Swift/Sequence/max(count:)``
- ``Swift/Collection/max(count:)``
- ``Swift/Sequence/max(count:sortedBy:)``
- ``Swift/Collection/max(count:sortedBy:)``
### Finding the Minimum and Maximum Elements Simulataneously
- ``Swift/Sequence/minAndMax()``
- ``Swift/Sequence/minAndMax(by:)``
@@ -0,0 +1,63 @@
# Partitioning and Rotating
Partition a collection according to a unary predicate,
rotate a collection around a particular index,
or find the index where a collection is already partitioned.
## Overview
A _stable partition_ maintains the relative order of elements within both partitions.
```swift
// partition(by:) - unstable ordering
var numbers = [10, 20, 30, 40, 50, 60, 70, 80]
let p1 = numbers.partition(by: { $0.isMultiple(of: 20) })
// p1 == 4
// numbers == [10, 70, 30, 50, 40, 60, 20, 80]
// ^ start of second partition
// stablePartition(by:) - maintains relative ordering
numbers = [10, 20, 30, 40, 50, 60, 70, 80]
let p2 = numbers.stablePartition(by: { $0.isMultiple(of: 20) })
// p2 == 4
// numbers == [10, 30, 50, 70, 20, 40, 60, 80]
// ^ start of second partition
```
Use the `rotate` method to shift the elements of a collection to start at a new position, moving the displaced elements to the end:
```swift
var numbers = [10, 20, 30, 40, 50, 60, 70, 80]
let p = numbers.rotate(toStartAt: 2)
// numbers == [30, 40, 50, 60, 70, 80, 10, 20]
// p == 6 -- numbers[p] == 10
```
## Topics
### Stable Partition
- ``Swift/MutableCollection/stablePartition(by:)``
- ``Swift/MutableCollection/stablePartition(subrange:by:)``
- ``Swift/Sequence/partitioned(by:)``
- ``Swift/Collection/partitioned(by:)``
### Partition of Subranges
- ``Swift/MutableCollection/partition(subrange:by:)-5vdh7``
- ``Swift/MutableCollection/partition(subrange:by:)-4gpqz``
### Finding a Partition Index
- ``Swift/Collection/partitioningIndex(where:)``
### Rotation
- ``Swift/MutableCollection/rotate(toStartAt:)-9fp48``
- ``Swift/MutableCollection/rotate(toStartAt:)-2r55j``
- ``Swift/MutableCollection/rotate(subrange:toStartAt:)-ov6a``
- ``Swift/MutableCollection/rotate(subrange:toStartAt:)-5teoq``
### Reversing
- ``Swift/MutableCollection/reverse(subrange:)``
@@ -0,0 +1,35 @@
# Reductions
Find the incremental values of a sequence "reduce" operation.
## Overview
Call one of the `reductions` methods when you want the result of a `reduce` operation along with all of its intermediate values:
```swift
let exclusiveRunningTotal = (1...5).reductions(0, +)
print(exclusiveRunningTotal)
// prints [0, 1, 3, 6, 10, 15]
let inclusiveRunningTotal = (1...5).reductions(+)
print(inclusiveRunningTotal)
// prints [1, 3, 6, 10, 15]
```
## Topics
- ``Swift/Sequence/reductions(_:)``
- ``Swift/Sequence/reductions(_:_:)``
- ``Swift/Sequence/reductions(into:_:)``
- ``Swift/LazySequenceProtocol/reductions(_:)``
- ``Swift/LazySequenceProtocol/reductions(_:_:)``
- ``Swift/LazySequenceProtocol/reductions(into:_:)``
### Supporting Types
- ``InclusiveReductionsSequence``
- ``ExclusiveReductionsSequence``
### Deprecated Methods
- <doc:DeprecatedScan>
@@ -0,0 +1,17 @@
# Random Sampling
Choose a specified number of random elements from a sequence or collection.
## Topics
### Random Sampling
- ``Swift/Sequence/randomSample(count:)``
- ``Swift/Collection/randomSample(count:)``
- ``Swift/Collection/randomStableSample(count:)``
### Random Sampling with a Generator
- ``Swift/Sequence/randomSample(count:using:)``
- ``Swift/Collection/randomSample(count:using:)``
- ``Swift/Collection/randomStableSample(count:using:)``
@@ -0,0 +1,25 @@
# Selecting Elements
Select elements at a particular interval, the first mapped value,
or iterate of elements with their indices.
## Topics
### Selecting Elements at an Interval
- ``Swift/Sequence/striding(by:)``
- ``Swift/Collection/striding(by:)``
### Conditionally Finding the First Mapped Value
- ``Swift/Sequence/firstNonNil(_:)``
### Iterating Over Elements with Their Indices
- ``Swift/Collection/indexed()``
### Supporting Types
- ``IndexedCollection``
- ``StridingSequence``
- ``StridingCollection``
@@ -0,0 +1,29 @@
# Slicing and Splitting
Iterate over tuple pairs of adjacent elements, overlapping windows of a specified size, or lazily-calculated splits.
## Topics
### Adjacent Pairs
- ``Swift/Sequence/adjacentPairs()``
- ``Swift/Collection/adjacentPairs()``
### Windows
- ``Swift/Collection/windows(ofCount:)``
### Lazily Splitting a Collection
- ``Swift/LazySequenceProtocol/split(separator:maxSplits:omittingEmptySubsequences:)-4q4x8``
- ``Swift/LazySequenceProtocol/split(maxSplits:omittingEmptySubsequences:whereSeparator:)-68oqf``
- ``Swift/LazySequenceProtocol/split(separator:maxSplits:omittingEmptySubsequences:)-a46s``
- ``Swift/LazySequenceProtocol/split(maxSplits:omittingEmptySubsequences:whereSeparator:)-3rwee``
### Supporting Types
- ``AdjacentPairsSequence``
- ``AdjacentPairsCollection``
- ``WindowsOfCountCollection``
- ``SplitSequence``
- ``SplitCollection``
@@ -0,0 +1,27 @@
# Trimming
Remove unwanted elements from the start, the end, or both ends of a collection.
## Topics
### Trimming Both Ends of a Collection
- ``Swift/BidirectionalCollection/trimming(while:)``
- ``Swift/BidirectionalCollection/trim(while:)-781az``
- ``Swift/BidirectionalCollection/trim(while:)-6cbz3``
### Trimming from the Start
- ``Swift/Collection/trimmingPrefix(while:)``
- ``Swift/Collection/trimPrefix(while:)-2r8n8``
- ``Swift/Collection/trimPrefix(while:)-93obt``
### Trimming from the End
- ``Swift/BidirectionalCollection/trimmingSuffix(while:)``
- ``Swift/BidirectionalCollection/trimSuffix(while:)-33ubj``
- ``Swift/BidirectionalCollection/trimSuffix(while:)-3o6x9``
### Finding the Suffix of a Collection
- ``Swift/BidirectionalCollection/suffix(while:)``
+5 -1
View File
@@ -94,6 +94,10 @@ extension Collection {
/// Returns a collection of pairs *(i, x)*, where *i* represents an index of
/// the collection, and *x* represents an element.
///
/// The `indexed()` method is similar to the standard library's `enumerated()`
/// method, but provides the index with each element instead of a zero-based
/// counter.
///
/// This example iterates over the indices and elements of a set, building an
/// array consisting of indices of names with five or fewer letters.
///
@@ -105,7 +109,7 @@ extension Collection {
/// }
/// }
///
/// Returns: A collection of paired indices and elements of this collection.
/// - Returns: A collection of paired indices and elements of this collection.
@inlinable
public func indexed() -> IndexedCollection<Self> {
IndexedCollection(base: self)
+3 -3
View File
@@ -125,7 +125,7 @@ extension Sequence {
/// largest values:
///
/// let numbers = [7, 1, 6, 2, 8, 3, 9]
/// let smallestThree = numbers.max(count: 3, sortedBy: <)
/// let largestThree = numbers.max(count: 3, sortedBy: <)
/// // [7, 8, 9]
///
/// If you need to sort a sequence but only need to access its largest
@@ -197,7 +197,7 @@ extension Sequence where Element: Comparable {
/// largest values:
///
/// let numbers = [7, 1, 6, 2, 8, 3, 9]
/// let smallestThree = numbers.max(count: 3)
/// let largestThree = numbers.max(count: 3)
/// // [7, 8, 9]
///
/// If you need to sort a sequence but only need to access its largest
@@ -280,7 +280,7 @@ extension Collection {
/// largest values:
///
/// let numbers = [7, 1, 6, 2, 8, 3, 9]
/// let smallestThree = numbers.max(count: 3, sortedBy: <)
/// let largestThree = numbers.max(count: 3, sortedBy: <)
/// // [7, 8, 9]
///
/// If you need to sort a collection but only need to access its largest
-58
View File
@@ -235,61 +235,3 @@ extension Sequence {
return randomSample(count: k, using: &g)
}
}
//===----------------------------------------------------------------------===//
// randomElement()
//===----------------------------------------------------------------------===//
// This method is a single-element specialization of `randomSample(count:)`,
// and extends the stdlib's `randomElement()` functionality (which is available
// for collections) down to sequences.
extension Sequence {
/// Randomly selects an element from this sequence, using the given generator
/// as the source of randomness.
///
/// - Parameter rng: The random number generator to use for sampling.
/// - Returns: A random element. If the sequence has no elements, this method
/// returns `nil`.
///
/// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
public func randomElement<G: RandomNumberGenerator>(
using rng: inout G
) -> Element? {
var iterator = makeIterator()
guard var result = iterator.next() else {
return nil
}
var w = 1.0
while true {
w *= nextW(k: 1, using: &rng)
var offset = nextOffset(w: w, using: &rng)
while offset > 0, let _ = iterator.next() {
offset -= 1
}
guard let nextElement = iterator.next()
else { break }
result = nextElement
}
return result
}
/// Randomly selects an element from this sequence.
///
/// This method is equivalent to calling `randomSample(using:)`, passing in
/// the system's default random generator.
///
/// - Returns: A random element. If the sequence has no elements, this method
/// returns `nil`.
///
/// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
public func randomElement() -> Element? {
var g = SystemRandomNumberGenerator()
return randomElement(using: &g)
}
}
-19
View File
@@ -1,19 +0,0 @@
//===----------------------------------------------------------*- swift -*-===//
//
// This source file is part of the Swift Argument Parser open source project
//
// Copyright (c) 2020 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
//===----------------------------------------------------------------------===//
#error("""
-----------------------------------------------------
Please test with `swift test --enable-test-discovery`
-----------------------------------------------------
""")
+33 -3
View File
@@ -87,9 +87,6 @@ final class ChunkedTests: XCTestCase {
[1, 2, 3, 4, 6, 7, 8, 9].lazy.chunked(by: { $1 - $0 == 1 }),
[[1, 2, 3, 4], [6, 7, 8, 9]])
print(Array([1, 2, 3].lazy.chunked(by: { $1 - $0 == 1 })))
print(Array([1, 2, 3].lazy.chunked(by: { $1 - $0 == 1 }).reversed()))
XCTAssertEqualSequences(
[1, 2, 3, 4, 6, 7, 8, 9].lazy.chunked(by: { $1 - $0 == 1 }).reversed(),
[[6, 7, 8, 9], [1, 2, 3, 4]])
@@ -173,4 +170,37 @@ final class ChunkedTests: XCTestCase {
expectedCount: range.count / i + (range.count % i).signum())
}
}
func testEvenChunks() {
XCTAssertEqualSequences(
(0..<10).evenlyChunked(in: 4),
[0..<3, 3..<6, 6..<8, 8..<10])
XCTAssertEqualSequences(
(0..<3).evenlyChunked(in: 5),
[0..<1, 1..<2, 2..<3, 3..<3, 3..<3])
XCTAssertEqualSequences(
"".evenlyChunked(in: 0),
[])
XCTAssertEqualSequences(
"".evenlyChunked(in: 1),
[""])
}
func testEvenChunksIndexTraversals() {
let validator = IndexValidator<EvenlyChunkedCollection<Range<Int>>>()
[
(0..<10).evenlyChunked(in: 1),
(0..<10).evenlyChunked(in: 2),
(0..<10).evenlyChunked(in: 3),
(0..<10).evenlyChunked(in: 10),
(0..<10).evenlyChunked(in: 20),
(0..<0).evenlyChunked(in: 0),
(0..<0).evenlyChunked(in: 1),
(0..<0).evenlyChunked(in: 10),
].forEach { validator.validate($0) }
}
}
@@ -12,17 +12,13 @@
import XCTest
@testable import Algorithms
func expectedRange(for value: Int) -> ClosedRange<Int> {
((value / 3) * 2) ... ((value / 3) * 4)
}
func validateRandomSamples<S: Sequence>(
_ samples: [Int: Int],
elements: S,
expectedValue: Int,
file: StaticString = #file, line: UInt = #line
) where S.Element == Int {
let expectedRange = expectedRange(for: expectedValue)
let expectedRange = ((expectedValue / 3) * 2) ... ((expectedValue / 3) * 4)
XCTAssertEqualSequences(samples.keys.sorted(), elements,
file: file, line: line)
for v in samples.values {
@@ -32,44 +28,41 @@ func validateRandomSamples<S: Sequence>(
private let n = 100
private let k = 12
private let iterations = 1000
/// A collection to sample from.
private let iterations = 10_000
private let c = 0..<n
/// A sequence to sample from.
private let s = sequence(first: 0, next: { $0 == n - 1 ? nil : $0 + 1 })
/// An empty sequence
private let emptySequence = sequence(state: 0, next: { (_) -> Int? in nil })
final class RandomSampleTests: XCTestCase {
func testRandomStableSampleCollection() {
let samples: [Int: Int] = (0..<iterations).reduce(into: [:]) { result, _ in
let sample = c.randomStableSample(count: k)
XCTAssert(sample.isSorted())
result.merge(sample.frequencies, uniquingKeysWith: +)
for x in sample {
result[x, default: 0] += 1
}
}
validateRandomSamples(samples, elements: c, expectedValue: (k * iterations) / n)
}
func testRandomSampleCollection() {
let samples: [Int: Int] = (0..<iterations).reduce(into: [:]) { result, _ in
result.merge(c.randomSample(count: k).frequencies, uniquingKeysWith: +)
for x in c.randomSample(count: k) {
result[x, default: 0] += 1
}
}
validateRandomSamples(samples, elements: c, expectedValue: (k * iterations) / n)
}
func testRandomSampleSequence() {
let samples: [Int: Int] = (0..<iterations).reduce(into: [:]) { result, _ in
result.merge(s.randomSample(count: k).frequencies, uniquingKeysWith: +)
for x in s.randomSample(count: k) {
result[x, default: 0] += 1
}
}
validateRandomSamples(samples, elements: s, expectedValue: (k * iterations) / n)
}
func testRandomSampleEdgeCases() {
XCTAssert(emptySequence.randomSample(count: 10).isEmpty)
XCTAssert(([] as [Int]).randomSample(count: 10).isEmpty)
XCTAssert(([] as [Int]).randomStableSample(count: 10).isEmpty)
XCTAssert(c.randomStableSample(count: 0).isEmpty)
XCTAssertEqualSequences(c.randomStableSample(count: n), c)
XCTAssertEqualSequences(c.randomStableSample(count: n * 2), c)
@@ -84,23 +77,21 @@ final class RandomSampleTests: XCTestCase {
}
func testRandomSampleRepeatable() {
let seed = UInt64.random(in: 0 ... .max)
var generator = SplitMix64(seed: seed)
var generator = SplitMix64(seed: 0)
let sample1a = c.randomSample(count: k, using: &generator)
generator = SplitMix64(seed: seed)
generator = SplitMix64(seed: 0)
let sample2a = c.randomSample(count: k, using: &generator)
XCTAssertEqual(sample1a, sample2a)
generator = SplitMix64(seed: seed)
generator = SplitMix64(seed: 0)
let sample1b = s.randomSample(count: k, using: &generator)
generator = SplitMix64(seed: seed)
generator = SplitMix64(seed: 0)
let sample2b = s.randomSample(count: k, using: &generator)
XCTAssertEqual(sample1b, sample2b)
generator = SplitMix64(seed: seed)
generator = SplitMix64(seed: 0)
let sample1c = c.randomStableSample(count: k, using: &generator)
generator = SplitMix64(seed: seed)
generator = SplitMix64(seed: 0)
let sample2c = c.randomStableSample(count: k, using: &generator)
XCTAssertEqual(sample1c, sample2c)
}
@@ -132,37 +123,4 @@ final class RandomSampleTests: XCTestCase {
almostAllZero = AlmostAllZeroGenerator(seed: 0)
_ = c.randomSample(count: k, using: &almostAllZero) // must not crash
}
func testSequenceRandomElement() {
XCTAssertNil(emptySequence.randomElement())
let expectedRange = expectedRange(for: iterations)
let randomElements = (0..<(n*iterations)).map { _ in
s.randomElement()!
}.frequencies
XCTAssertEqual(randomElements.count, n)
XCTAssert(randomElements.values.allSatisfy { expectedRange.contains($0) })
let oneElementSequence = sequence(first: 0, next: { _ in nil })
let randomOneElement = (0..<iterations).map { _ in
oneElementSequence.randomElement()!
}
XCTAssert(randomOneElement.allSatisfy { $0 == 0 })
let twoElementSequence = sequence(state: [1, 2].makeIterator(), next: { $0.next() })
let randomTwoElement = (0..<(2*iterations)).map { _ in
twoElementSequence.randomElement()!
}.frequencies
XCTAssertEqual(randomTwoElement.count, 2)
XCTAssert(randomElements.values.allSatisfy { expectedRange.contains($0) })
}
func testSequenceRandomElementRepeatable() {
let seed = UInt64.random(in: 0 ... .max)
var generator = SplitMix64(seed: seed)
let elements1 = (0..<500).map { _ in s.randomElement(using: &generator)! }
generator = SplitMix64(seed: seed)
let elements2 = (0..<500).map { _ in s.randomElement(using: &generator)! }
XCTAssertEqual(elements1, elements2)
}
}
@@ -23,12 +23,6 @@ extension Sequence where Element: Comparable {
}
}
extension Sequence where Element: Hashable {
var frequencies: [Element: Int] {
reduce(into: [:]) { $0[$1, default: 0] += 1 }
}
}
extension Numeric {
func factorial() -> Self {
guard self != 0 else { return 1 }