GCC Code Coverage Report

Directory: ./
File: tasks/dorofeev_i_bitwise_sort_double_eo_batcher_merge/seq/src/ops_seq.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 56 57 98.2%
Functions: 7 7 100.0%
Branches: 51 72 70.8%
Line Branch Exec Source
1 #include "dorofeev_i_bitwise_sort_double_eo_batcher_merge/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <cstdint>
6 #include <cstring>
7 #include <limits>
8 #include <vector>
9
10 #include "dorofeev_i_bitwise_sort_double_eo_batcher_merge/common/include/common.hpp"
11
12 namespace dorofeev_i_bitwise_sort_double_eo_batcher_merge {
13
14 namespace {
15
16 uint64_t DoubleToUint(double d) {
17 uint64_t u = 0;
18 std::memcpy(&u, &d, sizeof(double));
19
2/2
✓ Branch 0 taken 4984 times.
✓ Branch 1 taken 6408 times.
 11392 if ((u & 0x8000000000000000ULL) != 0) {
20 4984 u = ~u;
21 } else {
22 6408 u |= 0x8000000000000000ULL;
23 }
24 return u;
25 }
26
27 double UintToDouble(uint64_t u) {
28 11392 if ((u & 0x8000000000000000ULL) != 0) {
29 6408 u &= ~0x8000000000000000ULL;
30 } else {
31 4984 u = ~u;
32 }
33 double d = 0.0;
34 std::memcpy(&d, &u, sizeof(double));
35 return d;
36 }
37
38
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 64 times.
 64 void RadixSortDouble(std::vector<double> &arr) {
39
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 64 times.
 64 if (arr.empty()) {
40 ✗ return;
41 }
42
43 64 std::vector<uint64_t> uarr(arr.size());
44
2/2
✓ Branch 0 taken 11392 times.
✓ Branch 1 taken 64 times.
 11456 for (size_t i = 0; i < arr.size(); ++i) {
45
2/2
✓ Branch 0 taken 4984 times.
✓ Branch 1 taken 6408 times.
 22784 uarr[i] = DoubleToUint(arr[i]);
46 }
47
48
1/4
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 64 std::vector<uint64_t> temp(uarr.size());
49
2/2
✓ Branch 0 taken 512 times.
✓ Branch 1 taken 64 times.
 576 for (size_t byte = 0; byte < 8; ++byte) {
50
1/4
✓ Branch 1 taken 512 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 512 std::vector<int> count(256, 0);
51
2/2
✓ Branch 0 taken 91136 times.
✓ Branch 1 taken 512 times.
 91648 for (uint64_t val : uarr) {
52 91136 count[(val >> (byte * 8)) & 0xFF]++;
53 }
54
2/2
✓ Branch 0 taken 130560 times.
✓ Branch 1 taken 512 times.
 131072 for (size_t i = 1; i < 256; ++i) {
55 130560 count[i] += count[i - 1];
56 }
57
2/2
✓ Branch 0 taken 91136 times.
✓ Branch 1 taken 512 times.
 91648 for (int i = static_cast<int>(uarr.size()) - 1; i >= 0; --i) {
58 91136 temp[--count[(uarr[i] >> (byte * 8)) & 0xFF]] = uarr[i];
59 }
60
1/2
✓ Branch 1 taken 512 times.
✗ Branch 2 not taken.
 512 uarr = temp;
61 }
62
63
2/2
✓ Branch 0 taken 11392 times.
✓ Branch 1 taken 64 times.
 11456 for (size_t i = 0; i < arr.size(); ++i) {
64
2/2
✓ Branch 0 taken 6408 times.
✓ Branch 1 taken 4984 times.
 22784 arr[i] = UintToDouble(uarr[i]);
65 }
66 }
67
68 // Вынесли операцию сравнения и перестановки блоков в отдельную функцию
69 void CompareExchangeBlocks(std::vector<double> &arr, size_t i, size_t step) {
70
4/4
✓ Branch 0 taken 5696 times.
✓ Branch 1 taken 32 times.
✓ Branch 2 taken 41632 times.
✓ Branch 3 taken 11128 times.
 58488 for (size_t k = 0; k < step; ++k) {
71
4/4
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 5552 times.
✓ Branch 2 taken 20760 times.
✓ Branch 3 taken 20872 times.
 47328 if (arr[i + k] > arr[i + k + step]) {
72 std::swap(arr[i + k], arr[i + k + step]);
73 }
74 }
75 }
76
77 // Теперь функция выглядит максимально просто и элегантно
78 32 void OddEvenMergeIterative(std::vector<double> &arr, size_t n) {
79
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
 32 if (n <= 1) {
80 return;
81 }
82
83 // Первая фаза слияния
84 32 size_t step = n / 2;
85 CompareExchangeBlocks(arr, 0, step);
86
87 // Последующие фазы
88 32 step /= 2;
89
2/2
✓ Branch 0 taken 200 times.
✓ Branch 1 taken 32 times.
 232 for (; step > 0; step /= 2) {
90
2/2
✓ Branch 0 taken 11128 times.
✓ Branch 1 taken 200 times.
 11328 for (size_t i = step; i < n - step; i += step * 2) {
91 CompareExchangeBlocks(arr, i, step);
92 }
93 }
94 }
95
96 } // namespace
97
98
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 DorofeevIBitwiseSortDoubleEOBatcherMergeSEQ::DorofeevIBitwiseSortDoubleEOBatcherMergeSEQ(const InType &in) {
99 SetTypeOfTask(GetStaticTypeOfTask());
100
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 GetInput() = in;
101 32 }
102
103 32 bool DorofeevIBitwiseSortDoubleEOBatcherMergeSEQ::ValidationImpl() {
104 32 return true;
105 }
106
107 32 bool DorofeevIBitwiseSortDoubleEOBatcherMergeSEQ::PreProcessingImpl() {
108 32 local_data_ = GetInput();
109 32 return true;
110 }
111
112
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
 32 bool DorofeevIBitwiseSortDoubleEOBatcherMergeSEQ::RunImpl() {
113
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
 32 if (local_data_.empty()) {
114 return true;
115 }
116
117 size_t original_size = local_data_.size();
118
119 size_t pow2 = 1;
120
2/2
✓ Branch 0 taken 232 times.
✓ Branch 1 taken 32 times.
 264 while (pow2 < original_size) {
121 232 pow2 *= 2;
122 }
123
124
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 8 times.
 32 if (pow2 > original_size) {
125 24 local_data_.resize(pow2, std::numeric_limits<double>::max());
126 }
127
128 32 size_t mid = pow2 / 2;
129
1/2
✓ Branch 2 taken 32 times.
✗ Branch 3 not taken.
 32 std::vector<double> left(local_data_.begin(), local_data_.begin() + static_cast<ptrdiff_t>(mid));
130
1/4
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 32 std::vector<double> right(local_data_.begin() + static_cast<ptrdiff_t>(mid), local_data_.end());
131
132
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 RadixSortDouble(left);
133
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 RadixSortDouble(right);
134
135 std::ranges::copy(left, local_data_.begin());
136 std::ranges::copy(right, local_data_.begin() + static_cast<ptrdiff_t>(mid));
137
138 32 OddEvenMergeIterative(local_data_, pow2);
139
140
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 8 times.
 32 if (pow2 > original_size) {
141
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 local_data_.resize(original_size);
142 }
143
144 return true;
145 }
146
147 32 bool DorofeevIBitwiseSortDoubleEOBatcherMergeSEQ::PostProcessingImpl() {
148 32 GetOutput() = local_data_;
149 32 return true;
150 }
151
152 } // namespace dorofeev_i_bitwise_sort_double_eo_batcher_merge
153