GCC Code Coverage Report

Directory: ./
File: tasks/rozenberg_a_quicksort_simple_merge/stl/src/ops_stl.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 76 76 100.0%
Functions: 10 10 100.0%
Branches: 58 76 76.3%
Line Branch Exec Source
1 #include "rozenberg_a_quicksort_simple_merge/stl/include/ops_stl.hpp"
2
3 #include <stack>
4 #include <thread>
5 #include <utility>
6 #include <vector>
7
8 #include "rozenberg_a_quicksort_simple_merge/common/include/common.hpp"
9
10 namespace rozenberg_a_quicksort_simple_merge {
11
12 72 RozenbergAQuicksortSimpleMergeSTL::RozenbergAQuicksortSimpleMergeSTL(const InType &in) {
13 SetTypeOfTask(GetStaticTypeOfTask());
14
15 InType empty;
16 GetInput().swap(empty);
17
18
2/2
✓ Branch 0 taken 5416 times.
✓ Branch 1 taken 72 times.
 5488 for (const auto &elem : in) {
19 GetInput().push_back(elem);
20 }
21
22 GetOutput().clear();
23 72 }
24
25
1/2
✓ Branch 0 taken 72 times.
✗ Branch 1 not taken.
 72 bool RozenbergAQuicksortSimpleMergeSTL::ValidationImpl() {
26
2/4
✓ Branch 0 taken 72 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 72 times.
 72 return (!(GetInput().empty())) && (GetOutput().empty());
27 }
28
29 72 bool RozenbergAQuicksortSimpleMergeSTL::PreProcessingImpl() {
30 72 GetOutput().resize(GetInput().size());
31 72 return GetOutput().size() == GetInput().size();
32 }
33
34 4392 std::pair<int, int> RozenbergAQuicksortSimpleMergeSTL::Partition(InType &data, int left, int right) {
35 4392 const int pivot = data[left + ((right - left) / 2)];
36 int i = left;
37 int j = right;
38
39
2/2
✓ Branch 0 taken 11160 times.
✓ Branch 1 taken 4392 times.
 19944 while (i <= j) {
40
2/2
✓ Branch 0 taken 10872 times.
✓ Branch 1 taken 11160 times.
 22032 while (data[i] < pivot) {
41 10872 i++;
42 }
43
2/2
✓ Branch 0 taken 10056 times.
✓ Branch 1 taken 11160 times.
 21216 while (data[j] > pivot) {
44 10056 j--;
45 }
46
47
2/2
✓ Branch 0 taken 1248 times.
✓ Branch 1 taken 9912 times.
 11160 if (i <= j) {
48 std::swap(data[i], data[j]);
49 9912 i++;
50 9912 j--;
51 }
52 }
53 4392 return {i, j};
54 }
55
56 4392 void RozenbergAQuicksortSimpleMergeSTL::PushSubarrays(std::stack<std::pair<int, int>> &stack, int left, int right,
57 int i, int j) {
58
2/2
✓ Branch 0 taken 960 times.
✓ Branch 1 taken 3432 times.
 4392 if (j - left > right - i) {
59
1/2
✓ Branch 0 taken 960 times.
✗ Branch 1 not taken.
 960 if (left < j) {
60 stack.emplace(left, j);
61 }
62
2/2
✓ Branch 0 taken 504 times.
✓ Branch 1 taken 456 times.
 960 if (i < right) {
63 stack.emplace(i, right);
64 }
65 } else {
66
2/2
✓ Branch 0 taken 1704 times.
✓ Branch 1 taken 1728 times.
 3432 if (i < right) {
67 stack.emplace(i, right);
68 }
69
2/2
✓ Branch 0 taken 1064 times.
✓ Branch 1 taken 2368 times.
 3432 if (left < j) {
70 stack.emplace(left, j);
71 }
72 }
73 4392 }
74
75 168 void RozenbergAQuicksortSimpleMergeSTL::Quicksort(InType &data, int low, int high) {
76
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 160 times.
 168 if (low >= high) {
77 8 return;
78 }
79
80 std::stack<std::pair<int, int>> stack;
81
82 stack.emplace(low, high);
83
84
2/2
✓ Branch 0 taken 4392 times.
✓ Branch 1 taken 160 times.
 4552 while (!stack.empty()) {
85 const auto [left, right] = stack.top();
86 stack.pop();
87
88
1/2
✓ Branch 0 taken 4392 times.
✗ Branch 1 not taken.
 4392 if (left < right) {
89 4392 const auto [i, j] = Partition(data, left, right);
90
1/2
✓ Branch 1 taken 4392 times.
✗ Branch 2 not taken.
 4392 PushSubarrays(stack, left, right, i, j);
91 }
92 }
93 }
94
95 96 void RozenbergAQuicksortSimpleMergeSTL::Merge(InType &data, int left, int mid, int right) {
96 96 std::vector<int> temp(right - left + 1);
97 int i = left;
98 96 int j = mid + 1;
99 int k = 0;
100
101
2/2
✓ Branch 0 taken 11128 times.
✓ Branch 1 taken 96 times.
 11224 while (i <= mid && j <= right) {
102
2/2
✓ Branch 0 taken 7792 times.
✓ Branch 1 taken 3336 times.
 11128 if (data[i] <= data[j]) {
103 7792 temp[k++] = data[i++];
104 } else {
105 3336 temp[k++] = data[j++];
106 }
107 }
108
109
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 96 times.
 176 while (i <= mid) {
110 80 temp[k++] = data[i++];
111 }
112
2/2
✓ Branch 0 taken 632 times.
✓ Branch 1 taken 96 times.
 728 while (j <= right) {
113 632 temp[k++] = data[j++];
114 }
115
116
2/2
✓ Branch 0 taken 11840 times.
✓ Branch 1 taken 96 times.
 11936 for (int idx = 0; idx < k; ++idx) {
117 11840 data[left + idx] = temp[idx];
118 }
119 96 }
120
121 72 bool RozenbergAQuicksortSimpleMergeSTL::RunImpl() {
122 72 InType data = GetInput();
123 72 int n = static_cast<int>(data.size());
124
125 72 int num_threads = static_cast<int>(std::thread::hardware_concurrency());
126
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 72 times.
 72 if (num_threads == 0) {
127 num_threads = 2;
128 }
129
130
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 32 times.
 72 if (n < num_threads * 2) {
131
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 Quicksort(data, 0, n - 1);
132
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 GetOutput() = data;
133 return true;
134 }
135
136 // Create chunk borders container
137 32 std::vector<std::thread> threads;
138
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 threads.reserve(num_threads);
139
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 std::vector<int> borders(num_threads + 1);
140 32 int chunk_size = n / num_threads;
141
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 32 times.
 160 for (int i = 0; i < num_threads; i++) {
142 128 borders[i] = i * chunk_size;
143 }
144 32 borders[num_threads] = n;
145
146 // Sort local chunks
147
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 32 times.
 160 for (int i = 0; i < num_threads; i++) {
148
1/4
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 128 threads.emplace_back([&data, &borders, i]() {
149 128 rozenberg_a_quicksort_simple_merge::RozenbergAQuicksortSimpleMergeSTL::Quicksort(data, borders[i],
150 128 borders[i + 1] - 1);
151 128 });
152 }
153
154
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 32 times.
 160 for (auto &t : threads) {
155
1/2
✓ Branch 0 taken 128 times.
✗ Branch 1 not taken.
 128 if (t.joinable()) {
156
1/2
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
 128 t.join();
157 }
158 }
159
160 // Merge sorted chunks
161
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 32 times.
 128 for (int i = 1; i < num_threads; i++) {
162
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 Merge(data, 0, borders[i] - 1, borders[i + 1] - 1);
163 }
164
165
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 GetOutput() = data;
166 return true;
167 32 }
168
169 72 bool RozenbergAQuicksortSimpleMergeSTL::PostProcessingImpl() {
170 72 return true;
171 }
172
173 } // namespace rozenberg_a_quicksort_simple_merge
174