GCC Code Coverage Report

Directory: ./
File: tasks/gonozov_l_bitwise_sorting_double_Batcher_merge/seq/src/ops_seq.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 64 66 97.0%
Functions: 9 9 100.0%
Branches: 46 68 67.6%
Line Branch Exec Source
1 #include "gonozov_l_bitwise_sorting_double_Batcher_merge/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <cmath>
5 #include <cstddef>
6 #include <cstdint>
7 #include <cstring>
8 #include <limits>
9 #include <vector>
10
11 #include "gonozov_l_bitwise_sorting_double_Batcher_merge/common/include/common.hpp"
12
13 namespace gonozov_l_bitwise_sorting_double_batcher_merge {
14
15
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 GonozovLBitSortBatcherMergeSEQ::GonozovLBitSortBatcherMergeSEQ(const InType &in) {
16 SetTypeOfTask(GetStaticTypeOfTask());
17
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 GetInput() = in;
18 32 }
19
20 32 bool GonozovLBitSortBatcherMergeSEQ::ValidationImpl() {
21 32 return !GetInput().empty(); // проверка на то, что исходный массив непустой
22 }
23
24 32 bool GonozovLBitSortBatcherMergeSEQ::PreProcessingImpl() {
25 32 return true;
26 }
27
28 namespace {
29 /// double -> uint64_t
30 uint64_t DoubleToSortableInt(double d) {
31 uint64_t bits = 0;
32 std::memcpy(&bits, &d, sizeof(double));
33
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 208 times.
 256 if ((bits >> 63) != 0) { // Отрицательное число
34 48 return ~bits; // Инвертируем все биты
35 } // Положительное число или ноль
36 208 return bits | 0x8000000000000000ULL;
37 }
38
39 // uint64_t -> double
40 double SortableIntToDouble(uint64_t bits) {
41 256 if ((bits >> 63) != 0) { // Если старший бит установлен (было положительное)
42 208 bits &= ~0x8000000000000000ULL; // Убираем старший бит
43 } else { // Если старший бит не установлен (было отрицательное число)
44 48 bits = ~bits; // Инвертируем все биты обратно
45 }
46
47 double result = 0.0;
48 std::memcpy(&result, &bits, sizeof(double));
49 return result;
50 }
51
52
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 64 times.
 64 void RadixSortDouble(std::vector<double> &data) {
53
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 64 times.
 64 if (data.empty()) {
54 ✗ return;
55 }
56
57 // Преобразуем в сортируемые целые числа
58 64 std::vector<uint64_t> keys(data.size());
59
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 64 times.
 320 for (size_t i = 0; i < data.size(); ++i) {
60
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 208 times.
 512 keys[i] = DoubleToSortableInt(data[i]);
61 }
62
63 const int radix = 256; // 8 бит за проход
64
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_keys(data.size());
65
66 // 8 проходов для 64-битных чисел (8 байт)
67
2/2
✓ Branch 0 taken 512 times.
✓ Branch 1 taken 64 times.
 576 for (int pass = 0; pass < 8; ++pass) {
68
1/4
✓ Branch 1 taken 512 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 512 std::vector<size_t> count(radix, 0);
69 512 int shift = pass * 8;
70 // Подсчет
71
2/2
✓ Branch 0 taken 2048 times.
✓ Branch 1 taken 512 times.
 2560 for (uint64_t key : keys) {
72 2048 uint8_t byte = (key >> shift) & 0xFF;
73 2048 count[byte]++;
74 }
75
76 // Накопление
77
2/2
✓ Branch 0 taken 130560 times.
✓ Branch 1 taken 512 times.
 131072 for (int i = 1; i < radix; ++i) {
78 130560 count[i] += count[i - 1];
79 }
80
81 // Распределение
82
2/2
✓ Branch 0 taken 2048 times.
✓ Branch 1 taken 512 times.
 2560 for (int i = static_cast<int>(keys.size()) - 1; i >= 0; --i) {
83 2048 uint8_t byte = (keys[i] >> shift) & 0xFF;
84 2048 temp_keys[--count[byte]] = keys[i];
85 }
86 keys.swap(temp_keys);
87 }
88
89 // Преобразуем обратно
90
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 64 times.
 320 for (size_t i = 0; i < data.size(); ++i) {
91
2/2
✓ Branch 0 taken 208 times.
✓ Branch 1 taken 48 times.
 512 data[i] = SortableIntToDouble(keys[i]);
92 }
93 }
94
95 224 void MergingHalves(std::vector<double> &arr, size_t i, size_t len) { // слияние половинок
96 224 size_t half = len / 2;
97 224 size_t end = std::min(i + len, arr.size());
98
99
2/2
✓ Branch 0 taken 352 times.
✓ Branch 1 taken 224 times.
 576 for (size_t step = half; step > 0; step /= 2) {
100
2/2
✓ Branch 0 taken 992 times.
✓ Branch 1 taken 352 times.
 1344 for (size_t j = i; j + step < end; ++j) {
101
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 880 times.
 992 if (arr[j] > arr[j + step]) {
102 std::swap(arr[j], arr[j + step]);
103 }
104 }
105 }
106 224 }
107
108 32 void BatcherOddEvenMergeIterative(std::vector<double> &arr, size_t n) {
109
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
 32 if (n <= 1) {
110 return;
111 }
112 32 n = std::min(n, arr.size());
113 // Сначала сливаем блоки размером 1, потом 2, потом 4 и т.д.
114
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 32 times.
 128 for (size_t len = 2; len <= n; len *= 2) {
115
2/2
✓ Branch 0 taken 224 times.
✓ Branch 1 taken 96 times.
 320 for (size_t i = 0; i < n; i += len) {
116 224 MergingHalves(arr, i, len);
117 }
118 }
119 }
120
121 // Нахождение ближайшей степени двойки, большей или равной n
122 size_t NextPowerOfTwo(size_t n) {
123 size_t power = 1;
124
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 32 times.
 128 while (power < n) {
125 96 power <<= 1;
126 }
127 return power;
128 }
129
130
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
 32 void HybridSortDouble(std::vector<double> &data) {
131
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
 32 if (data.size() <= 1) {
132 ✗ return;
133 }
134
135 size_t original_size = data.size();
136
137 size_t new_size = NextPowerOfTwo(original_size);
138 32 data.resize(new_size, std::numeric_limits<double>::max());
139
140 32 size_t mid = new_size / 2;
141
1/2
✓ Branch 2 taken 32 times.
✗ Branch 3 not taken.
 32 std::vector<double> left(data.begin(), data.begin() + static_cast<ptrdiff_t>(mid));
142
1/4
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 32 std::vector<double> right(data.begin() + static_cast<ptrdiff_t>(mid), data.end());
143
144 // Сортируем каждую половину поразрядно
145
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 RadixSortDouble(left);
146
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 RadixSortDouble(right);
147
148 // Собираем обратно в единый массив
149 std::ranges::copy(left, data.begin());
150 std::ranges::copy(right, data.begin() + static_cast<ptrdiff_t>(mid));
151
152 // Используем слияние Бэтчера для слияния двух отсортированных массивов
153 32 BatcherOddEvenMergeIterative(data, new_size);
154
155 // Обрезаем до исходного размера
156
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 data.resize(original_size);
157 }
158
159 } // namespace
160
161 32 bool GonozovLBitSortBatcherMergeSEQ::RunImpl() {
162 32 std::vector<double> array = GetInput();
163
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 HybridSortDouble(array);
164
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 GetOutput() = array;
165 32 return true;
166 }
167
168 32 bool GonozovLBitSortBatcherMergeSEQ::PostProcessingImpl() {
169 32 return true;
170 }
171
172 } // namespace gonozov_l_bitwise_sorting_double_batcher_merge
173