1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
|
// 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))
}
func expectSortedCollection<C: Collection>(_ a: C,
by areInIncreasingOrder: (C.Element, C.Element) -> Bool
) {
expectFalse(zip(a.dropFirst(), a).contains(where: areInIncreasingOrder))
}
class OffsetCollection : MutableCollection, RandomAccessCollection {
typealias Indices = Range<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>) -> Slice<OffsetCollection> {
get {
return Slice(base: self, bounds: bounds)
}
set {
for i in 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
let ary = ${t}((0 ..< count).map { _ in Int.random(in: .min ... .max) })
// Similar test for sorting with predicate
% if comparePredicate:
let sortedAry1 = ary.sorted(by: ${comparePredicate})
% else:
let sortedAry1 = ary.sorted()
% end
expectSortedCollection(sortedAry1, ary)
// Check that sorting works well on intervals
let i1 = 400
let i2 = 700
var sortedAry2 = ary
sortedAry2[i1..<i2].sort(by: <)
expectEqual(ary[0..<i1], sortedAry2[0..<i1])
expectSortedCollection(sortedAry2[i1..<i2], ary[i1..<i2])
expectEqual(ary[i2..<count], sortedAry2[i2..<count])
}
% end
Algorithm.test("${t}/sorted/stable") {
let count = 1000
// Using a small range in the random array so that we have repeated elements
let ary = (0 ..< count).map { _ in Int.random(in: 1...20) }
// Decorate with offset, but sort by value
var input = ${t}(ary.enumerated())
input.sort(by: { $0.element < $1.element })
// Offsets should still be ordered for equal values
expectSortedCollection(input) {
if $0.element == $1.element {
return $0.offset < $1.offset
}
return $0.element < $1.element
}
}
% end
Algorithm.test("sort/CollectionsWithUnusualIndices") {
let count = 1000
let ary = (0 ..< count).map { _ in Int.random(in: .min ... .max) }
// Check if sorting routines work well on collections with startIndex != 0.
var offsetAry = OffsetCollection(ary, offset: 500, forward: false)
offsetAry.sort()
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()
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()
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()
|
