GCC Code Coverage Report

Directory: ./
File: tasks/chernov_t_radix_sort/seq/src/ops_seq.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 49 50 98.0%
Functions: 7 7 100.0%
Branches: 39 56 69.6%
Line Branch Exec Source
1 #include "chernov_t_radix_sort/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <cstdint>
6 #include <vector>
7
8 #include "chernov_t_radix_sort/common/include/common.hpp"
9
10 namespace chernov_t_radix_sort {
11
12
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 ChernovTRadixSortSEQ::ChernovTRadixSortSEQ(const InType &in) {
13 SetTypeOfTask(GetStaticTypeOfTask());
14
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 GetInput() = in;
15 GetOutput() = {};
16 64 }
17
18 64 bool ChernovTRadixSortSEQ::ValidationImpl() {
19 64 return true;
20 }
21
22 64 bool ChernovTRadixSortSEQ::PreProcessingImpl() {
23 64 GetOutput() = GetInput();
24 64 return true;
25 }
26
27 constexpr int kBitsPerDigit = 8;
28 constexpr int kRadix = 1 << kBitsPerDigit;
29 constexpr uint32_t kSignMask = 0x80000000U;
30
31
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 96 times.
 96 void ChernovTRadixSortSEQ::RadixSortLSD(std::vector<int> &data) {
32
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 96 times.
 96 if (data.empty()) {
33 ✗ return;
34 }
35
36 96 std::vector<uint32_t> temp(data.size());
37
2/2
✓ Branch 0 taken 328 times.
✓ Branch 1 taken 96 times.
 424 for (size_t i = 0; i < data.size(); ++i) {
38 328 temp[i] = static_cast<uint32_t>(data[i]) ^ kSignMask;
39 }
40
41
1/4
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 96 std::vector<uint32_t> buffer(temp.size());
42
43
2/2
✓ Branch 0 taken 384 times.
✓ Branch 1 taken 96 times.
 480 for (int byte_index = 0; byte_index < 4; ++byte_index) {
44
1/4
✓ Branch 1 taken 384 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 384 std::vector<int> count(kRadix, 0);
45
46
2/2
✓ Branch 0 taken 1312 times.
✓ Branch 1 taken 384 times.
 1696 for (uint32_t val : temp) {
47 1312 int digit = static_cast<int>((val >> (byte_index * kBitsPerDigit)) & 0xFFU);
48 1312 ++count[static_cast<size_t>(digit)];
49 }
50
51
2/2
✓ Branch 0 taken 97920 times.
✓ Branch 1 taken 384 times.
 98304 for (int i = 1; i < kRadix; ++i) {
52 97920 count[static_cast<size_t>(i)] += count[static_cast<size_t>(i - 1)];
53 }
54
55
2/2
✓ Branch 0 taken 1312 times.
✓ Branch 1 taken 384 times.
 1696 for (int i = static_cast<int>(temp.size()) - 1; i >= 0; --i) {
56 1312 uint32_t val = temp[i];
57 1312 int digit = static_cast<int>((val >> (byte_index * kBitsPerDigit)) & 0xFFU);
58 1312 int pos = --count[static_cast<size_t>(digit)];
59 1312 buffer[static_cast<size_t>(pos)] = val;
60 }
61
62 temp.swap(buffer);
63 }
64
65
2/2
✓ Branch 0 taken 328 times.
✓ Branch 1 taken 96 times.
 424 for (size_t i = 0; i < data.size(); ++i) {
66 328 data[i] = static_cast<int>(temp[i] ^ kSignMask);
67 }
68 }
69
70 48 void ChernovTRadixSortSEQ::SimpleMerge(const std::vector<int> &left, const std::vector<int> &right,
71 std::vector<int> &result) {
72 48 result.resize(left.size() + right.size());
73
74 size_t idx_left = 0;
75 size_t idx_right = 0;
76 size_t idx_result = 0;
77
78
4/4
✓ Branch 0 taken 208 times.
✓ Branch 1 taken 32 times.
✓ Branch 2 taken 16 times.
✓ Branch 3 taken 192 times.
 240 while (idx_left < left.size() && idx_right < right.size()) {
79
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 104 times.
 192 if (left[idx_left] <= right[idx_right]) {
80 88 result[idx_result++] = left[idx_left++];
81 } else {
82 104 result[idx_result++] = right[idx_right++];
83 }
84 }
85
86
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 48 times.
 104 while (idx_left < left.size()) {
87 56 result[idx_result++] = left[idx_left++];
88 }
89
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 48 times.
 128 while (idx_right < right.size()) {
90 80 result[idx_result++] = right[idx_right++];
91 }
92 48 }
93
94
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 16 times.
 64 bool ChernovTRadixSortSEQ::RunImpl() {
95 auto &data = GetOutput();
96
97
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 16 times.
 64 if (data.size() <= 1) {
98 return true;
99 }
100
101 48 size_t middle_index = data.size() / 2;
102
1/2
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 std::vector<int> left_part(data.begin(), data.begin() + static_cast<std::ptrdiff_t>(middle_index));
103
1/4
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 48 std::vector<int> right_part(data.begin() + static_cast<std::ptrdiff_t>(middle_index), data.end());
104
105
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 RadixSortLSD(left_part);
106
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 RadixSortLSD(right_part);
107
108
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 SimpleMerge(left_part, right_part, data);
109
110 return true;
111 }
112
113
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 8 times.
 64 bool ChernovTRadixSortSEQ::PostProcessingImpl() {
114 64 return std::is_sorted(GetOutput().begin(), GetOutput().end());
115 }
116
117 } // namespace chernov_t_radix_sort
118