GCC Code Coverage Report

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