Debian Codegraph @

sort/+test.ha

raw
1 // SPDX-License-Identifier: MPL-2.0
2 // (c) Hare authors <https://harelang.org>
3
4 use math::random;
5 use sort::cmp;
6 use types;
7
8 @test fn lbisect() void = {
9 const nums = [1, 3, 4, 4, 5, 7, 9, 11, 11, 11];
10 for (let i = 0z; i < len(nums); i += 1) {
11 if (i != 0 && nums[i - 1] == nums[i]) continue;
12 const key = nums[i];
13 assert(lbisect(nums, size(int), &key, &cmp::ints) == i);
14 };
15 const n = 0;
16 assert(lbisect(nums, size(int), &n, &cmp::ints) == 0);
17 const n = 6;
18 assert(lbisect(nums, size(int), &n, &cmp::ints) == 5);
19 const n = 8;
20 assert(lbisect(nums, size(int), &n, &cmp::ints) == 6);
21 const n = 12;
22 assert(lbisect(nums, size(int), &n, &cmp::ints) == len(nums));
23 };
24
25 @test fn rbisect() void = {
26 const nums = [1, 3, 4, 4, 5, 7, 9, 11, 11, 11];
27 for (let i = 0z; i < len(nums); i += 1) {
28 if (i != len(nums) - 1 && nums[i + 1] == nums[i]) continue;
29 const key = nums[i];
30 assert(rbisect(nums, size(int), &key, &cmp::ints) == i + 1);
31 };
32 const n = 0;
33 assert(rbisect(nums, size(int), &n, &cmp::ints) == 0);
34 const n = 6;
35 assert(rbisect(nums, size(int), &n, &cmp::ints) == 5);
36 const n = 8;
37 assert(rbisect(nums, size(int), &n, &cmp::ints) == 6);
38 const n = 12;
39 assert(rbisect(nums, size(int), &n, &cmp::ints) == len(nums));
40 };
41
42 @test fn search() void = {
43 const nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
44 for (let i = 0z; i < len(nums); i += 1) {
45 const key = nums[i];
46 const p = search(nums, size(int), &key, &cmp::ints) as size;
47 assert(p == i);
48 };
49 const key = 1337;
50 assert(search(nums, size(int), &key, &cmp::ints) is void);
51 };
52
53 @test fn sort() void = {
54 let nums = [
55 1, 6, 10, 7, 8, 10, 10, 3, 7, 5, 5, 8, 1, 1, 1, 9, 2, 3, 1, 4,
56 2, 1, 5, 3, 2, 5, 10, 1, 7, 6, 8, 10, 6, 5, 7, 4, 3, 9, 9, 4, 7,
57 10, 3, 4, 4, 8, 5, 6, 2, 1, 6, 2, 2, 2, 10, 8, 3, 4, 5, 6, 6, 2,
58 5, 2, 3, 7, 10, 7, 7, 5, 5, 2, 3, 4, 5, 3, 6, 2, 3, 6, 8, 8, 9,
59 7, 10, 4, 10, 3, 2, 7, 10, 8, 8, 2, 2, 5, 3, 7, 4, 1,
60 ];
61 sort(nums, size(int), &cmp::ints)!;
62 for (let i = 1z; i < len(nums); i += 1) {
63 assert(nums[i] >= nums[i - 1]);
64 };
65 };
66
67 @test fn big_equal() void = {
68 let nums = alloc([42...], 1000000)!;
69 defer free(nums);
70 sort(nums, size(int), &cmp::ints)!;
71 for (let i = 0z; i < len(nums); i += 1) {
72 assert(nums[i] == 42);
73 };
74 };
75
76 @test fn big_random() void = {
77 let nums = alloc([0...], 100000)!;
78 defer free(nums);
79
80 let rand = random::init(0x424242);
81 for (let i = 0z; i < len(nums); i += 1) {
82 nums[i] = random::next(&rand): int;
83 };
84
85 sort(nums, size(int), &cmp::ints)!;
86 for (let i = 1z; i < len(nums); i += 1) {
87 assert(nums[i] >= nums[i - 1]);
88 };
89 };
90
91 @test fn sorted() void = {
92 let nums = [1, 3, 2];
93
94 assert(!sorted(nums, size(int), &cmp::ints));
95
96 sort(nums, size(int), &cmp::ints)!;
97 assert(sorted(nums, size(int), &cmp::ints));
98 assert(sorted(nums[..0], size(int), &cmp::ints));
99 };
100
101 @test fn cmp::ints() void = {
102 assert(cmp::ints(&5, &0) == 1);
103 assert(cmp::ints(&0, &5) == -1);
104 assert(cmp::ints(&0, &0) == 0);
105 assert(cmp::ints(&0, &types::INT_MIN) == 1);
106 assert(cmp::ints(&types::INT_MIN, &0) == -1);
107 };
108
109 @test fn shuffle() void = {
110 let rand = random::init(0x424242);
111 let cases: [_][]int = [
112 [1, 2, 3, 4, 5],
113 [1, 2],
114 [1],
115 [],
116 ];
117 for (let testcase .. cases) {
118 assert(sorted(testcase, size(int), &cmp::ints));
119 shuffle(testcase, size(int), &rand);
120 if (len(testcase) <= 1) {
121 continue;
122 };
123
124 assert(!sorted(testcase, size(int), &cmp::ints));
125 sort(testcase, size(int), &cmp::ints)!;
126 assert(sorted(testcase, size(int), &cmp::ints));
127 };
128
129 // TODO: check for uniformness
130 let same = 0;
131 for (let i = 0; i < 5000; i += 1) {
132 let data = [0, 1, 2, 3, 4];
133 shuffle(data, size(int), &rand);
134 if (sorted(data, size(int), &cmp::ints)) {
135 same += 1;
136 };
137 };
138 assert(same >= 36 && same <= 46); // 5000 / 120 ~= 41.6
139 };