GCC Code Coverage Report

Directory: ./
File: tasks/karpich_i_bitwise_batcher/seq/src/ops_seq.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 87 88 98.9%
Functions: 10 10 100.0%
Branches: 66 94 70.2%
Line Branch Exec Source
1 #include "karpich_i_bitwise_batcher/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <random>
5 #include <utility>
6 #include <vector>
7
8 #include "karpich_i_bitwise_batcher/common/include/common.hpp"
9
10 namespace karpich_i_bitwise_batcher {
11
12 namespace {
13
14
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 80 times.
 320 void RadixSortPositive(std::vector<int> &arr) {
15 320 int n = static_cast<int>(arr.size());
16
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 80 times.
 320 if (n <= 1) {
17 80 return;
18 }
19
20 240 int max_val = *std::ranges::max_element(arr);
21
1/2
✓ Branch 0 taken 240 times.
✗ Branch 1 not taken.
 240 if (max_val == 0) {
22 return;
23 }
24
25 240 std::vector<int> buffer(n);
26
27
3/4
✓ Branch 0 taken 712 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 472 times.
✓ Branch 3 taken 240 times.
 712 for (int shift = 0; shift < 32 && (max_val >> shift) > 0; shift += 8) {
28
1/4
✓ Branch 1 taken 472 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 472 std::vector<int> count(256, 0);
29
2/2
✓ Branch 0 taken 39536 times.
✓ Branch 1 taken 472 times.
 40008 for (int i = 0; i < n; i++) {
30 39536 count[(arr[i] >> shift) & 0xFF]++;
31 }
32
2/2
✓ Branch 0 taken 120360 times.
✓ Branch 1 taken 472 times.
 120832 for (int i = 1; i < 256; i++) {
33 120360 count[i] += count[i - 1];
34 }
35
2/2
✓ Branch 0 taken 39536 times.
✓ Branch 1 taken 472 times.
 40008 for (int i = n - 1; i >= 0; i--) {
36 39536 buffer[--count[(arr[i] >> shift) & 0xFF]] = arr[i];
37 }
38
1/2
✓ Branch 1 taken 472 times.
✗ Branch 2 not taken.
 472 arr = buffer;
39 }
40 }
41
42
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 160 times.
 176 void RadixSort(std::vector<int> &arr) {
43 176 int n = static_cast<int>(arr.size());
44
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 160 times.
 176 if (n <= 1) {
45 16 return;
46 }
47
48 160 std::vector<int> negative;
49 160 std::vector<int> positive;
50
2/2
✓ Branch 0 taken 19840 times.
✓ Branch 1 taken 160 times.
 20000 for (int i = 0; i < n; i++) {
51
2/2
✓ Branch 0 taken 9680 times.
✓ Branch 1 taken 10160 times.
 19840 if (arr[i] < 0) {
52
1/4
✓ Branch 1 taken 9680 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 9680 negative.push_back(-arr[i]);
53 } else {
54 positive.push_back(arr[i]);
55 }
56 }
57
58
1/2
✓ Branch 1 taken 160 times.
✗ Branch 2 not taken.
 160 RadixSortPositive(positive);
59
1/2
✓ Branch 1 taken 160 times.
✗ Branch 2 not taken.
 160 RadixSortPositive(negative);
60
61 int idx = 0;
62
2/2
✓ Branch 0 taken 9680 times.
✓ Branch 1 taken 160 times.
 9840 for (int i = static_cast<int>(negative.size()) - 1; i >= 0; i--) {
63 9680 arr[idx++] = -negative[i];
64 }
65
2/2
✓ Branch 0 taken 10160 times.
✓ Branch 1 taken 160 times.
 10320 for (int x : positive) {
66 10160 arr[idx++] = x;
67 }
68 }
69
70 struct MergeTask {
71 int lo;
72 int hi;
73 int r;
74 };
75
76 88 std::vector<std::vector<std::pair<int, int>>> BuildMergeNetwork(int lo, int hi) {
77 88 std::vector<std::vector<std::pair<int, int>>> levels;
78
1/2
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
 88 std::vector<MergeTask> current = {{lo, hi, 1}};
79
80
2/2
✓ Branch 0 taken 424 times.
✓ Branch 1 taken 88 times.
 512 while (!current.empty()) {
81 424 std::vector<MergeTask> next;
82 424 std::vector<std::pair<int, int>> comps;
83
84
2/2
✓ Branch 0 taken 19768 times.
✓ Branch 1 taken 424 times.
 20192 for (const auto &[tlo, thi, tr] : current) {
85 19768 int step = tr * 2;
86
2/2
✓ Branch 0 taken 9840 times.
✓ Branch 1 taken 9928 times.
 19768 if (step < thi - tlo) {
87
1/2
✓ Branch 1 taken 9840 times.
✗ Branch 2 not taken.
 9840 next.push_back({tlo, thi, step});
88
1/2
✓ Branch 1 taken 9840 times.
✗ Branch 2 not taken.
 9840 next.push_back({tlo + tr, thi, step});
89
2/2
✓ Branch 0 taken 74544 times.
✓ Branch 1 taken 9840 times.
 84384 for (int i = tlo + tr; i + tr <= thi; i += step) {
90
1/2
✓ Branch 1 taken 74544 times.
✗ Branch 2 not taken.
 74544 comps.emplace_back(i, i + tr);
91 }
92
1/2
✓ Branch 0 taken 9928 times.
✗ Branch 1 not taken.
 9928 } else if (tlo + tr <= thi) {
93
1/4
✓ Branch 1 taken 9928 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 9928 comps.emplace_back(tlo, tlo + tr);
94 }
95 }
96
97 levels.push_back(std::move(comps));
98 current = std::move(next);
99 }
100
101 88 return levels;
102 ✗ }
103
104 88 void ApplyComparatorNetwork(std::vector<int> &arr, const std::vector<std::vector<std::pair<int, int>>> &levels) {
105
2/2
✓ Branch 0 taken 424 times.
✓ Branch 1 taken 88 times.
 512 for (int lvl = static_cast<int>(levels.size()) - 1; lvl >= 0; lvl--) {
106
2/2
✓ Branch 0 taken 84472 times.
✓ Branch 1 taken 424 times.
 84896 for (const auto &[a, b] : levels[lvl]) {
107
2/2
✓ Branch 0 taken 42928 times.
✓ Branch 1 taken 41544 times.
 84472 if (arr[a] > arr[b]) {
108 std::swap(arr[a], arr[b]);
109 }
110 }
111 }
112 88 }
113
114 88 void BatcherMerge(std::vector<int> &arr, int lo, int hi) {
115 88 auto levels = BuildMergeNetwork(lo, hi);
116 88 ApplyComparatorNetwork(arr, levels);
117 88 }
118
119 } // namespace
120
121 96 KarpichIBitwiseBatcherSEQ::KarpichIBitwiseBatcherSEQ(const InType &in) {
122 SetTypeOfTask(GetStaticTypeOfTask());
123 96 GetInput() = in;
124 GetOutput() = 0;
125 96 }
126
127 96 bool KarpichIBitwiseBatcherSEQ::ValidationImpl() {
128 96 return GetInput() > 0;
129 }
130
131 96 bool KarpichIBitwiseBatcherSEQ::PreProcessingImpl() {
132 96 int n = GetInput();
133 96 data_.resize(n);
134 96 std::mt19937 gen(static_cast<unsigned int>(n));
135 std::uniform_int_distribution<int> dist(-1000, 1000);
136
2/2
✓ Branch 0 taken 19408 times.
✓ Branch 1 taken 96 times.
 19504 for (int i = 0; i < n; i++) {
137 19408 data_[i] = dist(gen);
138 }
139 96 return true;
140 }
141
142
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 8 times.
 96 bool KarpichIBitwiseBatcherSEQ::RunImpl() {
143 96 int n = static_cast<int>(data_.size());
144
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 8 times.
 96 if (n <= 1) {
145 return true;
146 }
147
148 int padded = 1;
149
2/2
✓ Branch 0 taken 424 times.
✓ Branch 1 taken 88 times.
 512 while (padded < n) {
150 424 padded *= 2;
151 }
152
153 88 int max_elem = *std::ranges::max_element(data_);
154 88 data_.resize(padded, max_elem);
155
156 88 int half = padded / 2;
157
1/2
✓ Branch 2 taken 88 times.
✗ Branch 3 not taken.
 88 std::vector<int> left(data_.begin(), data_.begin() + half);
158
1/4
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 88 std::vector<int> right(data_.begin() + half, data_.end());
159
160
1/2
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
 88 RadixSort(left);
161
1/2
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
 88 RadixSort(right);
162
163 std::ranges::copy(left, data_.begin());
164 std::ranges::copy(right, data_.begin() + half);
165
166
1/2
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
 88 BatcherMerge(data_, 0, padded - 1);
167
168
1/2
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
 88 data_.resize(n);
169 return true;
170 }
171
172 96 bool KarpichIBitwiseBatcherSEQ::PostProcessingImpl() {
173 19408 for (int i = 1; std::cmp_less(i, data_.size()); i++) {
174
1/2
✓ Branch 0 taken 19312 times.
✗ Branch 1 not taken.
 19312 if (data_[i] < data_[i - 1]) {
175 return false;
176 }
177 }
178 96 GetOutput() = GetInput();
179 96 return true;
180 }
181
182 } // namespace karpich_i_bitwise_batcher
183