| //===--- Reverse.swift - Sequence and collection reversal -----------------===// |
| // |
| // 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 |
| // |
| //===----------------------------------------------------------------------===// |
| |
| extension MutableCollection where Self: BidirectionalCollection { |
| /// Reverses the elements of the collection in place. |
| /// |
| /// The following example reverses the elements of an array of characters: |
| /// |
| /// var characters: [Character] = ["C", "a", "f", "é"] |
| /// characters.reverse() |
| /// print(characters) |
| /// // Prints "["é", "f", "a", "C"] |
| /// |
| /// - Complexity: O(*n*), where *n* is the number of elements in the |
| /// collection. |
| @inlinable // protocol-only |
| public mutating func reverse() { |
| if isEmpty { return } |
| var f = startIndex |
| var l = index(before: endIndex) |
| while f < l { |
| swapAt(f, l) |
| formIndex(after: &f) |
| formIndex(before: &l) |
| } |
| } |
| } |
| |
| /// A collection that presents the elements of its base collection |
| /// in reverse order. |
| /// |
| /// - Note: This type is the result of `x.reversed()` where `x` is a |
| /// collection having bidirectional indices. |
| /// |
| /// The `reversed()` method is always lazy when applied to a collection |
| /// with bidirectional indices, but does not implicitly confer |
| /// laziness on algorithms applied to its result. In other words, for |
| /// ordinary collections `c` having bidirectional indices: |
| /// |
| /// * `c.reversed()` does not create new storage |
| /// * `c.reversed().map(f)` maps eagerly and returns a new array |
| /// * `c.lazy.reversed().map(f)` maps lazily and returns a `LazyMapCollection` |
| @_fixed_layout |
| public struct ReversedCollection<Base: BidirectionalCollection> { |
| public let _base: Base |
| |
| /// Creates an instance that presents the elements of `base` in |
| /// reverse order. |
| /// |
| /// - Complexity: O(1) |
| @inlinable |
| internal init(_base: Base) { |
| self._base = _base |
| } |
| } |
| |
| extension ReversedCollection { |
| // An iterator that can be much faster than the iterator of a reversed slice. |
| @_fixed_layout |
| public struct Iterator { |
| @usableFromInline |
| internal let _base: Base |
| @usableFromInline |
| internal var _position: Base.Index |
| |
| @inlinable |
| @inline(__always) |
| /// Creates an iterator over the given collection. |
| public /// @testable |
| init(_base: Base) { |
| self._base = _base |
| self._position = _base.endIndex |
| } |
| } |
| } |
| |
| extension ReversedCollection.Iterator: IteratorProtocol, Sequence { |
| public typealias Element = Base.Element |
| |
| @inlinable |
| @inline(__always) |
| public mutating func next() -> Element? { |
| guard _fastPath(_position != _base.startIndex) else { return nil } |
| _base.formIndex(before: &_position) |
| return _base[_position] |
| } |
| } |
| |
| extension ReversedCollection: Sequence { |
| /// A type that represents a valid position in the collection. |
| /// |
| /// Valid indices consist of the position of every element and a |
| /// "past the end" position that's not valid for use as a subscript. |
| public typealias Element = Base.Element |
| |
| @inlinable |
| @inline(__always) |
| public __consuming func makeIterator() -> Iterator { |
| return Iterator(_base: _base) |
| } |
| } |
| |
| extension ReversedCollection { |
| /// An index that traverses the same positions as an underlying index, |
| /// with inverted traversal direction. |
| @_fixed_layout |
| public struct Index { |
| /// The position after this position in the underlying collection. |
| /// |
| /// To find the position that corresponds with this index in the original, |
| /// underlying collection, use that collection's `index(before:)` method |
| /// with the `base` property. |
| /// |
| /// The following example declares a function that returns the index of the |
| /// last even number in the passed array, if one is found. First, the |
| /// function finds the position of the last even number as a `ReversedIndex` |
| /// in a reversed view of the array of numbers. Next, the function calls the |
| /// array's `index(before:)` method to return the correct position in the |
| /// passed array. |
| /// |
| /// func indexOfLastEven(_ numbers: [Int]) -> Int? { |
| /// let reversedNumbers = numbers.reversed() |
| /// guard let i = reversedNumbers.firstIndex(where: { $0 % 2 == 0 }) |
| /// else { return nil } |
| /// |
| /// return numbers.index(before: i.base) |
| /// } |
| /// |
| /// let numbers = [10, 20, 13, 19, 30, 52, 17, 40, 51] |
| /// if let lastEven = indexOfLastEven(numbers) { |
| /// print("Last even number: \(numbers[lastEven])") |
| /// } |
| /// // Prints "Last even number: 40" |
| public let base: Base.Index |
| |
| /// Creates a new index into a reversed collection for the position before |
| /// the specified index. |
| /// |
| /// When you create an index into a reversed collection using `base`, an |
| /// index from the underlying collection, the resulting index is the |
| /// position of the element *before* the element referenced by `base`. The |
| /// following example creates a new `ReversedIndex` from the index of the |
| /// `"a"` character in a string's character view. |
| /// |
| /// let name = "Horatio" |
| /// let aIndex = name.firstIndex(of: "a")! |
| /// // name[aIndex] == "a" |
| /// |
| /// let reversedName = name.reversed() |
| /// let i = ReversedIndex<String>(aIndex) |
| /// // reversedName[i] == "r" |
| /// |
| /// The element at the position created using `ReversedIndex<...>(aIndex)` is |
| /// `"r"`, the character before `"a"` in the `name` string. |
| /// |
| /// - Parameter base: The position after the element to create an index for. |
| @inlinable |
| public init(_ base: Base.Index) { |
| self.base = base |
| } |
| } |
| } |
| |
| extension ReversedCollection.Index: Comparable { |
| @inlinable |
| public static func == ( |
| lhs: ReversedCollection<Base>.Index, |
| rhs: ReversedCollection<Base>.Index |
| ) -> Bool { |
| // Note ReversedIndex has inverted logic compared to base Base.Index |
| return lhs.base == rhs.base |
| } |
| |
| @inlinable |
| public static func < ( |
| lhs: ReversedCollection<Base>.Index, |
| rhs: ReversedCollection<Base>.Index |
| ) -> Bool { |
| // Note ReversedIndex has inverted logic compared to base Base.Index |
| return lhs.base > rhs.base |
| } |
| } |
| |
| extension ReversedCollection.Index: Hashable where Base.Index: Hashable { |
| /// Hashes the essential components of this value by feeding them into the |
| /// given hasher. |
| /// |
| /// - Parameter hasher: The hasher to use when combining the components |
| /// of this instance. |
| @inlinable |
| public func hash(into hasher: inout Hasher) { |
| hasher.combine(base) |
| } |
| } |
| |
| extension ReversedCollection: BidirectionalCollection { |
| @inlinable |
| public var startIndex: Index { |
| return Index(_base.endIndex) |
| } |
| |
| @inlinable |
| public var endIndex: Index { |
| return Index(_base.startIndex) |
| } |
| |
| @inlinable |
| public func index(after i: Index) -> Index { |
| return Index(_base.index(before: i.base)) |
| } |
| |
| @inlinable |
| public func index(before i: Index) -> Index { |
| return Index(_base.index(after: i.base)) |
| } |
| |
| @inlinable |
| public func index(_ i: Index, offsetBy n: Int) -> Index { |
| // FIXME: swift-3-indexing-model: `-n` can trap on Int.min. |
| return Index(_base.index(i.base, offsetBy: -n)) |
| } |
| |
| @inlinable |
| public func index( |
| _ i: Index, offsetBy n: Int, limitedBy limit: Index |
| ) -> Index? { |
| // FIXME: swift-3-indexing-model: `-n` can trap on Int.min. |
| return _base.index(i.base, offsetBy: -n, limitedBy: limit.base) |
| .map(Index.init) |
| } |
| |
| @inlinable |
| public func distance(from start: Index, to end: Index) -> Int { |
| return _base.distance(from: end.base, to: start.base) |
| } |
| |
| @inlinable |
| public subscript(position: Index) -> Element { |
| return _base[_base.index(before: position.base)] |
| } |
| } |
| |
| extension ReversedCollection: RandomAccessCollection where Base: RandomAccessCollection { } |
| |
| extension ReversedCollection { |
| /// Reversing a reversed collection returns the original collection. |
| /// |
| /// - Complexity: O(1) |
| @inlinable |
| @available(swift, introduced: 4.2) |
| public func reversed() -> Base { |
| return _base |
| } |
| } |
| |
| extension BidirectionalCollection { |
| /// Returns a view presenting the elements of the collection in reverse |
| /// order. |
| /// |
| /// You can reverse a collection without allocating new space for its |
| /// elements by calling this `reversed()` method. A `ReversedCollection` |
| /// instance wraps an underlying collection and provides access to its |
| /// elements in reverse order. This example prints the characters of a |
| /// string in reverse order: |
| /// |
| /// let word = "Backwards" |
| /// for char in word.reversed() { |
| /// print(char, terminator: "") |
| /// } |
| /// // Prints "sdrawkcaB" |
| /// |
| /// If you need a reversed collection of the same type, you may be able to |
| /// use the collection's sequence-based or collection-based initializer. For |
| /// example, to get the reversed version of a string, reverse its |
| /// characters and initialize a new `String` instance from the result. |
| /// |
| /// let reversedWord = String(word.reversed()) |
| /// print(reversedWord) |
| /// // Prints "sdrawkcaB" |
| /// |
| /// - Complexity: O(1) |
| @inlinable |
| public func reversed() -> ReversedCollection<Self> { |
| return ReversedCollection(_base: self) |
| } |
| } |
| |
| extension LazyCollectionProtocol |
| where |
| Self: BidirectionalCollection, |
| Elements: BidirectionalCollection { |
| |
| /// Returns the elements of the collection in reverse order. |
| /// |
| /// - Complexity: O(1) |
| @inlinable |
| public func reversed() -> LazyCollection<ReversedCollection<Elements>> { |
| return ReversedCollection(_base: elements).lazy |
| } |
| } |