GCC Code Coverage Report

Directory: ./
File: tasks/kutuzov_i_convex_hull_jarvis/stl/src/ops_stl.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 89 104 85.6%
Functions: 10 13 76.9%
Branches: 56 78 71.8%
Line Branch Exec Source
1 #include "kutuzov_i_convex_hull_jarvis/stl/include/ops_stl.hpp"
2
3 #include <cmath>
4 #include <cstddef>
5 #include <limits>
6 #include <thread>
7 #include <vector>
8
9 #include "kutuzov_i_convex_hull_jarvis/common/include/common.hpp"
10
11 namespace kutuzov_i_convex_hull_jarvis {
12
13 namespace {
14
15 struct BestCandidate {
16 size_t index;
17 double x;
18 double y;
19 };
20
21 inline unsigned GetNumThreads() {
22 48 const unsigned hw = std::thread::hardware_concurrency();
23 48 return (hw == 0) ? 1 : hw;
24 }
25
26 inline double DistanceSquared(double a_x, double a_y, double b_x, double b_y) {
27 56 return ((a_x - b_x) * (a_x - b_x)) + ((a_y - b_y) * (a_y - b_y));
28 }
29
30 inline double CrossProduct(double o_x, double o_y, double a_x, double a_y, double b_x, double b_y) {
31 ✗ return ((a_x - o_x) * (b_y - o_y)) - ((a_y - o_y) * (b_x - o_x));
32 }
33
34 BestCandidate FindLeftmostInRange(const InType &points, size_t start, size_t end) {
35 size_t best_idx = start;
36 96 double best_x = std::get<0>(points[start]);
37 96 double best_y = std::get<1>(points[start]);
38
39
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 96 times.
 160 for (size_t i = start + 1; i < end; ++i) {
40 64 double px = std::get<0>(points[i]);
41 64 double py = std::get<1>(points[i]);
42
3/6
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 40 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 64 if ((px < best_x) || (px == best_x && py < best_y)) {
43 best_x = px;
44 best_y = py;
45 best_idx = i;
46 }
47 }
48
49 return {.index = best_idx, .x = best_x, .y = best_y};
50 }
51
52 288 BestCandidate FindBestCandidateInRange(const InType &points, size_t start, size_t end, size_t current_idx,
53 double current_x, double current_y, double epsilon) {
54 288 BestCandidate best{.index = current_idx, .x = current_x, .y = current_y};
55
56
2/2
✓ Branch 0 taken 496 times.
✓ Branch 1 taken 288 times.
 784 for (size_t i = start; i < end; ++i) {
57
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 424 times.
 496 if (i == current_idx) {
58 72 continue;
59 }
60
61 const auto &p = points[i];
62 424 double px = std::get<0>(p);
63 424 double py = std::get<1>(p);
64
65 424 double cross = ((best.x - current_x) * (py - current_y)) - ((best.y - current_y) * (px - current_x));
66
67
4/4
✓ Branch 0 taken 384 times.
✓ Branch 1 taken 40 times.
✓ Branch 2 taken 312 times.
✓ Branch 3 taken 72 times.
 424 if (cross < -epsilon ||
68 312 (std::abs(cross) < epsilon &&
69 312 ((px - current_x) * (px - current_x)) + ((py - current_y) * (py - current_y)) >
70
2/2
✓ Branch 0 taken 296 times.
✓ Branch 1 taken 16 times.
 312 ((best.x - current_x) * (best.x - current_x)) + ((best.y - current_y) * (best.y - current_y)))) {
71 336 best.index = i;
72 336 best.x = px;
73 336 best.y = py;
74 }
75 }
76
77 288 return best;
78 }
79
80 72 BestCandidate FindGlobalBest(const std::vector<BestCandidate> &locals, size_t current_idx, double current_x,
81 double current_y, double epsilon) {
82 72 size_t global_idx = locals[0].index;
83 72 double global_x = locals[0].x;
84 72 double global_y = locals[0].y;
85
86
2/2
✓ Branch 0 taken 216 times.
✓ Branch 1 taken 72 times.
 288 for (size_t i = 1; i < locals.size(); ++i) {
87
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 216 times.
 216 if (locals[i].index == current_idx) {
88 ✗ continue;
89 }
90
91 double cross =
92 216 ((global_x - current_x) * (locals[i].y - current_y)) - ((global_y - current_y) * (locals[i].x - current_x));
93
94
4/4
✓ Branch 0 taken 168 times.
✓ Branch 1 taken 48 times.
✓ Branch 2 taken 112 times.
✓ Branch 3 taken 56 times.
 216 if (cross < -epsilon ||
95
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 32 times.
 56 (std::abs(cross) < epsilon && DistanceSquared(current_x, current_y, locals[i].x, locals[i].y) >
96 DistanceSquared(current_x, current_y, global_x, global_y))) {
97 global_idx = locals[i].index;
98 global_x = locals[i].x;
99 global_y = locals[i].y;
100 }
101 }
102
103 72 return {.index = global_idx, .x = global_x, .y = global_y};
104 }
105
106 } // anonymous namespace
107
108
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 KutuzovITestConvexHullSTL::KutuzovITestConvexHullSTL(const InType &in) {
109 SetTypeOfTask(GetStaticTypeOfTask());
110
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 GetInput() = in;
111 GetOutput() = {};
112 24 }
113
114 ✗ double KutuzovITestConvexHullSTL::DistanceSquared(double a_x, double a_y, double b_x, double b_y) {
115 ✗ return kutuzov_i_convex_hull_jarvis::DistanceSquared(a_x, a_y, b_x, b_y);
116 }
117
118 ✗ double KutuzovITestConvexHullSTL::CrossProduct(double o_x, double o_y, double a_x, double a_y, double b_x, double b_y) {
119 ✗ return kutuzov_i_convex_hull_jarvis::CrossProduct(o_x, o_y, a_x, a_y, b_x, b_y);
120 }
121
122 24 size_t KutuzovITestConvexHullSTL::FindLeftmostPoint(const InType &input) {
123 const size_t n = input.size();
124 const unsigned num_threads = GetNumThreads();
125
126 24 std::vector<BestCandidate> locals(num_threads);
127
128 24 std::vector<std::thread> threads;
129
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 threads.reserve(num_threads);
130
131
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 24 times.
 120 for (unsigned tid = 0; tid < num_threads; ++tid) {
132 96 size_t start = (tid * n) / num_threads;
133 96 size_t end = ((tid + 1) * n) / num_threads;
134
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 96 times.
 96 if (start >= end) {
135 ✗ locals[tid] = {.index = 0, .x = std::numeric_limits<double>::max(), .y = 0.0};
136 ✗ continue;
137 }
138
139
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 192 threads.emplace_back([&, tid, start, end]() { locals[tid] = FindLeftmostInRange(input, start, end); });
140 }
141
142
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 24 times.
 120 for (auto &t : threads) {
143
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 t.join();
144 }
145
146 size_t global_idx = 0;
147 double global_x = std::numeric_limits<double>::max();
148 double global_y = 0.0;
149
150
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 24 times.
 120 for (unsigned i = 0; i < num_threads; ++i) {
151
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 32 times.
 96 if (locals[i].x > global_x) {
152 64 continue;
153 }
154
4/6
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 8 times.
 32 if (locals[i].x < global_x || (locals[i].x == global_x && locals[i].y < global_y)) {
155 24 global_idx = locals[i].index;
156 global_x = locals[i].x;
157 24 global_y = locals[i].y;
158 }
159 }
160
161 24 return global_idx;
162 24 }
163
164 ✗ bool KutuzovITestConvexHullSTL::IsBetterPoint(double cross, double epsilon, double current_x, double current_y,
165 double i_x, double i_y, double next_x, double next_y) {
166 ✗ if (cross < -epsilon) {
167 return true;
168 }
169 ✗ if (std::abs(cross) < epsilon) {
170 ✗ return DistanceSquared(current_x, current_y, i_x, i_y) > DistanceSquared(current_x, current_y, next_x, next_y);
171 }
172 return false;
173 }
174
175 24 bool KutuzovITestConvexHullSTL::ValidationImpl() {
176 24 return true;
177 }
178 24 bool KutuzovITestConvexHullSTL::PreProcessingImpl() {
179 24 return true;
180 }
181
182
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 bool KutuzovITestConvexHullSTL::RunImpl() {
183 const auto &points = GetInput();
184
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (points.size() < 3) {
185 ✗ GetOutput() = points;
186 ✗ return true;
187 }
188
189 auto &output = GetOutput();
190 output.clear();
191
192 24 const double epsilon = 1e-9;
193 const size_t n = points.size();
194
195 24 const size_t leftmost_idx = FindLeftmostPoint(points);
196
197 const unsigned num_threads = GetNumThreads();
198 24 std::vector<BestCandidate> locals(num_threads);
199
200 24 size_t current_idx = leftmost_idx;
201 24 double current_x = std::get<0>(points[current_idx]);
202 24 double current_y = std::get<1>(points[current_idx]);
203
204 while (true) {
205
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 64 times.
 72 output.push_back(points[current_idx]);
206
207 72 std::vector<std::thread> threads;
208
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 threads.reserve(num_threads);
209
210
2/2
✓ Branch 0 taken 288 times.
✓ Branch 1 taken 72 times.
 360 for (unsigned tid = 0; tid < num_threads; ++tid) {
211 288 size_t start = (tid * n) / num_threads;
212 288 size_t end = ((tid + 1) * n) / num_threads;
213
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 288 times.
 288 if (start >= end) {
214 ✗ continue;
215 }
216
217
1/2
✓ Branch 1 taken 288 times.
✗ Branch 2 not taken.
 288 threads.emplace_back([&, tid, start, end]() {
218 288 locals[tid] = FindBestCandidateInRange(points, start, end, current_idx, current_x, current_y, epsilon);
219 288 });
220 }
221
222
2/2
✓ Branch 0 taken 288 times.
✓ Branch 1 taken 72 times.
 360 for (auto &t : threads) {
223
1/2
✓ Branch 1 taken 288 times.
✗ Branch 2 not taken.
 288 t.join();
224 }
225
226 72 BestCandidate global = FindGlobalBest(locals, current_idx, current_x, current_y, epsilon);
227
228 72 current_idx = global.index;
229 72 current_x = global.x;
230 72 current_y = global.y;
231
232
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 24 times.
 72 if (current_idx == leftmost_idx) {
233 break;
234 }
235 72 }
236
237 return true;
238 }
239
240 24 bool KutuzovITestConvexHullSTL::PostProcessingImpl() {
241 24 return true;
242 }
243
244 } // namespace kutuzov_i_convex_hull_jarvis
245