Sort.swift.gyb

// RUN: rm -f %t.swift %t.out

// RUN: %S/../../utils/gyb %s -o %t.swift
// RUN: %S/../../utils/line-directive %t.swift -- %target-build-swift %t.swift -o %t.out
// RUN: %S/../../utils/line-directive %t.swift -- %target-run %t.out
// REQUIRES: executable_test

import StdlibUnittest
import StdlibCollectionUnittest
import SwiftPrivate


// FIXME(prext): fold this test into Algorithm.swift.gyb.

var Algorithm = TestSuite("Algorithm")

// Check if one array is a correctly sorted version of another array.
// We can't simply sort both arrays and compare them, because it is needed to
// check correctness of sorting itself.
func expectSortedCollection(_ sortedAry: [Int], _ originalAry: [Int]) {
  expectEqual(sortedAry.count, originalAry.count)
  var sortedVals = [Int:Int]()
  var originalVals = [Int:Int]()
  // Keep track of what values we have in sortedAry.
  for e in sortedAry {
    if let v = sortedVals[e] {
      sortedVals[e] = v + 1
    } else {
      sortedVals[e] = 0
    }
  }
  // And do the same for originalAry.
  for e in originalAry {
    if let v = originalVals[e] {
      originalVals[e] = v + 1
    } else {
      originalVals[e] = 0
    }
  }
  // Now check if sets of elements are the same in both arrays.
  for (key, value) in sortedVals {
    expectNotEmpty(originalVals[key])
    expectEqual(originalVals[key]!, value)
  }

  // Check if values in sortedAry are actually sorted.
  for i in 1..<sortedAry.count {
    expectTrue(sortedAry[i - 1] <= sortedAry[i])
  }
}

func expectSortedCollection(
  _ sortedAry: [Int],
  _ originalAry: ContiguousArray<Int>
) {
  expectSortedCollection(sortedAry, Array(originalAry))
}

func expectSortedCollection(_ sortedAry: ArraySlice<Int>, _ originalAry: ArraySlice<Int>) {
  expectSortedCollection([Int](sortedAry), [Int](originalAry))
}

class OffsetCollection : MutableCollection, RandomAccessCollection {
  typealias Indices = CountableRange<Int>
  
  let offset: Int
  var data: [Int] = []
  let forward: Bool
  var startIndex: Int { return forward ? offset : offset - data.count }
  var endIndex: Int { return forward ? offset + data.count : offset }
  subscript (i: Int) -> Int {
    get { return data[i - startIndex] }
    set { data[i - startIndex] = newValue }
  }
  func toArray() -> [Int] {
    return data
  }
  var count: Int { return data.count }
  init(_ ary: [Int], offset: Int, forward: Bool) {
    data = ary
    self.offset = offset
    self.forward = forward
  }
  typealias Index = Int
  subscript(bounds: Range<Int>) -> MutableRandomAccessSlice<OffsetCollection> {
    get {
      return MutableRandomAccessSlice(base: self, bounds: bounds)
    }
    set {
      for i in CountableRange(bounds) {
        self[i] = newValue[i]
      }
    }
  }
}

// Generate two versions of tests: one for sort with explicitly passed
// predicate and the other using default comparison operator.
% withArrayTypeNames = ["Array", "ContiguousArray"]
% withPredicateValues = [True, False]
% for t in withArrayTypeNames:
// workaround for <rdar://problem/18900352> gyb miscompiles nested loops
%   for p in withPredicateValues:
// workaround for <rdar://problem/18900352> gyb miscompiles nested loops
%     comparePredicate = "<" if p else ""
%     commaComparePredicate = ", isOrderedBefore: <" if p else ""
%     name = "lessPredicate" if p else "noPredicate"

Algorithm.test("${t}/sorted/${name}") {
  let count = 1000
  var ary = ${t}(randArray(count))
  var sortedAry1 = [Int]()
  var sortedAry2 = ${t}<Int>()

  // Similar test for sorting with predicate
%       if comparePredicate:
  sortedAry1 = ary.sorted(isOrderedBefore: ${comparePredicate})
%       else:
  sortedAry1 = ary.sorted()
%       end
  expectSortedCollection(sortedAry1, ary)

  // Check that sorting works well on intervals
  let i1 = 400
  let i2 = 700
  sortedAry2 = ary
  _introSort(&sortedAry2, subRange: i1..<i2${commaComparePredicate})

  expectEqual(ary[0..<i1], sortedAry2[0..<i1])
  expectSortedCollection(sortedAry2[i1..<i2], ary[i1..<i2])
  expectEqual(ary[i2..<count], sortedAry2[i2..<count])
}
%   end
% end

Algorithm.test("sort/CollectionsWithUnusualIndices") {
  let count = 1000
  var ary = randArray(count)

  // Check if sorting routines work well on collections with startIndex != 0.
  var offsetAry = OffsetCollection(ary, offset: 500, forward: false)
  offsetAry.sort(${comparePredicate})
  expectSortedCollection(offsetAry.toArray(), ary)

  // Check if sorting routines work well on collections with endIndex = Int.max.
  // That could expose overflow errors in index computations.
  offsetAry = OffsetCollection(ary, offset: Int.max, forward: false)
  offsetAry.sort(${comparePredicate})
  expectSortedCollection(offsetAry.toArray(), ary)

  // Check if sorting routines work well on collections with
  // startIndex = Int.min.
  offsetAry = OffsetCollection(ary, offset: Int.min, forward: true)
  offsetAry.sort(${comparePredicate})
  expectSortedCollection(offsetAry.toArray(), ary)
}

Algorithm.test("partition/CrashOnSingleElement") {
  var a = DefaultedMutableRandomAccessCollection([10])
  expectEqual(a.startIndex, a.partition())
}

runAllTests()