GCC Code Coverage Report

Directory: ./
File: tasks/krymova_k_lsd_sort_merge_double/seq/src/ops_seq.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 67 73 91.8%
Functions: 8 11 72.7%
Branches: 53 72 73.6%
Line Branch Exec Source
1 #include "krymova_k_lsd_sort_merge_double/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <cstdint>
5 #include <cstring>
6 #include <vector>
7
8 #include "krymova_k_lsd_sort_merge_double/common/include/common.hpp"
9
10 namespace krymova_k_lsd_sort_merge_double {
11
12
1/2
✓ Branch 1 taken 104 times.
✗ Branch 2 not taken.
 104 KrymovaKLsdSortMergeDoubleSEQ::KrymovaKLsdSortMergeDoubleSEQ(const InType &in) {
13 SetTypeOfTask(GetStaticTypeOfTask());
14
1/2
✓ Branch 1 taken 104 times.
✗ Branch 2 not taken.
 104 GetInput() = in;
15 104 GetOutput() = OutType();
16 104 }
17
18 104 bool KrymovaKLsdSortMergeDoubleSEQ::ValidationImpl() {
19 104 return !GetInput().empty();
20 }
21
22 104 bool KrymovaKLsdSortMergeDoubleSEQ::PreProcessingImpl() {
23 104 GetOutput() = GetInput();
24 104 return true;
25 }
26
27 ✗ uint64_t KrymovaKLsdSortMergeDoubleSEQ::DoubleToULL(double d) {
28 uint64_t ull = 0;
29 std::memcpy(&ull, &d, sizeof(double));
30
31
2/4
✓ Branch 0 taken 800 times.
✓ Branch 1 taken 900000 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 900800 if ((ull & 0x8000000000000000ULL) != 0U) {
32 800 ull = ~ull;
33 } else {
34 900000 ull |= 0x8000000000000000ULL;
35 }
36
37 ✗ return ull;
38 }
39
40 ✗ double KrymovaKLsdSortMergeDoubleSEQ::ULLToDouble(uint64_t ull) {
41
2/4
✓ Branch 0 taken 900000 times.
✓ Branch 1 taken 800 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 900800 if ((ull & 0x8000000000000000ULL) != 0U) {
42 900000 ull &= 0x7FFFFFFFFFFFFFFFULL;
43 } else {
44 800 ull = ~ull;
45 }
46
47 double d = 0.0;
48 std::memcpy(&d, &ull, sizeof(double));
49 ✗ return d;
50 }
51
52 960 void KrymovaKLsdSortMergeDoubleSEQ::LSDSortDouble(double *arr, int size) {
53
2/2
✓ Branch 0 taken 160 times.
✓ Branch 1 taken 800 times.
 960 if (size <= 1) {
54 160 return;
55 }
56
57 const int k_bits_per_pass = 8;
58 const int k_radix = 1 << k_bits_per_pass;
59 const int k_passes = static_cast<int>(sizeof(double)) * 8 / k_bits_per_pass;
60
61 800 std::vector<uint64_t> ull_arr(size);
62
1/4
✓ Branch 1 taken 800 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 800 std::vector<uint64_t> ull_tmp(size);
63
64
2/2
✓ Branch 0 taken 900800 times.
✓ Branch 1 taken 800 times.
 901600 for (int i = 0; i < size; ++i) {
65
2/2
✓ Branch 0 taken 800 times.
✓ Branch 1 taken 900000 times.
 1801600 ull_arr[i] = DoubleToULL(arr[i]);
66 }
67
68
1/4
✓ Branch 1 taken 800 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 800 std::vector<unsigned int> count(k_radix, 0U);
69
70
2/2
✓ Branch 0 taken 6400 times.
✓ Branch 1 taken 800 times.
 7200 for (int pass = 0; pass < k_passes; ++pass) {
71
1/2
✓ Branch 0 taken 6400 times.
✗ Branch 1 not taken.
 6400 int shift = pass * k_bits_per_pass;
72
73 std::ranges::fill(count, 0U);
74
75
2/2
✓ Branch 0 taken 7206400 times.
✓ Branch 1 taken 6400 times.
 7212800 for (int i = 0; i < size; ++i) {
76 7206400 unsigned int digit = (ull_arr[i] >> shift) & (k_radix - 1);
77 7206400 ++count[digit];
78 }
79
80
2/2
✓ Branch 0 taken 1632000 times.
✓ Branch 1 taken 6400 times.
 1638400 for (int i = 1; i < k_radix; ++i) {
81 1632000 count[i] += count[i - 1];
82 }
83
84
2/2
✓ Branch 0 taken 7206400 times.
✓ Branch 1 taken 6400 times.
 7212800 for (int i = size - 1; i >= 0; --i) {
85 7206400 unsigned int digit = (ull_arr[i] >> shift) & (k_radix - 1);
86 7206400 ull_tmp[--count[digit]] = ull_arr[i];
87 }
88
89 ull_arr.swap(ull_tmp);
90 }
91
92
2/2
✓ Branch 0 taken 900800 times.
✓ Branch 1 taken 800 times.
 901600 for (int i = 0; i < size; ++i) {
93
2/2
✓ Branch 0 taken 900000 times.
✓ Branch 1 taken 800 times.
 1801600 arr[i] = ULLToDouble(ull_arr[i]);
94 }
95 }
96
97 864 void KrymovaKLsdSortMergeDoubleSEQ::MergeSections(double *left, const double *right, int left_size, int right_size) {
98 864 std::vector<double> temp(left_size);
99 864 std::copy(left, left + left_size, temp.begin());
100
101 int l = 0;
102 int r = 0;
103 int k = 0;
104
105
2/2
✓ Branch 0 taken 1892607 times.
✓ Branch 1 taken 864 times.
 1893471 while (l < left_size && r < right_size) {
106
2/2
✓ Branch 0 taken 1890264 times.
✓ Branch 1 taken 2343 times.
 1892607 if (temp[l] <= right[r]) {
107 1890264 left[k++] = temp[l++];
108 } else {
109 2343 left[k++] = right[r++];
110 }
111 }
112
113
2/2
✓ Branch 0 taken 1752 times.
✓ Branch 1 taken 864 times.
 2616 while (l < left_size) {
114 1752 left[k++] = temp[l++];
115 }
116 864 }
117
118 ✗ void KrymovaKLsdSortMergeDoubleSEQ::SortSections(double *arr, int size, int portion) {
119
2/4
✓ Branch 0 taken 960 times.
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 1056 for (int i = 0; i < size; i += portion) {
120 960 int current_size = std::min(portion, size - i);
121 960 LSDSortDouble(arr + i, current_size);
122 }
123 ✗ }
124
125 96 void KrymovaKLsdSortMergeDoubleSEQ::IterativeMergeSort(double *arr, int size, int portion) {
126
1/2
✓ Branch 0 taken 96 times.
✗ Branch 1 not taken.
 96 if (size <= 1) {
127 return;
128 }
129
130 SortSections(arr, size, portion);
131
132
2/2
✓ Branch 0 taken 384 times.
✓ Branch 1 taken 96 times.
 480 for (int merge_size = portion; merge_size < size; merge_size *= 2) {
133
2/2
✓ Branch 0 taken 1056 times.
✓ Branch 1 taken 384 times.
 1440 for (int i = 0; i < size; i += 2 * merge_size) {
134 int left_size = merge_size;
135
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 864 times.
 1056 int right_size = std::min(merge_size, size - (i + merge_size));
136
137
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 864 times.
 1056 if (right_size <= 0) {
138 192 continue;
139 }
140
141 864 double *left = arr + i;
142 864 const double *right = arr + i + left_size;
143
144 864 MergeSections(left, right, left_size, right_size);
145 }
146 }
147 }
148
149
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 8 times.
 104 bool KrymovaKLsdSortMergeDoubleSEQ::RunImpl() {
150 OutType &output = GetOutput();
151 104 int size = static_cast<int>(output.size());
152
153
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 8 times.
 104 if (size <= 1) {
154 return true;
155 }
156
157
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 80 times.
 96 int portion = std::max(1, size / 10);
158 96 IterativeMergeSort(output.data(), size, portion); // без tmp
159
160 96 return true;
161 }
162
163 104 bool KrymovaKLsdSortMergeDoubleSEQ::PostProcessingImpl() {
164 const OutType &output = GetOutput();
165
166
2/2
✓ Branch 0 taken 900864 times.
✓ Branch 1 taken 104 times.
 900968 for (size_t i = 1; i < output.size(); ++i) {
167
1/2
✓ Branch 0 taken 900864 times.
✗ Branch 1 not taken.
 900864 if (output[i] < output[i - 1]) {
168 return false;
169 }
170 }
171
172 return true;
173 }
174
175 } // namespace krymova_k_lsd_sort_merge_double
176