GCC Code Coverage Report

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