GCC Code Coverage Report

Line	Branch	Exec	Source
1			#include "shkryleva_s_shell_sort_simple_merge/stl/include/ops_stl.hpp"
2
3			#include <algorithm>
4			#include <cstddef>
5			#include <thread>
6			#include <vector>
7
8			#include "shkryleva_s_shell_sort_simple_merge/common/include/common.hpp"
9
10			namespace shkryleva_s_shell_sort_simple_merge {
11
12		✗	ShkrylevaSShellMergeSTL::ShkrylevaSShellMergeSTL(const InType &in) {
13			SetTypeOfTask(GetStaticTypeOfTask());
14		✗	GetInput() = in;
15			GetOutput() = {};
16		✗	}
17
18		✗	bool ShkrylevaSShellMergeSTL::ValidationImpl() {
19		✗	return true;
20			}
21
22		✗	bool ShkrylevaSShellMergeSTL::PreProcessingImpl() {
23		✗	input_data_ = GetInput();
24			output_data_.clear();
25		✗	return true;
26			}
27
28		✗	void ShkrylevaSShellMergeSTL::ShellSort(int left, int right, std::vector<int> &arr) {
29		✗	int sub_array_size = right - left + 1;
30			int gap = 1;
31		✗	while (gap <= sub_array_size / 3) {
32		✗	gap = (gap * 3) + 1;
33			}
34		✗	for (; gap > 0; gap /= 3) {
35		✗	for (int i = left + gap; i <= right; ++i) {
36		✗	int temp = arr[i];
37			int j = i;
38		✗	while (j >= left + gap && arr[j - gap] > temp) {
39		✗	arr[j] = arr[j - gap];
40			j -= gap;
41			}
42		✗	arr[j] = temp;
43			}
44			}
45		✗	}
46
47		✗	void ShkrylevaSShellMergeSTL::Merge(int left, int mid, int right, std::vector<int> &arr, std::vector<int> &buffer) {
48			int i = left;
49		✗	int j = mid + 1;
50			int k = 0;
51		✗	int merge_size = right - left + 1;
52		✗	if (static_cast<std::size_t>(merge_size) > buffer.size()) {
53		✗	buffer.resize(static_cast<std::size_t>(merge_size));
54			}
55		✗	while (i <= mid || j <= right) {
56		✗	if (i > mid) {
57		✗	buffer[k++] = arr[j++];
58		✗	} else if (j > right) {
59		✗	buffer[k++] = arr[i++];
60			} else {
61		✗	buffer[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
62			}
63			}
64		✗	for (int idx = 0; idx < k; ++idx) {
65		✗	arr[left + idx] = buffer[idx];
66			}
67		✗	}
68
69		✗	void ShkrylevaSShellMergeSTL::SortSegments(std::vector<int> &arr, int num_threads, int sub_arr_size) {
70		✗	std::vector<std::thread> threads;
71		✗	for (int i = 0; i < num_threads; ++i) {
72		✗	int left = i * sub_arr_size;
73		✗	int right = std::min(left + sub_arr_size - 1, static_cast<int>(arr.size()) - 1);
74		✗	if (left < right) {
75		✗	threads.emplace_back([&arr, left, right] { ShellSort(left, right, arr); });
76			}
77			}
78		✗	for (auto &t : threads) {
79		✗	if (t.joinable()) {
80		✗	t.join();
81			}
82			}
83		✗	}
84
85		✗	void ShkrylevaSShellMergeSTL::HierarchicalMerge(std::vector<int> &arr, int num_threads, int sub_arr_size) {
86		✗	while (num_threads > 1) {
87		✗	int new_num_threads = (num_threads + 1) / 2;
88		✗	std::vector<std::thread> threads;
89		✗	for (int i = 0; i < new_num_threads; ++i) {
90		✗	int left = i * 2 * sub_arr_size;
91		✗	int mid = std::min(left + sub_arr_size - 1, static_cast<int>(arr.size()) - 1);
92		✗	int right = std::min(left + (2 * sub_arr_size) - 1, static_cast<int>(arr.size()) - 1);
93		✗	if (mid < right) {
94		✗	threads.emplace_back([&arr, left, mid, right] {
95		✗	std::vector<int> local_buffer;
96		✗	Merge(left, mid, right, arr, local_buffer);
97		✗	});
98			}
99			}
100		✗	for (auto &t : threads) {
101		✗	if (t.joinable()) {
102		✗	t.join();
103			}
104			}
105		✗	sub_arr_size *= 2;
106			num_threads = new_num_threads;
107		✗	}
108		✗	}
109
110		✗	bool ShkrylevaSShellMergeSTL::RunImpl() {
111		✗	if (input_data_.empty()) {
112			output_data_.clear();
113		✗	return true;
114			}
115
116		✗	std::vector<int> arr = input_data_;
117		✗	const int array_size = static_cast<int>(arr.size());
118
119		✗	unsigned int hardware_threads = std::thread::hardware_concurrency();
120		✗	int num_threads = (hardware_threads > 0) ? static_cast<int>(hardware_threads) : 1;
121		✗	num_threads = std::min(num_threads, array_size);
122
123		✗	int sub_arr_size = (array_size + num_threads - 1) / num_threads;
124
125		✗	SortSegments(arr, num_threads, sub_arr_size);
126		✗	HierarchicalMerge(arr, num_threads, sub_arr_size);
127
128		✗	output_data_ = arr;
129			return true;
130			}
131
132		✗	bool ShkrylevaSShellMergeSTL::PostProcessingImpl() {
133		✗	GetOutput() = output_data_;
134		✗	return true;
135			}
136
137			} // namespace shkryleva_s_shell_sort_simple_merge
138