| //===----------------------------------------------------------------------===// |
| // |
| // 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 |
| // |
| //===----------------------------------------------------------------------===// |
| |
| %{ |
| def cmp(a, b, p): |
| if p: |
| return "(try areInIncreasingOrder(" + a + ", " + b + "))" |
| else: |
| return "(" + a + " < " + b + ")" |
| |
| }% |
| |
| // Generate two versions of sorting functions: one with an explicitly passed |
| // predicate 'areInIncreasingOrder' and the other for Comparable types that don't |
| // need such a predicate. |
| % preds = [True, False] |
| % for p in preds: |
| %{ |
| if p: |
| rethrows_ = "rethrows" |
| try_ = "try" |
| else: |
| rethrows_ = "" |
| try_ = "" |
| }% |
| |
| @inlinable |
| internal func _insertionSort<C>( |
| _ elements: inout C, |
| subRange range: Range<C.Index> |
| ${", by areInIncreasingOrder: (C.Element, C.Element) throws -> Bool" if p else ""} |
| ) ${rethrows_} |
| where |
| C : MutableCollection & BidirectionalCollection |
| ${"" if p else ", C.Element : Comparable"} { |
| |
| if !range.isEmpty { |
| let start = range.lowerBound |
| |
| // Keep track of the end of the initial sequence of sorted |
| // elements. |
| var sortedEnd = start |
| |
| // One element is trivially already-sorted, thus pre-increment |
| // Continue until the sorted elements cover the whole sequence |
| elements.formIndex(after: &sortedEnd) |
| while sortedEnd != range.upperBound { |
| // get the first unsorted element |
| let x: C.Element = elements[sortedEnd] |
| |
| // Look backwards for x's position in the sorted sequence, |
| // moving elements forward to make room. |
| var i = sortedEnd |
| repeat { |
| let predecessor: C.Element = elements[elements.index(before: i)] |
| |
| % if p: |
| // If clouser throws the error, We catch the error put the element at right |
| // place and rethrow the error. |
| do { |
| // if x doesn't belong before y, we've found its position |
| if !${cmp("x", "predecessor", p)} { |
| break |
| } |
| } catch { |
| elements[i] = x |
| throw error |
| } |
| % else: |
| if !${cmp("x", "predecessor", p)} { |
| break |
| } |
| % end |
| |
| // Move y forward |
| elements[i] = predecessor |
| elements.formIndex(before: &i) |
| } while i != start |
| |
| if i != sortedEnd { |
| // Plop x into position |
| elements[i] = x |
| } |
| elements.formIndex(after: &sortedEnd) |
| } |
| } |
| } |
| |
| /// Sorts the elements at `elements[a]`, `elements[b]`, and `elements[c]`. |
| /// Stable. |
| /// |
| /// The indices passed as `a`, `b`, and `c` do not need to be consecutive, but |
| /// must be in strict increasing order. |
| /// |
| /// - Precondition: `a < b && b < c` |
| /// - Postcondition: `elements[a] <= elements[b] && elements[b] <= elements[c]` |
| @inlinable |
| public // @testable |
| func _sort3<C>( |
| _ elements: inout C, |
| _ a: C.Index, _ b: C.Index, _ c: C.Index |
| ${", by areInIncreasingOrder: (C.Element, C.Element) throws -> Bool" if p else ""} |
| ) ${rethrows_} |
| where |
| C : MutableCollection & RandomAccessCollection |
| ${"" if p else ", C.Element : Comparable"} |
| { |
| // There are thirteen possible permutations for the original ordering of |
| // the elements at indices `a`, `b`, and `c`. The comments in the code below |
| // show the relative ordering of the three elements using a three-digit |
| // number as shorthand for the position and comparative relationship of |
| // each element. For example, "312" indicates that the element at `a` is the |
| // largest of the three, the element at `b` is the smallest, and the element |
| // at `c` is the median. This hypothetical input array has a 312 ordering for |
| // `a`, `b`, and `c`: |
| // |
| // [ 7, 4, 3, 9, 2, 0, 3, 7, 6, 5 ] |
| // ^ ^ ^ |
| // a b c |
| // |
| // - If each of the three elements is distinct, they could be ordered as any |
| // of the permutations of 1, 2, and 3: 123, 132, 213, 231, 312, or 321. |
| // - If two elements are equivalent and one is distinct, they could be |
| // ordered as any permutation of 1, 1, and 2 or 1, 2, and 2: 112, 121, 211, |
| // 122, 212, or 221. |
| // - If all three elements are equivalent, they are already in order: 111. |
| |
| switch (${cmp("elements[b]", "elements[a]", p)}, |
| ${cmp("elements[c]", "elements[b]", p)}) { |
| case (false, false): |
| // 0 swaps: 123, 112, 122, 111 |
| break |
| |
| case (true, true): |
| // 1 swap: 321 |
| // swap(a, c): 312->123 |
| elements.swapAt(a, c) |
| |
| case (true, false): |
| // 1 swap: 213, 212 --- 2 swaps: 312, 211 |
| // swap(a, b): 213->123, 212->122, 312->132, 211->121 |
| elements.swapAt(a, b) |
| |
| if ${cmp("elements[c]", "elements[b]", p)} { |
| // 132 (started as 312), 121 (started as 211) |
| // swap(b, c): 132->123, 121->112 |
| elements.swapAt(b, c) |
| } |
| |
| case (false, true): |
| // 1 swap: 132, 121 --- 2 swaps: 231, 221 |
| // swap(b, c): 132->123, 121->112, 231->213, 221->212 |
| elements.swapAt(b, c) |
| |
| if ${cmp("elements[b]", "elements[a]", p)} { |
| // 213 (started as 231), 212 (started as 221) |
| // swap(a, b): 213->123, 212->122 |
| elements.swapAt(a, b) |
| } |
| } |
| } |
| |
| /// Reorders `elements` and returns an index `p` such that every element in |
| /// `elements[range.lowerBound..<p]` is less than every element in |
| /// `elements[p..<range.upperBound]`. |
| /// |
| /// - Precondition: The count of `range` must be >= 3: |
| /// `elements.distance(from: range.lowerBound, to: range.upperBound) >= 3` |
| @inlinable |
| internal func _partition<C>( |
| _ elements: inout C, |
| subRange range: Range<C.Index> |
| ${", by areInIncreasingOrder: (C.Element, C.Element) throws -> Bool" if p else ""} |
| ) ${rethrows_} -> C.Index |
| where |
| C : MutableCollection & RandomAccessCollection |
| ${"" if p else ", C.Element : Comparable"} |
| { |
| var lo = range.lowerBound |
| var hi = elements.index(before: range.upperBound) |
| |
| // Sort the first, middle, and last elements, then use the middle value |
| // as the pivot for the partition. |
| let half = numericCast(elements.distance(from: lo, to: hi)) as UInt / 2 |
| let mid = elements.index(lo, offsetBy: numericCast(half)) |
| ${try_} _sort3(&elements, lo, mid, hi |
| ${", by: areInIncreasingOrder" if p else ""}) |
| let pivot = elements[mid] |
| |
| // Loop invariants: |
| // * lo < hi |
| // * elements[i] < pivot, for i in range.lowerBound..<lo |
| // * pivot <= elements[i] for i in hi..<range.upperBound |
| Loop: while true { |
| FindLo: do { |
| elements.formIndex(after: &lo) |
| while lo != hi { |
| if !${cmp("elements[lo]", "pivot", p)} { break FindLo } |
| elements.formIndex(after: &lo) |
| } |
| break Loop |
| } |
| |
| FindHi: do { |
| elements.formIndex(before: &hi) |
| while hi != lo { |
| if ${cmp("elements[hi]", "pivot", p)} { break FindHi } |
| elements.formIndex(before: &hi) |
| } |
| break Loop |
| } |
| |
| elements.swapAt(lo, hi) |
| } |
| |
| return lo |
| } |
| |
| @inlinable |
| public // @testable |
| func _introSort<C>( |
| _ elements: inout C, |
| subRange range: Range<C.Index> |
| ${", by areInIncreasingOrder: (C.Element, C.Element) throws -> Bool" if p else ""} |
| ) ${rethrows_} |
| where |
| C : MutableCollection & RandomAccessCollection |
| ${"" if p else ", C.Element : Comparable"} { |
| |
| let count = |
| elements.distance(from: range.lowerBound, to: range.upperBound) |
| if count < 2 { |
| return |
| } |
| // Set max recursion depth to 2*floor(log(N)), as suggested in the introsort |
| // paper: http://www.cs.rpi.edu/~musser/gp/introsort.ps |
| let depthLimit = 2 * count._binaryLogarithm() |
| ${try_} _introSortImpl( |
| &elements, |
| subRange: range, |
| ${"by: areInIncreasingOrder," if p else ""} |
| depthLimit: depthLimit) |
| } |
| |
| @inlinable |
| internal func _introSortImpl<C>( |
| _ elements: inout C, |
| subRange range: Range<C.Index> |
| ${", by areInIncreasingOrder: (C.Element, C.Element) throws -> Bool" if p else ""}, |
| depthLimit: Int |
| ) ${rethrows_} |
| where |
| C : MutableCollection & RandomAccessCollection |
| ${"" if p else ", C.Element : Comparable"} { |
| |
| // Insertion sort is better at handling smaller regions. |
| if elements.distance(from: range.lowerBound, to: range.upperBound) < 20 { |
| ${try_} _insertionSort( |
| &elements, |
| subRange: range |
| ${", by: areInIncreasingOrder" if p else ""}) |
| return |
| } |
| if depthLimit == 0 { |
| ${try_} _heapSort( |
| &elements, |
| subRange: range |
| ${", by: areInIncreasingOrder" if p else ""}) |
| return |
| } |
| |
| // Partition and sort. |
| // We don't check the depthLimit variable for underflow because this variable |
| // is always greater than zero (see check above). |
| let partIdx: C.Index = ${try_} _partition( |
| &elements, |
| subRange: range |
| ${", by: areInIncreasingOrder" if p else ""}) |
| ${try_} _introSortImpl( |
| &elements, |
| subRange: range.lowerBound..<partIdx, |
| ${"by: areInIncreasingOrder, " if p else ""} |
| depthLimit: depthLimit &- 1) |
| ${try_} _introSortImpl( |
| &elements, |
| subRange: partIdx..<range.upperBound, |
| ${"by: areInIncreasingOrder, " if p else ""} |
| depthLimit: depthLimit &- 1) |
| } |
| |
| @inlinable |
| internal func _siftDown<C>( |
| _ elements: inout C, |
| index: C.Index, |
| subRange range: Range<C.Index> |
| ${", by areInIncreasingOrder: (C.Element, C.Element) throws -> Bool" if p else ""} |
| ) ${rethrows_} |
| where |
| C : MutableCollection & RandomAccessCollection |
| ${"" if p else ", C.Element : Comparable"} { |
| |
| let countToIndex = elements.distance(from: range.lowerBound, to: index) |
| let countFromIndex = elements.distance(from: index, to: range.upperBound) |
| // Check if left child is within bounds. If not, return, because there are |
| // no children of the given node in the heap. |
| if countToIndex + 1 >= countFromIndex { |
| return |
| } |
| let left = elements.index(index, offsetBy: countToIndex + 1) |
| var largest = index |
| if ${cmp("elements[largest]", "elements[left]", p)} { |
| largest = left |
| } |
| // Check if right child is also within bounds before trying to examine it. |
| if countToIndex + 2 < countFromIndex { |
| let right = elements.index(after: left) |
| if ${cmp("elements[largest]", "elements[right]", p)} { |
| largest = right |
| } |
| } |
| // If a child is bigger than the current node, swap them and continue sifting |
| // down. |
| if largest != index { |
| elements.swapAt(index, largest) |
| ${try_} _siftDown( |
| &elements, |
| index: largest, |
| subRange: range |
| ${", by: areInIncreasingOrder" if p else ""}) |
| } |
| } |
| |
| @inlinable |
| internal func _heapify<C>( |
| _ elements: inout C, |
| subRange range: Range<C.Index> |
| ${", by areInIncreasingOrder: (C.Element, C.Element) throws -> Bool" if p else ""} |
| ) ${rethrows_} |
| where |
| C : MutableCollection & RandomAccessCollection |
| ${"" if p else ", C.Element : Comparable"} { |
| // Here we build a heap starting from the lowest nodes and moving to the root. |
| // On every step we sift down the current node to obey the max-heap property: |
| // parent >= max(leftChild, rightChild) |
| // |
| // We skip the rightmost half of the array, because these nodes don't have |
| // any children. |
| let root = range.lowerBound |
| var node = elements.index( |
| root, |
| offsetBy: elements.distance( |
| from: range.lowerBound, to: range.upperBound) / 2) |
| |
| while node != root { |
| elements.formIndex(before: &node) |
| ${try_} _siftDown( |
| &elements, |
| index: node, |
| subRange: range |
| ${", by: areInIncreasingOrder" if p else ""}) |
| } |
| } |
| |
| @inlinable |
| internal func _heapSort<C>( |
| _ elements: inout C, |
| subRange range: Range<C.Index> |
| ${", by areInIncreasingOrder: (C.Element, C.Element) throws -> Bool" if p else ""} |
| ) ${rethrows_} |
| where |
| C : MutableCollection & RandomAccessCollection |
| ${"" if p else ", C.Element : Comparable"} { |
| var hi = range.upperBound |
| let lo = range.lowerBound |
| ${try_} _heapify( |
| &elements, |
| subRange: range |
| ${", by: areInIncreasingOrder" if p else ""}) |
| elements.formIndex(before: &hi) |
| while hi != lo { |
| elements.swapAt(lo, hi) |
| ${try_} _siftDown( |
| &elements, |
| index: lo, |
| subRange: lo..<hi |
| ${", by: areInIncreasingOrder" if p else ""}) |
| elements.formIndex(before: &hi) |
| } |
| } |
| |
| % end |
| // for p in preds |
| |
| /// Exchanges the values of the two arguments. |
| /// |
| /// The two arguments must not alias each other. To swap two elements of a |
| /// mutable collection, use the `swapAt(_:_:)` method of that collection |
| /// instead of this function. |
| /// |
| /// - Parameters: |
| /// - a: The first value to swap. |
| /// - b: The second value to swap. |
| @inlinable |
| public func swap<T>(_ a: inout T, _ b: inout T) { |
| // Semantically equivalent to (a, b) = (b, a). |
| // Microoptimized to avoid retain/release traffic. |
| let p1 = Builtin.addressof(&a) |
| let p2 = Builtin.addressof(&b) |
| _debugPrecondition( |
| p1 != p2, |
| "swapping a location with itself is not supported") |
| |
| // Take from P1. |
| let tmp: T = Builtin.take(p1) |
| // Transfer P2 into P1. |
| Builtin.initialize(Builtin.take(p2) as T, p1) |
| // Initialize P2. |
| Builtin.initialize(tmp, p2) |
| } |