GCC Code Coverage Report

Directory: ./
File: tasks/popova_e_radix_sort_for_double_with_simple_merge/seq/src/ops_seq.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 76 77 98.7%
Functions: 8 8 100.0%
Branches: 80 106 75.5%
Line Branch Exec Source
1 #include "popova_e_radix_sort_for_double_with_simple_merge/seq/include/ops_seq.hpp"
2
3 #include <cstdint>
4 #include <cstring>
5 #include <random>
6 #include <vector>
7
8 #include "popova_e_radix_sort_for_double_with_simple_merge/common/include/common.hpp"
9
10 namespace popova_e_radix_sort_for_double_with_simple_merge_threads {
11 namespace {
12 uint64_t DoubleToSortable(double value) {
13 uint64_t bits = 0;
14 memcpy(&bits, &value, sizeof(double));
15
16 49688 bool is_negative = (bits >> 63) == 1;
17
4/4
✓ Branch 0 taken 12401 times.
✓ Branch 1 taken 12431 times.
✓ Branch 2 taken 12311 times.
✓ Branch 3 taken 12545 times.
 49688 if (is_negative) {
18 24712 bits = ~bits;
19 } else {
20 24976 bits ^= (1ULL << 63); // сдвиг старшего бита
21 }
22 return bits;
23 }
24
25 double SortableToDouble(uint64_t bits) {
26 49688 bool is_negative = (bits >> 63) == 1;
27 49688 if (is_negative) {
28 24976 bits ^= (1ULL << 63);
29 } else {
30 24712 bits = ~bits;
31 }
32
33 double value = 0;
34 memcpy(&value, &bits, sizeof(double));
35 return value;
36 }
37
38
1/2
✓ Branch 0 taken 192 times.
✗ Branch 1 not taken.
 192 void RadixSortUInt(std::vector<uint64_t> &arr) {
39
1/2
✓ Branch 0 taken 192 times.
✗ Branch 1 not taken.
 192 if (arr.empty()) {
40 return;
41 }
42
43 const int bytes_count = 8;
44 const int base = 256;
45
46
2/2
✓ Branch 0 taken 1536 times.
✓ Branch 1 taken 192 times.
 1728 for (int byte_index = 0; byte_index < bytes_count; byte_index++) {
47 1536 int sdvig = byte_index * 8;
48 1536 std::vector<std::vector<uint64_t>> buckets(base);
49
50
2/2
✓ Branch 0 taken 397504 times.
✓ Branch 1 taken 1536 times.
 399040 for (const auto &value : arr) {
51
2/2
✓ Branch 0 taken 210301 times.
✓ Branch 1 taken 187203 times.
 397504 const auto bucket_index = static_cast<size_t>((value >> sdvig) & 0xFFULL);
52 buckets[bucket_index].push_back(value);
53 }
54
55 size_t pos = 0;
56
2/2
✓ Branch 0 taken 393216 times.
✓ Branch 1 taken 1536 times.
 394752 for (const auto &bucket : buckets) {
57
2/2
✓ Branch 0 taken 397504 times.
✓ Branch 1 taken 393216 times.
 790720 for (const auto &value : bucket) {
58 397504 arr[pos++] = value;
59 }
60 }
61 1536 }
62 }
63
64 49688 double RandomDouble(double min_val = -100.0, double max_val = 100.0) {
65
4/6
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 49680 times.
✓ Branch 3 taken 8 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 8 times.
✗ Branch 7 not taken.
 49688 static std::random_device rd;
66
3/4
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 49680 times.
✓ Branch 3 taken 8 times.
✗ Branch 4 not taken.
 49704 static std::mt19937 gen(rd());
67 std::uniform_real_distribution<> dis(min_val, max_val);
68 49688 return dis(gen);
69 }
70
71 96 std::vector<double> MergeSorted(const std::vector<double> &left, const std::vector<double> &right) {
72 96 std::vector<double> result;
73 size_t i = 0;
74 size_t j = 0;
75
4/4
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 49607 times.
✓ Branch 2 taken 56 times.
✓ Branch 3 taken 49551 times.
 49647 while (i < left.size() && j < right.size()) {
76
2/2
✓ Branch 0 taken 24755 times.
✓ Branch 1 taken 24796 times.
 49551 if (left[i] <= right[j]) {
77
2/2
✓ Branch 0 taken 24497 times.
✓ Branch 1 taken 258 times.
 24755 result.push_back(left[i++]);
78 } else {
79
2/2
✓ Branch 0 taken 24512 times.
✓ Branch 1 taken 284 times.
 24796 result.push_back(right[j++]);
80 }
81 }
82
2/2
✓ Branch 0 taken 77 times.
✓ Branch 1 taken 96 times.
 173 while (i < left.size()) {
83
2/2
✓ Branch 0 taken 53 times.
✓ Branch 1 taken 24 times.
 77 result.push_back(left[i++]);
84 }
85
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 96 times.
 156 while (j < right.size()) {
86
2/2
✓ Branch 0 taken 42 times.
✓ Branch 1 taken 18 times.
 60 result.push_back(right[j++]);
87 }
88
89 96 return result;
90 }
91
92 bool IsSorted(const std::vector<double> &arr) {
93
2/2
✓ Branch 0 taken 49592 times.
✓ Branch 1 taken 96 times.
 49688 for (size_t i = 1; i < arr.size(); ++i) {
94
1/2
✓ Branch 0 taken 49592 times.
✗ Branch 1 not taken.
 49592 if (arr[i - 1] > arr[i]) {
95 return false;
96 }
97 }
98 return true;
99 }
100
101 bool SameData(const std::vector<double> &original, const std::vector<double> &result) {
102 uint64_t hash_original = 0;
103 uint64_t hash_result = 0;
104
105
2/2
✓ Branch 0 taken 49688 times.
✓ Branch 1 taken 96 times.
 49784 for (const double &value : original) {
106 uint64_t bits = 0;
107 memcpy(&bits, &value, sizeof(double));
108 49688 hash_original ^= bits;
109 }
110
111
2/2
✓ Branch 0 taken 49688 times.
✓ Branch 1 taken 96 times.
 49784 for (const double &value : result) {
112 uint64_t bits = 0;
113 memcpy(&bits, &value, sizeof(double));
114 49688 hash_result ^= bits;
115 }
116
117 96 return hash_original == hash_result;
118 }
119 } // namespace
120
121 96 PopovaERadixSorForDoubleWithSimpleMergeSEQ::PopovaERadixSorForDoubleWithSimpleMergeSEQ(const InType &in) {
122 SetTypeOfTask(GetStaticTypeOfTask());
123 96 GetInput() = in;
124 GetOutput() = 0;
125 96 }
126
127 96 bool PopovaERadixSorForDoubleWithSimpleMergeSEQ::ValidationImpl() {
128 96 return GetInput() > 0;
129 }
130
131 96 bool PopovaERadixSorForDoubleWithSimpleMergeSEQ::PreProcessingImpl() {
132 96 int size = GetInput();
133 96 array_.resize(size);
134
135
2/2
✓ Branch 0 taken 49688 times.
✓ Branch 1 taken 96 times.
 49784 for (int i = 0; i < size; ++i) {
136 49688 array_[i] = RandomDouble();
137 }
138
139 96 return true;
140 }
141
142
1/2
✓ Branch 0 taken 96 times.
✗ Branch 1 not taken.
 96 bool PopovaERadixSorForDoubleWithSimpleMergeSEQ::RunImpl() {
143
1/2
✓ Branch 0 taken 96 times.
✗ Branch 1 not taken.
 96 if (array_.empty()) {
144 return false;
145 }
146
147 96 size_t mid = array_.size() / 2;
148 96 std::vector<uint64_t> left_bits;
149 96 std::vector<uint64_t> right_bits;
150
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 left_bits.reserve(mid);
151
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 right_bits.reserve(array_.size() - mid);
152
153
2/2
✓ Branch 0 taken 24832 times.
✓ Branch 1 taken 96 times.
 24928 for (size_t i = 0; i < mid; ++i) {
154
3/4
✓ Branch 0 taken 12401 times.
✓ Branch 1 taken 12431 times.
✓ Branch 3 taken 24832 times.
✗ Branch 4 not taken.
 49664 left_bits.push_back(DoubleToSortable(array_[i]));
155 }
156
2/2
✓ Branch 0 taken 24856 times.
✓ Branch 1 taken 96 times.
 24952 for (size_t i = mid; i < array_.size(); ++i) {
157
3/4
✓ Branch 0 taken 12311 times.
✓ Branch 1 taken 12545 times.
✓ Branch 3 taken 24856 times.
✗ Branch 4 not taken.
 49712 right_bits.push_back(DoubleToSortable(array_[i]));
158 }
159
160
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 RadixSortUInt(left_bits);
161
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 RadixSortUInt(right_bits);
162
163
2/6
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 96 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 96 std::vector<double> left(left_bits.size());
164
1/4
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 96 std::vector<double> right(right_bits.size());
165
166
2/2
✓ Branch 0 taken 24832 times.
✓ Branch 1 taken 96 times.
 24928 for (size_t i = 0; i < left_bits.size(); ++i) {
167
2/2
✓ Branch 0 taken 12431 times.
✓ Branch 1 taken 12401 times.
 49664 left[i] = SortableToDouble(left_bits[i]);
168 }
169
2/2
✓ Branch 0 taken 24856 times.
✓ Branch 1 taken 96 times.
 24952 for (size_t i = 0; i < right_bits.size(); ++i) {
170
2/2
✓ Branch 0 taken 12545 times.
✓ Branch 1 taken 12311 times.
 49712 right[i] = SortableToDouble(right_bits[i]);
171 }
172
173
2/6
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 96 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 192 result_ = MergeSorted(left, right);
174
175 return true;
176 }
177
178 96 bool PopovaERadixSorForDoubleWithSimpleMergeSEQ::PostProcessingImpl() {
179 bool sorted = IsSorted(result_);
180 bool same = SameData(array_, result_);
181
182
1/2
✓ Branch 0 taken 96 times.
✗ Branch 1 not taken.
 96 if (sorted && same) {
183 96 GetOutput() = 1;
184 } else {
185 ✗ GetOutput() = 0;
186 }
187
188 96 return true;
189 }
190
191 } // namespace popova_e_radix_sort_for_double_with_simple_merge_threads
192