GCC Code Coverage Report

Directory: ./
File: tasks/balchunayte_z_shell_batcher/seq/src/ops_seq.cpp
Date: 2026-01-27 01:59:34
Exec Total Coverage
Lines: 85 85 100.0%
Functions: 10 10 100.0%
Branches: 79 102 77.5%
Line Branch Exec Source
1 #include "balchunayte_z_shell_batcher/seq/include/ops_seq.hpp"
2
3 #include <cstddef>
4 #include <utility>
5 #include <vector>
6
7 #include "balchunayte_z_shell_batcher/common/include/common.hpp"
8
9 namespace balchunayte_z_shell_batcher {
10
11 namespace {
12
13 208 void ShellSort(std::vector<int> *vec) {
14 auto &a = *vec;
15 const std::size_t n = a.size();
16
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 208 times.
 256 for (std::size_t gap = n / 2; gap > 0; gap /= 2) {
17
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 48 times.
 96 for (std::size_t i = gap; i < n; ++i) {
18 48 const int tmp = a[i];
19 std::size_t j = i;
20
4/4
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 32 times.
✓ Branch 2 taken 32 times.
✓ Branch 3 taken 16 times.
 80 while (j >= gap && a[j - gap] > tmp) {
21 32 a[j] = a[j - gap];
22 j -= gap;
23 }
24 48 a[j] = tmp;
25 }
26 }
27 208 }
28
29 struct Elem {
30 int val{};
31 bool pad{false};
32
33 752 Elem(int value, bool padding) : val(value), pad(padding) {}
34 };
35
36 inline bool Greater(const Elem &lhs, const Elem &rhs) {
37
2/2
✓ Branch 0 taken 400 times.
✓ Branch 1 taken 1416 times.
 1816 if (lhs.pad != rhs.pad) {
38
3/4
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 160 times.
✓ Branch 2 taken 240 times.
✗ Branch 3 not taken.
 400 return lhs.pad && !rhs.pad;
39 }
40 1416 return lhs.val > rhs.val;
41 }
42
43
2/2
✓ Branch 0 taken 400 times.
✓ Branch 1 taken 1416 times.
 1816 inline void CompareExchange(std::vector<Elem> *arr, std::size_t i, std::size_t j) {
44
2/2
✓ Branch 0 taken 496 times.
✓ Branch 1 taken 920 times.
 1416 if (Greater((*arr)[i], (*arr)[j])) {
45 std::swap((*arr)[i], (*arr)[j]);
46 }
47 1816 }
48
49 std::size_t NextPow2(std::size_t x) {
50 std::size_t p = 1;
51
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 168 times.
 312 while (p < x) {
52 144 p <<= 1U;
53 }
54 return p;
55 }
56
57 512 void OddEvenMergeStep(std::vector<Elem> *arr, std::size_t k, std::size_t j) {
58 const std::size_t n = arr->size();
59
2/2
✓ Branch 0 taken 3632 times.
✓ Branch 1 taken 512 times.
 4144 for (std::size_t i = 0; i < n; ++i) {
60 3632 const std::size_t ixj = i ^ j;
61
2/2
✓ Branch 0 taken 1816 times.
✓ Branch 1 taken 1816 times.
 3632 if (ixj > i) {
62
2/2
✓ Branch 0 taken 1376 times.
✓ Branch 1 taken 440 times.
 1816 if ((i & k) == 0) {
63 1376 CompareExchange(arr, i, ixj);
64 } else {
65 440 CompareExchange(arr, ixj, i);
66 }
67 }
68 }
69 512 }
70
71
1/2
✓ Branch 0 taken 168 times.
✗ Branch 1 not taken.
 168 void OddEvenMergeNetwork(std::vector<Elem> *arr) {
72 const std::size_t n = arr->size();
73
1/2
✓ Branch 0 taken 168 times.
✗ Branch 1 not taken.
 168 if (n <= 1) {
74 return;
75 }
76
77
2/2
✓ Branch 0 taken 312 times.
✓ Branch 1 taken 168 times.
 480 for (std::size_t k = 2; k <= n; k <<= 1U) {
78
2/2
✓ Branch 0 taken 512 times.
✓ Branch 1 taken 312 times.
 824 for (std::size_t j = (k >> 1U); j > 0; j >>= 1U) {
79 512 OddEvenMergeStep(arr, k, j);
80 }
81 }
82 }
83
84
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 48 times.
 168 std::vector<int> BatcherOddEvenMerge(const std::vector<int> &a, const std::vector<int> &b) {
85 168 const std::size_t need = a.size() + b.size();
86
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 48 times.
 168 const std::size_t half = NextPow2((a.size() > b.size()) ? a.size() : b.size());
87
88 168 std::vector<Elem> buffer;
89
1/2
✓ Branch 1 taken 168 times.
✗ Branch 2 not taken.
 168 buffer.reserve(2 * half);
90
91
2/2
✓ Branch 0 taken 376 times.
✓ Branch 1 taken 168 times.
 544 for (std::size_t i = 0; i < half; ++i) {
92
2/2
✓ Branch 0 taken 344 times.
✓ Branch 1 taken 32 times.
 376 if (i < a.size()) {
93
1/2
✓ Branch 1 taken 344 times.
✗ Branch 2 not taken.
 344 buffer.emplace_back(a[i], false);
94 } else {
95
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 buffer.emplace_back(0, true);
96 }
97 }
98
2/2
✓ Branch 0 taken 376 times.
✓ Branch 1 taken 168 times.
 544 for (std::size_t i = 0; i < half; ++i) {
99
2/2
✓ Branch 0 taken 288 times.
✓ Branch 1 taken 88 times.
 376 if (i < b.size()) {
100
1/2
✓ Branch 1 taken 288 times.
✗ Branch 2 not taken.
 288 buffer.emplace_back(b[i], false);
101 } else {
102
1/4
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 88 buffer.emplace_back(0, true);
103 }
104 }
105
106 168 OddEvenMergeNetwork(&buffer);
107
108 168 std::vector<int> out;
109
1/2
✓ Branch 1 taken 168 times.
✗ Branch 2 not taken.
 168 out.reserve(need);
110
1/2
✓ Branch 0 taken 632 times.
✗ Branch 1 not taken.
 632 for (const auto &elem : buffer) {
111
1/2
✓ Branch 0 taken 632 times.
✗ Branch 1 not taken.
 632 if (!elem.pad) {
112
1/2
✓ Branch 0 taken 632 times.
✗ Branch 1 not taken.
 632 out.push_back(elem.val);
113 }
114
2/2
✓ Branch 0 taken 464 times.
✓ Branch 1 taken 168 times.
 632 if (out.size() == need) {
115 break;
116 }
117 }
118 168 return out;
119 }
120
121 } // namespace
122
123
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 BalchunayteZShellBatcherSEQ::BalchunayteZShellBatcherSEQ(const InType &in) {
124 SetTypeOfTask(GetStaticTypeOfTask());
125
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 GetInput() = in;
126 GetOutput() = {};
127 56 }
128
129 56 bool BalchunayteZShellBatcherSEQ::ValidationImpl() {
130 56 return true;
131 }
132
133 56 bool BalchunayteZShellBatcherSEQ::PreProcessingImpl() {
134 56 data_ = GetInput();
135 GetOutput().clear();
136 56 return true;
137 }
138
139
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 16 times.
 56 bool BalchunayteZShellBatcherSEQ::RunImpl() {
140 const std::size_t n = data_.size();
141
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 16 times.
 56 if (n <= 1) {
142 return true;
143 }
144
145 std::size_t blocks = 1;
146
3/4
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 40 times.
✓ Branch 2 taken 88 times.
✗ Branch 3 not taken.
 128 while ((blocks << 1U) <= n && (blocks << 1U) <= 16) {
147 blocks <<= 1U;
148 }
149
150 40 std::vector<std::vector<int>> parts;
151
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 parts.reserve(blocks);
152
153 40 const std::size_t base = n / blocks;
154 40 const std::size_t rem = n % blocks;
155
156 std::size_t pos = 0;
157
2/2
✓ Branch 0 taken 208 times.
✓ Branch 1 taken 40 times.
 248 for (std::size_t block_index = 0; block_index < blocks; ++block_index) {
158
2/2
✓ Branch 0 taken 160 times.
✓ Branch 1 taken 48 times.
 208 const std::size_t sz = base + (block_index < rem ? 1 : 0);
159 208 std::vector<int> chunk;
160
1/2
✓ Branch 1 taken 208 times.
✗ Branch 2 not taken.
 208 chunk.reserve(sz);
161
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 208 times.
 464 for (std::size_t i = 0; i < sz; ++i) {
162
1/2
✓ Branch 0 taken 256 times.
✗ Branch 1 not taken.
 256 chunk.push_back(data_[pos++]);
163 }
164 208 ShellSort(&chunk);
165 parts.push_back(std::move(chunk));
166 }
167
168
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 40 times.
 128 while (parts.size() > 1) {
169
1/2
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
 88 std::vector<std::vector<int>> next;
170
1/2
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
 88 next.reserve(parts.size() / 2);
171
2/2
✓ Branch 0 taken 168 times.
✓ Branch 1 taken 88 times.
 256 for (std::size_t i = 0; i < parts.size(); i += 2) {
172
1/2
✓ Branch 1 taken 168 times.
✗ Branch 2 not taken.
 336 next.push_back(BatcherOddEvenMerge(parts[i], parts[i + 1]));
173 }
174 88 parts = std::move(next);
175 88 }
176
177 40 data_ = std::move(parts[0]);
178 return true;
179 40 }
180
181 56 bool BalchunayteZShellBatcherSEQ::PostProcessingImpl() {
182 56 GetOutput() = data_;
183 56 return true;
184 }
185
186 } // namespace balchunayte_z_shell_batcher
187