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

 %{

 # 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:)`, `sort()`
   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()`, `sort(by:)`
   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()
   }
 }
	//===--- 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:)`, `sort()`
	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()`, `sort(by:)`
	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()
	}
	}