GCC Code Coverage Report

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