stdlib/public/core/Sort.swift.gyb

//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2016 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See http://swift.org/LICENSE.txt for license information
// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//

%{
def cmp(a, b, p):
  if p:
    return "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:

func _insertionSort<C>(
  _ elements: inout C,
  subRange range: Range<C.Index>
  ${", by areInIncreasingOrder: inout (C.Iterator.Element, C.Iterator.Element) -> Bool" if p else ""}
) where
  C : MutableCollection & BidirectionalCollection
  ${"" if p else ", C.Iterator.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.Iterator.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.Iterator.Element = elements[elements.index(before: i)]

        // if x doesn't belong before y, we've found its position
        if !${cmp("x", "predecessor", p)} {
          break
        }

        // 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)
    }
  }
}

func _partition<C>(
  _ elements: inout C,
  subRange range: Range<C.Index>
  ${", by areInIncreasingOrder: inout (C.Iterator.Element, C.Iterator.Element) -> Bool" if p else ""}
) -> C.Index
  where
  C : MutableCollection & RandomAccessCollection
  ${"" if p else ", C.Iterator.Element : Comparable"} {

  var lo = range.lowerBound
  var hi = range.upperBound

  if lo == hi {
    return lo
  }

  // The first element is the pivot.
  let pivot = elements[range.lowerBound]

  // Loop invariants:
  // * lo < hi
  // * elements[i] < pivot, for i in range.lowerBound+1..lo
  // * pivot <= elements[i] for i in hi..range.upperBound

Loop: while true {
  FindLo: repeat {
      elements.formIndex(after: &lo)
      while lo != hi {
        if !${cmp("elements[lo]", "pivot", p)} { break FindLo }
        elements.formIndex(after: &lo)
      }
      break Loop
    } while false

  FindHi: repeat {
      elements.formIndex(before: &hi)
      while hi != lo {
        if ${cmp("elements[hi]", "pivot", p)} { break FindHi }
        elements.formIndex(before: &hi)
      }
      break Loop
    } while false

    swap(&elements[lo], &elements[hi])
  }

  elements.formIndex(before: &lo)
  if lo != range.lowerBound {
    // swap the pivot into place
    swap(&elements[lo], &elements[range.lowerBound])
  }

  return lo
}

public // @testable
func _introSort<C>(
  _ elements: inout C,
  subRange range: Range<C.Index>
  ${", by areInIncreasingOrder: @escaping (C.Iterator.Element, C.Iterator.Element) -> Bool" if p else ""}
) where
  C : MutableCollection & RandomAccessCollection
  ${"" if p else ", C.Iterator.Element : Comparable"} {

%   if p:
  var areIncreasingVar = areInIncreasingOrder
%   end
  let count =
    elements.distance(from: range.lowerBound, to: range.upperBound).toIntMax()
  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 * _floorLog2(Int64(count))
  _introSortImpl(
    &elements,
    subRange: range,
    ${"by: &areIncreasingVar," if p else ""}
    depthLimit: depthLimit)
}

func _introSortImpl<C>(
  _ elements: inout C,
  subRange range: Range<C.Index>
  ${", by areInIncreasingOrder: inout (C.Iterator.Element, C.Iterator.Element) -> Bool" if p else ""},
  depthLimit: Int
) where
  C : MutableCollection & RandomAccessCollection
  ${"" if p else ", C.Iterator.Element : Comparable"} {

  // Insertion sort is better at handling smaller regions.
  if elements.distance(from: range.lowerBound, to: range.upperBound) < 20 {
    _insertionSort(
      &elements,
      subRange: range
      ${", by: &areInIncreasingOrder" if p else ""})
    return
  }
  if depthLimit == 0 {
    _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 = _partition(
    &elements,
    subRange: range
    ${", by: &areInIncreasingOrder" if p else ""})
  _introSortImpl(
    &elements,
    subRange: range.lowerBound..<partIdx,
    ${"by: &areInIncreasingOrder, " if p else ""}
    depthLimit: depthLimit &- 1)
  _introSortImpl(
    &elements,
    subRange: (elements.index(after: partIdx))..<range.upperBound,
    ${"by: &areInIncreasingOrder, " if p else ""}
    depthLimit: depthLimit &- 1)
}

func _siftDown<C>(
  _ elements: inout C,
  index: C.Index,
  subRange range: Range<C.Index>
  ${", by areInIncreasingOrder: inout (C.Iterator.Element, C.Iterator.Element) -> Bool" if p else ""}
) where
  C : MutableCollection & RandomAccessCollection
  ${"" if p else ", C.Iterator.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 {
    swap(&elements[index], &elements[largest])
    _siftDown(
      &elements,
      index: largest,
      subRange: range
      ${", by: &areInIncreasingOrder" if p else ""})
  }
}
func _heapify<C>(
  _ elements: inout C,
  subRange range: Range<C.Index>
  ${", by areInIncreasingOrder: inout (C.Iterator.Element, C.Iterator.Element) -> Bool" if p else ""}
) where
  C : MutableCollection & RandomAccessCollection
  ${"" if p else ", C.Iterator.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)
    _siftDown(
      &elements,
      index: node,
      subRange: range
      ${", by: &areInIncreasingOrder" if p else ""})
  }
}
func _heapSort<C>(
  _ elements: inout C,
  subRange range: Range<C.Index>
  ${", by areInIncreasingOrder: inout (C.Iterator.Element, C.Iterator.Element) -> Bool" if p else ""}
) where
  C : MutableCollection & RandomAccessCollection
  ${"" if p else ", C.Iterator.Element : Comparable"} {
  var hi = range.upperBound
  let lo = range.lowerBound
  _heapify(
    &elements,
    subRange: range
    ${", by: &areInIncreasingOrder" if p else ""})
  elements.formIndex(before: &hi)
  while hi != lo {
    swap(&elements[lo], &elements[hi])
    _siftDown(
      &elements,
      index: lo,
      subRange: lo..<hi
      ${", by: &areInIncreasingOrder" if p else ""})
    elements.formIndex(before: &hi)
  }
}

% end
// for p in preds

/// Exchange the values of `a` and `b`.
///
/// - Precondition: `a` and `b` do not alias each other.
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)
}