| // RUN: %target-run-simple-swiftgyb |
| // 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 { |
| expectNotNil(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 = ", by: <" 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(by: ${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]) |
| let first = a.first! |
| expectEqual(a.startIndex, a.partition(by: {$0 >= first})) |
| } |
| |
| runAllTests() |