GCC Code Coverage Report

Directory: ./
File: tasks/kutuzov_i_convex_hull_jarvis/tbb/src/ops_tbb.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 62 72 86.1%
Functions: 10 13 76.9%
Branches: 37 56 66.1%
Line Branch Exec Source
1 #include "kutuzov_i_convex_hull_jarvis/tbb/include/ops_tbb.hpp"
2
3 #include <tbb/blocked_range.h>
4 #include <tbb/combinable.h>
5 #include <tbb/parallel_for.h>
6 #include <tbb/partitioner.h>
7
8 #include <cmath>
9 #include <cstddef>
10 #include <vector>
11
12 #include "kutuzov_i_convex_hull_jarvis/common/include/common.hpp"
13
14 namespace kutuzov_i_convex_hull_jarvis {
15
16 namespace {
17
18 struct BestPoint {
19 size_t idx = 0;
20 double x = 0.0;
21 double y = 0.0;
22 };
23
24 12 size_t FindLeftmostPointHelper(const InType &input) {
25 12 BestPoint init;
26 init.idx = 0;
27 12 init.x = std::get<0>(input[0]);
28 12 init.y = std::get<1>(input[0]);
29
30 26 tbb::combinable<BestPoint> local_best([&]() { return init; });
31
32
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 tbb::parallel_for(tbb::blocked_range<size_t>(0, input.size()), [&](const tbb::blocked_range<size_t> &r) {
33 48 BestPoint &best = local_best.local();
34
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 48 times.
 128 for (size_t i = r.begin(); i != r.end(); ++i) {
35
1/2
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
 80 double ix = std::get<0>(input[i]);
36 80 double iy = std::get<1>(input[i]);
37
4/6
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 16 times.
✓ Branch 3 taken 64 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 16 times.
 80 if ((ix < best.x) || ((ix == best.x) && (iy < best.y))) {
38 ✗ best.idx = i;
39 ✗ best.x = ix;
40 ✗ best.y = iy;
41 }
42 }
43
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 }, tbb::static_partitioner{});
44
45 BestPoint global = local_best.combine([](const BestPoint &a, const BestPoint &b) -> BestPoint {
46
3/6
✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 2 times.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
 2 if ((b.x < a.x) || ((b.x == a.x) && (b.y < a.y))) {
47 ✗ return b;
48 }
49 return a;
50 });
51 12 return global.idx;
52 }
53
54 36 size_t FindNextPointHelper(const InType &input, size_t current, double current_x, double current_y, double epsilon) {
55 36 size_t init_idx = (current + 1) % input.size();
56 36 BestPoint init;
57 36 init.idx = init_idx;
58 36 init.x = std::get<0>(input[init_idx]);
59 36 init.y = std::get<1>(input[init_idx]);
60
61 81 tbb::combinable<BestPoint> local_next([&]() { return init; });
62
63
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 tbb::parallel_for(tbb::blocked_range<size_t>(0, input.size()), [&](const tbb::blocked_range<size_t> &r) {
64 144 BestPoint &best = local_next.local();
65 392 for (size_t i = r.begin(); i != r.end(); ++i) {
66
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 212 times.
 248 if (i == current) {
67 36 continue;
68 }
69
70
2/2
✓ Branch 0 taken 182 times.
✓ Branch 1 taken 30 times.
 212 double ix = std::get<0>(input[i]);
71 212 double iy = std::get<1>(input[i]);
72
73 212 double cross = KutuzovITestConvexHullTBB::CrossProduct(current_x, current_y, best.x, best.y, ix, iy);
74
75 272 if (KutuzovITestConvexHullTBB::IsBetterPoint(cross, epsilon, current_x, current_y, ix, iy, best.x, best.y)) {
76 46 best.idx = i;
77 46 best.x = ix;
78 46 best.y = iy;
79 }
80 }
81
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 }, tbb::static_partitioner{});
82
83 45 BestPoint global = local_next.combine([&](const BestPoint &a, const BestPoint &b) -> BestPoint {
84 9 double cross = KutuzovITestConvexHullTBB::CrossProduct(current_x, current_y, a.x, a.y, b.x, b.y);
85 13 if (KutuzovITestConvexHullTBB::IsBetterPoint(cross, epsilon, current_x, current_y, b.x, b.y, a.x, a.y)) {
86 2 return b;
87 }
88
89 7 return a;
90 });
91 36 return global.idx;
92 }
93
94 } // anonymous namespace
95
96
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 KutuzovITestConvexHullTBB::KutuzovITestConvexHullTBB(const InType &in) {
97 SetTypeOfTask(GetStaticTypeOfTask());
98
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 GetInput() = in;
99 GetOutput() = {};
100 12 }
101
102 ✗ double KutuzovITestConvexHullTBB::DistanceSquared(double a_x, double a_y, double b_x, double b_y) {
103
3/4
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 16 times.
✓ Branch 3 taken 44 times.
 64 return ((a_x - b_x) * (a_x - b_x)) + ((a_y - b_y) * (a_y - b_y));
104 }
105
106 ✗ double KutuzovITestConvexHullTBB::CrossProduct(double o_x, double o_y, double a_x, double a_y, double b_x, double b_y) {
107 221 return ((a_x - o_x) * (b_y - o_y)) - ((a_y - o_y) * (b_x - o_x));
108 }
109
110 ✗ bool KutuzovITestConvexHullTBB::IsBetterPoint(double cross, double epsilon, double current_x, double current_y,
111 double i_x, double i_y, double next_x, double next_y) {
112
4/6
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 7 times.
✓ Branch 3 taken 2 times.
✓ Branch 4 taken 182 times.
✓ Branch 5 taken 30 times.
 221 if (cross < -epsilon) {
113 return true;
114 }
115
4/6
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 3 times.
✓ Branch 4 taken 60 times.
✓ Branch 5 taken 122 times.
 189 if (std::abs(cross) < epsilon) {
116 ✗ return DistanceSquared(current_x, current_y, i_x, i_y) > DistanceSquared(current_x, current_y, next_x, next_y);
117 }
118 return false;
119 }
120
121 12 bool KutuzovITestConvexHullTBB::ValidationImpl() {
122 12 return true;
123 }
124
125 12 bool KutuzovITestConvexHullTBB::PreProcessingImpl() {
126 12 return true;
127 }
128
129
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 bool KutuzovITestConvexHullTBB::RunImpl() {
130
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 if (GetInput().size() < 3) {
131 ✗ GetOutput() = GetInput();
132 ✗ return true;
133 }
134
135 12 size_t leftmost = FindLeftmostPointHelper(GetInput());
136 size_t current = leftmost;
137 12 double current_x = std::get<0>(GetInput()[current]);
138 12 double current_y = std::get<1>(GetInput()[current]);
139 const double epsilon = 1e-9;
140
141
4/4
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 12 times.
✓ Branch 3 taken 12 times.
 48 while (current != leftmost || GetOutput().empty()) {
142 GetOutput().push_back(GetInput()[current]);
143
144 36 size_t next = FindNextPointHelper(GetInput(), current, current_x, current_y, epsilon);
145
146 current = next;
147 36 current_x = std::get<0>(GetInput()[current]);
148 36 current_y = std::get<1>(GetInput()[current]);
149 }
150 return true;
151 }
152
153 12 bool KutuzovITestConvexHullTBB::PostProcessingImpl() {
154 12 return true;
155 }
156
157 } // namespace kutuzov_i_convex_hull_jarvis
158