GCC Code Coverage Report

Directory: ./
File: tasks/zenin_a_radix_sort_double_batcher_merge_seq/seq/src/ops_seq.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 68 75 90.7%
Functions: 8 11 72.7%
Branches: 54 82 65.9%
Line Branch Exec Source
1 #include "zenin_a_radix_sort_double_batcher_merge_seq/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <cstdint>
6 #include <cstring>
7 #include <limits>
8 #include <vector>
9
10 // #include "util/include/util.hpp"
11 #include "zenin_a_radix_sort_double_batcher_merge_seq/common/include/common.hpp"
12
13 namespace zenin_a_radix_sort_double_batcher_merge_seq {
14
15
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 ZeninARadixSortDoubleBatcherMergeSeqseq::ZeninARadixSortDoubleBatcherMergeSeqseq(const InType &in) {
16 SetTypeOfTask(GetStaticTypeOfTask());
17
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 GetInput() = in;
18 GetOutput() = {};
19 96 }
20
21 96 bool ZeninARadixSortDoubleBatcherMergeSeqseq::ValidationImpl() {
22 96 return true;
23 }
24
25 96 bool ZeninARadixSortDoubleBatcherMergeSeqseq::PreProcessingImpl() {
26 96 return true;
27 }
28
29 ✗ void ZeninARadixSortDoubleBatcherMergeSeqseq::BlocksComparing(std::vector<double> &arr, size_t i, size_t step) {
30
4/6
✓ Branch 0 taken 272 times.
✓ Branch 1 taken 80 times.
✓ Branch 2 taken 320 times.
✓ Branch 3 taken 256 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 928 for (size_t k = 0; k < step; ++k) {
31
4/6
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 240 times.
✓ Branch 2 taken 120 times.
✓ Branch 3 taken 200 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 592 if (arr[i + k] > arr[i + k + step]) {
32 std::swap(arr[i + k], arr[i + k + step]);
33 }
34 }
35 ✗ }
36
37 80 void ZeninARadixSortDoubleBatcherMergeSeqseq::BatcherOddEvenMerge(std::vector<double> &arr, size_t n) {
38
1/2
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
 80 if (n <= 1) {
39 return;
40 }
41
42 80 size_t step = n / 2;
43 BlocksComparing(arr, 0, step);
44
45 80 step /= 2;
46
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 80 times.
 208 for (; step > 0; step /= 2) {
47
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 128 times.
 384 for (size_t i = step; i < n - step; i += step * 2) {
48 BlocksComparing(arr, i, step);
49 }
50 }
51 }
52
53
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 80 times.
 96 void ZeninARadixSortDoubleBatcherMergeSeqseq::BatcherMergeSort(std::vector<double> &array) {
54 96 int n = static_cast<int>(array.size());
55
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 80 times.
 96 if (n <= 1) {
56 16 return;
57 }
58
59 int padded_n = 1;
60
2/2
✓ Branch 0 taken 208 times.
✓ Branch 1 taken 80 times.
 288 while (padded_n < n) {
61 208 padded_n <<= 1;
62 }
63 80 array.resize(padded_n, std::numeric_limits<double>::max());
64 80 int mid = padded_n / 2;
65
66
1/2
✓ Branch 2 taken 80 times.
✗ Branch 3 not taken.
 80 std::vector<double> left(array.begin(), array.begin() + mid);
67
1/4
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 80 std::vector<double> right(array.begin() + mid, array.end());
68
69
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 LSDRadixSort(left);
70
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 LSDRadixSort(right);
71
72 std::ranges::copy(left.begin(), left.end(), array.begin());
73 std::ranges::copy(right.begin(), right.end(), array.begin() + mid);
74
75 80 BatcherOddEvenMerge(array, static_cast<size_t>(padded_n));
76
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 array.resize(n);
77 }
78
79 ✗ uint64_t ZeninARadixSortDoubleBatcherMergeSeqseq::PackDouble(double v) noexcept {
80 uint64_t bits = 0ULL;
81 std::memcpy(&bits, &v, sizeof(bits));
82
2/4
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 432 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 512 if ((bits & (1ULL << 63)) != 0ULL) {
83 80 bits = ~bits;
84 } else {
85 432 bits ^= (1ULL << 63);
86 }
87 ✗ return bits;
88 }
89
90 ✗ double ZeninARadixSortDoubleBatcherMergeSeqseq::UnpackDouble(uint64_t k) noexcept {
91 ✗ if ((k & (1ULL << 63)) != 0ULL) {
92 432 k ^= (1ULL << 63);
93 } else {
94 80 k = ~k;
95 }
96 double v = 0.0;
97 std::memcpy(&v, &k, sizeof(v));
98 ✗ return v;
99 }
100
101
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 128 times.
 160 void ZeninARadixSortDoubleBatcherMergeSeqseq::LSDRadixSort(std::vector<double> &array) {
102 const std::size_t n = array.size();
103
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 128 times.
 160 if (n <= 1U) {
104 32 return;
105 }
106
107 constexpr int kBits = 8;
108 constexpr int kBuckets = 1 << kBits;
109 constexpr int kPasses = static_cast<int>((sizeof(uint64_t) * 8) / kBits);
110
111 128 std::vector<uint64_t> keys;
112
1/2
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
 128 keys.resize(n);
113
2/2
✓ Branch 0 taken 512 times.
✓ Branch 1 taken 128 times.
 640 for (std::size_t i = 0; i < n; ++i) {
114
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 432 times.
 1024 keys[i] = PackDouble(array[i]);
115 }
116
117 128 std::vector<uint64_t> tmp_keys;
118
1/2
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
 128 tmp_keys.resize(n);
119 128 std::vector<double> tmp_vals;
120
1/2
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
 128 tmp_vals.resize(n);
121
122
2/2
✓ Branch 0 taken 1024 times.
✓ Branch 1 taken 128 times.
 1152 for (int pass = 0; pass < kPasses; ++pass) {
123 1024 int shift = pass * kBits;
124 1024 std::vector<std::size_t> cnt;
125
1/4
✓ Branch 1 taken 1024 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 1024 cnt.assign(kBuckets + 1, 0U);
126
127
2/2
✓ Branch 0 taken 4096 times.
✓ Branch 1 taken 1024 times.
 5120 for (std::size_t i = 0; i < n; ++i) {
128 4096 auto d = static_cast<std::size_t>((keys[i] >> shift) & (kBuckets - 1));
129 4096 ++cnt[d + 1];
130 }
131
2/2
✓ Branch 0 taken 262144 times.
✓ Branch 1 taken 1024 times.
 263168 for (int i = 0; i < kBuckets; ++i) {
132 262144 cnt[i + 1] += cnt[i];
133 }
134
135
2/2
✓ Branch 0 taken 4096 times.
✓ Branch 1 taken 1024 times.
 5120 for (std::size_t i = 0; i < n; ++i) {
136 4096 auto d = static_cast<std::size_t>((keys[i] >> shift) & (kBuckets - 1));
137 4096 std::size_t pos = cnt[d]++;
138 4096 tmp_keys[pos] = keys[i];
139 4096 tmp_vals[pos] = array[i];
140 }
141
142 keys.swap(tmp_keys);
143 array.swap(tmp_vals);
144 }
145
146
2/2
✓ Branch 0 taken 512 times.
✓ Branch 1 taken 128 times.
 640 for (std::size_t i = 0; i < n; ++i) {
147
2/2
✓ Branch 0 taken 432 times.
✓ Branch 1 taken 80 times.
 1024 array[i] = UnpackDouble(keys[i]);
148 }
149 }
150
151 96 bool ZeninARadixSortDoubleBatcherMergeSeqseq::RunImpl() {
152 96 std::vector<double> data = GetInput();
153
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 BatcherMergeSort(data);
154
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 GetOutput() = data;
155 96 return true;
156 }
157
158 96 bool ZeninARadixSortDoubleBatcherMergeSeqseq::PostProcessingImpl() {
159 96 return true;
160 }
161
162 } // namespace zenin_a_radix_sort_double_batcher_merge_seq
163