stdlib/public/core/CollectionAlgorithms.swift.gyb - third_party/swift - Git at Google

 //===--- 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
 //
 //===----------------------------------------------------------------------===//

 //===----------------------------------------------------------------------===//
 // 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"
   @_inlineable
   public var last: Element? {
     return isEmpty ? nil : self[index(before: endIndex)]
   }
 }

 //===----------------------------------------------------------------------===//
 // index(of:)/index(where:)
 //===----------------------------------------------------------------------===//

 extension Collection where Element : 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`.
   @_inlineable
   public func index(of element: Element) -> 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`.
   @_inlineable
   public func index(
     where predicate: (Element) 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 {
   @_inlineable
   public mutating func partition(
     by belongsInSecondPartition: (Element) 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]) {
         swapAt(i, pivot)
         formIndex(after: &pivot)
       }
       formIndex(after: &i)
     }
     return pivot
   }
 }

 extension MutableCollection where Self : BidirectionalCollection {
   @_inlineable
   public mutating func partition(
     by belongsInSecondPartition: (Element) throws -> Bool
   ) rethrows -> Index {
     let maybeOffset = try _withUnsafeMutableBufferPointerIfSupported {
       (bufferPointer) -> Int in
       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

       swapAt(lo, hi)
       formIndex(after: &lo)
     }

     return lo
   }
 }

 //===----------------------------------------------------------------------===//
 // sorted()
 //===----------------------------------------------------------------------===//

 % for Self in ['Sequence', 'MutableCollection']:

 % sequenceKind = 'sequence' if 'Sequence' in Self else 'collection'

 extension ${Self} where 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.
   @_inlineable
   public func sorted() -> [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.
   @_inlineable
   public func sorted(
     by areInIncreasingOrder:
       (Element, Element) throws -> Bool
   ) rethrows -> [Element] {
     var result = ContiguousArray(self)
     try result.sort(by: areInIncreasingOrder)
     return Array(result)
   }
 }

 % end

 extension MutableCollection
   where
   Self : RandomAccessCollection, 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"]"
   @_inlineable
   public mutating func sort() {
     let didSortUnsafeBuffer: Void? =
       _withUnsafeMutableBufferPointerIfSupported {
       (bufferPointer) -> Void in
       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.
   ///
   /// This method can take throwing closure. If closure throws error while sorting,
   /// order of elements may change. No elements will be lost.
   ///
   /// 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`.
   @_inlineable
   public mutating func sort(
     by areInIncreasingOrder:
       (Element, Element) throws -> Bool
   ) rethrows {

     let didSortUnsafeBuffer: Void? =
       try _withUnsafeMutableBufferPointerIfSupported {
       (bufferPointer) -> Void in
       try bufferPointer.sort(by: areInIncreasingOrder)
       return ()
     }
     if didSortUnsafeBuffer == nil {
       try _introSort(
         &self,
         subRange: startIndex..<endIndex,
         by: areInIncreasingOrder)
     }
   }
 }
	//===--- 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
	//
	//===----------------------------------------------------------------------===//

	//===----------------------------------------------------------------------===//
	// 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"
	@_inlineable
	public var last: Element? {
	return isEmpty ? nil : self[index(before: endIndex)]
	}
	}

	//===----------------------------------------------------------------------===//
	// index(of:)/index(where:)
	//===----------------------------------------------------------------------===//

	extension Collection where Element : 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`.
	@_inlineable
	public func index(of element: Element) -> 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`.
	@_inlineable
	public func index(
	where predicate: (Element) 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 {
	@_inlineable
	public mutating func partition(
	by belongsInSecondPartition: (Element) 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]) {
	swapAt(i, pivot)
	formIndex(after: &pivot)
	}
	formIndex(after: &i)
	}
	return pivot
	}
	}

	extension MutableCollection where Self : BidirectionalCollection {
	@_inlineable
	public mutating func partition(
	by belongsInSecondPartition: (Element) throws -> Bool
	) rethrows -> Index {
	let maybeOffset = try _withUnsafeMutableBufferPointerIfSupported {
	(bufferPointer) -> Int in
	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

	swapAt(lo, hi)
	formIndex(after: &lo)
	}

	return lo
	}
	}

	//===----------------------------------------------------------------------===//
	// sorted()
	//===----------------------------------------------------------------------===//

	% for Self in ['Sequence', 'MutableCollection']:

	% sequenceKind = 'sequence' if 'Sequence' in Self else 'collection'

	extension ${Self} where 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.
	@_inlineable
	public func sorted() -> [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.
	@_inlineable
	public func sorted(
	by areInIncreasingOrder:
	(Element, Element) throws -> Bool
	) rethrows -> [Element] {
	var result = ContiguousArray(self)
	try result.sort(by: areInIncreasingOrder)
	return Array(result)
	}
	}

	% end

	extension MutableCollection
	where
	Self : RandomAccessCollection, 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"]"
	@_inlineable
	public mutating func sort() {
	let didSortUnsafeBuffer: Void? =
	_withUnsafeMutableBufferPointerIfSupported {
	(bufferPointer) -> Void in
	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.
	///
	/// This method can take throwing closure. If closure throws error while sorting,
	/// order of elements may change. No elements will be lost.
	///
	/// 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`.
	@_inlineable
	public mutating func sort(
	by areInIncreasingOrder:
	(Element, Element) throws -> Bool
	) rethrows {

	let didSortUnsafeBuffer: Void? =
	try _withUnsafeMutableBufferPointerIfSupported {
	(bufferPointer) -> Void in
	try bufferPointer.sort(by: areInIncreasingOrder)
	return ()
	}
	if didSortUnsafeBuffer == nil {
	try _introSort(
	&self,
	subRange: startIndex..<endIndex,
	by: areInIncreasingOrder)
	}
	}
	}