GCC Code Coverage Report

Directory: ./
File: tasks/tsarkov_k_jarvis_convex_hull/all/src/ops_all.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 124 128 96.9%
Functions: 17 17 100.0%
Branches: 66 96 68.8%
Line Branch Exec Source
1 #include "tsarkov_k_jarvis_convex_hull/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4 #include <omp.h>
5
6 #include <algorithm>
7 #include <cstddef>
8 #include <cstdint>
9 #include <ranges>
10 #include <thread>
11 #include <vector>
12
13 #include "oneapi/tbb/blocked_range.h"
14 #include "oneapi/tbb/parallel_reduce.h"
15 #include "tsarkov_k_jarvis_convex_hull/common/include/common.hpp"
16 #include "util/include/util.hpp"
17
18 namespace tsarkov_k_jarvis_convex_hull {
19
20 namespace {
21
22 struct BestPointState {
23 std::size_t point_index = 0;
24 bool is_initialized = false;
25 };
26
27 std::int64_t CrossProduct(const Point &first_point, const Point &second_point, const Point &third_point) {
28 106 const std::int64_t vector_first_x =
29 106 static_cast<std::int64_t>(second_point.x) - static_cast<std::int64_t>(first_point.x);
30 106 const std::int64_t vector_first_y =
31 106 static_cast<std::int64_t>(second_point.y) - static_cast<std::int64_t>(first_point.y);
32 106 const std::int64_t vector_second_x =
33 106 static_cast<std::int64_t>(third_point.x) - static_cast<std::int64_t>(first_point.x);
34 106 const std::int64_t vector_second_y =
35 106 static_cast<std::int64_t>(third_point.y) - static_cast<std::int64_t>(first_point.y);
36
37 106 return (vector_first_x * vector_second_y) - (vector_first_y * vector_second_x);
38 }
39
40 std::int64_t SquaredDistance(const Point &first_point, const Point &second_point) {
41 const std::int64_t delta_x = static_cast<std::int64_t>(second_point.x) - static_cast<std::int64_t>(first_point.x);
42 const std::int64_t delta_y = static_cast<std::int64_t>(second_point.y) - static_cast<std::int64_t>(first_point.y);
43
44 26 return (delta_x * delta_x) + (delta_y * delta_y);
45 }
46
47 142 bool PointLess(const Point &first_point, const Point &second_point) {
48
2/2
✓ Branch 0 taken 110 times.
✓ Branch 1 taken 32 times.
 142 if (first_point.x != second_point.x) {
49 110 return first_point.x < second_point.x;
50 }
51 32 return first_point.y < second_point.y;
52 }
53
54 14 std::vector<Point> RemoveDuplicatePoints(const std::vector<Point> &input_points) {
55 14 std::vector<Point> unique_points = input_points;
56
57 std::ranges::sort(unique_points, PointLess);
58 unique_points.erase(std::ranges::unique(unique_points).begin(), unique_points.end());
59
60 14 return unique_points;
61 }
62
63 10 std::size_t FindLeftmostPointIndex(const std::vector<Point> &input_points) {
64 std::size_t leftmost_point_index = 0;
65
66
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 10 times.
 50 for (std::size_t point_index = 1; point_index < input_points.size(); ++point_index) {
67 const Point &current_point = input_points[point_index];
68 const Point &leftmost_point = input_points[leftmost_point_index];
69
70
3/4
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 36 times.
✓ Branch 3 taken 4 times.
 40 if ((current_point.x < leftmost_point.x) ||
71
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 ((current_point.x == leftmost_point.x) && (current_point.y < leftmost_point.y))) {
72 leftmost_point_index = point_index;
73 }
74 }
75
76 10 return leftmost_point_index;
77 }
78
79 106 bool ShouldReplaceBestPoint(const std::vector<Point> &unique_points, std::size_t current_point_index,
80 std::size_t best_point_index, std::size_t candidate_point_index) {
81
1/2
✓ Branch 0 taken 106 times.
✗ Branch 1 not taken.
 106 if (candidate_point_index == current_point_index) {
82 return false;
83 }
84
85 const std::int64_t orientation = CrossProduct(unique_points[current_point_index], unique_points[best_point_index],
86 unique_points[candidate_point_index]);
87
88
2/2
✓ Branch 0 taken 68 times.
✓ Branch 1 taken 38 times.
 106 if (orientation < 0) {
89 return true;
90 }
91
92
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 42 times.
 68 if (orientation == 0) {
93 const std::int64_t best_distance =
94 SquaredDistance(unique_points[current_point_index], unique_points[best_point_index]);
95 const std::int64_t candidate_distance =
96 SquaredDistance(unique_points[current_point_index], unique_points[candidate_point_index]);
97
98 26 return candidate_distance > best_distance;
99 }
100
101 return false;
102 }
103
104 346 BestPointState SelectBetterState(const std::vector<Point> &unique_points, std::size_t current_point_index,
105 const BestPointState &first_state, const BestPointState &second_state) {
106
2/2
✓ Branch 0 taken 234 times.
✓ Branch 1 taken 112 times.
 346 if (!first_state.is_initialized) {
107 234 return second_state;
108 }
109
110
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 106 times.
 112 if (!second_state.is_initialized) {
111 6 return first_state;
112 }
113
114
2/2
✓ Branch 0 taken 50 times.
✓ Branch 1 taken 56 times.
 106 if (ShouldReplaceBestPoint(unique_points, current_point_index, first_state.point_index, second_state.point_index)) {
115 50 return second_state;
116 }
117
118 56 return first_state;
119 }
120
121 104 BestPointState FindBestStateInRange(const std::vector<Point> &unique_points, std::size_t current_point_index,
122 std::size_t range_begin, std::size_t range_end) {
123 104 BestPointState local_best_state;
124
125
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 104 times.
 208 for (std::size_t point_index = range_begin; point_index < range_end; ++point_index) {
126
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 86 times.
 104 if (point_index == current_point_index) {
127 18 continue;
128 }
129
130 86 const BestPointState candidate_state{.point_index = point_index, .is_initialized = true};
131 86 local_best_state = SelectBetterState(unique_points, current_point_index, local_best_state, candidate_state);
132 }
133
134 104 return local_best_state;
135 }
136
137 34 BestPointState FindBestStateOMP(const std::vector<Point> &unique_points, std::size_t current_point_index,
138 std::size_t range_begin, std::size_t range_end) {
139 34 const auto range_size = range_end - range_begin;
140
141
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 34 times.
 34 if (range_size == 0) {
142 ✗ return BestPointState{};
143 }
144
145 34 const auto requested_thread_count = static_cast<std::size_t>(ppc::util::GetNumThreads());
146 const auto actual_thread_count = std::min(requested_thread_count, range_size);
147 34 const auto actual_thread_count_int = static_cast<int>(actual_thread_count);
148 34 const auto chunk_size = (range_size + actual_thread_count - 1) / actual_thread_count;
149
150 34 std::vector<BestPointState> local_best_states(actual_thread_count);
151
152 34 #pragma omp parallel for default(none) schedule(static) num_threads(actual_thread_count_int) \
153 shared(unique_points, current_point_index, range_begin, range_end, chunk_size, local_best_states, \
154 actual_thread_count_int)
155 for (int thread_index = 0; thread_index < actual_thread_count_int; ++thread_index) {
156 const auto current_thread_index = static_cast<std::size_t>(thread_index);
157 const std::size_t thread_range_begin = range_begin + (current_thread_index * chunk_size);
158 const std::size_t thread_range_end = std::min(thread_range_begin + chunk_size, range_end);
159
160 local_best_states[current_thread_index] =
161 FindBestStateInRange(unique_points, current_point_index, thread_range_begin, thread_range_end);
162 }
163
164 34 BestPointState best_state;
165
166
2/2
✓ Branch 0 taken 42 times.
✓ Branch 1 taken 34 times.
 76 for (const BestPointState &local_best_state : local_best_states) {
167 42 best_state = SelectBetterState(unique_points, current_point_index, best_state, local_best_state);
168 }
169
170
1/2
✓ Branch 0 taken 34 times.
✗ Branch 1 not taken.
 34 return best_state;
171 }
172
173 34 BestPointState FindBestStateSTL(const std::vector<Point> &unique_points, std::size_t current_point_index,
174 std::size_t range_begin, std::size_t range_end) {
175 34 const auto range_size = range_end - range_begin;
176
177
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 34 times.
 34 if (range_size == 0) {
178 ✗ return BestPointState{};
179 }
180
181 34 const auto requested_thread_count = static_cast<std::size_t>(ppc::util::GetNumThreads());
182 const auto actual_thread_count = std::min(requested_thread_count, range_size);
183 34 const auto chunk_size = (range_size + actual_thread_count - 1) / actual_thread_count;
184
185 34 std::vector<std::thread> worker_threads(actual_thread_count);
186
1/2
✓ Branch 1 taken 34 times.
✗ Branch 2 not taken.
 34 std::vector<BestPointState> local_best_states(actual_thread_count);
187
188
2/2
✓ Branch 0 taken 62 times.
✓ Branch 1 taken 34 times.
 96 for (std::size_t thread_index = 0; thread_index < actual_thread_count; ++thread_index) {
189 62 const std::size_t thread_range_begin = range_begin + (thread_index * chunk_size);
190
1/2
✓ Branch 1 taken 62 times.
✗ Branch 2 not taken.
 62 const std::size_t thread_range_end = std::min(thread_range_begin + chunk_size, range_end);
191
192
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 62 worker_threads[thread_index] = std::thread([&unique_points, &local_best_states, current_point_index,
193 thread_range_begin, thread_range_end, thread_index]() {
194 62 local_best_states[thread_index] =
195 62 FindBestStateInRange(unique_points, current_point_index, thread_range_begin, thread_range_end);
196
1/2
✓ Branch 1 taken 62 times.
✗ Branch 2 not taken.
 62 });
197 }
198
199
2/2
✓ Branch 0 taken 62 times.
✓ Branch 1 taken 34 times.
 96 for (std::thread &worker_thread : worker_threads) {
200
1/2
✓ Branch 0 taken 62 times.
✗ Branch 1 not taken.
 62 if (worker_thread.joinable()) {
201
1/2
✓ Branch 1 taken 62 times.
✗ Branch 2 not taken.
 62 worker_thread.join();
202 }
203 }
204
205 34 BestPointState best_state;
206
207
2/2
✓ Branch 0 taken 62 times.
✓ Branch 1 taken 34 times.
 96 for (const BestPointState &local_best_state : local_best_states) {
208 62 best_state = SelectBetterState(unique_points, current_point_index, best_state, local_best_state);
209 }
210
211
1/2
✓ Branch 0 taken 34 times.
✗ Branch 1 not taken.
 34 return best_state;
212 34 }
213
214 34 BestPointState FindBestStateTBB(const std::vector<Point> &unique_points, std::size_t current_point_index,
215 std::size_t range_begin, std::size_t range_end) {
216
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 34 times.
 34 if (range_begin == range_end) {
217 ✗ return BestPointState{};
218 }
219
220 return oneapi::tbb::parallel_reduce(
221 68 oneapi::tbb::blocked_range<std::size_t>(range_begin, range_end), BestPointState{},
222 70 [&](const oneapi::tbb::blocked_range<std::size_t> &point_range, BestPointState local_best_state) {
223
2/2
✓ Branch 0 taken 70 times.
✓ Branch 1 taken 70 times.
 140 for (std::size_t point_index = point_range.begin(); point_index < point_range.end(); ++point_index) {
224
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 54 times.
 70 if (point_index == current_point_index) {
225 16 continue;
226 }
227
228 54 const BestPointState candidate_state{.point_index = point_index, .is_initialized = true};
229 54 local_best_state = SelectBetterState(unique_points, current_point_index, local_best_state, candidate_state);
230 }
231
232 70 return local_best_state;
233 34 }, [&](const BestPointState &first_state, const BestPointState &second_state) {
234 ✗ return SelectBetterState(unique_points, current_point_index, first_state, second_state);
235 });
236 }
237
238 34 std::size_t FindNextHullPointIndexALL(const std::vector<Point> &unique_points, std::size_t current_point_index) {
239 const auto point_count = unique_points.size();
240 34 const auto first_border = point_count / 3;
241 34 const auto second_border = (2 * point_count) / 3;
242
243 34 const BestPointState omp_best_state = FindBestStateOMP(unique_points, current_point_index, 0, first_border);
244 const BestPointState stl_best_state =
245 34 FindBestStateSTL(unique_points, current_point_index, first_border, second_border);
246 const BestPointState tbb_best_state =
247 34 FindBestStateTBB(unique_points, current_point_index, second_border, point_count);
248
249 34 BestPointState result_state;
250 34 result_state = SelectBetterState(unique_points, current_point_index, result_state, omp_best_state);
251 34 result_state = SelectBetterState(unique_points, current_point_index, result_state, stl_best_state);
252 34 result_state = SelectBetterState(unique_points, current_point_index, result_state, tbb_best_state);
253
254 34 return result_state.point_index;
255 }
256
257 } // namespace
258
259
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 TsarkovKJarvisConvexHullALL::TsarkovKJarvisConvexHullALL(const InType &input_points) {
260 SetTypeOfTask(GetStaticTypeOfTask());
261
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 GetInput() = input_points;
262 GetOutput().clear();
263 14 }
264
265
1/2
✓ Branch 0 taken 14 times.
✗ Branch 1 not taken.
 14 bool TsarkovKJarvisConvexHullALL::ValidationImpl() {
266
2/4
✓ Branch 0 taken 14 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 14 times.
 14 return !GetInput().empty() && GetOutput().empty();
267 }
268
269
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 14 times.
 14 bool TsarkovKJarvisConvexHullALL::PreProcessingImpl() {
270 GetOutput().clear();
271 14 return true;
272 }
273
274 14 bool TsarkovKJarvisConvexHullALL::RunImpl() {
275 14 int rank = -1;
276 14 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
277
278 14 const std::vector<Point> unique_points = RemoveDuplicatePoints(GetInput());
279
280
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 14 times.
 14 if (unique_points.empty()) {
281 return false;
282 }
283
284
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 12 times.
 14 if (unique_points.size() == 1) {
285
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 GetOutput() = unique_points;
286
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 MPI_Barrier(MPI_COMM_WORLD);
287 return true;
288 }
289
290
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 10 times.
 12 if (unique_points.size() == 2) {
291
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 GetOutput() = unique_points;
292
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 MPI_Barrier(MPI_COMM_WORLD);
293 return true;
294 }
295
296 10 const auto start_point_index = FindLeftmostPointIndex(unique_points);
297 std::size_t current_point_index = start_point_index;
298
299 while (true) {
300 GetOutput().push_back(unique_points[current_point_index]);
301
302
1/2
✓ Branch 1 taken 34 times.
✗ Branch 2 not taken.
 34 current_point_index = FindNextHullPointIndexALL(unique_points, current_point_index);
303
304
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 10 times.
 34 if (current_point_index == start_point_index) {
305 break;
306 }
307 }
308
309
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 MPI_Barrier(MPI_COMM_WORLD);
310
311
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 10 times.
 10 return (rank >= 0) && !GetOutput().empty();
312 }
313
314 14 bool TsarkovKJarvisConvexHullALL::PostProcessingImpl() {
315 14 return true;
316 }
317
318 } // namespace tsarkov_k_jarvis_convex_hull
319