GCC Code Coverage Report

Directory: ./
File: tasks/leonova_a_radix_merge_sort/seq/src/ops_seq.cpp
Date: 2026-01-10 02:40:41
Exec Total Coverage
Lines: 76 83 91.6%
Functions: 8 9 88.9%
Branches: 57 104 54.8%
Line Branch Exec Source
1 #include "leonova_a_radix_merge_sort/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <cstdint>
6 #include <cstring>
7 #include <vector>
8
9 #include "leonova_a_radix_merge_sort/common/include/common.hpp"
10
11 namespace leonova_a_radix_merge_sort {
12
13
1/2
✓ Branch 1 taken 160 times.
✗ Branch 2 not taken.
 160 LeonovaARadixMergeSortSEQ::LeonovaARadixMergeSortSEQ(const InType &in) {
14 SetTypeOfTask(GetStaticTypeOfTask());
15
1/2
✓ Branch 1 taken 160 times.
✗ Branch 2 not taken.
 160 GetInput() = in;
16
1/2
✓ Branch 1 taken 160 times.
✗ Branch 2 not taken.
 160 GetOutput() = std::vector<double>(GetInput().size());
17 160 }
18
19 320 bool LeonovaARadixMergeSortSEQ::ValidationImpl() {
20 320 return !GetInput().empty();
21 }
22
23 160 bool LeonovaARadixMergeSortSEQ::PreProcessingImpl() {
24 160 return true;
25 }
26
27 160 bool LeonovaARadixMergeSortSEQ::RunImpl() {
28
1/2
✓ Branch 1 taken 160 times.
✗ Branch 2 not taken.
 160 if (!ValidationImpl()) {
29 return false;
30 }
31 160 GetOutput() = GetInput();
32
2/2
✓ Branch 0 taken 152 times.
✓ Branch 1 taken 8 times.
 160 if (GetOutput().size() > 1) {
33 152 RadixMergeSort(GetOutput(), 0, GetOutput().size());
34 }
35 return true;
36 }
37
38 160 bool LeonovaARadixMergeSortSEQ::PostProcessingImpl() {
39 160 return true;
40 }
41
42 ✗ uint64_t LeonovaARadixMergeSortSEQ::TransformDoubleToKey(double value) {
43 uint64_t int_value = 0;
44 std::memcpy(&int_value, &value, sizeof(double));
45
46 constexpr uint64_t kSignBitMask = 0x8000000000000000ULL;
47 // Преобразование для корректной сортировки чисел с плавающей точкой
48
5/12
✗ Branch 0 not taken.
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 128 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 4688 times.
✓ Branch 8 taken 88 times.
✓ Branch 9 taken 5424 times.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
 10456 if ((int_value & kSignBitMask) != 0U) {
49 88 return ~int_value;
50 }
51 10368 return int_value | kSignBitMask;
52 }
53
54 280 void LeonovaARadixMergeSortSEQ::RadixSort(std::vector<double> &arr, size_t left, size_t right) {
55 280 size_t size = right - left;
56
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 280 times.
 280 if (size <= 1) {
57 ✗ return;
58 }
59
60 280 std::vector<uint64_t> keys(size);
61
2/2
✓ Branch 0 taken 5512 times.
✓ Branch 1 taken 280 times.
 5792 for (size_t index = 0; index < size; ++index) {
62
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 5424 times.
 11024 keys[index] = TransformDoubleToKey(arr[left + index]);
63 }
64
65
1/4
✓ Branch 1 taken 280 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 280 std::vector<double> temp_arr(size);
66
1/4
✓ Branch 1 taken 280 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 280 std::vector<uint64_t> temp_keys(size);
67
68
2/2
✓ Branch 0 taken 2240 times.
✓ Branch 1 taken 280 times.
 2520 for (int byte_pos = 0; byte_pos < kNumBytes; ++byte_pos) {
69
1/4
✓ Branch 1 taken 2240 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 2240 std::vector<size_t> count(kNumCounters, 0);
70
71
2/2
✓ Branch 0 taken 44096 times.
✓ Branch 1 taken 2240 times.
 46336 for (size_t index = 0; index < size; ++index) {
72 44096 uint8_t byte_val = (keys[index] >> (byte_pos * kByteSize)) & 0xFF;
73 44096 ++count[byte_val];
74 }
75
76 size_t total = 0;
77
2/2
✓ Branch 0 taken 573440 times.
✓ Branch 1 taken 2240 times.
 575680 for (size_t &elem : count) {
78 573440 size_t old_count = elem;
79 573440 elem = total;
80 573440 total += old_count;
81 }
82
83
2/2
✓ Branch 0 taken 44096 times.
✓ Branch 1 taken 2240 times.
 46336 for (size_t index = 0; index < size; ++index) {
84 44096 uint8_t byte_val = (keys[index] >> (byte_pos * kByteSize)) & 0xFF;
85 44096 size_t pos = count[byte_val]++;
86 44096 temp_arr[pos] = arr[left + index];
87 44096 temp_keys[pos] = keys[index];
88 }
89
90 auto left_it = arr.begin() + static_cast<typename std::vector<double>::difference_type>(left);
91 std::ranges::copy(temp_arr, left_it);
92 keys.swap(temp_keys);
93 }
94 }
95
96 128 void LeonovaARadixMergeSortSEQ::SimpleRadixMerge(std::vector<double> &arr, size_t left, size_t mid, size_t right) {
97 128 size_t left_size = mid - left;
98 128 size_t right_size = right - mid;
99
100 128 std::vector<double> merged(left_size + right_size);
101
102 size_t index = 0;
103 size_t jndex = 0;
104 size_t kndex = 0;
105
106 uint64_t key_left = 0;
107 uint64_t key_right = 0;
108
1/2
✓ Branch 0 taken 128 times.
✗ Branch 1 not taken.
 128 if (left_size > 0) {
109
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 128 times.
 128 key_left = TransformDoubleToKey(arr[left]);
110 }
111
1/2
✓ Branch 0 taken 128 times.
✗ Branch 1 not taken.
 128 if (right_size > 0) {
112
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 128 times.
 128 key_right = TransformDoubleToKey(arr[mid]);
113 }
114
115
2/2
✓ Branch 0 taken 4816 times.
✓ Branch 1 taken 128 times.
 4944 while (index < left_size && jndex < right_size) {
116
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4816 times.
 4816 if (key_left < key_right) {
117 ✗ merged[kndex++] = arr[left + index++];
118 ✗ if (index < left_size) {
119 ✗ key_left = TransformDoubleToKey(arr[left + index]);
120 }
121 } else {
122
2/2
✓ Branch 0 taken 4688 times.
✓ Branch 1 taken 128 times.
 4816 merged[kndex++] = arr[mid + jndex++];
123
2/2
✓ Branch 0 taken 4688 times.
✓ Branch 1 taken 128 times.
 4816 if (jndex < right_size) {
124
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4688 times.
 4688 key_right = TransformDoubleToKey(arr[mid + jndex]);
125 }
126 }
127 }
128
129
2/2
✓ Branch 0 taken 4792 times.
✓ Branch 1 taken 128 times.
 4920 while (index < left_size) {
130 4792 merged[kndex++] = arr[left + index++];
131 }
132
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 128 times.
 128 while (jndex < right_size) {
133 ✗ merged[kndex++] = arr[mid + jndex++];
134 }
135
136 auto left_it = arr.begin() + static_cast<typename std::vector<double>::difference_type>(left);
137 std::ranges::copy(merged, left_it);
138 128 }
139
140 152 void LeonovaARadixMergeSortSEQ::RadixMergeSort(std::vector<double> &arr, size_t left, size_t right) {
141 struct SortTask {
142 size_t left;
143 size_t right;
144 bool sorted;
145 };
146
147 152 std::vector<SortTask> stack;
148
1/2
✓ Branch 1 taken 152 times.
✗ Branch 2 not taken.
 152 stack.reserve(128);
149
1/2
✓ Branch 1 taken 152 times.
✗ Branch 2 not taken.
 152 stack.push_back({left, right, false});
150
151
2/2
✓ Branch 0 taken 536 times.
✓ Branch 1 taken 152 times.
 688 while (!stack.empty()) {
152
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 536 times.
 536 SortTask current = stack.back();
153 stack.pop_back();
154
155 536 size_t size = current.right - current.left;
156
157
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 536 times.
 536 if (size <= 1) {
158 ✗ continue;
159 }
160
161
2/2
✓ Branch 0 taken 280 times.
✓ Branch 1 taken 256 times.
 536 if (size <= kRadixThreshold) {
162
1/2
✓ Branch 1 taken 280 times.
✗ Branch 2 not taken.
 280 RadixSort(arr, current.left, current.right);
163 280 continue;
164 }
165
166
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 128 times.
 256 if (!current.sorted) {
167 128 size_t mid = current.left + (size / 2);
168
169
1/2
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
 128 stack.push_back({current.left, current.right, true});
170
1/2
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
 128 stack.push_back({mid, current.right, false});
171
1/4
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 128 stack.push_back({current.left, mid, false});
172 } else {
173 128 size_t mid = current.left + (size / 2);
174
1/2
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
 128 SimpleRadixMerge(arr, current.left, mid, current.right);
175 }
176 }
177 152 }
178
179 } // namespace leonova_a_radix_merge_sort
180