GCC Code Coverage Report

Directory: ./
File: tasks/perepelkin_i_convex_hull_graham_scan/tbb/src/ops_tbb.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 48 52 92.3%
Functions: 9 11 81.8%
Branches: 40 90 44.4%
Line Branch Exec Source
1 #include "perepelkin_i_convex_hull_graham_scan/tbb/include/ops_tbb.hpp"
2
3 #include <tbb/blocked_range.h>
4 #include <tbb/global_control.h>
5 #include <tbb/parallel_reduce.h>
6 #include <tbb/parallel_sort.h>
7
8 #include <cmath>
9 #include <cstddef>
10 #include <utility>
11 #include <vector>
12
13 #include "perepelkin_i_convex_hull_graham_scan/common/include/common.hpp"
14 #include "util/include/util.hpp"
15
16 namespace perepelkin_i_convex_hull_graham_scan {
17
18
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 PerepelkinIConvexHullGrahamScanTBB::PerepelkinIConvexHullGrahamScanTBB(const InType &in) {
19 SetTypeOfTask(GetStaticTypeOfTask());
20
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 GetInput() = in;
21 48 GetOutput() = std::vector<std::pair<double, double>>();
22 48 }
23
24 48 bool PerepelkinIConvexHullGrahamScanTBB::ValidationImpl() {
25 48 return GetOutput().empty();
26 }
27
28 48 bool PerepelkinIConvexHullGrahamScanTBB::PreProcessingImpl() {
29 48 return true;
30 }
31
32
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 40 times.
 48 bool PerepelkinIConvexHullGrahamScanTBB::RunImpl() {
33 const auto &data = GetInput();
34
35
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 40 times.
 48 if (data.size() < 2) {
36 8 GetOutput() = data;
37 8 return true;
38 }
39
40 40 tbb::global_control gc(tbb::global_control::max_allowed_parallelism, ppc::util::GetNumThreads());
41
42
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 std::vector<std::pair<double, double>> pts = data;
43
44 // Find pivot
45
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 size_t pivot_idx = FindPivotParallel(pts);
46
47 std::pair<double, double> pivot = pts[pivot_idx];
48 pts.erase(pts.begin() + static_cast<std::ptrdiff_t>(pivot_idx));
49
50 // Parallel sorting
51 ParallelSort(pts, pivot);
52
53 // Sequential hull construction
54 40 std::vector<std::pair<double, double>> hull;
55 40 HullConstruction(hull, pts, pivot);
56
57 GetOutput() = std::move(hull);
58 return true;
59 }
60
61 40 size_t PerepelkinIConvexHullGrahamScanTBB::FindPivotParallel(const std::vector<std::pair<double, double>> &pts) {
62 auto better = [&](size_t a, size_t b) {
63
6/8
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 108 times.
✓ Branch 5 taken 32 times.
✓ Branch 6 taken 16 times.
✓ Branch 7 taken 16 times.
 141 if (pts[b].second < pts[a].second || (pts[b].second == pts[a].second && pts[b].first < pts[a].first)) {
64 return b;
65 }
66 return a;
67 40 };
68
69 80 size_t pivot = tbb::parallel_reduce(tbb::blocked_range<size_t>(1, pts.size()), static_cast<size_t>(0),
70 168 [&](const tbb::blocked_range<size_t> &r, size_t local_idx) {
71
2/2
✓ Branch 0 taken 168 times.
✓ Branch 1 taken 168 times.
 336 for (size_t i = r.begin(); i != r.end(); i++) {
72
2/2
✓ Branch 0 taken 140 times.
✓ Branch 1 taken 28 times.
 168 local_idx = better(local_idx, i);
73 }
74 168 return local_idx;
75
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
 42 }, [&](size_t a, size_t b) { return better(a, b); });
76
77 40 return pivot;
78 }
79
80 ✗ void PerepelkinIConvexHullGrahamScanTBB::ParallelSort(std::vector<std::pair<double, double>> &data,
81 const std::pair<double, double> &pivot) {
82
6/46
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✓ Branch 20 taken 92 times.
✓ Branch 21 taken 108 times.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 30 not taken.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 36 not taken.
✗ Branch 37 not taken.
✓ Branch 38 taken 20 times.
✓ Branch 39 taken 108 times.
✗ Branch 40 not taken.
✗ Branch 41 not taken.
✓ Branch 44 taken 40 times.
✗ Branch 45 not taken.
✓ Branch 47 taken 40 times.
✗ Branch 48 not taken.
 368 tbb::parallel_sort(data.begin(), data.end(), [&](const auto &a, const auto &b) { return AngleCmp(a, b, pivot); });
83 ✗ }
84
85 40 void PerepelkinIConvexHullGrahamScanTBB::HullConstruction(std::vector<std::pair<double, double>> &hull,
86 const std::vector<std::pair<double, double>> &pts,
87 const std::pair<double, double> &pivot) {
88 40 hull.reserve(pts.size() + 1);
89
90 hull.push_back(pivot);
91 hull.push_back(pts[0]);
92
93
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 40 times.
 168 for (size_t i = 1; i < pts.size(); i++) {
94
4/4
✓ Branch 0 taken 168 times.
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 40 times.
✓ Branch 3 taken 104 times.
 336 while (hull.size() >= 2 && Orientation(hull[hull.size() - 2], hull[hull.size() - 1], pts[i]) <= 0) {
95 hull.pop_back();
96 }
97
98 hull.push_back(pts[i]);
99 }
100 40 }
101
102 ✗ double PerepelkinIConvexHullGrahamScanTBB::Orientation(const std::pair<double, double> &p,
103 const std::pair<double, double> &q,
104 const std::pair<double, double> &r) {
105
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
✓ Branch 3 taken 144 times.
 168 double val = ((q.first - p.first) * (r.second - p.second)) - ((q.second - p.second) * (r.first - p.first));
106
107
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
✓ Branch 3 taken 144 times.
 168 if (std::abs(val) < 1e-9) {
108 ✗ return 0.0;
109 }
110
111 return val;
112 }
113
114 328 bool PerepelkinIConvexHullGrahamScanTBB::AngleCmp(const std::pair<double, double> &a,
115 const std::pair<double, double> &b,
116 const std::pair<double, double> &pivot) {
117 328 double dx1 = a.first - pivot.first;
118 328 double dy1 = a.second - pivot.second;
119 328 double dx2 = b.first - pivot.first;
120 328 double dy2 = b.second - pivot.second;
121
122
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 256 times.
 328 double cross = (dx1 * dy2) - (dy1 * dx2);
123
124
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 256 times.
 328 if (std::abs(cross) < 1e-9) {
125 72 double dist1 = (dx1 * dx1) + (dy1 * dy1);
126 72 double dist2 = (dx2 * dx2) + (dy2 * dy2);
127 72 return dist1 < dist2;
128 }
129
130 256 return cross > 0;
131 }
132
133 48 bool PerepelkinIConvexHullGrahamScanTBB::PostProcessingImpl() {
134 48 return true;
135 }
136
137 } // namespace perepelkin_i_convex_hull_graham_scan
138