GCC Code Coverage Report

Directory: ./
File: tasks/tsarkov_k_jarvis_convex_hull/stl/src/ops_stl.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 69 69 100.0%
Functions: 11 11 100.0%
Branches: 49 68 72.1%
Line Branch Exec Source
1 #include "tsarkov_k_jarvis_convex_hull/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <cstdint>
6 #include <ranges>
7 #include <thread>
8 #include <vector>
9
10 #include "tsarkov_k_jarvis_convex_hull/common/include/common.hpp"
11 #include "util/include/util.hpp"
12
13 namespace tsarkov_k_jarvis_convex_hull {
14
15 namespace {
16
17 std::int64_t CrossProduct(const Point &first_point, const Point &second_point, const Point &third_point) {
18 894 const std::int64_t vector_first_x =
19 894 static_cast<std::int64_t>(second_point.x) - static_cast<std::int64_t>(first_point.x);
20 894 const std::int64_t vector_first_y =
21 894 static_cast<std::int64_t>(second_point.y) - static_cast<std::int64_t>(first_point.y);
22 894 const std::int64_t vector_second_x =
23 894 static_cast<std::int64_t>(third_point.x) - static_cast<std::int64_t>(first_point.x);
24 894 const std::int64_t vector_second_y =
25 894 static_cast<std::int64_t>(third_point.y) - static_cast<std::int64_t>(first_point.y);
26
27 894 return (vector_first_x * vector_second_y) - (vector_first_y * vector_second_x);
28 }
29
30 std::int64_t SquaredDistance(const Point &first_point, const Point &second_point) {
31 const std::int64_t delta_x = static_cast<std::int64_t>(second_point.x) - static_cast<std::int64_t>(first_point.x);
32 const std::int64_t delta_y = static_cast<std::int64_t>(second_point.y) - static_cast<std::int64_t>(first_point.y);
33
34 410 return (delta_x * delta_x) + (delta_y * delta_y);
35 }
36
37 568 bool PointLess(const Point &first_point, const Point &second_point) {
38
2/2
✓ Branch 0 taken 440 times.
✓ Branch 1 taken 128 times.
 568 if (first_point.x != second_point.x) {
39 440 return first_point.x < second_point.x;
40 }
41 128 return first_point.y < second_point.y;
42 }
43
44 56 std::vector<Point> RemoveDuplicatePoints(const std::vector<Point> &input_points) {
45 56 std::vector<Point> unique_points = input_points;
46
47 std::ranges::sort(unique_points, PointLess);
48 unique_points.erase(std::ranges::unique(unique_points).begin(), unique_points.end());
49
50 56 return unique_points;
51 }
52
53 40 std::size_t FindLeftmostPointIndex(const std::vector<Point> &input_points) {
54 std::size_t leftmost_point_index = 0;
55
56
2/2
✓ Branch 0 taken 160 times.
✓ Branch 1 taken 40 times.
 200 for (std::size_t point_index = 1; point_index < input_points.size(); ++point_index) {
57 const Point &current_point = input_points[point_index];
58 const Point &leftmost_point = input_points[leftmost_point_index];
59
60
3/4
✓ Branch 0 taken 160 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 144 times.
✓ Branch 3 taken 16 times.
 160 if ((current_point.x < leftmost_point.x) ||
61
1/2
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
 16 ((current_point.x == leftmost_point.x) && (current_point.y < leftmost_point.y))) {
62 leftmost_point_index = point_index;
63 }
64 }
65
66 40 return leftmost_point_index;
67 }
68
69 1030 bool ShouldReplaceBestPoint(const std::vector<Point> &unique_points, std::size_t current_point_index,
70 std::size_t best_point_index, std::size_t candidate_point_index) {
71
2/2
✓ Branch 0 taken 894 times.
✓ Branch 1 taken 136 times.
 1030 if (candidate_point_index == current_point_index) {
72 return false;
73 }
74
75 const std::int64_t orientation = CrossProduct(unique_points[current_point_index], unique_points[best_point_index],
76 unique_points[candidate_point_index]);
77
78
2/2
✓ Branch 0 taken 630 times.
✓ Branch 1 taken 264 times.
 894 if (orientation < 0) {
79 return true;
80 }
81
82
2/2
✓ Branch 0 taken 410 times.
✓ Branch 1 taken 220 times.
 630 if (orientation == 0) {
83 const std::int64_t best_distance =
84 SquaredDistance(unique_points[current_point_index], unique_points[best_point_index]);
85 const std::int64_t candidate_distance =
86 SquaredDistance(unique_points[current_point_index], unique_points[candidate_point_index]);
87
88 410 return candidate_distance > best_distance;
89 }
90
91 return false;
92 }
93
94 std::size_t FindThreadLocalBestIndex(const std::vector<Point> &unique_points, std::size_t current_point_index,
95 std::size_t initial_best_index, std::size_t range_begin, std::size_t range_end) {
96 std::size_t local_best_index = initial_best_index;
97
98
2/2
✓ Branch 0 taken 696 times.
✓ Branch 1 taken 334 times.
 1030 for (std::size_t point_index = range_begin; point_index < range_end; ++point_index) {
99
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 504 times.
 696 if (ShouldReplaceBestPoint(unique_points, current_point_index, local_best_index, point_index)) {
100 local_best_index = point_index;
101 }
102 }
103
104 return local_best_index;
105 }
106
107 std::size_t ReduceBestIndices(const std::vector<Point> &unique_points, std::size_t current_point_index,
108 std::size_t initial_best_index, const std::vector<std::size_t> &local_best_indices) {
109 std::size_t next_point_index = initial_best_index;
110
111
2/2
✓ Branch 0 taken 334 times.
✓ Branch 1 taken 136 times.
 470 for (std::size_t local_best_index : local_best_indices) {
112
2/2
✓ Branch 0 taken 134 times.
✓ Branch 1 taken 200 times.
 334 if (ShouldReplaceBestPoint(unique_points, current_point_index, next_point_index, local_best_index)) {
113 next_point_index = local_best_index;
114 }
115 }
116
117 return next_point_index;
118 }
119
120 136 std::size_t FindNextHullPointIndexSTL(const std::vector<Point> &unique_points, std::size_t current_point_index) {
121
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 40 times.
 232 const std::size_t initial_next_point_index = (current_point_index == 0) ? 1 : 0;
122 136 const auto point_count = unique_points.size();
123 136 const auto thread_count = static_cast<std::size_t>(ppc::util::GetNumThreads());
124 const auto actual_thread_count = std::min(thread_count, point_count);
125 136 const auto chunk_size = (point_count + actual_thread_count - 1) / actual_thread_count;
126
127 136 std::vector<std::thread> threads(actual_thread_count);
128
1/2
✓ Branch 1 taken 136 times.
✗ Branch 2 not taken.
 136 std::vector<std::size_t> local_best_indices(actual_thread_count, initial_next_point_index);
129
130
2/2
✓ Branch 0 taken 334 times.
✓ Branch 1 taken 136 times.
 470 for (std::size_t thread_index = 0; thread_index < actual_thread_count; ++thread_index) {
131 334 const std::size_t range_begin = thread_index * chunk_size;
132
1/2
✓ Branch 1 taken 334 times.
✗ Branch 2 not taken.
 334 const std::size_t range_end = std::min(range_begin + chunk_size, point_count);
133
134
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 334 threads[thread_index] = std::thread([&unique_points, &local_best_indices, current_point_index,
135 initial_next_point_index, range_begin, range_end, thread_index]() {
136 334 local_best_indices[thread_index] = FindThreadLocalBestIndex(unique_points, current_point_index,
137 initial_next_point_index, range_begin, range_end);
138
1/2
✓ Branch 1 taken 334 times.
✗ Branch 2 not taken.
 334 });
139 }
140
141
2/2
✓ Branch 0 taken 334 times.
✓ Branch 1 taken 136 times.
 470 for (std::thread &worker_thread : threads) {
142
1/2
✓ Branch 0 taken 334 times.
✗ Branch 1 not taken.
 334 if (worker_thread.joinable()) {
143
1/2
✓ Branch 1 taken 334 times.
✗ Branch 2 not taken.
 334 worker_thread.join();
144 }
145 }
146
147 136 return ReduceBestIndices(unique_points, current_point_index, initial_next_point_index, local_best_indices);
148 136 }
149
150 } // namespace
151
152
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 TsarkovKJarvisConvexHullSTL::TsarkovKJarvisConvexHullSTL(const InType &input_points) {
153 SetTypeOfTask(GetStaticTypeOfTask());
154
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 GetInput() = input_points;
155 GetOutput().clear();
156 56 }
157
158
1/2
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
 56 bool TsarkovKJarvisConvexHullSTL::ValidationImpl() {
159
2/4
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 56 times.
 56 return !GetInput().empty() && GetOutput().empty();
160 }
161
162
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 bool TsarkovKJarvisConvexHullSTL::PreProcessingImpl() {
163 GetOutput().clear();
164 56 return true;
165 }
166
167 56 bool TsarkovKJarvisConvexHullSTL::RunImpl() {
168 56 const std::vector<Point> unique_points = RemoveDuplicatePoints(GetInput());
169
170
1/2
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
 56 if (unique_points.empty()) {
171 return false;
172 }
173
174
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 48 times.
 56 if (unique_points.size() == 1) {
175
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 GetOutput() = unique_points;
176 return true;
177 }
178
179
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 40 times.
 48 if (unique_points.size() == 2) {
180
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 GetOutput() = unique_points;
181 return true;
182 }
183
184 40 const auto start_point_index = FindLeftmostPointIndex(unique_points);
185 std::size_t current_point_index = start_point_index;
186
187 while (true) {
188 GetOutput().push_back(unique_points[current_point_index]);
189
190
1/2
✓ Branch 1 taken 136 times.
✗ Branch 2 not taken.
 136 current_point_index = FindNextHullPointIndexSTL(unique_points, current_point_index);
191
192
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 40 times.
 136 if (current_point_index == start_point_index) {
193 break;
194 }
195 }
196
197 40 return !GetOutput().empty();
198 }
199
200 56 bool TsarkovKJarvisConvexHullSTL::PostProcessingImpl() {
201 56 return true;
202 }
203
204 } // namespace tsarkov_k_jarvis_convex_hull
205