The stdlib's randomElement() method extends Collection, since it
operates by selecting a random index. This adds randomElement() as
a Sequence method, specializing the reservoir sampling algorithm
from randomSample(count:) for a count of 1.
* Use back ticks around code references
* Add missing spaces before parenthesis
* Use “passed” instead of “past”
Add missing comma
Add back ticks around code references
Add missing space before parenthesis
* Consistently use spaces around `%` operator
Co-authored-by: Matt Zanchelli <mattt@apple.com>
This could result in fewer comparisons.
Additionally, it ensures that the insertion index is valid for insertion. The `removeLast()` documentation states:
> Calling this method may invalidate all saved indices of this collection. Do not rely on a previously stored index value after altering a collection with any operation that can change its length.
* Add `partitioned(_:)`
`partitioned(_:)` works like `filter(_:)`, but also returns the excluded elements by returning a tuple of two `Array`s
* For collections with fewer than 8 elements, use the `Sequence`-based implementation
This constant was determined using benchmarking. More information: https://github.com/apple/swift-algorithms/pull/152#issuecomment-887130149
* Remove check for collections fewer than 8 elements
* Make `_partitioned` `internal`
* Prefer `Array` over `ContiguousArray`
* Document `partitioned(_:)` on `Collection`
* Remove `partitioned(upTo:)`
* Remove `_tupleMap`
* Remove `_partitioned` and use it inline (since it’s no longer used by the `Collection` implementation
* Remove unnecessary conversation of `Array` to `Array`
* Correct indentation
Co-authored-by: Xiaodi Wu <13952+xwu@users.noreply.github.com>
* Consistent syntax
Co-authored-by: Xiaodi Wu <13952+xwu@users.noreply.github.com>
* Add an external `by:` label to `partitioned`
* Add labels to returned tuple `falseElements`, `trueElements`
* Correct function signature
* Rename `belongsInSecondCollection` parameter name to simply `predicate`
The parameter name was potentially confusing. Unlike the other `partition` functions, this function can rely on its named tuple to clarify its behavior.
* Update copyright information
Co-authored-by: Nate Cook <natecook@apple.com>
* Update documentation
Co-authored-by: Nate Cook <natecook@apple.com>
* Update comment
* Add a precondition to ensure that the count matches up with the number of actual elements found while iterating
Co-authored-by: Xiaodi Wu <13952+xwu@users.noreply.github.com>
Co-authored-by: Nate Cook <natecook@apple.com>
* Rename types to include a Sequence or Collection suffix, and clean up some guides
* Various refactors
* Replace `validateIndexTraversals` test method with `IndexValidator` type
* Add LazySequenceProtocol to StridingSequence, StridingCollection
* Update the Numerics dependency to 1.0
* Set `IndexedCollection.Indices` to `Base.Indices`
* Remove deprecations
* Update the changelog/README for the 1.0.0 release
* Fix compiler error on Linux
* Rename `WindowsCollection` to `WindowsOfCountCollection`
Benchmarks on Xcode 12.4 showed compiling / type checking
StrideCollection.offsetBackward was the bottleneck for building
the package. Replacing the ternary operator in that function
with an explicit if/else removes the bottleneck.
* Add function to find MIN and MAX in one pass
Add a method extending sequences that finds both the minimal and maximal elements of the receiver in a single pass, based off a given ordering predicate. Add an overload that defaults the comparison predicate to the standard less-than operator.
* Add scan function
* Add initial conditional conformances to Collection and BidirectionalCollection
* Rename scan to reductions
* Add information to the readme about the reductions name
* Add eager API
* Remove Reductions' conformance to BidirectionalCollection
* Implement Reductions subscript such that it occurs in constant time
* Add a variant which includes the given initial result
* Add a variant which takes no initial result value
* Add excluding label to show the initial result is not included
* Test lazy implementations
* Remove reductions(including:_:)
* Add conformance to LazySequenceProtocol and LazyCollectionProtocol when the base sequence conforms
* Fix implementation of lazy reductions
* Add test cases for sequences with one element
* Tidy up tests
* Improve ergonomics of no initial value eager reductions call and provide it as an extension on Sequence
* Add lazy InclusiveReductions sequence
* Rename Reductions to ExclusiveReductions
* Add Collection implementation for InclusiveReductions
* Update guide
* Add links for C++ implementations
* Add conformance to Collection for ExclusiveReductions
* Improve ergonomics of ExclusiveReductions' index representation
* Improve ergonomics of InclusiveReductions' index representation by sharing the Index implementation
* Tidy up internal function
* Add exclusive eager version of reductions(into:_:)
* Use new lazy assertion functions
* Correct the complexity claims for reductions
* Separate the index types
This will allow for future changes to either implementation without causing a breakage for the other.
* Update guide to reflect that arrays are returned directly
* Add scan as deprecated methods
* Add lazy overload of reductions(into:_:)
* Add the reductions(into:_:) functions
* More succinctly introduce reductions
* Add a note about the deprecated scan functions
* Update documentation
* Add @inlinable and @usableFromInline
* Copy documentation to all variants of reductions
* Test the value after the function is complete
* Just use the += operator
* Add an example for reductions(into:_:)
* Improve the documentation of the return value
* Update complexity note
* Use the reduce documentation for inspiration for the discussion of reductions
* Add uniquePermutations as wrapper for nextPermutation
* Implement uniquePermutations(ofCount:) variants
* Simplify UniquePermutations.Iterator.next()
* Add tests for uniquePermutations
* Move to a predicate-based uniquePermutations
* Add method documentation
* Convert to Hashable-based uniquing instead of Comparable
* Streamline tests, cover uniqueness
* Use optional count to collapse no-count method
* Update API documentation
* Remove leftover version of nextPermutation()
* Remove Hashable requirement from the UniquePermutations type
* Update documentation
* Apply Tim's great revisions
Co-authored-by: Tim Vermeulen <tvermeulen@apple.com>
* Add lazy conformance to UniquePermutations
Co-authored-by: Tim Vermeulen <tvermeulen@apple.com>
* Implement StrideSequence so that the default implementation for collection uses IndexingIterator
* Update Sources/Algorithms/Stride.swift
Co-authored-by: Tim Vermeulen <tvermeulen@apple.com>
* reinstate documentation for Sequence and remove explicit Sequence conformance on Stride
* documentation
* rename Stride to StrideCollection
Co-authored-by: Tim Vermeulen <tvermeulen@apple.com>
`split(maxSplits:omittingEmptySubsequences:whereSeparator:)`
and
`split(separator:maxSplits:omittingEmptySubsequences:)`
now operate lazily when called on `LazySequenceProtocol`- or
`LazyCollectionProtocol`-conforming values. In the latter case,
no additional storage is allocated on the heap.
This renames sortedPrefix to min(count:), adds max(count:),
and moves both methods down to Sequence.
In order to still provide the optimization when `count` is close to
a collection's length, we include a Collection-specific overload of
all methods. These won't be accessed when in a Sequence-generic context,
but it's the best we can do without adding these methods as protocol
requirements.