GCC Code Coverage Report

Line	Branch	Exec	Source
1			#include "buzulukskiy_d_sort_batcher/seq/include/ops_seq.hpp"
2
3			#include <algorithm>
4			#include <climits>
5			#include <cstddef>
6			#include <utility>
7			#include <vector>
8
9			#include "buzulukskiy_d_sort_batcher/common/include/common.hpp"
10
11			namespace buzulukskiy_d_sort_batcher {
12			namespace {
13			constexpr int kRadixBase = 10;
14			constexpr std::size_t kBlockSize = 64;
15
16		✗	void RadixSortUnsigned(std::vector<int> &arr) {
17		✗	if (arr.empty()) {
18		✗	return;
19			}
20		✗	const int max_val = *std::ranges::max_element(arr);
21		✗	std::vector<int> output(arr.size());
22		✗	for (int exp = 1; max_val / exp > 0; exp *= kRadixBase) {
23		✗	std::vector<int> count(static_cast<std::size_t>(kRadixBase), 0);
24		✗	for (const int val : arr) {
25		✗	count[static_cast<std::size_t>((val / exp) % kRadixBase)]++;
26			}
27		✗	for (std::size_t i = 1; i < static_cast<std::size_t>(kRadixBase); ++i) {
28		✗	count[i] += count[i - 1];
29			}
30		✗	for (std::size_t i = arr.size(); i-- > 0;) {
31		✗	const int digit = (arr[i] / exp) % kRadixBase;
32		✗	output[--count[static_cast<std::size_t>(digit)]] = arr[i];
33			}
34			arr.swap(output);
35			}
36			}
37
38		✗	void RadixSortLSD(std::vector<int> &data) {
39		✗	if (data.empty()) {
40		✗	return;
41			}
42		✗	std::vector<int> positives;
43		✗	std::vector<int> negatives;
44		✗	for (const int value : data) {
45		✗	if (value < 0) {
46		✗	negatives.push_back(value == INT_MIN ? INT_MAX : -value);
47			} else {
48			positives.push_back(value);
49			}
50			}
51		✗	if (!positives.empty()) {
52		✗	RadixSortUnsigned(positives);
53			}
54		✗	if (!negatives.empty()) {
55		✗	RadixSortUnsigned(negatives);
56			std::ranges::reverse(negatives);
57		✗	for (int &v_ref : negatives) {
58		✗	v_ref = (v_ref == INT_MAX ? INT_MIN : -v_ref);
59			}
60			}
61		✗	data.assign(negatives.begin(), negatives.end());
62		✗	data.insert(data.end(), positives.begin(), positives.end());
63			}
64
65		✗	void BatcherStep(std::vector<int> &data, std::size_t i, std::size_t j, std::size_t k, std::size_t phase_step) {
66		✗	const std::size_t r1 = i + j;
67		✗	const std::size_t r2 = i + j + k;
68		✗	if (r2 < data.size() && (r1 / (phase_step * 2)) == (r2 / (phase_step * 2))) {
69		✗	if (data[r1] > data[r2]) {
70			std::swap(data[r1], data[r2]);
71			}
72			}
73		✗	}
74
75		✗	void BatcherInner(std::vector<int> &data, std::size_t k, std::size_t phase_step) {
76		✗	for (std::size_t j = k % phase_step; j + k < data.size(); j += 2 * k) {
77		✗	for (std::size_t i = 0; i < k; ++i) {
78		✗	BatcherStep(data, i, j, k, phase_step);
79			}
80			}
81		✗	}
82
83		✗	void BatcherMergeNetwork(std::vector<int> &data) {
84			const std::size_t n = data.size();
85		✗	for (std::size_t phase_step = 1; phase_step < n; phase_step <<= 1) {
86		✗	for (std::size_t k = phase_step; k > 0; k >>= 1) {
87		✗	BatcherInner(data, k, phase_step);
88			}
89			}
90		✗	}
91			} // namespace
92
93		✗	BuzulukskiyDSortBatcherSEQ::BuzulukskiyDSortBatcherSEQ(const InType &in) : BaseTask() {
94			SetTypeOfTask(GetStaticTypeOfTask());
95		✗	GetInput() = in;
96		✗	}
97
98		✗	bool BuzulukskiyDSortBatcherSEQ::ValidationImpl() {
99		✗	return true;
100			}
101		✗	bool BuzulukskiyDSortBatcherSEQ::PreProcessingImpl() {
102		✗	return true;
103			}
104		✗	bool BuzulukskiyDSortBatcherSEQ::PostProcessingImpl() {
105		✗	return true;
106			}
107
108		✗	bool BuzulukskiyDSortBatcherSEQ::RunImpl() {
109		✗	if (GetInput().empty()) {
110		✗	GetOutput() = InType();
111		✗	return true;
112			}
113		✗	std::vector<int> data = GetInput();
114		✗	for (std::size_t i = 0; i < data.size(); i += kBlockSize) {
115		✗	std::size_t current_size = std::min(kBlockSize, data.size() - i);
116			std::vector<int> block(data.begin() + static_cast<std::ptrdiff_t>(i),
117		✗	data.begin() + static_cast<std::ptrdiff_t>(i + current_size));
118		✗	RadixSortLSD(block);
119			std::ranges::copy(block, data.begin() + static_cast<std::ptrdiff_t>(i));
120			}
121		✗	BatcherMergeNetwork(data);
122			GetOutput() = std::move(data);
123			return true;
124			}
125			} // namespace buzulukskiy_d_sort_batcher
126