GCC Code Coverage Report

Line	Branch	Exec	Source
1			#include "titaev_m_sortirovka_betchera/seq/include/ops_seq.hpp"
2
3			#include <algorithm>
4			#include <cstdint>
5			#include <cstring>
6			#include <vector>
7
8			#include "titaev_m_sortirovka_betchera/common/include/common.hpp"
9
10			namespace titaev_m_sortirovka_betchera {
11
12			namespace {
13
14			uint64_t DoubleToOrderedUint(double value) {
15			uint64_t x = 0;
16			std::memcpy(&x, &value, sizeof(double));
17
18			constexpr uint64_t kSignMask = (1ULL << 63);
19
20		✗	if ((x & kSignMask) != 0ULL) {
21		✗	x = ~x;
22			} else {
23		✗	x ^= kSignMask;
24			}
25
26			return x;
27			}
28
29			double OrderedUintToDouble(uint64_t x) {
30			constexpr uint64_t kSignMask = (1ULL << 63);
31
32		✗	if ((x & kSignMask) != 0ULL) {
33		✗	x ^= kSignMask;
34			} else {
35		✗	x = ~x;
36			}
37
38			double result = 0.0;
39			std::memcpy(&result, &x, sizeof(double));
40			return result;
41			}
42			} // namespace
43
44		✗	TitaevSortirovkaBetcheraSEQ::TitaevSortirovkaBetcheraSEQ(const InType &in) {
45			SetTypeOfTask(GetStaticTypeOfTask());
46		✗	GetInput() = in;
47			GetOutput().clear();
48		✗	}
49
50		✗	bool TitaevSortirovkaBetcheraSEQ::ValidationImpl() {
51		✗	return !GetInput().empty();
52			}
53
54		✗	bool TitaevSortirovkaBetcheraSEQ::PreProcessingImpl() {
55		✗	GetOutput() = GetInput();
56		✗	return true;
57			}
58
59		✗	void TitaevSortirovkaBetcheraSEQ::ConvertToKeys(const InType &input, std::vector<uint64_t> &keys) {
60			const size_t n = input.size();
61		✗	for (size_t i = 0; i < n; i++) {
62		✗	keys[i] = DoubleToOrderedUint(input[i]);
63			}
64		✗	}
65
66		✗	void TitaevSortirovkaBetcheraSEQ::RadixSort(std::vector<uint64_t> &keys) {
67			const size_t n = keys.size();
68		✗	if (n <= 1) {
69		✗	return;
70			}
71
72			constexpr int kBits = 8;
73			constexpr int kBuckets = 1 << kBits;
74			constexpr int kPasses = 64 / kBits;
75
76		✗	std::vector<uint64_t> tmp(n);
77
78		✗	for (int pass = 0; pass < kPasses; pass++) {
79		✗	std::vector<size_t> count(kBuckets, 0);
80
81		✗	for (size_t i = 0; i < n; i++) {
82		✗	size_t bucket = (keys[i] >> (pass * kBits)) & (kBuckets - 1);
83		✗	count[bucket]++;
84			}
85
86		✗	for (int i = 1; i < kBuckets; i++) {
87		✗	count[i] += count[i - 1];
88			}
89
90		✗	for (size_t i = n; i-- > 0;) {
91		✗	size_t bucket = (keys[i] >> (pass * kBits)) & (kBuckets - 1);
92		✗	tmp[--count[bucket]] = keys[i];
93			}
94
95			keys.swap(tmp);
96			}
97			}
98
99		✗	void TitaevSortirovkaBetcheraSEQ::ConvertFromKeys(const std::vector<uint64_t> &keys, OutType &output) {
100			const size_t n = keys.size();
101		✗	output.resize(n);
102		✗	for (size_t i = 0; i < n; i++) {
103		✗	output[i] = OrderedUintToDouble(keys[i]);
104			}
105		✗	}
106
107		✗	void TitaevSortirovkaBetcheraSEQ::BatcherStep(OutType &result, size_t n, size_t step, size_t stage) {
108		✗	for (size_t i = 0; i < n; i++) {
109		✗	size_t j = i ^ stage;
110		✗	if (j <= i || j >= n) {
111		✗	continue;
112			}
113
114		✗	const bool ascending = (i & step) == 0;
115		✗	const bool need_swap = ascending ? result[i] > result[j] : result[i] < result[j];
116		✗	if (need_swap) {
117			std::swap(result[i], result[j]);
118			}
119			}
120		✗	}
121
122		✗	void TitaevSortirovkaBetcheraSEQ::BatcherSort() {
123			auto &result = GetOutput();
124			const size_t n = result.size();
125
126		✗	for (size_t step = 1; step < n; step <<= 1) {
127		✗	for (size_t stage = step; stage > 0; stage >>= 1) {
128		✗	BatcherStep(result, n, step, stage);
129			}
130			}
131		✗	}
132
133		✗	bool TitaevSortirovkaBetcheraSEQ::RunImpl() {
134			auto &input = GetInput();
135			const size_t n = input.size();
136		✗	if (n <= 1) {
137			return true;
138			}
139
140		✗	std::vector<uint64_t> keys(n);
141			ConvertToKeys(input, keys);
142		✗	RadixSort(keys);
143
144		✗	ConvertFromKeys(keys, GetOutput());
145
146		✗	if ((n & (n - 1)) == 0) {
147		✗	BatcherSort();
148			}
149
150			return true;
151			}
152
153		✗	bool TitaevSortirovkaBetcheraSEQ::PostProcessingImpl() {
154		✗	return true;
155			}
156
157			} // namespace titaev_m_sortirovka_betchera
158