GCC Code Coverage Report

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