[stdlib] Update complexity docs for seq/collection algorithms (#17254) (#18247)
* [stdlib] Update complexity docs for seq/collection algorithms
This corrects and standardizes the complexity documentation for Sequence
and Collection methods. The use of constants is more consistent, with `n`
equal to the length of the target collection, `m` equal to the length of
a collection passed in as a parameter, and `k` equal to any other passed
or calculated constant.
* Apply notes from @brentdax about complexity nomenclature
* Change `n` to `distance` in `index(_:offsetBy:)`
* Use equivalency language more places; sync across array types
* Use k instead of n for parameter names
* Slight changes to index(_:offsetBy:) discussion.
* Update tests with new parameter names
diff --git a/stdlib/public/core/Arrays.swift.gyb b/stdlib/public/core/Arrays.swift.gyb
index 84a2090..791da64 100644
--- a/stdlib/public/core/Arrays.swift.gyb
+++ b/stdlib/public/core/Arrays.swift.gyb
@@ -619,24 +619,25 @@
/// print(numbers[i])
/// // Prints "50"
///
- /// The value passed as `n` must not offset `i` beyond the bounds of the
- /// collection.
+ /// The value passed as `distance` must not offset `i` beyond the bounds of
+ /// the collection.
///
/// - Parameters:
/// - i: A valid index of the array.
- /// - n: The distance to offset `i`.
- /// - Returns: An index offset by `n` from the index `i`. If `n` is positive,
- /// this is the same value as the result of `n` calls to `index(after:)`.
- /// If `n` is negative, this is the same value as the result of `-n` calls
- /// to `index(before:)`.
+ /// - distance: The distance to offset `i`.
+ /// - Returns: An index offset by `distance` from the index `i`. If
+ /// `distance` is positive, this is the same value as the result of
+ /// `distance` calls to `index(after:)`. If `distance` is negative, this
+ /// is the same value as the result of `abs(distance)` calls to
+ /// `index(before:)`.
@inlinable
- public func index(_ i: Int, offsetBy n: Int) -> Int {
+ public func index(_ i: Int, offsetBy distance: Int) -> Int {
// NOTE: this is a manual specialization of index movement for a Strideable
// index that is required for Array performance. The optimizer is not
// capable of creating partial specializations yet.
// NOTE: Range checks are not performed here, because it is done later by
// the subscript function.
- return i + n
+ return i + distance
}
/// Returns an index that is the specified distance from the given index,
@@ -665,22 +666,25 @@
/// print(j)
/// // Prints "nil"
///
- /// The value passed as `n` must not offset `i` beyond the bounds of the
- /// collection, unless the index passed as `limit` prevents offsetting
+ /// The value passed as `distance` must not offset `i` beyond the bounds of
+ /// the collection, unless the index passed as `limit` prevents offsetting
/// beyond those bounds.
///
/// - Parameters:
/// - i: A valid index of the array.
- /// - n: The distance to offset `i`.
- /// - limit: A valid index of the collection to use as a limit. If `n > 0`,
- /// `limit` has no effect if it is less than `i`. Likewise, if `n < 0`,
- /// `limit` has no effect if it is greater than `i`.
- /// - Returns: An index offset by `n` from the index `i`, unless that index
- /// would be beyond `limit` in the direction of movement. In that case,
- /// the method returns `nil`.
+ /// - distance: The distance to offset `i`.
+ /// - limit: A valid index of the collection to use as a limit. If
+ /// `distance > 0`, `limit` has no effect if it is less than `i`.
+ /// Likewise, if `distance < 0`, `limit` has no effect if it is greater
+ /// than `i`.
+ /// - Returns: An index offset by `distance` from the index `i`, unless that
+ /// index would be beyond `limit` in the direction of movement. In that
+ /// case, the method returns `nil`.
+ ///
+ /// - Complexity: O(1)
@inlinable
public func index(
- _ i: Int, offsetBy n: Int, limitedBy limit: Int
+ _ i: Int, offsetBy distance: Int, limitedBy limit: Int
) -> Int? {
// NOTE: this is a manual specialization of index movement for a Strideable
// index that is required for Array performance. The optimizer is not
@@ -688,10 +692,10 @@
// NOTE: Range checks are not performed here, because it is done later by
// the subscript function.
let l = limit - i
- if n > 0 ? l >= 0 && l < n : l <= 0 && n < l {
+ if distance > 0 ? l >= 0 && l < distance : l <= 0 && distance < l {
return nil
}
- return i + n
+ return i + distance
}
/// Returns the distance between two indices.
@@ -735,12 +739,15 @@
/// - Parameter index: The position of the element to access. `index` must be
/// greater than or equal to `startIndex` and less than `endIndex`.
///
+%if Self == 'ContiguousArray':
/// - Complexity: Reading an element from an array is O(1). Writing is O(1)
/// unless the array's storage is shared with another array, in which case
/// writing is O(*n*), where *n* is the length of the array.
-%if Self == 'Array':
- /// If the array uses a bridged `NSArray` instance as its storage, the
- /// efficiency is unspecified.
+%else:
+ /// - Complexity: Reading an element from an array is O(1). Writing is O(1)
+ /// unless the array's storage is shared with another array or uses a
+ /// bridged `NSArray` instance as its storage, in which case writing is
+ /// O(*n*), where *n* is the length of the array.
%end
@inlinable
public subscript(index: Int) -> Element {
@@ -1416,9 +1423,8 @@
///
/// - Parameter newElement: The element to append to the array.
///
- /// - Complexity: Amortized O(1) over many additions. If the array uses a
- /// bridged `NSArray` instance as its storage, the efficiency is
- /// unspecified.
+ /// - Complexity: O(1) on average, over many calls to `append(_:)` on the
+ /// same array.
@inlinable
@_semantics("array.append_element")
public mutating func append(_ newElement: Element) {
@@ -1441,7 +1447,9 @@
///
/// - Parameter newElements: The elements to append to the array.
///
- /// - Complexity: O(*n*), where *n* is the length of the resulting array.
+ /// - Complexity: O(*m*) on average, where *m* is the length of
+ /// `newElements`, over many calls to `append(contentsOf:)` on the same
+ /// array.
@inlinable
@_semantics("array.append_contentsOf")
public mutating func append<S : Sequence>(contentsOf newElements: S)
@@ -1588,7 +1596,8 @@
/// `index` must be a valid index of the array or equal to its `endIndex`
/// property.
///
- /// - Complexity: O(*n*), where *n* is the length of the array.
+ /// - Complexity: O(*n*), where *n* is the length of the array. If
+ /// `i == endIndex`, this method is equivalent to `append(_:)`.
@inlinable
public mutating func insert(_ newElement: Element, at i: Int) {
_checkIndex(i)
@@ -1943,9 +1952,10 @@
/// a subrange must be valid indices of the array.
/// - newElements: The new elements to add to the array.
///
- /// - Complexity: O(`subrange.count`) if you are replacing a suffix of the
- /// array with an empty collection; otherwise, O(*n*), where *n* is the
- /// length of the array.
+ /// - Complexity: O(*n* + *m*), where *n* is length of the array and
+ /// *m* is the length of `newElements`. If the call to this method simply
+ /// appends the contents of `newElements` to the array, this method is
+ /// equivalent to `append(contentsOf:)`.
@inlinable
@_semantics("array.mutate_unknown")
public mutating func replaceSubrange<C>(
diff --git a/stdlib/public/core/BidirectionalCollection.swift b/stdlib/public/core/BidirectionalCollection.swift
index 34063b1..ed35a55 100644
--- a/stdlib/public/core/BidirectionalCollection.swift
+++ b/stdlib/public/core/BidirectionalCollection.swift
@@ -235,6 +235,8 @@
///
/// - Parameter bounds: A range of the collection's indices. The bounds of
/// the range must be valid indices of the collection.
+ ///
+ /// - Complexity: O(1)
subscript(bounds: Range<Index>) -> SubSequence { get }
// FIXME(ABI): Associated type inference requires this.
@@ -257,12 +259,12 @@
}
@inlinable // FIXME(sil-serialize-all)
- public func index(_ i: Index, offsetBy n: Int) -> Index {
- if n >= 0 {
- return _advanceForward(i, by: n)
+ public func index(_ i: Index, offsetBy distance: Int) -> Index {
+ if distance >= 0 {
+ return _advanceForward(i, by: distance)
}
var i = i
- for _ in stride(from: 0, to: n, by: -1) {
+ for _ in stride(from: 0, to: distance, by: -1) {
formIndex(before: &i)
}
return i
@@ -270,13 +272,13 @@
@inlinable // FIXME(sil-serialize-all)
public func index(
- _ i: Index, offsetBy n: Int, limitedBy limit: Index
+ _ i: Index, offsetBy distance: Int, limitedBy limit: Index
) -> Index? {
- if n >= 0 {
- return _advanceForward(i, by: n, limitedBy: limit)
+ if distance >= 0 {
+ return _advanceForward(i, by: distance, limitedBy: limit)
}
var i = i
- for _ in stride(from: 0, to: n, by: -1) {
+ for _ in stride(from: 0, to: distance, by: -1) {
if i == limit {
return nil
}
@@ -317,7 +319,7 @@
/// - Returns: The last element of the collection if the collection has one
/// or more elements; otherwise, `nil`.
///
- /// - Complexity: O(1).
+ /// - Complexity: O(1)
@inlinable // FIXME(sil-serialize-all)
public mutating func popLast() -> Element? {
guard !isEmpty else { return nil }
@@ -344,20 +346,20 @@
/// Removes the given number of elements from the end of the collection.
///
- /// - Parameter n: The number of elements to remove. `n` must be greater
+ /// - Parameter k: The number of elements to remove. `k` must be greater
/// than or equal to zero, and must be less than or equal to the number of
/// elements in the collection.
///
/// - Complexity: O(1) if the collection conforms to
- /// `RandomAccessCollection`; otherwise, O(*n*), where *n* is the length
- /// of the collection.
+ /// `RandomAccessCollection`; otherwise, O(*k*), where *k* is the number of
+ /// elements to remove.
@inlinable // FIXME(sil-serialize-all)
- public mutating func removeLast(_ n: Int) {
- if n == 0 { return }
- _precondition(n >= 0, "Number of elements to remove should be non-negative")
- _precondition(count >= n,
+ public mutating func removeLast(_ k: Int) {
+ if k == 0 { return }
+ _precondition(k >= 0, "Number of elements to remove should be non-negative")
+ _precondition(count >= k,
"Can't remove more items from a collection than it contains")
- self = self[startIndex..<index(endIndex, offsetBy: -n)]
+ self = self[startIndex..<index(endIndex, offsetBy: -k)]
}
}
@@ -374,18 +376,20 @@
/// print(numbers.dropLast(10))
/// // Prints "[]"
///
- /// - Parameter n: The number of elements to drop off the end of the
- /// collection. `n` must be greater than or equal to zero.
- /// - Returns: A subsequence that leaves off `n` elements from the end.
+ /// - Parameter k: The number of elements to drop off the end of the
+ /// collection. `k` must be greater than or equal to zero.
+ /// - Returns: A subsequence that leaves off `k` elements from the end.
///
- /// - Complexity: O(*n*), where *n* is the number of elements to drop.
+ /// - Complexity: O(1) if the collection conforms to
+ /// `RandomAccessCollection`; otherwise, O(*k*), where *k* is the number of
+ /// elements to drop.
@inlinable // FIXME(sil-serialize-all)
- public func dropLast(_ n: Int) -> SubSequence {
+ public func dropLast(_ k: Int) -> SubSequence {
_precondition(
- n >= 0, "Can't drop a negative number of elements from a collection")
+ k >= 0, "Can't drop a negative number of elements from a collection")
let end = index(
endIndex,
- offsetBy: -n,
+ offsetBy: -k,
limitedBy: startIndex) ?? startIndex
return self[startIndex..<end]
}
@@ -407,7 +411,9 @@
/// - Returns: A subsequence terminating at the end of the collection with at
/// most `maxLength` elements.
///
- /// - Complexity: O(*n*), where *n* is equal to `maxLength`.
+ /// - Complexity: O(1) if the collection conforms to
+ /// `RandomAccessCollection`; otherwise, O(*k*), where *k* is equal to
+ /// `maxLength`.
@inlinable // FIXME(sil-serialize-all)
public func suffix(_ maxLength: Int) -> SubSequence {
_precondition(
diff --git a/stdlib/public/core/ClosedRange.swift b/stdlib/public/core/ClosedRange.swift
index c9c1917..474ed75 100644
--- a/stdlib/public/core/ClosedRange.swift
+++ b/stdlib/public/core/ClosedRange.swift
@@ -232,24 +232,24 @@
}
@inlinable
- public func index(_ i: Index, offsetBy n: Int) -> Index {
+ public func index(_ i: Index, offsetBy distance: Int) -> Index {
switch i {
case .inRange(let x):
let d = x.distance(to: upperBound)
- if n <= d {
- let newPosition = x.advanced(by: numericCast(n))
+ if distance <= d {
+ let newPosition = x.advanced(by: numericCast(distance))
_precondition(newPosition >= lowerBound,
"Advancing past start index")
return .inRange(newPosition)
}
- if d - -1 == n { return .pastEnd }
+ if d - -1 == distance { return .pastEnd }
_preconditionFailure("Advancing past end index")
case .pastEnd:
- if n == 0 {
+ if distance == 0 {
return i
}
- if n < 0 {
- return index(.inRange(upperBound), offsetBy: numericCast(n + 1))
+ if distance < 0 {
+ return index(.inRange(upperBound), offsetBy: numericCast(distance + 1))
}
_preconditionFailure("Advancing past end index")
}
diff --git a/stdlib/public/core/Collection.swift b/stdlib/public/core/Collection.swift
index f8f9a29..28d8e16 100644
--- a/stdlib/public/core/Collection.swift
+++ b/stdlib/public/core/Collection.swift
@@ -628,7 +628,7 @@
/// or `Optional(nil)` if an element was determined to be missing;
/// otherwise, `nil`.
///
- /// - Complexity: O(*n*)
+ /// - Complexity: O(*n*), where *n* is the length of the collection.
func _customIndexOfEquatableElement(_ element: Element) -> Index??
/// Customization point for `Collection.lastIndex(of:)`.
@@ -664,22 +664,24 @@
/// print(s[i])
/// // Prints "t"
///
- /// The value passed as `n` must not offset `i` beyond the bounds of the
- /// collection.
+ /// The value passed as `distance` must not offset `i` beyond the bounds of
+ /// the collection.
///
/// - Parameters:
/// - i: A valid index of the collection.
- /// - n: The distance to offset `i`. `n` must not be negative unless the
- /// collection conforms to the `BidirectionalCollection` protocol.
- /// - Returns: An index offset by `n` from the index `i`. If `n` is positive,
- /// this is the same value as the result of `n` calls to `index(after:)`.
- /// If `n` is negative, this is the same value as the result of `-n` calls
- /// to `index(before:)`.
+ /// - distance: The distance to offset `i`. `distance` must not be negative
+ /// unless the collection conforms to the `BidirectionalCollection`
+ /// protocol.
+ /// - Returns: An index offset by `distance` from the index `i`. If
+ /// `distance` is positive, this is the same value as the result of
+ /// `distance` calls to `index(after:)`. If `distance` is negative, this
+ /// is the same value as the result of `abs(distance)` calls to
+ /// `index(before:)`.
///
/// - Complexity: O(1) if the collection conforms to
- /// `RandomAccessCollection`; otherwise, O(*n*), where *n* is the absolute
- /// value of `n`.
- func index(_ i: Index, offsetBy n: Int) -> Index
+ /// `RandomAccessCollection`; otherwise, O(*k*), where *k* is the absolute
+ /// value of `distance`.
+ func index(_ i: Index, offsetBy distance: Int) -> Index
/// Returns an index that is the specified distance from the given index,
/// unless that distance is beyond a given limiting index.
@@ -703,26 +705,28 @@
/// print(j)
/// // Prints "nil"
///
- /// The value passed as `n` must not offset `i` beyond the bounds of the
- /// collection, unless the index passed as `limit` prevents offsetting
+ /// The value passed as `distance` must not offset `i` beyond the bounds of
+ /// the collection, unless the index passed as `limit` prevents offsetting
/// beyond those bounds.
///
/// - Parameters:
/// - i: A valid index of the collection.
- /// - n: The distance to offset `i`. `n` must not be negative unless the
- /// collection conforms to the `BidirectionalCollection` protocol.
- /// - limit: A valid index of the collection to use as a limit. If `n > 0`,
- /// a limit that is less than `i` has no effect. Likewise, if `n < 0`, a
- /// limit that is greater than `i` has no effect.
- /// - Returns: An index offset by `n` from the index `i`, unless that index
- /// would be beyond `limit` in the direction of movement. In that case,
- /// the method returns `nil`.
+ /// - distance: The distance to offset `i`. `distance` must not be negative
+ /// unless the collection conforms to the `BidirectionalCollection`
+ /// protocol.
+ /// - limit: A valid index of the collection to use as a limit. If
+ /// `distance > 0`, a limit that is less than `i` has no effect.
+ /// Likewise, if `distance < 0`, a limit that is greater than `i` has no
+ /// effect.
+ /// - Returns: An index offset by `distance` from the index `i`, unless that
+ /// index would be beyond `limit` in the direction of movement. In that
+ /// case, the method returns `nil`.
///
/// - Complexity: O(1) if the collection conforms to
- /// `RandomAccessCollection`; otherwise, O(*n*), where *n* is the absolute
- /// value of `n`.
+ /// `RandomAccessCollection`; otherwise, O(*k*), where *k* is the absolute
+ /// value of `distance`.
func index(
- _ i: Index, offsetBy n: Int, limitedBy limit: Index
+ _ i: Index, offsetBy distance: Int, limitedBy limit: Index
) -> Index?
/// Returns the distance between two indices.
@@ -739,7 +743,7 @@
/// `BidirectionalCollection` protocol.
///
/// - Complexity: O(1) if the collection conforms to
- /// `RandomAccessCollection`; otherwise, O(*n*), where *n* is the
+ /// `RandomAccessCollection`; otherwise, O(*k*), where *k* is the
/// resulting distance.
func distance(from start: Index, to end: Index) -> Int
@@ -868,24 +872,26 @@
/// print(s[i])
/// // Prints "t"
///
- /// The value passed as `n` must not offset `i` beyond the bounds of the
- /// collection.
+ /// The value passed as `distance` must not offset `i` beyond the bounds of
+ /// the collection.
///
/// - Parameters:
/// - i: A valid index of the collection.
- /// - n: The distance to offset `i`. `n` must not be negative unless the
- /// collection conforms to the `BidirectionalCollection` protocol.
- /// - Returns: An index offset by `n` from the index `i`. If `n` is positive,
- /// this is the same value as the result of `n` calls to `index(after:)`.
- /// If `n` is negative, this is the same value as the result of `-n` calls
- /// to `index(before:)`.
+ /// - distance: The distance to offset `i`. `distance` must not be negative
+ /// unless the collection conforms to the `BidirectionalCollection`
+ /// protocol.
+ /// - Returns: An index offset by `distance` from the index `i`. If
+ /// `distance` is positive, this is the same value as the result of
+ /// `distance` calls to `index(after:)`. If `distance` is negative, this
+ /// is the same value as the result of `abs(distance)` calls to
+ /// `index(before:)`.
///
/// - Complexity: O(1) if the collection conforms to
- /// `RandomAccessCollection`; otherwise, O(*n*), where *n* is the absolute
- /// value of `n`.
+ /// `RandomAccessCollection`; otherwise, O(*k*), where *k* is the absolute
+ /// value of `distance`.
@inlinable
- public func index(_ i: Index, offsetBy n: Int) -> Index {
- return self._advanceForward(i, by: n)
+ public func index(_ i: Index, offsetBy distance: Int) -> Index {
+ return self._advanceForward(i, by: distance)
}
/// Returns an index that is the specified distance from the given index,
@@ -910,75 +916,80 @@
/// print(j)
/// // Prints "nil"
///
- /// The value passed as `n` must not offset `i` beyond the bounds of the
- /// collection, unless the index passed as `limit` prevents offsetting
+ /// The value passed as `distance` must not offset `i` beyond the bounds of
+ /// the collection, unless the index passed as `limit` prevents offsetting
/// beyond those bounds.
///
/// - Parameters:
/// - i: A valid index of the collection.
- /// - n: The distance to offset `i`. `n` must not be negative unless the
- /// collection conforms to the `BidirectionalCollection` protocol.
- /// - limit: A valid index of the collection to use as a limit. If `n > 0`,
- /// a limit that is less than `i` has no effect. Likewise, if `n < 0`, a
- /// limit that is greater than `i` has no effect.
- /// - Returns: An index offset by `n` from the index `i`, unless that index
- /// would be beyond `limit` in the direction of movement. In that case,
- /// the method returns `nil`.
+ /// - distance: The distance to offset `i`. `distance` must not be negative
+ /// unless the collection conforms to the `BidirectionalCollection`
+ /// protocol.
+ /// - limit: A valid index of the collection to use as a limit. If
+ /// `distance > 0`, a limit that is less than `i` has no effect.
+ /// Likewise, if `distance < 0`, a limit that is greater than `i` has no
+ /// effect.
+ /// - Returns: An index offset by `distance` from the index `i`, unless that
+ /// index would be beyond `limit` in the direction of movement. In that
+ /// case, the method returns `nil`.
///
/// - Complexity: O(1) if the collection conforms to
- /// `RandomAccessCollection`; otherwise, O(*n*), where *n* is the absolute
- /// value of `n`.
+ /// `RandomAccessCollection`; otherwise, O(*k*), where *k* is the absolute
+ /// value of `distance`.
@inlinable
public func index(
- _ i: Index, offsetBy n: Int, limitedBy limit: Index
+ _ i: Index, offsetBy distance: Int, limitedBy limit: Index
) -> Index? {
- return self._advanceForward(i, by: n, limitedBy: limit)
+ return self._advanceForward(i, by: distance, limitedBy: limit)
}
/// Offsets the given index by the specified distance.
///
- /// The value passed as `n` must not offset `i` beyond the bounds of the
- /// collection.
+ /// The value passed as `distance` must not offset `i` beyond the bounds of
+ /// the collection.
///
/// - Parameters:
/// - i: A valid index of the collection.
- /// - n: The distance to offset `i`. `n` must not be negative unless the
- /// collection conforms to the `BidirectionalCollection` protocol.
+ /// - distance: The distance to offset `i`. `distance` must not be negative
+ /// unless the collection conforms to the `BidirectionalCollection`
+ /// protocol.
///
/// - Complexity: O(1) if the collection conforms to
- /// `RandomAccessCollection`; otherwise, O(*n*), where *n* is the absolute
- /// value of `n`.
+ /// `RandomAccessCollection`; otherwise, O(*k*), where *k* is the absolute
+ /// value of `distance`.
@inlinable
- public func formIndex(_ i: inout Index, offsetBy n: Int) {
- i = index(i, offsetBy: n)
+ public func formIndex(_ i: inout Index, offsetBy distance: Int) {
+ i = index(i, offsetBy: distance)
}
/// Offsets the given index by the specified distance, or so that it equals
/// the given limiting index.
///
- /// The value passed as `n` must not offset `i` beyond the bounds of the
- /// collection, unless the index passed as `limit` prevents offsetting
+ /// The value passed as `distance` must not offset `i` beyond the bounds of
+ /// the collection, unless the index passed as `limit` prevents offsetting
/// beyond those bounds.
///
/// - Parameters:
/// - i: A valid index of the collection.
- /// - n: The distance to offset `i`. `n` must not be negative unless the
- /// collection conforms to the `BidirectionalCollection` protocol.
- /// - limit: A valid index of the collection to use as a limit. If `n > 0`,
- /// a limit that is less than `i` has no effect. Likewise, if `n < 0`, a
- /// limit that is greater than `i` has no effect.
- /// - Returns: `true` if `i` has been offset by exactly `n` steps without
- /// going beyond `limit`; otherwise, `false`. When the return value is
- /// `false`, the value of `i` is equal to `limit`.
+ /// - distance: The distance to offset `i`. `distance` must not be negative
+ /// unless the collection conforms to the `BidirectionalCollection`
+ /// protocol.
+ /// - limit: A valid index of the collection to use as a limit. If
+ /// `distance > 0`, a limit that is less than `i` has no effect.
+ /// Likewise, if `distance < 0`, a limit that is greater than `i` has no
+ /// effect.
+ /// - Returns: `true` if `i` has been offset by exactly `distance` steps
+ /// without going beyond `limit`; otherwise, `false`. When the return
+ /// value is `false`, the value of `i` is equal to `limit`.
///
/// - Complexity: O(1) if the collection conforms to
- /// `RandomAccessCollection`; otherwise, O(*n*), where *n* is the absolute
- /// value of `n`.
+ /// `RandomAccessCollection`; otherwise, O(*k*), where *k* is the absolute
+ /// value of `distance`.
@inlinable
public func formIndex(
- _ i: inout Index, offsetBy n: Int, limitedBy limit: Index
+ _ i: inout Index, offsetBy distance: Int, limitedBy limit: Index
) -> Bool {
- if let advancedIndex = index(i, offsetBy: n, limitedBy: limit) {
+ if let advancedIndex = index(i, offsetBy: distance, limitedBy: limit) {
i = advancedIndex
return true
}
@@ -1000,7 +1011,7 @@
/// `BidirectionalCollection` protocol.
///
/// - Complexity: O(1) if the collection conforms to
- /// `RandomAccessCollection`; otherwise, O(*n*), where *n* is the
+ /// `RandomAccessCollection`; otherwise, O(*k*), where *k* is the
/// resulting distance.
@inlinable
public func distance(from start: Index, to end: Index) -> Int {
@@ -1031,6 +1042,10 @@
/// a random element.
/// - Returns: A random element from the collection. If the collection is
/// empty, the method returns `nil`.
+ ///
+ /// - Complexity: O(1) if the collection conforms to
+ /// `RandomAccessCollection`; otherwise, O(*n*), where *n* is the length of
+ /// the collection.
@inlinable
public func randomElement<T: RandomNumberGenerator>(
using generator: inout T
@@ -1058,6 +1073,10 @@
///
/// - Returns: A random element from the collection. If the collection is
/// empty, the method returns `nil`.
+ ///
+ /// - Complexity: O(1) if the collection conforms to
+ /// `RandomAccessCollection`; otherwise, O(*n*), where *n* is the length of
+ /// the collection.
@inlinable
public func randomElement() -> Element? {
var g = SystemRandomNumberGenerator()
@@ -1332,18 +1351,19 @@
/// print(numbers.dropFirst(10))
/// // Prints "[]"
///
- /// - Parameter n: The number of elements to drop from the beginning of
- /// the collection. `n` must be greater than or equal to zero.
+ /// - Parameter k: The number of elements to drop from the beginning of
+ /// the collection. `k` must be greater than or equal to zero.
/// - Returns: A subsequence starting after the specified number of
/// elements.
///
- /// - Complexity: O(*n*), where *n* is the number of elements to drop from
- /// the beginning of the collection.
+ /// - Complexity: O(1) if the collection conforms to
+ /// `RandomAccessCollection`; otherwise, O(*k*), where *k* is the number of
+ /// elements to drop from the beginning of the collection.
@inlinable
- public func dropFirst(_ n: Int) -> SubSequence {
- _precondition(n >= 0, "Can't drop a negative number of elements from a collection")
+ public func dropFirst(_ k: Int) -> SubSequence {
+ _precondition(k >= 0, "Can't drop a negative number of elements from a collection")
let start = index(startIndex,
- offsetBy: n, limitedBy: endIndex) ?? endIndex
+ offsetBy: k, limitedBy: endIndex) ?? endIndex
return self[start..<endIndex]
}
@@ -1359,17 +1379,19 @@
/// print(numbers.dropLast(10))
/// // Prints "[]"
///
- /// - Parameter n: The number of elements to drop off the end of the
- /// collection. `n` must be greater than or equal to zero.
+ /// - Parameter k: The number of elements to drop off the end of the
+ /// collection. `k` must be greater than or equal to zero.
/// - Returns: A subsequence that leaves off the specified number of elements
/// at the end.
///
- /// - Complexity: O(*n*), where *n* is the length of the collection.
+ /// - Complexity: O(1) if the collection conforms to
+ /// `RandomAccessCollection`; otherwise, O(*n*), where *n* is the length of
+ /// the collection.
@inlinable
- public func dropLast(_ n: Int) -> SubSequence {
+ public func dropLast(_ k: Int) -> SubSequence {
_precondition(
- n >= 0, "Can't drop a negative number of elements from a collection")
- let amount = Swift.max(0, count - n)
+ k >= 0, "Can't drop a negative number of elements from a collection")
+ let amount = Swift.max(0, count - k)
let end = index(startIndex,
offsetBy: amount, limitedBy: endIndex) ?? endIndex
return self[startIndex..<end]
@@ -1411,6 +1433,10 @@
/// `maxLength` must be greater than or equal to zero.
/// - Returns: A subsequence starting at the beginning of this collection
/// with at most `maxLength` elements.
+ ///
+ /// - Complexity: O(1) if the collection conforms to
+ /// `RandomAccessCollection`; otherwise, O(*k*), where *k* is the number of
+ /// elements to select from the beginning of the collection.
@inlinable
public func prefix(_ maxLength: Int) -> SubSequence {
_precondition(
@@ -1458,7 +1484,9 @@
/// - Returns: A subsequence terminating at the end of the collection with at
/// most `maxLength` elements.
///
- /// - Complexity: O(*n*), where *n* is the length of the collection.
+ /// - Complexity: O(1) if the collection conforms to
+ /// `RandomAccessCollection`; otherwise, O(*n*), where *n* is the length of
+ /// the collection.
@inlinable
public func suffix(_ maxLength: Int) -> SubSequence {
_precondition(
@@ -1627,6 +1655,8 @@
/// split at that element.
/// - Returns: An array of subsequences, split from this collection's
/// elements.
+ ///
+ /// - Complexity: O(*n*), where *n* is the length of the collection.
@inlinable
public func split(
maxSplits: Int = Int.max,
@@ -1720,6 +1750,8 @@
/// subsequences are returned. The default value is `true`.
/// - Returns: An array of subsequences, split from this collection's
/// elements.
+ ///
+ /// - Complexity: O(*n*), where *n* is the length of the collection.
@inlinable
public func split(
separator: Element,
@@ -1755,19 +1787,20 @@
/// Removes the specified number of elements from the beginning of the
/// collection.
///
- /// - Parameter n: The number of elements to remove. `n` must be greater than
+ /// - Parameter k: The number of elements to remove. `k` must be greater than
/// or equal to zero, and must be less than or equal to the number of
/// elements in the collection.
///
/// - Complexity: O(1) if the collection conforms to
- /// `RandomAccessCollection`; otherwise, O(*n*).
+ /// `RandomAccessCollection`; otherwise, O(*k*), where *k* is the specified
+ /// number of elements.
@inlinable
- public mutating func removeFirst(_ n: Int) {
- if n == 0 { return }
- _precondition(n >= 0, "Number of elements to remove should be non-negative")
- _precondition(count >= n,
+ public mutating func removeFirst(_ k: Int) {
+ if k == 0 { return }
+ _precondition(k >= 0, "Number of elements to remove should be non-negative")
+ _precondition(count >= k,
"Can't remove more items from a collection than it contains")
- self = self[index(startIndex, offsetBy: n)..<endIndex]
+ self = self[index(startIndex, offsetBy: k)..<endIndex]
}
}
diff --git a/stdlib/public/core/CollectionAlgorithms.swift b/stdlib/public/core/CollectionAlgorithms.swift
index db18ab1..f2138ad 100644
--- a/stdlib/public/core/CollectionAlgorithms.swift
+++ b/stdlib/public/core/CollectionAlgorithms.swift
@@ -24,6 +24,8 @@
/// print(lastNumber)
/// }
/// // Prints "50"
+ ///
+ /// - Complexity: O(1)
@inlinable
public var last: Element? {
return isEmpty ? nil : self[index(before: endIndex)]
@@ -53,6 +55,8 @@
/// - Parameter element: An element to search for in the collection.
/// - Returns: The first index where `element` is found. If `element` is not
/// found in the collection, returns `nil`.
+ ///
+ /// - Complexity: O(*n*), where *n* is the length of the collection.
@inlinable
public func firstIndex(of element: Element) -> Index? {
if let result = _customIndexOfEquatableElement(element) {
@@ -98,6 +102,8 @@
/// - Returns: The index of the first element for which `predicate` returns
/// `true`. If no elements in the collection satisfy the given predicate,
/// returns `nil`.
+ ///
+ /// - Complexity: O(*n*), where *n* is the length of the collection.
@inlinable
public func firstIndex(
where predicate: (Element) throws -> Bool
@@ -144,6 +150,8 @@
/// element is a match.
/// - Returns: The last element of the sequence that satisfies `predicate`,
/// or `nil` if there is no element that satisfies `predicate`.
+ ///
+ /// - Complexity: O(*n*), where *n* is the length of the collection.
@inlinable
public func last(
where predicate: (Element) throws -> Bool
@@ -170,6 +178,8 @@
/// represents a match.
/// - Returns: The index of the last element in the collection that matches
/// `predicate`, or `nil` if no elements match.
+ ///
+ /// - Complexity: O(*n*), where *n* is the length of the collection.
@inlinable
public func lastIndex(
where predicate: (Element) throws -> Bool
@@ -204,6 +214,8 @@
/// - Parameter element: An element to search for in the collection.
/// - Returns: The last index where `element` is found. If `element` is not
/// found in the collection, returns `nil`.
+ ///
+ /// - Complexity: O(*n*), where *n* is the length of the collection.
@inlinable
public func lastIndex(of element: Element) -> Index? {
if let result = _customLastIndexOfEquatableElement(element) {
@@ -253,7 +265,7 @@
/// collection match `belongsInSecondPartition`, the returned index is
/// equal to the collection's `endIndex`.
///
- /// - Complexity: O(*n*)
+ /// - Complexity: O(*n*), where *n* is the length of the collection.
@inlinable
public mutating func partition(
by belongsInSecondPartition: (Element) throws -> Bool
@@ -318,7 +330,7 @@
/// collection match `belongsInSecondPartition`, the returned index is
/// equal to the collection's `endIndex`.
///
- /// - Complexity: O(*n*)
+ /// - Complexity: O(*n*), where *n* is the length of the collection.
@inlinable
public mutating func partition(
by belongsInSecondPartition: (Element) throws -> Bool
@@ -388,7 +400,7 @@
/// the sequence.
/// - Returns: An array of this sequence's elements in a shuffled order.
///
- /// - Complexity: O(*n*)
+ /// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
public func shuffled<T: RandomNumberGenerator>(
using generator: inout T
@@ -412,7 +424,7 @@
///
/// - Returns: A shuffled array of this sequence's elements.
///
- /// - Complexity: O(*n*)
+ /// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
public func shuffled() -> [Element] {
var g = SystemRandomNumberGenerator()
@@ -435,7 +447,7 @@
/// - Parameter generator: The random number generator to use when shuffling
/// the collection.
///
- /// - Complexity: O(*n*)
+ /// - Complexity: O(*n*), where *n* is the length of the collection.
@inlinable
public mutating func shuffle<T: RandomNumberGenerator>(
using generator: inout T
@@ -467,7 +479,7 @@
/// This method is equivalent to calling the version that takes a generator,
/// passing in the system's default random generator.
///
- /// - Complexity: O(*n*)
+ /// - Complexity: O(*n*), where *n* is the length of the collection.
@inlinable
public mutating func shuffle() {
var g = SystemRandomNumberGenerator()
diff --git a/stdlib/public/core/MutableCollection.swift b/stdlib/public/core/MutableCollection.swift
index dc1f10b..1ad94be 100644
--- a/stdlib/public/core/MutableCollection.swift
+++ b/stdlib/public/core/MutableCollection.swift
@@ -95,6 +95,8 @@
/// - Parameter position: The position of the element to access. `position`
/// must be a valid index of the collection that is not equal to the
/// `endIndex` property.
+ ///
+ /// - Complexity: O(1)
subscript(position: Index) -> Element { get set }
/// Accesses a contiguous subrange of the collection's elements.
@@ -119,6 +121,8 @@
///
/// - Parameter bounds: A range of the collection's indices. The bounds of
/// the range must be valid indices of the collection.
+ ///
+ /// - Complexity: O(1)
subscript(bounds: Range<Index>) -> SubSequence { get set }
/// Reorders the elements of the collection such that all the elements
@@ -156,7 +160,7 @@
/// collection match `belongsInSecondPartition`, the returned index is
/// equal to the collection's `endIndex`.
///
- /// - Complexity: O(*n*)
+ /// - Complexity: O(*n*), where *n* is the length of the collection.
mutating func partition(
by belongsInSecondPartition: (Element) throws -> Bool
) rethrows -> Index
@@ -170,6 +174,8 @@
/// - Parameters:
/// - i: The index of the first value to swap.
/// - j: The index of the second value to swap.
+ ///
+ /// - Complexity: O(1)
mutating func swapAt(_ i: Index, _ j: Index)
/// Call `body(p)`, where `p` is a pointer to the collection's
@@ -218,6 +224,8 @@
///
/// - Parameter bounds: A range of the collection's indices. The bounds of
/// the range must be valid indices of the collection.
+ ///
+ /// - Complexity: O(1)
@inlinable
public subscript(bounds: Range<Index>) -> Slice<Self> {
get {
@@ -238,6 +246,8 @@
/// - Parameters:
/// - i: The index of the first value to swap.
/// - j: The index of the second value to swap.
+ ///
+ /// - Complexity: O(1)
@inlinable
public mutating func swapAt(_ i: Index, _ j: Index) {
guard i != j else { return }
diff --git a/stdlib/public/core/RandomAccessCollection.swift b/stdlib/public/core/RandomAccessCollection.swift
index 39a0d71..fb1cf1c 100644
--- a/stdlib/public/core/RandomAccessCollection.swift
+++ b/stdlib/public/core/RandomAccessCollection.swift
@@ -93,6 +93,8 @@
///
/// - Parameter bounds: A range of the collection's indices. The bounds of
/// the range must be valid indices of the collection.
+ ///
+ /// - Complexity: O(1)
subscript(bounds: Range<Index>) -> SubSequence { get }
// FIXME(ABI): Associated type inference requires this.
@@ -228,9 +230,6 @@
func distance(from start: Index, to end: Index) -> Int
}
-// TODO: swift-3-indexing-model - Make sure RandomAccessCollection has
-// documented complexity guarantees, e.g. for index(_:offsetBy:).
-
// TODO: swift-3-indexing-model - (By creating an ambiguity?), try to
// make sure RandomAccessCollection models implement
// index(_:offsetBy:) and distance(from:to:), or they will get the
@@ -261,31 +260,32 @@
/// print(j)
/// // Prints "nil"
///
- /// The value passed as `n` must not offset `i` beyond the bounds of the
- /// collection, unless the index passed as `limit` prevents offsetting
+ /// The value passed as `distance` must not offset `i` beyond the bounds of
+ /// the collection, unless the index passed as `limit` prevents offsetting
/// beyond those bounds.
///
/// - Parameters:
/// - i: A valid index of the array.
- /// - n: The distance to offset `i`.
- /// - limit: A valid index of the collection to use as a limit. If `n > 0`,
- /// `limit` should be greater than `i` to have any effect. Likewise, if
- /// `n < 0`, `limit` should be less than `i` to have any effect.
- /// - Returns: An index offset by `n` from the index `i`, unless that index
- /// would be beyond `limit` in the direction of movement. In that case,
- /// the method returns `nil`.
+ /// - distance: The distance to offset `i`.
+ /// - limit: A valid index of the collection to use as a limit. If
+ /// `distance > 0`, `limit` should be greater than `i` to have any
+ /// effect. Likewise, if `distance < 0`, `limit` should be less than `i`
+ /// to have any effect.
+ /// - Returns: An index offset by `distance` from the index `i`, unless that
+ /// index would be beyond `limit` in the direction of movement. In that
+ /// case, the method returns `nil`.
///
/// - Complexity: O(1)
@inlinable
public func index(
- _ i: Index, offsetBy n: Int, limitedBy limit: Index
+ _ i: Index, offsetBy distance: Int, limitedBy limit: Index
) -> Index? {
// FIXME: swift-3-indexing-model: tests.
- let l = distance(from: i, to: limit)
- if n > 0 ? l >= 0 && l < n : l <= 0 && n < l {
+ let l = self.distance(from: i, to: limit)
+ if distance > 0 ? l >= 0 && l < distance : l <= 0 && distance < l {
return nil
}
- return index(i, offsetBy: n)
+ return index(i, offsetBy: distance)
}
}
@@ -345,21 +345,22 @@
/// print(numbers[i])
/// // Prints "50"
///
- /// The value passed as `n` must not offset `i` beyond the bounds of the
- /// collection.
+ /// The value passed as `distance` must not offset `i` beyond the bounds of
+ /// the collection.
///
/// - Parameters:
/// - i: A valid index of the collection.
- /// - n: The distance to offset `i`.
- /// - Returns: An index offset by `n` from the index `i`. If `n` is positive,
- /// this is the same value as the result of `n` calls to `index(after:)`.
- /// If `n` is negative, this is the same value as the result of `-n` calls
- /// to `index(before:)`.
+ /// - distance: The distance to offset `i`.
+ /// - Returns: An index offset by `distance` from the index `i`. If
+ /// `distance` is positive, this is the same value as the result of
+ /// `distance` calls to `index(after:)`. If `distance` is negative, this
+ /// is the same value as the result of `abs(distance)` calls to
+ /// `index(before:)`.
///
/// - Complexity: O(1)
@inlinable
- public func index(_ i: Index, offsetBy n: Index.Stride) -> Index {
- let result = i.advanced(by: n)
+ public func index(_ i: Index, offsetBy distance: Index.Stride) -> Index {
+ let result = i.advanced(by: distance)
// This range check is not precise, tighter bounds exist based on `n`.
// Unfortunately, we would need to perform index manipulation to
// compute those bounds, which is probably too slow in the general
diff --git a/stdlib/public/core/RangeReplaceableCollection.swift b/stdlib/public/core/RangeReplaceableCollection.swift
index 9cffa90..939ada3 100644
--- a/stdlib/public/core/RangeReplaceableCollection.swift
+++ b/stdlib/public/core/RangeReplaceableCollection.swift
@@ -66,9 +66,9 @@
/// add an empty initializer and the `replaceSubrange(_:with:)` method to your
/// custom type. `RangeReplaceableCollection` provides default implementations
/// of all its other methods using this initializer and method. For example,
-/// the `removeSubrange(_:)` method is implemented by calling
-/// `replaceSubrange(_:with:)` with an empty collection for the `newElements`
-/// parameter. You can override any of the protocol's required methods to
+/// the `removeSubrange(_:)` method is implemented by calling
+/// `replaceSubrange(_:with:)` with an empty collection for the `newElements`
+/// parameter. You can override any of the protocol's required methods to
/// provide your own custom implementation.
public protocol RangeReplaceableCollection : Collection
where SubSequence : RangeReplaceableCollection {
@@ -112,10 +112,10 @@
/// the range must be valid indices of the collection.
/// - newElements: The new elements to add to the collection.
///
- /// - Complexity: O(*m*), where *m* is the combined length of the collection
- /// and `newElements`. If the call to `replaceSubrange` simply appends the
- /// contents of `newElements` to the collection, the complexity is O(*n*),
- /// where *n* is the length of `newElements`.
+ /// - Complexity: O(*n* + *m*), where *n* is length of this collection and
+ /// *m* is the length of `newElements`. If the call to this method simply
+ /// appends the contents of `newElements` to the collection, this method is
+ /// equivalent to `append(contentsOf:)`.
mutating func replaceSubrange<C>(
_ subrange: Range<Index>,
with newElements: C
@@ -173,8 +173,8 @@
///
/// - Parameter newElement: The element to append to the collection.
///
- /// - Complexity: O(1) on average, over many additions to the same
- /// collection.
+ /// - Complexity: O(1) on average, over many calls to `append(_:)` on the
+ /// same collection.
mutating func append(_ newElement: Element)
/// Adds the elements of a sequence or collection to the end of this
@@ -193,12 +193,11 @@
///
/// - Parameter newElements: The elements to append to the collection.
///
- /// - Complexity: O(*n*), where *n* is the length of the resulting
- /// collection.
- // FIXME(ABI)#166 (Evolution): Consider replacing .append(contentsOf) with +=
- // suggestion in SE-91
+ /// - Complexity: O(*m*), where *m* is the length of `newElements`.
mutating func append<S : Sequence>(contentsOf newElements: S)
where S.Element == Element
+ // FIXME(ABI)#166 (Evolution): Consider replacing .append(contentsOf) with +=
+ // suggestion in SE-91
/// Inserts a new element into the collection at the specified position.
///
@@ -221,7 +220,8 @@
/// - Parameter i: The position at which to insert the new element.
/// `index` must be a valid index into the collection.
///
- /// - Complexity: O(*n*), where *n* is the length of the collection.
+ /// - Complexity: O(*n*), where *n* is the length of the collection. If
+ /// `i == endIndex`, this method is equivalent to `append(_:)`.
mutating func insert(_ newElement: Element, at i: Index)
/// Inserts the elements of a sequence into the collection at the specified
@@ -246,10 +246,9 @@
/// - Parameter i: The position at which to insert the new elements. `index`
/// must be a valid index of the collection.
///
- /// - Complexity: O(*m*), where *m* is the combined length of the collection
- /// and `newElements`. If `i` is equal to the collection's `endIndex`
- /// property, the complexity is O(*n*), where *n* is the length of
- /// `newElements`.
+ /// - Complexity: O(*n* + *m*), where *n* is length of this collection and
+ /// *m* is the length of `newElements`. If `i == endIndex`, this method
+ /// is equivalent to `append(contentsOf:)`.
mutating func insert<S : Collection>(contentsOf newElements: S, at i: Index)
where S.Element == Element
@@ -333,12 +332,12 @@
/// Calling this method may invalidate any existing indices for use with this
/// collection.
///
- /// - Parameter n: The number of elements to remove from the collection.
- /// `n` must be greater than or equal to zero and must not exceed the
+ /// - Parameter k: The number of elements to remove from the collection.
+ /// `k` must be greater than or equal to zero and must not exceed the
/// number of elements in the collection.
///
/// - Complexity: O(*n*), where *n* is the length of the collection.
- mutating func removeFirst(_ n: Int)
+ mutating func removeFirst(_ k: Int)
/// Removes all elements from the collection.
///
@@ -422,8 +421,8 @@
///
/// - Parameter newElement: The element to append to the collection.
///
- /// - Complexity: O(1) on average, over many additions to the same
- /// collection.
+ /// - Complexity: O(1) on average, over many calls to `append(_:)` on the
+ /// same collection.
@inlinable
public mutating func append(_ newElement: Element) {
insert(newElement, at: endIndex)
@@ -445,8 +444,7 @@
///
/// - Parameter newElements: The elements to append to the collection.
///
- /// - Complexity: O(*n*), where *n* is the length of the resulting
- /// collection.
+ /// - Complexity: O(*m*), where *m* is the length of `newElements`.
@inlinable
public mutating func append<S : Sequence>(contentsOf newElements: S)
where S.Element == Element {
@@ -480,7 +478,8 @@
/// - Parameter i: The position at which to insert the new element.
/// `index` must be a valid index into the collection.
///
- /// - Complexity: O(*n*), where *n* is the length of the collection.
+ /// - Complexity: O(*n*), where *n* is the length of the collection. If
+ /// `i == endIndex`, this method is equivalent to `append(_:)`.
@inlinable
public mutating func insert(
_ newElement: Element, at i: Index
@@ -510,10 +509,9 @@
/// - Parameter i: The position at which to insert the new elements. `index`
/// must be a valid index of the collection.
///
- /// - Complexity: O(*m*), where *m* is the combined length of the collection
- /// and `newElements`. If `i` is equal to the collection's `endIndex`
- /// property, the complexity is O(*n*), where *n* is the length of
- /// `newElements`.
+ /// - Complexity: O(*n* + *m*), where *n* is length of this collection and
+ /// *m* is the length of `newElements`. If `i == endIndex`, this method
+ /// is equivalent to `append(contentsOf:)`.
@inlinable
public mutating func insert<C : Collection>(
contentsOf newElements: C, at i: Index
@@ -535,9 +533,9 @@
/// Calling this method may invalidate any existing indices for use with this
/// collection.
///
- /// - Parameter position: The position of the element to remove. `position` must be
- /// a valid index of the collection that is not equal to the collection's
- /// end index.
+ /// - Parameter position: The position of the element to remove. `position`
+ /// must be a valid index of the collection that is not equal to the
+ /// collection's end index.
/// - Returns: The removed element.
///
/// - Complexity: O(*n*), where *n* is the length of the collection.
@@ -584,18 +582,18 @@
/// Calling this method may invalidate any existing indices for use with this
/// collection.
///
- /// - Parameter n: The number of elements to remove from the collection.
- /// `n` must be greater than or equal to zero and must not exceed the
+ /// - Parameter k: The number of elements to remove from the collection.
+ /// `k` must be greater than or equal to zero and must not exceed the
/// number of elements in the collection.
///
/// - Complexity: O(*n*), where *n* is the length of the collection.
@inlinable
- public mutating func removeFirst(_ n: Int) {
- if n == 0 { return }
- _precondition(n >= 0, "Number of elements to remove should be non-negative")
- _precondition(count >= numericCast(n),
+ public mutating func removeFirst(_ k: Int) {
+ if k == 0 { return }
+ _precondition(k >= 0, "Number of elements to remove should be non-negative")
+ _precondition(count >= k,
"Can't remove more items from a collection than it has")
- let end = index(startIndex, offsetBy: numericCast(n))
+ let end = index(startIndex, offsetBy: k)
removeSubrange(startIndex..<end)
}
@@ -671,7 +669,6 @@
/// - Returns: The first element of the collection.
///
/// - Complexity: O(1)
- /// - Precondition: `!self.isEmpty`.
@inlinable
@discardableResult
public mutating func removeFirst() -> Element {
@@ -691,18 +688,20 @@
/// collection. Do not rely on a previously stored index value after
/// altering a collection with any operation that can change its length.
///
- /// - Parameter n: The number of elements to remove from the collection.
- /// `n` must be greater than or equal to zero and must not exceed the
+ /// - Parameter k: The number of elements to remove from the collection.
+ /// `k` must be greater than or equal to zero and must not exceed the
/// number of elements in the collection.
///
- /// - Complexity: O(1)
+ /// - Complexity: O(1) if the collection conforms to
+ /// `RandomAccessCollection`; otherwise, O(*k*), where *k* is the specified
+ /// number of elements.
@inlinable
- public mutating func removeFirst(_ n: Int) {
- if n == 0 { return }
- _precondition(n >= 0, "Number of elements to remove should be non-negative")
- _precondition(count >= numericCast(n),
+ public mutating func removeFirst(_ k: Int) {
+ if k == 0 { return }
+ _precondition(k >= 0, "Number of elements to remove should be non-negative")
+ _precondition(count >= k,
"Can't remove more items from a collection than it contains")
- self = self[index(startIndex, offsetBy: numericCast(n))..<endIndex]
+ self = self[index(startIndex, offsetBy: k)..<endIndex]
}
}
@@ -739,10 +738,10 @@
/// the range must be valid indices of the collection.
/// - newElements: The new elements to add to the collection.
///
- /// - Complexity: O(*m*), where *m* is the combined length of the collection
- /// and `newElements`. If the call to `replaceSubrange` simply appends the
- /// contents of `newElements` to the collection, the complexity is O(*n*),
- /// where *n* is the length of `newElements`.
+ /// - Complexity: O(*n* + *m*), where *n* is length of this collection and
+ /// *m* is the length of `newElements`. If the call to this method simply
+ /// appends the contents of `newElements` to the collection, the complexity
+ /// is O(*m*).
@inlinable
public mutating func replaceSubrange<C: Collection, R: RangeExpression>(
_ subrange: R,
@@ -856,22 +855,22 @@
/// collection. Do not rely on a previously stored index value after
/// altering a collection with any operation that can change its length.
///
- /// - Parameter n: The number of elements to remove from the collection.
- /// `n` must be greater than or equal to zero and must not exceed the
+ /// - Parameter k: The number of elements to remove from the collection.
+ /// `k` must be greater than or equal to zero and must not exceed the
/// number of elements in the collection.
///
- /// - Complexity: O(*n*), where *n* is the specified number of elements.
+ /// - Complexity: O(*k*), where *k* is the specified number of elements.
@inlinable
- public mutating func removeLast(_ n: Int) {
- if n == 0 { return }
- _precondition(n >= 0, "Number of elements to remove should be non-negative")
- _precondition(count >= numericCast(n),
+ public mutating func removeLast(_ k: Int) {
+ if k == 0 { return }
+ _precondition(k >= 0, "Number of elements to remove should be non-negative")
+ _precondition(count >= k,
"Can't remove more items from a collection than it contains")
- if _customRemoveLast(n) {
+ if _customRemoveLast(k) {
return
}
let end = endIndex
- removeSubrange(index(end, offsetBy: numericCast(-n))..<end)
+ removeSubrange(index(end, offsetBy: -k)..<end)
}
}
@@ -926,22 +925,22 @@
/// collection. Do not rely on a previously stored index value after
/// altering a collection with any operation that can change its length.
///
- /// - Parameter n: The number of elements to remove from the collection.
- /// `n` must be greater than or equal to zero and must not exceed the
+ /// - Parameter k: The number of elements to remove from the collection.
+ /// `k` must be greater than or equal to zero and must not exceed the
/// number of elements in the collection.
///
- /// - Complexity: O(*n*), where *n* is the specified number of elements.
+ /// - Complexity: O(*k*), where *k* is the specified number of elements.
@inlinable
- public mutating func removeLast(_ n: Int) {
- if n == 0 { return }
- _precondition(n >= 0, "Number of elements to remove should be non-negative")
- _precondition(count >= numericCast(n),
+ public mutating func removeLast(_ k: Int) {
+ if k == 0 { return }
+ _precondition(k >= 0, "Number of elements to remove should be non-negative")
+ _precondition(count >= k,
"Can't remove more items from a collection than it contains")
- if _customRemoveLast(n) {
+ if _customRemoveLast(k) {
return
}
let end = endIndex
- removeSubrange(index(end, offsetBy: numericCast(-n))..<end)
+ removeSubrange(index(end, offsetBy: -k)..<end)
}
}
@@ -1008,8 +1007,8 @@
/// Appends the elements of a sequence to a range-replaceable collection.
///
/// Use this operator to append the elements of a sequence to the end of
- /// range-replaceable collection with same `Element` type. This example appends
- /// the elements of a `Range<Int>` instance to an array of integers.
+ /// range-replaceable collection with same `Element` type. This example
+ /// appends the elements of a `Range<Int>` instance to an array of integers.
///
/// var numbers = [1, 2, 3, 4, 5]
/// numbers += 10...15
@@ -1020,7 +1019,8 @@
/// - lhs: The array to append to.
/// - rhs: A collection or finite sequence.
///
- /// - Complexity: O(*n*), where *n* is the length of the resulting array.
+ /// - Complexity: O(*m*), where *m* is the length of the right-hand-side
+ /// argument.
@inlinable
public static func += <
Other : Sequence
@@ -1074,8 +1074,10 @@
///
/// - Parameter isIncluded: A closure that takes an element of the
/// sequence as its argument and returns a Boolean value indicating
- /// whether the element should be included in the returned array.
- /// - Returns: An array of the elements that `isIncluded` allowed.
+ /// whether the element should be included in the returned collection.
+ /// - Returns: A collection of the elements that `isIncluded` allowed.
+ ///
+ /// - Complexity: O(*n*), where *n* is the length of the collection.
@inlinable
@available(swift, introduced: 4.0)
public func filter(
diff --git a/stdlib/public/core/Sequence.swift b/stdlib/public/core/Sequence.swift
index 45d32c4..092995d 100644
--- a/stdlib/public/core/Sequence.swift
+++ b/stdlib/public/core/Sequence.swift
@@ -365,6 +365,8 @@
/// value of the same or of a different type.
/// - Returns: An array containing the transformed elements of this
/// sequence.
+ ///
+ /// - Complexity: O(*n*), where *n* is the length of the sequence.
func map<T>(
_ transform: (Element) throws -> T
) rethrows -> [T]
@@ -384,6 +386,8 @@
/// sequence as its argument and returns a Boolean value indicating
/// whether the element should be included in the returned array.
/// - Returns: An array of the elements that `isIncluded` allowed.
+ ///
+ /// - Complexity: O(*n*), where *n* is the length of the sequence.
func filter(
_ isIncluded: (Element) throws -> Bool
) rethrows -> [Element]
@@ -435,14 +439,14 @@
/// print(numbers.dropFirst(10))
/// // Prints "[]"
///
- /// - Parameter n: The number of elements to drop from the beginning of
- /// the sequence. `n` must be greater than or equal to zero.
+ /// - Parameter k: The number of elements to drop from the beginning of
+ /// the sequence. `k` must be greater than or equal to zero.
/// - Returns: A subsequence starting after the specified number of
/// elements.
///
- /// - Complexity: O(*n*), where *n* is the number of elements to drop from
+ /// - Complexity: O(*k*), where *k* is the number of elements to drop from
/// the beginning of the sequence.
- func dropFirst(_ n: Int) -> SubSequence
+ func dropFirst(_ k: Int) -> SubSequence
/// Returns a subsequence containing all but the specified number of final
/// elements.
@@ -457,12 +461,12 @@
/// print(numbers.dropLast(10))
/// // Prints "[]"
///
- /// - Parameter n: The number of elements to drop off the end of the
- /// sequence. `n` must be greater than or equal to zero.
+ /// - Parameter k: The number of elements to drop off the end of the
+ /// sequence. `k` must be greater than or equal to zero.
/// - Returns: A subsequence leaving off the specified number of elements.
///
/// - Complexity: O(*n*), where *n* is the length of the sequence.
- func dropLast(_ n: Int) -> SubSequence
+ func dropLast(_ k: Int) -> SubSequence
/// Returns a subsequence by skipping elements while `predicate` returns
/// `true` and returning the remaining elements.
@@ -471,7 +475,7 @@
/// sequence as its argument and returns a Boolean value indicating
/// whether the element is a match.
///
- /// - Complexity: O(*n*), where *n* is the length of the collection.
+ /// - Complexity: O(*n*), where *n* is the length of the sequence.
func drop(
while predicate: (Element) throws -> Bool
) rethrows -> SubSequence
@@ -492,6 +496,9 @@
/// `maxLength` must be greater than or equal to zero.
/// - Returns: A subsequence starting at the beginning of this sequence
/// with at most `maxLength` elements.
+ ///
+ /// - Complexity: O(*k*), where *k* is the number of elements to select from
+ /// the beginning of the sequence.
func prefix(_ maxLength: Int) -> SubSequence
/// Returns a subsequence containing the initial, consecutive elements that
@@ -515,7 +522,7 @@
/// - Returns: A subsequence of the initial, consecutive elements that
/// satisfy `predicate`.
///
- /// - Complexity: O(*n*), where *n* is the length of the collection.
+ /// - Complexity: O(*k*), where *k* is the length of the result.
func prefix(
while predicate: (Element) throws -> Bool
) rethrows -> SubSequence
@@ -590,6 +597,8 @@
/// - isSeparator: A closure that returns `true` if its argument should be
/// used to split the sequence; otherwise, `false`.
/// - Returns: An array of subsequences, split from this sequence's elements.
+ ///
+ /// - Complexity: O(*n*), where *n* is the length of the sequence.
func split(
maxSplits: Int, omittingEmptySubsequences: Bool,
whereSeparator isSeparator: (Element) throws -> Bool
@@ -674,7 +683,7 @@
}
@inlinable
- internal func dropFirst(_ n: Int) -> AnySequence<Base.Element> {
+ internal func dropFirst(_ k: Int) -> AnySequence<Base.Element> {
// If this is already a _DropFirstSequence, we need to fold in
// the current drop count and drop limit so no data is lost.
//
@@ -682,7 +691,7 @@
// [1,2,3,4].dropFirst(2).
return AnySequence(
_DropFirstSequence(
- _iterator: _iterator, limit: _limit + n, dropped: _dropped))
+ _iterator: _iterator, limit: _limit + k, dropped: _dropped))
}
}
@@ -816,6 +825,8 @@
/// value of the same or of a different type.
/// - Returns: An array containing the transformed elements of this
/// sequence.
+ ///
+ /// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
public func map<T>(
_ transform: (Element) throws -> T
@@ -852,6 +863,8 @@
/// sequence as its argument and returns a Boolean value indicating
/// whether the element should be included in the returned array.
/// - Returns: An array of the elements that `isIncluded` allowed.
+ ///
+ /// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
public func filter(
_ isIncluded: (Element) throws -> Bool
@@ -961,6 +974,8 @@
/// element is a match.
/// - Returns: The first element of the sequence that satisfies `predicate`,
/// or `nil` if there is no element that satisfies `predicate`.
+ ///
+ /// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
public func first(
where predicate: (Element) throws -> Bool
@@ -1020,6 +1035,8 @@
/// start or end of the sequence. If `true`, only nonempty subsequences
/// are returned. The default value is `true`.
/// - Returns: An array of subsequences, split from this sequence's elements.
+ ///
+ /// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
public func split(
separator: Element,
@@ -1082,6 +1099,8 @@
/// - isSeparator: A closure that returns `true` if its argument should be
/// used to split the sequence; otherwise, `false`.
/// - Returns: An array of subsequences, split from this sequence's elements.
+ ///
+ /// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
public func split(
maxSplits: Int = Int.max,
@@ -1145,6 +1164,7 @@
///
/// - Parameter maxLength: The maximum number of elements to return. The
/// value of `maxLength` must be greater than or equal to zero.
+ ///
/// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
public func suffix(_ maxLength: Int) -> AnySequence<Element> {
@@ -1190,17 +1210,19 @@
/// print(numbers.dropFirst(10))
/// // Prints "[]"
///
- /// - Parameter n: The number of elements to drop from the beginning of
- /// the sequence. `n` must be greater than or equal to zero.
+ /// - Parameter k: The number of elements to drop from the beginning of
+ /// the sequence. `k` must be greater than or equal to zero.
/// - Returns: A subsequence starting after the specified number of
/// elements.
///
- /// - Complexity: O(1).
+ /// - Complexity: O(1), with O(*k*) deferred to each iteration of the result,
+ /// where *k* is the number of elements to drop from the beginning of
+ /// the sequence.
@inlinable
- public func dropFirst(_ n: Int) -> AnySequence<Element> {
- _precondition(n >= 0, "Can't drop a negative number of elements from a sequence")
- if n == 0 { return AnySequence(self) }
- return AnySequence(_DropFirstSequence(_iterator: makeIterator(), limit: n))
+ public func dropFirst(_ k: Int) -> AnySequence<Element> {
+ _precondition(k >= 0, "Can't drop a negative number of elements from a sequence")
+ if k == 0 { return AnySequence(self) }
+ return AnySequence(_DropFirstSequence(_iterator: makeIterator(), limit: k))
}
/// Returns a subsequence containing all but the given number of final
@@ -1222,27 +1244,27 @@
///
/// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
- public func dropLast(_ n: Int) -> AnySequence<Element> {
- _precondition(n >= 0, "Can't drop a negative number of elements from a sequence")
- if n == 0 { return AnySequence(self) }
+ public func dropLast(_ k: Int) -> AnySequence<Element> {
+ _precondition(k >= 0, "Can't drop a negative number of elements from a sequence")
+ if k == 0 { return AnySequence(self) }
// FIXME: <rdar://problem/21885650> Create reusable RingBuffer<T>
// Put incoming elements from this sequence in a holding tank, a ring buffer
- // of size <= n. If more elements keep coming in, pull them out of the
+ // of size <= k. If more elements keep coming in, pull them out of the
// holding tank into the result, an `Array`. This saves
- // `n` * sizeof(Element) of memory, because slices keep the entire
+ // `k` * sizeof(Element) of memory, because slices keep the entire
// memory of an `Array` alive.
var result: [Element] = []
var ringBuffer: [Element] = []
var i = ringBuffer.startIndex
for element in self {
- if ringBuffer.count < n {
+ if ringBuffer.count < k {
ringBuffer.append(element)
} else {
result.append(ringBuffer[i])
ringBuffer[i] = element
- i = ringBuffer.index(after: i) % n
+ i = ringBuffer.index(after: i) % k
}
}
return AnySequence(result)
@@ -1269,7 +1291,8 @@
/// - Returns: A subsequence starting after the initial, consecutive elements
/// that satisfy `predicate`.
///
- /// - Complexity: O(*n*), where *n* is the length of the collection.
+ /// - Complexity: O(*k*), where *k* is the number of elements to drop from
+ /// the beginning of the sequence.
@inlinable
public func drop(
while predicate: (Element) throws -> Bool
@@ -1328,7 +1351,7 @@
/// - Returns: A subsequence of the initial, consecutive elements that
/// satisfy `predicate`.
///
- /// - Complexity: O(*n*), where *n* is the length of the collection.
+ /// - Complexity: O(*k*), where *k* is the length of the result.
@inlinable
public func prefix(
while predicate: (Element) throws -> Bool
diff --git a/stdlib/public/core/SequenceAlgorithms.swift b/stdlib/public/core/SequenceAlgorithms.swift
index e6f9162..b779541 100644
--- a/stdlib/public/core/SequenceAlgorithms.swift
+++ b/stdlib/public/core/SequenceAlgorithms.swift
@@ -61,6 +61,8 @@
/// // Prints "Mateo"
///
/// - Returns: A sequence of pairs enumerating the sequence.
+ ///
+ /// - Complexity: O(1)
@inlinable
public func enumerated() -> EnumeratedSequence<Self> {
return EnumeratedSequence(_base: self)
@@ -102,6 +104,8 @@
/// - Returns: The sequence's minimum element, according to
/// `areInIncreasingOrder`. If the sequence has no elements, returns
/// `nil`.
+ ///
+ /// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
@warn_unqualified_access
public func min(
@@ -144,6 +148,8 @@
/// otherwise, `false`.
/// - Returns: The sequence's maximum element if the sequence is not empty;
/// otherwise, `nil`.
+ ///
+ /// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
@warn_unqualified_access
public func max(
@@ -170,6 +176,8 @@
///
/// - Returns: The sequence's minimum element. If the sequence has no
/// elements, returns `nil`.
+ ///
+ /// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
@warn_unqualified_access
public func min() -> Element? {
@@ -187,6 +195,8 @@
///
/// - Returns: The sequence's maximum element. If the sequence has no
/// elements, returns `nil`.
+ ///
+ /// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
@warn_unqualified_access
public func max() -> Element? {
@@ -219,6 +229,9 @@
/// - Returns: `true` if the initial elements of the sequence are equivalent
/// to the elements of `possiblePrefix`; otherwise, `false`. If
/// `possiblePrefix` has no elements, the return value is `true`.
+ ///
+ /// - Complexity: O(*m*), where *m* is the lesser of the length of the
+ /// sequence and the length of `possiblePrefix`.
@inlinable
public func starts<PossiblePrefix: Sequence>(
with possiblePrefix: PossiblePrefix,
@@ -262,6 +275,9 @@
/// - Returns: `true` if the initial elements of the sequence are the same as
/// the elements of `possiblePrefix`; otherwise, `false`. If
/// `possiblePrefix` has no elements, the return value is `true`.
+ ///
+ /// - Complexity: O(*m*), where *m* is the lesser of the length of the
+ /// sequence and the length of `possiblePrefix`.
@inlinable
public func starts<PossiblePrefix: Sequence>(
with possiblePrefix: PossiblePrefix
@@ -296,6 +312,9 @@
/// are equivalent; otherwise, `false`.
/// - Returns: `true` if this sequence and `other` contain equivalent items,
/// using `areEquivalent` as the equivalence test; otherwise, `false.`
+ ///
+ /// - Complexity: O(*m*), where *m* is the lesser of the length of the
+ /// sequence and the length of `other`.
@inlinable
public func elementsEqual<OtherSequence: Sequence>(
_ other: OtherSequence,
@@ -336,6 +355,9 @@
/// - Parameter other: A sequence to compare to this sequence.
/// - Returns: `true` if this sequence and `other` contain the same elements
/// in the same order.
+ ///
+ /// - Complexity: O(*m*), where *m* is the lesser of the length of the
+ /// sequence and the length of `other`.
@inlinable
public func elementsEqual<OtherSequence: Sequence>(
_ other: OtherSequence
@@ -378,6 +400,9 @@
/// ordering, which has no connection to Unicode. If you are sorting
/// strings to present to the end user, use `String` APIs that perform
/// localized comparison instead.
+ ///
+ /// - Complexity: O(*m*), where *m* is the lesser of the length of the
+ /// sequence and the length of `other`.
@inlinable
public func lexicographicallyPrecedes<OtherSequence: Sequence>(
_ other: OtherSequence,
@@ -429,6 +454,9 @@
/// ordering, which has no connection to Unicode. If you are sorting
/// strings to present to the end user, use `String` APIs that
/// perform localized comparison.
+ ///
+ /// - Complexity: O(*m*), where *m* is the lesser of the length of the
+ /// sequence and the length of `other`.
@inlinable
public func lexicographicallyPrecedes<OtherSequence: Sequence>(
_ other: OtherSequence
@@ -477,6 +505,8 @@
/// the passed element represents a match.
/// - Returns: `true` if the sequence contains an element that satisfies
/// `predicate`; otherwise, `false`.
+ ///
+ /// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
public func contains(
where predicate: (Element) throws -> Bool
@@ -504,6 +534,8 @@
/// the passed element satisfies a condition.
/// - Returns: `true` if the sequence contains only elements that satisfy
/// `predicate`; otherwise, `false`.
+ ///
+ /// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
public func allSatisfy(
_ predicate: (Element) throws -> Bool
@@ -528,6 +560,8 @@
/// - Parameter element: The element to find in the sequence.
/// - Returns: `true` if the element was found in the sequence; otherwise,
/// `false`.
+ ///
+ /// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
public func contains(_ element: Element) -> Bool {
if let result = _customContainsEquatableElement(element) {
@@ -584,6 +618,8 @@
/// the caller.
/// - Returns: The final accumulated value. If the sequence has no elements,
/// the result is `initialResult`.
+ ///
+ /// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
public func reduce<Result>(
_ initialResult: Result,
@@ -639,6 +675,8 @@
/// value with an element of the sequence.
/// - Returns: The final accumulated value. If the sequence has no elements,
/// the result is `initialResult`.
+ ///
+ /// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
public func reduce<Result>(
into initialResult: Result,
@@ -663,10 +701,10 @@
///
/// The sequence must be finite.
///
- /// - Complexity: O(*n*), where *n* is the length of the sequence.
- ///
/// - Returns: An array containing the elements of this sequence in
/// reverse order.
+ ///
+ /// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
public func reversed() -> [Element] {
// FIXME(performance): optimize to 1 pass? But Array(self) can be
@@ -710,8 +748,8 @@
/// sequence as its argument and returns a sequence or collection.
/// - Returns: The resulting flattened array.
///
- /// - Complexity: O(*m* + *n*), where *m* is the length of this sequence
- /// and *n* is the length of the result.
+ /// - Complexity: O(*m* + *n*), where *n* is the length of this sequence
+ /// and *m* is the length of the result.
@inlinable
public func flatMap<SegmentOfResult : Sequence>(
_ transform: (Element) throws -> SegmentOfResult
@@ -747,8 +785,8 @@
/// - Returns: An array of the non-`nil` results of calling `transform`
/// with each element of the sequence.
///
- /// - Complexity: O(*m* + *n*), where *m* is the length of this sequence
- /// and *n* is the length of the result.
+ /// - Complexity: O(*m* + *n*), where *n* is the length of this sequence
+ /// and *m* is the length of the result.
@inlinable
public func compactMap<ElementOfResult>(
_ transform: (Element) throws -> ElementOfResult?
diff --git a/stdlib/public/core/StringRangeReplaceableCollection.swift b/stdlib/public/core/StringRangeReplaceableCollection.swift
index 000ac08..709f8bc 100644
--- a/stdlib/public/core/StringRangeReplaceableCollection.swift
+++ b/stdlib/public/core/StringRangeReplaceableCollection.swift
@@ -161,20 +161,21 @@
/// print(s[i])
/// // Prints "t"
///
- /// The value passed as `n` must not offset `i` beyond the bounds of the
- /// collection.
+ /// The value passed as `distance` must not offset `i` beyond the bounds of
+ /// the collection.
///
/// - Parameters:
/// - i: A valid index of the collection.
- /// - n: The distance to offset `i`.
- /// - Returns: An index offset by `n` from the index `i`. If `n` is positive,
- /// this is the same value as the result of `n` calls to `index(after:)`.
- /// If `n` is negative, this is the same value as the result of `-n` calls
- /// to `index(before:)`.
+ /// - distance: The distance to offset `i`.
+ /// - Returns: An index offset by `distance` from the index `i`. If
+ /// `distance` is positive, this is the same value as the result of
+ /// `distance` calls to `index(after:)`. If `distance` is negative, this
+ /// is the same value as the result of `abs(distance)` calls to
+ /// `index(before:)`.
///
- /// - Complexity: O(*n*), where *n* is the absolute value of `n`.
- public func index(_ i: Index, offsetBy n: IndexDistance) -> Index {
- return _visitGuts(_guts, args: (i, n),
+ /// - Complexity: O(*k*), where *k* is the absolute value of `distance`.
+ public func index(_ i: Index, offsetBy distance: IndexDistance) -> Index {
+ return _visitGuts(_guts, args: (i, distance),
ascii: { ascii, args in let (i, n) = args
return ascii.characterIndex(i, offsetBy: n) },
utf16: { utf16, args in let (i, n) = args
@@ -205,25 +206,25 @@
/// print(j)
/// // Prints "nil"
///
- /// The value passed as `n` must not offset `i` beyond the bounds of the
+ /// The value passed as `distance` must not offset `i` beyond the bounds of the
/// collection, unless the index passed as `limit` prevents offsetting
/// beyond those bounds.
///
/// - Parameters:
/// - i: A valid index of the collection.
- /// - n: The distance to offset `i`.
- /// - limit: A valid index of the collection to use as a limit. If `n > 0`,
- /// a limit that is less than `i` has no effect. Likewise, if `n < 0`, a
+ /// - distance: The distance to offset `i`.
+ /// - limit: A valid index of the collection to use as a limit. If `distance > 0`,
+ /// a limit that is less than `i` has no effect. Likewise, if `distance < 0`, a
/// limit that is greater than `i` has no effect.
- /// - Returns: An index offset by `n` from the index `i`, unless that index
+ /// - Returns: An index offset by `distance` from the index `i`, unless that index
/// would be beyond `limit` in the direction of movement. In that case,
/// the method returns `nil`.
///
- /// - Complexity: O(*n*), where *n* is the absolute value of `n`.
+ /// - Complexity: O(*k*), where *k* is the absolute value of `distance`.
public func index(
- _ i: Index, offsetBy n: IndexDistance, limitedBy limit: Index
+ _ i: Index, offsetBy distance: IndexDistance, limitedBy limit: Index
) -> Index? {
- return _visitGuts(_guts, args: (i, n, limit),
+ return _visitGuts(_guts, args: (i, distance, limit),
ascii: { ascii, args in let (i, n, limit) = args
return ascii.characterIndex(i, offsetBy: n, limitedBy: limit) },
utf16: { utf16, args in let (i, n, limit) = args
@@ -240,7 +241,7 @@
/// `start`, the result is zero.
/// - Returns: The distance between `start` and `end`.
///
- /// - Complexity: O(*n*), where *n* is the resulting distance.
+ /// - Complexity: O(*k*), where *k* is the resulting distance.
public func distance(from start: Index, to end: Index) -> IndexDistance {
return _visitGuts(_guts, args: (start, end),
ascii: { ascii, args in let (start, end) = args
diff --git a/test/IDE/complete_from_stdlib.swift b/test/IDE/complete_from_stdlib.swift
index ecaea90..4d6239e 100644
--- a/test/IDE/complete_from_stdlib.swift
+++ b/test/IDE/complete_from_stdlib.swift
@@ -134,8 +134,8 @@
// PRIVATE_NOMINAL_MEMBERS_5-DAG: Decl[InstanceMethod]/CurrNominal: insert({#(newElement): Equatable#}, {#at: Int#})[#Void#]{{; name=.+}}
// PRIVATE_NOMINAL_MEMBERS_5-DAG: Decl[InstanceVar]/Super: isEmpty[#Bool#]{{; name=.+}}
// PRIVATE_NOMINAL_MEMBERS_5-DAG: Decl[InstanceVar]/Super: first[#Equatable?#]{{; name=.+}}
-// PRIVATE_NOMINAL_MEMBERS_5-DAG: Decl[InstanceMethod]/Super: dropFirst({#(n): Int#})[#ArraySlice<Equatable>#]{{; name=.+}}
-// PRIVATE_NOMINAL_MEMBERS_5-DAG: Decl[InstanceMethod]/Super: dropLast({#(n): Int#})[#ArraySlice<Equatable>#]{{; name=.+}}
+// PRIVATE_NOMINAL_MEMBERS_5-DAG: Decl[InstanceMethod]/Super: dropFirst({#(k): Int#})[#ArraySlice<Equatable>#]{{; name=.+}}
+// PRIVATE_NOMINAL_MEMBERS_5-DAG: Decl[InstanceMethod]/Super: dropLast({#(k): Int#})[#ArraySlice<Equatable>#]{{; name=.+}}
// PRIVATE_NOMINAL_MEMBERS_5-DAG: Decl[InstanceMethod]/Super: prefix({#(maxLength): Int#})[#ArraySlice<Equatable>#]{{; name=.+}}
// PRIVATE_NOMINAL_MEMBERS_5-DAG: Decl[InstanceMethod]/Super: suffix({#(maxLength): Int#})[#ArraySlice<Equatable>#]{{; name=.+}}
@@ -154,7 +154,7 @@
// PRIVATE_NOMINAL_MEMBERS_6-DAG: Decl[InstanceMethod]/Super: max({#by: (Equatable, Equatable) throws -> Bool##(Equatable, Equatable) throws -> Bool#})[' rethrows'][#Equatable?#]{{; name=.+}}
// FIXME: The following should include 'partialResult' as local parameter name: "(nextPartialResult): (_ partialResult: Result, Equatable)"
// PRIVATE_NOMINAL_MEMBERS_6-DAG: Decl[InstanceMethod]/Super: reduce({#(initialResult): Result#}, {#(nextPartialResult): (Result, Equatable) throws -> Result##(Result, Equatable) throws -> Result#})[' rethrows'][#Result#]{{; name=.+}}
-// PRIVATE_NOMINAL_MEMBERS_6-DAG: Decl[InstanceMethod]/Super: dropFirst({#(n): Int#})[#ArraySlice<Equatable>#]{{; name=.+}}
+// PRIVATE_NOMINAL_MEMBERS_6-DAG: Decl[InstanceMethod]/Super: dropFirst({#(k): Int#})[#ArraySlice<Equatable>#]{{; name=.+}}
// FIXME: restore Decl[InstanceMethod]/Super: flatMap({#(transform): (Equatable) throws -> Sequence##(Equatable) throws -> Sequence#})[' rethrows'][#[IteratorProtocol.Element]#]{{; name=.+}}
func testArchetypeReplacement3 (_ a : [Int]) {
@@ -166,7 +166,7 @@
// PRIVATE_NOMINAL_MEMBERS_7-DAG: Decl[InstanceMethod]/Super: removeLast()[#Int#]
// PRIVATE_NOMINAL_MEMBERS_7-DAG: Decl[InstanceVar]/Super: first[#Int?#]
// PRIVATE_NOMINAL_MEMBERS_7-DAG: Decl[InstanceMethod]/Super: map({#(transform): (Int) throws -> T##(Int) throws -> T#})[' rethrows'][#[T]#]
-// PRIVATE_NOMINAL_MEMBERS_7-DAG: Decl[InstanceMethod]/Super: dropLast({#(n): Int#})[#ArraySlice<Int>#]
+// PRIVATE_NOMINAL_MEMBERS_7-DAG: Decl[InstanceMethod]/Super: dropLast({#(k): Int#})[#ArraySlice<Int>#]
// PRIVATE_NOMINAL_MEMBERS_7-DAG: Decl[InstanceMethod]/Super: elementsEqual({#(other): Sequence#}, {#by: (Int, Sequence.Element) throws -> Bool##(Int, Sequence.Element) throws -> Bool#})[' rethrows'][#Bool#]; name=elementsEqual(other: Sequence, by: (Int, Sequence.Element) throws -> Bool) rethrows
// PRIVATE_NOMINAL_MEMBERS_7-DAG: Decl[InstanceMethod]/Super: elementsEqual({#(other): Sequence#})[#Bool#]; name=elementsEqual(other: Sequence)
@@ -220,7 +220,7 @@
struct Test1000 : Sequence {
func #^RETURNS_ANY_SEQUENCE^#
}
-// RETURNS_ANY_SEQUENCE: Decl[InstanceMethod]/Super: dropFirst(_ n: Int)
+// RETURNS_ANY_SEQUENCE: Decl[InstanceMethod]/Super: dropFirst(_ k: Int)
func testPostfixOperator1(_ x: Int) {
x#^POSTFIX_INT_1^#
diff --git a/test/IDE/print_type_interface.swift b/test/IDE/print_type_interface.swift
index 675fb9e..a43f207 100644
--- a/test/IDE/print_type_interface.swift
+++ b/test/IDE/print_type_interface.swift
@@ -72,7 +72,7 @@
// TYPE4-DAG: public typealias Index = Int
// TYPE4-DAG: public func min() -> Int?
// TYPE4-DAG: public mutating func insert<C>(contentsOf newElements: C, at i: Int)
-// TYPE4-DAG: public mutating func removeFirst(_ n: Int)
+// TYPE4-DAG: public mutating func removeFirst(_ k: Int)
// TYPE4-DAG: public func makeIterator() -> IndexingIterator<Array<Int>>
// TYPE4-NOT: public func joined
@@ -80,6 +80,6 @@
// TYPE5-DAG: public func prefix(_ maxLength: Int) -> ArraySlice<String>
// TYPE5-DAG: public func suffix(_ maxLength: Int) -> ArraySlice<String>
// TYPE5-DAG: public func split(separator: String, maxSplits: Int = default, omittingEmptySubsequences: Bool = default) -> [ArraySlice<String>]
-// TYPE5-DAG: public func formIndex(_ i: inout Int, offsetBy n: Int)
+// TYPE5-DAG: public func formIndex(_ i: inout Int, offsetBy distance: Int)
// TYPE5-DAG: public func distance(from start: Int, to end: Int) -> Int
// TYPE5-DAG: public func joined(separator: String = default) -> String
