| //===----------------------------------------------------------------------===// |
| // |
| // This source file is part of the Swift.org open source project |
| // |
| // Copyright (c) 2014 - 2017 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 |
| // See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors |
| // |
| //===----------------------------------------------------------------------===// |
| |
| /// A collection that supports backward as well as forward traversal. |
| /// |
| /// Bidirectional collections offer traversal backward from any valid index, |
| /// not including a collection's `startIndex`. Bidirectional collections can |
| /// therefore offer additional operations, such as a `last` property that |
| /// provides efficient access to the last element and a `reversed()` method |
| /// that presents the elements in reverse order. In addition, bidirectional |
| /// collections have more efficient implementations of some sequence and |
| /// collection methods, such as `suffix(_:)`. |
| /// |
| /// Conforming to the BidirectionalCollection Protocol |
| /// ================================================== |
| /// |
| /// To add `BidirectionalProtocol` conformance to your custom types, implement |
| /// the `index(before:)` method in addition to the requirements of the |
| /// `Collection` protocol. |
| /// |
| /// Indices that are moved forward and backward in a bidirectional collection |
| /// move by the same amount in each direction. That is, for any index `i` into |
| /// a bidirectional collection `c`: |
| /// |
| /// - If `i >= c.startIndex && i < c.endIndex`, |
| /// `c.index(before: c.index(after: i)) == i`. |
| /// - If `i > c.startIndex && i <= c.endIndex` |
| /// `c.index(after: c.index(before: i)) == i`. |
| public protocol BidirectionalCollection: Collection |
| where SubSequence: BidirectionalCollection, Indices: BidirectionalCollection { |
| // FIXME: Only needed for associated type inference. |
| override associatedtype Element |
| override associatedtype Index |
| override associatedtype SubSequence |
| override associatedtype Indices |
| |
| /// Returns the position immediately before the given index. |
| /// |
| /// - Parameter i: A valid index of the collection. `i` must be greater than |
| /// `startIndex`. |
| /// - Returns: The index value immediately before `i`. |
| func index(before i: Index) -> Index |
| |
| /// Replaces the given index with its predecessor. |
| /// |
| /// - Parameter i: A valid index of the collection. `i` must be greater than |
| /// `startIndex`. |
| func formIndex(before i: inout Index) |
| |
| /// Returns the position immediately after the given index. |
| /// |
| /// The successor of an index must be well defined. For an index `i` into a |
| /// collection `c`, calling `c.index(after: i)` returns the same index every |
| /// time. |
| /// |
| /// - Parameter i: A valid index of the collection. `i` must be less than |
| /// `endIndex`. |
| /// - Returns: The index value immediately after `i`. |
| override func index(after i: Index) -> Index |
| |
| /// Replaces the given index with its successor. |
| /// |
| /// - Parameter i: A valid index of the collection. `i` must be less than |
| /// `endIndex`. |
| override func formIndex(after i: inout Index) |
| |
| /// Returns an index that is the specified distance from the given index. |
| /// |
| /// The following example obtains an index advanced four positions from a |
| /// string's starting index and then prints the character at that position. |
| /// |
| /// let s = "Swift" |
| /// let i = s.index(s.startIndex, offsetBy: 4) |
| /// print(s[i]) |
| /// // Prints "t" |
| /// |
| /// The value passed as `distance` must not offset `i` beyond the bounds of |
| /// the collection. |
| /// |
| /// - Parameters: |
| /// - i: A valid index of the collection. |
| /// - 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(*k*), where *k* is the absolute |
| /// value of `distance`. |
| @_nonoverride 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. |
| /// |
| /// The following example obtains an index advanced four positions from a |
| /// string's starting index and then prints the character at that position. |
| /// The operation doesn't require going beyond the limiting `s.endIndex` |
| /// value, so it succeeds. |
| /// |
| /// let s = "Swift" |
| /// if let i = s.index(s.startIndex, offsetBy: 4, limitedBy: s.endIndex) { |
| /// print(s[i]) |
| /// } |
| /// // Prints "t" |
| /// |
| /// The next example attempts to retrieve an index six positions from |
| /// `s.startIndex` but fails, because that distance is beyond the index |
| /// passed as `limit`. |
| /// |
| /// let j = s.index(s.startIndex, offsetBy: 6, limitedBy: s.endIndex) |
| /// print(j) |
| /// // Prints "nil" |
| /// |
| /// 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. |
| /// - 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(*k*), where *k* is the absolute |
| /// value of `distance`. |
| @_nonoverride func index( |
| _ i: Index, offsetBy distance: Int, limitedBy limit: Index |
| ) -> Index? |
| |
| /// Returns the distance between two indices. |
| /// |
| /// Unless the collection conforms to the `BidirectionalCollection` protocol, |
| /// `start` must be less than or equal to `end`. |
| /// |
| /// - Parameters: |
| /// - start: A valid index of the collection. |
| /// - end: Another valid index of the collection. If `end` is equal to |
| /// `start`, the result is zero. |
| /// - Returns: The distance between `start` and `end`. The result can be |
| /// negative only if the collection conforms to the |
| /// `BidirectionalCollection` protocol. |
| /// |
| /// - Complexity: O(1) if the collection conforms to |
| /// `RandomAccessCollection`; otherwise, O(*k*), where *k* is the |
| /// resulting distance. |
| @_nonoverride func distance(from start: Index, to end: Index) -> Int |
| |
| /// The indices that are valid for subscripting the collection, in ascending |
| /// order. |
| /// |
| /// A collection's `indices` property can hold a strong reference to the |
| /// collection itself, causing the collection to be non-uniquely referenced. |
| /// If you mutate the collection while iterating over its indices, a strong |
| /// reference can cause an unexpected copy of the collection. To avoid the |
| /// unexpected copy, use the `index(after:)` method starting with |
| /// `startIndex` to produce indices instead. |
| /// |
| /// var c = MyFancyCollection([10, 20, 30, 40, 50]) |
| /// var i = c.startIndex |
| /// while i != c.endIndex { |
| /// c[i] /= 5 |
| /// i = c.index(after: i) |
| /// } |
| /// // c == MyFancyCollection([2, 4, 6, 8, 10]) |
| override var indices: Indices { get } |
| |
| // TODO: swift-3-indexing-model: tests. |
| /// The last element of the collection. |
| /// |
| /// If the collection is empty, the value of this property is `nil`. |
| /// |
| /// let numbers = [10, 20, 30, 40, 50] |
| /// if let lastNumber = numbers.last { |
| /// print(lastNumber) |
| /// } |
| /// // Prints "50" |
| /// |
| /// - Complexity: O(1) |
| var last: Element? { get } |
| |
| /// Accesses a contiguous subrange of the collection's elements. |
| /// |
| /// The accessed slice uses the same indices for the same elements as the |
| /// original collection uses. Always use the slice's `startIndex` property |
| /// instead of assuming that its indices start at a particular value. |
| /// |
| /// This example demonstrates getting a slice of an array of strings, finding |
| /// the index of one of the strings in the slice, and then using that index |
| /// in the original array. |
| /// |
| /// let streets = ["Adams", "Bryant", "Channing", "Douglas", "Evarts"] |
| /// let streetsSlice = streets[2 ..< streets.endIndex] |
| /// print(streetsSlice) |
| /// // Prints "["Channing", "Douglas", "Evarts"]" |
| /// |
| /// let index = streetsSlice.firstIndex(of: "Evarts") // 4 |
| /// print(streets[index!]) |
| /// // Prints "Evarts" |
| /// |
| /// - Parameter bounds: A range of the collection's indices. The bounds of |
| /// the range must be valid indices of the collection. |
| /// |
| /// - Complexity: O(1) |
| override subscript(bounds: Range<Index>) -> SubSequence { get } |
| |
| // FIXME: Only needed for associated type inference. |
| override subscript(position: Index) -> Element { get } |
| override var startIndex: Index { get } |
| override var endIndex: Index { get } |
| } |
| |
| /// Default implementation for bidirectional collections. |
| extension BidirectionalCollection { |
| |
| @inlinable // protocol-only |
| @inline(__always) |
| public func formIndex(before i: inout Index) { |
| i = index(before: i) |
| } |
| |
| @inlinable // protocol-only |
| public func index(_ i: Index, offsetBy distance: Int) -> Index { |
| return _index(i, offsetBy: distance) |
| } |
| |
| @inlinable // protocol-only |
| internal 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: distance, by: -1) { |
| formIndex(before: &i) |
| } |
| return i |
| } |
| |
| @inlinable // protocol-only |
| public func index( |
| _ i: Index, offsetBy distance: Int, limitedBy limit: Index |
| ) -> Index? { |
| return _index(i, offsetBy: distance, limitedBy: limit) |
| } |
| |
| @inlinable // protocol-only |
| internal func _index( |
| _ i: Index, offsetBy distance: Int, limitedBy limit: Index |
| ) -> Index? { |
| if distance >= 0 { |
| return _advanceForward(i, by: distance, limitedBy: limit) |
| } |
| var i = i |
| for _ in stride(from: 0, to: distance, by: -1) { |
| if i == limit { |
| return nil |
| } |
| formIndex(before: &i) |
| } |
| return i |
| } |
| |
| @inlinable // protocol-only |
| public func distance(from start: Index, to end: Index) -> Int { |
| return _distance(from: start, to: end) |
| } |
| |
| @inlinable // protocol-only |
| internal func _distance(from start: Index, to end: Index) -> Int { |
| var start = start |
| var count = 0 |
| |
| if start < end { |
| while start != end { |
| count += 1 |
| formIndex(after: &start) |
| } |
| } |
| else if start > end { |
| while start != end { |
| count -= 1 |
| formIndex(before: &start) |
| } |
| } |
| |
| return count |
| } |
| } |
| |
| extension BidirectionalCollection where SubSequence == Self { |
| /// Removes and returns the last element of the collection. |
| /// |
| /// You can use `popLast()` to remove the last element of a collection that |
| /// might be empty. The `removeLast()` method must be used only on a |
| /// nonempty collection. |
| /// |
| /// - Returns: The last element of the collection if the collection has one |
| /// or more elements; otherwise, `nil`. |
| /// |
| /// - Complexity: O(1) |
| @inlinable // protocol-only |
| public mutating func popLast() -> Element? { |
| guard !isEmpty else { return nil } |
| let element = last! |
| self = self[startIndex..<index(before: endIndex)] |
| return element |
| } |
| |
| /// Removes and returns the last element of the collection. |
| /// |
| /// The collection must not be empty. To remove the last element of a |
| /// collection that might be empty, use the `popLast()` method instead. |
| /// |
| /// - Returns: The last element of the collection. |
| /// |
| /// - Complexity: O(1) |
| @inlinable // protocol-only |
| @discardableResult |
| public mutating func removeLast() -> Element { |
| let element = last! |
| self = self[startIndex..<index(before: endIndex)] |
| return element |
| } |
| |
| /// Removes the given number of elements from the end of the collection. |
| /// |
| /// - 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(*k*), where *k* is the number of |
| /// elements to remove. |
| @inlinable // protocol-only |
| 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: -k)] |
| } |
| } |
| |
| extension BidirectionalCollection { |
| /// Returns a subsequence containing all but the specified number of final |
| /// elements. |
| /// |
| /// If the number of elements to drop exceeds the number of elements in the |
| /// collection, the result is an empty subsequence. |
| /// |
| /// let numbers = [1, 2, 3, 4, 5] |
| /// print(numbers.dropLast(2)) |
| /// // Prints "[1, 2, 3]" |
| /// print(numbers.dropLast(10)) |
| /// // Prints "[]" |
| /// |
| /// - 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(1) if the collection conforms to |
| /// `RandomAccessCollection`; otherwise, O(*k*), where *k* is the number of |
| /// elements to drop. |
| @inlinable // protocol-only |
| public func dropLast(_ k: Int) -> SubSequence { |
| _precondition( |
| k >= 0, "Can't drop a negative number of elements from a collection") |
| let end = index( |
| endIndex, |
| offsetBy: -k, |
| limitedBy: startIndex) ?? startIndex |
| return self[startIndex..<end] |
| } |
| |
| /// Returns a subsequence, up to the given maximum length, containing the |
| /// final elements of the collection. |
| /// |
| /// If the maximum length exceeds the number of elements in the collection, |
| /// the result contains the entire collection. |
| /// |
| /// let numbers = [1, 2, 3, 4, 5] |
| /// print(numbers.suffix(2)) |
| /// // Prints "[4, 5]" |
| /// print(numbers.suffix(10)) |
| /// // Prints "[1, 2, 3, 4, 5]" |
| /// |
| /// - Parameter maxLength: The maximum number of elements to return. |
| /// `maxLength` must be greater than or equal to zero. |
| /// - Returns: A subsequence terminating at the end of the collection with at |
| /// most `maxLength` elements. |
| /// |
| /// - Complexity: O(1) if the collection conforms to |
| /// `RandomAccessCollection`; otherwise, O(*k*), where *k* is equal to |
| /// `maxLength`. |
| @inlinable // protocol-only |
| public func suffix(_ maxLength: Int) -> SubSequence { |
| _precondition( |
| maxLength >= 0, |
| "Can't take a suffix of negative length from a collection") |
| let start = index( |
| endIndex, |
| offsetBy: -maxLength, |
| limitedBy: startIndex) ?? startIndex |
| return self[start..<endIndex] |
| } |
| } |
| |