Permalink
Find file
649 lines (595 sloc) 21.1 KB
//===--- CollectionAlgorithms.swift.gyb -----------------------*- swift -*-===//
//
// 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
//
//===----------------------------------------------------------------------===//
%{
# We know we will eventually get a Sequence.Element type. Define
# a shorthand that we can use today.
IElement = "Iterator.Element"
}%
//===----------------------------------------------------------------------===//
// last
//===----------------------------------------------------------------------===//
extension BidirectionalCollection {
/// 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"
public var last: Iterator.Element? {
return isEmpty ? nil : self[index(before: endIndex)]
}
}
//===----------------------------------------------------------------------===//
// index(of:)/index(where:)
//===----------------------------------------------------------------------===//
extension Collection where ${IElement} : Equatable {
/// Returns the first index where the specified value appears in the
/// collection.
///
/// After using `index(of:)` to find the position of a particular element in
/// a collection, you can use it to access the element by subscripting. This
/// example shows how you can modify one of the names in an array of
/// students.
///
/// var students = ["Ben", "Ivy", "Jordell", "Maxime"]
/// if let i = students.index(of: "Maxime") {
/// students[i] = "Max"
/// }
/// print(students)
/// // Prints "["Ben", "Ivy", "Jordell", "Max"]"
///
/// - 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`.
///
/// - SeeAlso: `index(where:)`
public func index(of element: ${IElement}) -> Index? {
if let result = _customIndexOfEquatableElement(element) {
return result
}
var i = self.startIndex
while i != self.endIndex {
if self[i] == element {
return i
}
self.formIndex(after: &i)
}
return nil
}
}
extension Collection {
/// Returns the first index in which an element of the collection satisfies
/// the given predicate.
///
/// You can use the predicate to find an element of a type that doesn't
/// conform to the `Equatable` protocol or to find an element that matches
/// particular criteria. Here's an example that finds a student name that
/// begins with the letter "A":
///
/// let students = ["Kofi", "Abena", "Peter", "Kweku", "Akosua"]
/// if let i = students.index(where: { $0.hasPrefix("A") }) {
/// print("\(students[i]) starts with 'A'!")
/// }
/// // Prints "Abena starts with 'A'!"
///
/// - Parameter predicate: A closure that takes an element as its argument
/// and returns a Boolean value that indicates whether the passed element
/// represents a match.
/// - Returns: The index of the first element for which `predicate` returns
/// `true`. If no elements in the collection satisfy the given predicate,
/// returns `nil`.
///
/// - SeeAlso: `index(of:)`
public func index(
where predicate: (${IElement}) throws -> Bool
) rethrows -> Index? {
var i = self.startIndex
while i != self.endIndex {
if try predicate(self[i]) {
return i
}
self.formIndex(after: &i)
}
return nil
}
}
//===----------------------------------------------------------------------===//
// MutableCollection
//===----------------------------------------------------------------------===//
%{
orderingExplanation = """\
/// The predicate must be a *strict weak ordering* over the elements. That
/// is, for any elements `a`, `b`, and `c`, the following conditions must
/// hold:
///
/// - `areInIncreasingOrder(a, a)` is always `false`. (Irreflexivity)
/// - If `areInIncreasingOrder(a, b)` and `areInIncreasingOrder(b, c)` are
/// both `true`, then `areInIncreasingOrder(a, c)` is also `true`.
/// (Transitive comparability)
/// - Two elements are *incomparable* if neither is ordered before the other
/// according to the predicate. If `a` and `b` are incomparable, and `b`
/// and `c` are incomparable, then `a` and `c` are also incomparable.
/// (Transitive incomparability)
///"""
}%
//===----------------------------------------------------------------------===//
// partition()
//===----------------------------------------------------------------------===//
extension MutableCollection {
public mutating func partition(
by belongsInSecondPartition: (${IElement}) throws -> Bool
) rethrows -> Index {
var pivot = startIndex
while true {
if pivot == endIndex {
return pivot
}
if try belongsInSecondPartition(self[pivot]) {
break
}
formIndex(after: &pivot)
}
var i = index(after: pivot)
while i < endIndex {
if try !belongsInSecondPartition(self[i]) {
swap(&self[i], &self[pivot])
formIndex(after: &pivot)
}
formIndex(after: &i)
}
return pivot
}
}
extension MutableCollection where Self : BidirectionalCollection {
public mutating func partition(
by belongsInSecondPartition: (${IElement}) throws -> Bool
) rethrows -> Index {
let maybeOffset = try _withUnsafeMutableBufferPointerIfSupported {
(baseAddress, count) -> Int in
var bufferPointer =
UnsafeMutableBufferPointer(start: baseAddress, count: count)
let unsafeBufferPivot = try bufferPointer.partition(
by: belongsInSecondPartition)
return unsafeBufferPivot - bufferPointer.startIndex
}
if let offset = maybeOffset {
return index(startIndex, offsetBy: numericCast(offset))
}
var lo = startIndex
var hi = endIndex
// 'Loop' invariants (at start of Loop, all are true):
// * lo < hi
// * predicate(self[i]) == false, for i in startIndex ..< lo
// * predicate(self[i]) == true, for i in hi ..< endIndex
Loop: while true {
FindLo: repeat {
while lo < hi {
if try belongsInSecondPartition(self[lo]) { break FindLo }
formIndex(after: &lo)
}
break Loop
} while false
FindHi: repeat {
formIndex(before: &hi)
while lo < hi {
if try !belongsInSecondPartition(self[hi]) { break FindHi }
formIndex(before: &hi)
}
break Loop
} while false
swap(&self[lo], &self[hi])
formIndex(after: &lo)
}
return lo
}
}
//===----------------------------------------------------------------------===//
// sorted()
//===----------------------------------------------------------------------===//
% for Self in ['Sequence', 'MutableCollection']:
% sequenceKind = 'sequence' if 'Sequence' in Self else 'collection'
extension ${Self} where Self.Iterator.Element : Comparable {
/// Returns the elements of the ${sequenceKind}, sorted.
///
/// You can sort any ${sequenceKind} of elements that conform to the
/// `Comparable` protocol by calling this method. Elements are sorted in
/// ascending order.
///
/// The sorting algorithm is not stable. A nonstable sort may change the
/// relative order of elements that compare equal.
///
/// Here's an example of sorting a list of students' names. Strings in Swift
/// conform to the `Comparable` protocol, so the names are sorted in
/// ascending order according to the less-than operator (`<`).
///
/// let students: Set = ["Kofi", "Abena", "Peter", "Kweku", "Akosua"]
/// let sortedStudents = students.sorted()
/// print(sortedStudents)
/// // Prints "["Abena", "Akosua", "Kofi", "Kweku", "Peter"]"
///
/// To sort the elements of your ${sequenceKind} in descending order, pass the
/// greater-than operator (`>`) to the `sorted(by:)` method.
///
/// let descendingStudents = students.sorted(by: >)
/// print(descendingStudents)
/// // Prints "["Peter", "Kweku", "Kofi", "Akosua", "Abena"]"
///
/// - Returns: A sorted array of the ${sequenceKind}'s elements.
///
/// - SeeAlso: `sorted(by:)`
/// ${'- MutatingVariant: sort' if Self == 'MutableCollection' else ''}
public func sorted() -> [Iterator.Element] {
var result = ContiguousArray(self)
result.sort()
return Array(result)
}
}
extension ${Self} {
/// Returns the elements of the ${sequenceKind}, sorted using the given
/// predicate as the comparison between elements.
///
/// When you want to sort a ${sequenceKind} of elements that don't conform to
/// the `Comparable` protocol, pass a predicate to this method that returns
/// `true` when the first element passed should be ordered before the
/// second. The elements of the resulting array are ordered according to the
/// given predicate.
///
${orderingExplanation}
/// The sorting algorithm is not stable. A nonstable sort may change the
/// relative order of elements for which `areInIncreasingOrder` does not
/// establish an order.
///
/// In the following example, the predicate provides an ordering for an array
/// of a custom `HTTPResponse` type. The predicate orders errors before
/// successes and sorts the error responses by their error code.
///
/// enum HTTPResponse {
/// case ok
/// case error(Int)
/// }
///
/// let responses: [HTTPResponse] = [.error(500), .ok, .ok, .error(404), .error(403)]
/// let sortedResponses = responses.sorted {
/// switch ($0, $1) {
/// // Order errors by code
/// case let (.error(aCode), .error(bCode)):
/// return aCode < bCode
///
/// // All successes are equivalent, so none is before any other
/// case (.ok, .ok): return false
///
/// // Order errors before successes
/// case (.error, .ok): return true
/// case (.ok, .error): return false
/// }
/// }
/// print(sortedResponses)
/// // Prints "[.error(403), .error(404), .error(500), .ok, .ok]"
///
/// You also use this method to sort elements that conform to the
/// `Comparable` protocol in descending order. To sort your ${sequenceKind}
/// in descending order, pass the greater-than operator (`>`) as the
/// `areInIncreasingOrder` parameter.
///
/// let students: Set = ["Kofi", "Abena", "Peter", "Kweku", "Akosua"]
/// let descendingStudents = students.sorted(by: >)
/// print(descendingStudents)
/// // Prints "["Peter", "Kweku", "Kofi", "Akosua", "Abena"]"
///
/// Calling the related `sorted()` method is equivalent to calling this
/// method and passing the less-than operator (`<`) as the predicate.
///
/// print(students.sorted())
/// // Prints "["Abena", "Akosua", "Kofi", "Kweku", "Peter"]"
/// print(students.sorted(by: <))
/// // Prints "["Abena", "Akosua", "Kofi", "Kweku", "Peter"]"
///
/// - Parameter areInIncreasingOrder: A predicate that returns `true` if its first
/// argument should be ordered before its second argument; otherwise,
/// `false`.
/// - Returns: A sorted array of the ${sequenceKind}'s elements.
///
/// - SeeAlso: `sorted()`
/// ${'- MutatingVariant: sort' if Self == 'MutableCollection' else ''}
public func sorted(
by areInIncreasingOrder:
(${IElement}, ${IElement}) -> Bool
) -> [Iterator.Element] {
var result = ContiguousArray(self)
result.sort(by: areInIncreasingOrder)
return Array(result)
}
}
% end
extension MutableCollection
where
Self : RandomAccessCollection,
Self.Iterator.Element : Comparable {
/// Sorts the collection in place.
///
/// You can sort any mutable collection of elements that conform to the
/// `Comparable` protocol by calling this method. Elements are sorted in
/// ascending order.
///
/// The sorting algorithm is not stable. A nonstable sort may change the
/// relative order of elements that compare equal.
///
/// Here's an example of sorting a list of students' names. Strings in Swift
/// conform to the `Comparable` protocol, so the names are sorted in
/// ascending order according to the less-than operator (`<`).
///
/// var students = ["Kofi", "Abena", "Peter", "Kweku", "Akosua"]
/// students.sort()
/// print(students)
/// // Prints "["Abena", "Akosua", "Kofi", "Kweku", "Peter"]"
///
/// To sort the elements of your collection in descending order, pass the
/// greater-than operator (`>`) to the `sort(by:)` method.
///
/// students.sort(by: >)
/// print(students)
/// // Prints "["Peter", "Kweku", "Kofi", "Akosua", "Abena"]"
public mutating func sort() {
let didSortUnsafeBuffer: Void? =
_withUnsafeMutableBufferPointerIfSupported {
(baseAddress, count) -> Void in
var bufferPointer =
UnsafeMutableBufferPointer(start: baseAddress, count: count)
bufferPointer.sort()
return ()
}
if didSortUnsafeBuffer == nil {
_introSort(&self, subRange: startIndex..<endIndex)
}
}
}
extension MutableCollection where Self : RandomAccessCollection {
/// Sorts the collection in place, using the given predicate as the
/// comparison between elements.
///
/// When you want to sort a collection of elements that doesn't conform to
/// the `Comparable` protocol, pass a closure to this method that returns
/// `true` when the first element passed should be ordered before the
/// second.
///
${orderingExplanation}
/// The sorting algorithm is not stable. A nonstable sort may change the
/// relative order of elements for which `areInIncreasingOrder` does not
/// establish an order.
///
/// In the following example, the closure provides an ordering for an array
/// of a custom enumeration that describes an HTTP response. The predicate
/// orders errors before successes and sorts the error responses by their
/// error code.
///
/// enum HTTPResponse {
/// case ok
/// case error(Int)
/// }
///
/// var responses: [HTTPResponse] = [.error(500), .ok, .ok, .error(404), .error(403)]
/// responses.sort {
/// switch ($0, $1) {
/// // Order errors by code
/// case let (.error(aCode), .error(bCode)):
/// return aCode < bCode
///
/// // All successes are equivalent, so none is before any other
/// case (.ok, .ok): return false
///
/// // Order errors before successes
/// case (.error, .ok): return true
/// case (.ok, .error): return false
/// }
/// }
/// print(responses)
/// // Prints "[.error(403), .error(404), .error(500), .ok, .ok]"
///
/// Alternatively, use this method to sort a collection of elements that do
/// conform to `Comparable` when you want the sort to be descending instead
/// of ascending. Pass the greater-than operator (`>`) operator as the
/// predicate.
///
/// var students = ["Kofi", "Abena", "Peter", "Kweku", "Akosua"]
/// students.sort(by: >)
/// print(students)
/// // Prints "["Peter", "Kweku", "Kofi", "Akosua", "Abena"]"
///
/// - Parameter areInIncreasingOrder: A predicate that returns `true` if its first
/// argument should be ordered before its second argument; otherwise,
/// `false`.
public mutating func sort(
by areInIncreasingOrder:
(${IElement}, ${IElement}) -> Bool
) {
let didSortUnsafeBuffer: Void? =
_withUnsafeMutableBufferPointerIfSupported {
(baseAddress, count) -> Void in
var bufferPointer =
UnsafeMutableBufferPointer(start: baseAddress, count: count)
bufferPointer.sort(by: areInIncreasingOrder)
return ()
}
if didSortUnsafeBuffer == nil {
_introSort(
&self,
subRange: startIndex..<endIndex,
by: areInIncreasingOrder)
}
}
}
% for Self in '_Indexable', '_MutableIndexable':
%{
subscriptCommentPre = """\
/// Accesses a contiguous subrange of the collection's elements.
///
/// The accessed slice uses the same indices for the same elements as the
/// original collection. 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.index(of: "Evarts") // 4"""
if 'Mutable' in Self:
subscriptCommentMid = """\
/// streets[index!] = "Eustace"
/// print(streets[index!])
/// // Prints "Eustace\""""
else:
subscriptCommentMid = """\
/// print(streets[index!])
/// // Prints "Evarts\""""
subscriptCommentPost = """\
///
/// - Parameter bounds: A range of the collection's indices. The bounds of
/// the range must be valid indices of the collection."""
}%
// FIXME(ABI)#180 (Type checker)
// WORKAROUND rdar://25214066 - should be on Collection
extension ${Self} {
${subscriptCommentPre}
${subscriptCommentMid}
${subscriptCommentPost}
public subscript(bounds: ClosedRange<Index>) -> SubSequence {
get {
return self[
Range(
uncheckedBounds: (
lower: bounds.lowerBound,
upper: index(after: bounds.upperBound)))
]
}
% if 'Mutable' in Self:
set {
self[
Range(
uncheckedBounds: (
lower: bounds.lowerBound,
upper: index(after: bounds.upperBound)))
] = newValue
}
% end
}
}
// FIXME(ABI)#180 (Type checker)
// WORKAROUND rdar://25214066 - should be on Collection
extension ${Self} where Index : Strideable, Index.Stride : SignedInteger {
${subscriptCommentPre}
${subscriptCommentMid}
${subscriptCommentPost}
public subscript(bounds: CountableRange<Index>) -> SubSequence {
get {
return self[Range(bounds)]
}
% if 'Mutable' in Self:
set {
self[Range(bounds)] = newValue
}
% end
}
${subscriptCommentPre}
${subscriptCommentMid}
${subscriptCommentPost}
public subscript(bounds: CountableClosedRange<Index>) -> SubSequence {
get {
return self[ClosedRange(bounds)]
}
% if 'Mutable' in Self:
set {
self[ClosedRange(bounds)] = newValue
}
% end
}
}
% end
//===--- Unavailable stuff ------------------------------------------------===//
extension MutableCollection where Self : RandomAccessCollection {
@available(*, unavailable, message: "call partition(by:)")
public mutating func partition(
isOrderedBefore: (${IElement}, ${IElement}) -> Bool
) -> Index {
Builtin.unreachable()
}
@available(*, unavailable, message: "slice the collection using the range, and call partition(by:)")
public mutating func partition(
_ range: Range<Index>,
isOrderedBefore: (${IElement}, ${IElement}) -> Bool
) -> Index {
Builtin.unreachable()
}
}
extension MutableCollection
where Self : RandomAccessCollection, ${IElement} : Comparable {
@available(*, unavailable, message: "call partition(by:)")
public mutating func partition() -> Index {
Builtin.unreachable()
}
@available(*, unavailable, message: "slice the collection using the range, and call partition(by:)")
public mutating func partition(_ range: Range<Index>) -> Index {
Builtin.unreachable()
}
}
extension Sequence {
@available(*, unavailable, renamed: "sorted(by:)")
public func sort(
_ isOrderedBefore: (${IElement}, ${IElement}) -> Bool
) -> [${IElement}] {
Builtin.unreachable()
}
}
extension Sequence where ${IElement} : Comparable {
@available(*, unavailable, renamed: "sorted()")
public func sort() -> [${IElement}] {
Builtin.unreachable()
}
}
extension MutableCollection
where
Self : RandomAccessCollection,
Self.Iterator.Element : Comparable {
@available(*, unavailable, renamed: "sort()")
public mutating func sortInPlace() {
Builtin.unreachable()
}
}
extension MutableCollection where Self : RandomAccessCollection {
@available(*, unavailable, renamed: "sort(by:)")
public mutating func sortInPlace(
_ isOrderedBefore: (${IElement}, ${IElement}) -> Bool
) {
Builtin.unreachable()
}
}
extension Collection where ${IElement} : Equatable {
@available(*, unavailable, renamed: "index(of:)")
public func indexOf(_ element: ${IElement}) -> Index? {
Builtin.unreachable()
}
}
extension Collection {
@available(*, unavailable, renamed: "index(where:)")
public func indexOf(
_ predicate: (${IElement}) throws -> Bool
) rethrows -> Index? {
Builtin.unreachable()
}
}