GCC Code Coverage Report

Directory: ./
File: tasks/makovskiy_i_graham_hull/tbb/src/ops_tbb.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 66 66 100.0%
Functions: 12 12 100.0%
Branches: 59 86 68.6%
Line Branch Exec Source
1 #include "makovskiy_i_graham_hull/tbb/include/ops_tbb.hpp"
2
3 #include <tbb/tbb.h>
4
5 #include <algorithm>
6 #include <cmath>
7 #include <cstddef>
8 #include <cstdint>
9 #include <vector>
10
11 #include "makovskiy_i_graham_hull/common/include/common.hpp"
12
13 namespace makovskiy_i_graham_hull {
14
15 namespace {
16
17 double CrossProduct(const Point &o, const Point &a, const Point &b) {
18
2/2
✓ Branch 0 taken 5324 times.
✓ Branch 1 taken 7936 times.
 13260 return ((a.x - o.x) * (b.y - o.y)) - ((a.y - o.y) * (b.x - o.x));
19 }
20
21 double DistSq(const Point &a, const Point &b) {
22 16676 return ((a.x - b.x) * (a.x - b.x)) + ((a.y - b.y) * (a.y - b.y));
23 }
24
25 28 size_t FindMinPointIndexTBB(const std::vector<Point> &points) {
26 56 return tbb::parallel_reduce(tbb::blocked_range<size_t>(1, points.size()), static_cast<size_t>(0),
27 1212 [&points](const tbb::blocked_range<size_t> &r, size_t local_min) {
28
2/2
✓ Branch 0 taken 13288 times.
✓ Branch 1 taken 1212 times.
 14500 for (size_t i = r.begin(); i != r.end(); ++i) {
29
3/4
✓ Branch 0 taken 13288 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 252 times.
✓ Branch 3 taken 13036 times.
 13288 if (points[i].y < points[local_min].y - 1e-9 ||
30
3/4
✓ Branch 0 taken 252 times.
✓ Branch 1 taken 13036 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 252 times.
 13288 (std::abs(points[i].y - points[local_min].y) <= 1e-9 && points[i].x < points[local_min].x)) {
31 local_min = i;
32 }
33 }
34 1212 return local_min;
35 28 }, [&points](size_t a, size_t b) {
36
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 15 times.
✓ Branch 2 taken 15 times.
✗ Branch 3 not taken.
 15 if (points[a].y < points[b].y - 1e-9 ||
37
2/4
✓ Branch 0 taken 15 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 15 times.
 15 (std::abs(points[a].y - points[b].y) <= 1e-9 && points[a].x < points[b].x)) {
38 return a;
39 }
40 return b;
41 28 });
42 }
43
44 template <typename RandomIt, typename Compare>
45
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 12 times.
 52 void TbbQuickSort(RandomIt first, RandomIt last, Compare comp) {
46
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 12 times.
 52 if (last - first < 2048) {
47 40 std::sort(first, last, comp);
48 40 return;
49 }
50 12 auto pivot = *(first + ((last - first) / 2));
51
4/4
✓ Branch 0 taken 6052 times.
✓ Branch 1 taken 4752 times.
✓ Branch 2 taken 20264 times.
✓ Branch 3 taken 4740 times.
 35820 RandomIt middle1 = std::partition(first, last, [pivot, comp](const auto &a) { return comp(a, pivot); });
52
3/4
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 24980 times.
✓ Branch 3 taken 12 times.
 25028 RandomIt middle2 = std::partition(middle1, last, [pivot, comp](const auto &a) { return !comp(pivot, a); });
53
54 tbb::task_group tg;
55
1/2
✓ Branch 2 taken 12 times.
✗ Branch 3 not taken.
 24 tg.run([first, middle1, comp]() { TbbQuickSort(first, middle1, comp); });
56
1/2
✓ Branch 2 taken 12 times.
✗ Branch 3 not taken.
 24 tg.run([middle2, last, comp]() { TbbQuickSort(middle2, last, comp); });
57
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 tg.wait();
58 }
59
60 28 std::vector<Point> FilterPointsTBB(const std::vector<Point> &points, const Point &p0) {
61 size_t n = points.size();
62 28 std::vector<uint8_t> keep(n, 1);
63
64
1/4
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 1206 tbb::parallel_for(tbb::blocked_range<size_t>(1, n - 1), [&](const tbb::blocked_range<size_t> &r) {
65 1178 for (size_t i = r.begin(); i != r.end(); ++i) {
66
2/2
✓ Branch 0 taken 5324 times.
✓ Branch 1 taken 7936 times.
 13260 if (std::abs(CrossProduct(p0, points[i], points[i + 1])) < 1e-9) {
67 5324 keep[i] = 0;
68 }
69 }
70 1178 });
71
72 28 std::vector<Point> filtered;
73
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 filtered.reserve(n);
74
2/2
✓ Branch 0 taken 13316 times.
✓ Branch 1 taken 28 times.
 13344 for (size_t i = 0; i < n; ++i) {
75
2/2
✓ Branch 0 taken 7992 times.
✓ Branch 1 taken 5324 times.
 13316 if (keep[i] != 0) {
76 filtered.push_back(points[i]);
77 }
78 }
79 28 return filtered;
80 }
81
82 20 std::vector<Point> BuildHull(const std::vector<Point> &filtered) {
83
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 std::vector<Point> hull;
84 hull.push_back(filtered[0]);
85 hull.push_back(filtered[1]);
86 hull.push_back(filtered[2]);
87
88
2/2
✓ Branch 0 taken 7916 times.
✓ Branch 1 taken 20 times.
 7936 for (size_t i = 3; i < filtered.size(); ++i) {
89
3/4
✓ Branch 0 taken 15816 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 7900 times.
✓ Branch 3 taken 7916 times.
 15816 while (hull.size() > 1 && CrossProduct(hull[hull.size() - 2], hull.back(), filtered[i]) <= 1e-9) {
90 hull.pop_back();
91 }
92 hull.push_back(filtered[i]);
93 }
94 20 return hull;
95 }
96
97 } // namespace
98
99
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 ConvexHullGrahamTBB::ConvexHullGrahamTBB(const InType &in) {
100 SetTypeOfTask(GetStaticTypeOfTask());
101
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 GetInput() = in;
102 36 }
103
104 36 bool ConvexHullGrahamTBB::ValidationImpl() {
105 36 return true;
106 }
107
108 36 bool ConvexHullGrahamTBB::PreProcessingImpl() {
109 36 return true;
110 }
111
112 36 bool ConvexHullGrahamTBB::RunImpl() {
113 36 InType points = GetInput();
114
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 28 times.
 36 if (points.size() < 3) {
115
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 GetOutput() = points;
116 return true;
117 }
118
119
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 size_t min_idx = FindMinPointIndexTBB(points);
120
121 std::swap(points[0], points[min_idx]);
122 28 Point p0 = points[0];
123
124
2/2
✓ Branch 0 taken 16676 times.
✓ Branch 1 taken 203612 times.
 220288 auto comp = [p0](const Point &a, const Point &b) {
125 double cp = CrossProduct(p0, a, b);
126
2/2
✓ Branch 0 taken 16676 times.
✓ Branch 1 taken 203612 times.
 220288 if (std::abs(cp) < 1e-9) {
127 16676 return DistSq(p0, a) < DistSq(p0, b);
128 }
129 203612 return cp > 0;
130
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 };
131
132
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 TbbQuickSort(points.begin() + 1, points.end(), comp);
133
134
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 InType filtered = FilterPointsTBB(points, p0);
135
136
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 20 times.
 28 if (filtered.size() < 3) {
137
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 GetOutput() = filtered;
138 return true;
139 }
140
141
1/4
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 20 GetOutput() = BuildHull(filtered);
142 20 return true;
143 }
144
145 36 bool ConvexHullGrahamTBB::PostProcessingImpl() {
146 36 return true;
147 }
148
149 } // namespace makovskiy_i_graham_hull
150