GCC Code Coverage Report

Directory: ./
File: tasks/dergachev_a_graham_scan/tbb/src/ops_tbb.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 46 50 92.0%
Functions: 9 9 100.0%
Branches: 36 46 78.3%
Line Branch Exec Source
1 #include "dergachev_a_graham_scan/tbb/include/ops_tbb.hpp"
2
3 #include <cmath>
4 #include <cstddef>
5 #include <utility>
6 #include <vector>
7
8 #include "dergachev_a_graham_scan/common/include/common.hpp"
9 #include "oneapi/tbb/blocked_range.h"
10 #include "oneapi/tbb/parallel_for.h"
11 #include "oneapi/tbb/parallel_reduce.h"
12 #include "oneapi/tbb/parallel_sort.h"
13
14 namespace dergachev_a_graham_scan {
15
16 namespace {
17
18 using Pt = std::pair<double, double>;
19
20 double CrossProduct(const Pt &o, const Pt &a, const Pt &b) {
21 57798 return ((a.first - o.first) * (b.second - o.second)) - ((a.second - o.second) * (b.first - o.first));
22 }
23
24 double DistSquared(const Pt &a, const Pt &b) {
25 ✗ double dx = a.first - b.first;
26 ✗ double dy = a.second - b.second;
27 ✗ return (dx * dx) + (dy * dy);
28 }
29
30 const double kPi = std::acos(-1.0);
31
32 44 int FindPivotIndex(const std::vector<Pt> &pts, int n) {
33 88 return tbb::parallel_reduce(tbb::blocked_range<int>(1, n), 0,
34 1888 [&pts](const tbb::blocked_range<int> &range, int best) -> int {
35
2/2
✓ Branch 0 taken 4800 times.
✓ Branch 1 taken 1888 times.
 6688 for (int i = range.begin(); i < range.end(); ++i) {
36 4800 auto ui = static_cast<std::size_t>(i);
37 4800 auto ub = static_cast<std::size_t>(best);
38
5/6
✓ Branch 0 taken 3563 times.
✓ Branch 1 taken 1237 times.
✓ Branch 2 taken 1 times.
✓ Branch 3 taken 3562 times.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
 4800 if (pts[ui].second < pts[ub].second || (pts[ui].second == pts[ub].second && pts[ui].first < pts[ub].first)) {
39 best = i;
40 }
41 }
42 1888 return best;
43 44 }, [&pts](int a, int b) -> int {
44 43 auto ua = static_cast<std::size_t>(a);
45 43 auto ub = static_cast<std::size_t>(b);
46
6/6
✓ Branch 0 taken 25 times.
✓ Branch 1 taken 18 times.
✓ Branch 2 taken 19 times.
✓ Branch 3 taken 6 times.
✓ Branch 4 taken 3 times.
✓ Branch 5 taken 3 times.
 43 if (pts[ua].second < pts[ub].second || (pts[ua].second == pts[ub].second && pts[ua].first < pts[ub].first)) {
47 return a;
48 }
49 return b;
50 44 });
51 }
52
53 } // namespace
54
55 52 DergachevAGrahamScanTBB::DergachevAGrahamScanTBB(const InType &in) {
56 SetTypeOfTask(GetStaticTypeOfTask());
57 52 GetInput() = in;
58 GetOutput() = 0;
59 52 }
60
61 52 bool DergachevAGrahamScanTBB::ValidationImpl() {
62 52 return GetInput() >= 0;
63 }
64
65
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 52 times.
 52 bool DergachevAGrahamScanTBB::PreProcessingImpl() {
66 hull_.clear();
67 52 int n = GetInput();
68
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 48 times.
 52 if (n <= 0) {
69 points_.clear();
70 4 return true;
71 }
72 48 points_.resize(n);
73 48 double step = (2.0 * kPi) / n;
74 tbb::parallel_for(0, n,
75 48 [&](int i) { points_[static_cast<std::size_t>(i)] = {std::cos(step * i), std::sin(step * i)}; });
76
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 12 times.
 48 if (n > 3) {
77 36 points_.emplace_back(0.0, 0.0);
78 }
79 return true;
80 }
81
82
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 52 times.
 52 bool DergachevAGrahamScanTBB::RunImpl() {
83 hull_.clear();
84
2/2
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 44 times.
 52 std::vector<Pt> pts(points_.begin(), points_.end());
85 52 int n = static_cast<int>(pts.size());
86
87
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 44 times.
 52 if (n <= 1) {
88
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 hull_.assign(pts.begin(), pts.end());
89 8 return true;
90 }
91
92
1/2
✓ Branch 1 taken 44 times.
✗ Branch 2 not taken.
 44 int pivot_idx = FindPivotIndex(pts, n);
93
1/2
✓ Branch 1 taken 44 times.
✗ Branch 2 not taken.
 44 std::swap(pts[0], pts[static_cast<std::size_t>(pivot_idx)]);
94
95 Pt pivot = pts[0];
96
1/4
✓ Branch 1 taken 44 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 44 tbb::parallel_sort(pts.begin() + 1, pts.end(), [&pivot](const Pt &a, const Pt &b) {
97 53006 double cross = CrossProduct(pivot, a, b);
98
1/2
✓ Branch 0 taken 53006 times.
✗ Branch 1 not taken.
 53006 if (cross != 0.0) {
99 53006 return cross > 0.0;
100 }
101 ✗ return DistSquared(pivot, a) < DistSquared(pivot, b);
102 });
103
104
2/2
✓ Branch 0 taken 4844 times.
✓ Branch 1 taken 44 times.
 4888 for (const auto &p : pts) {
105
4/4
✓ Branch 0 taken 4792 times.
✓ Branch 1 taken 88 times.
✓ Branch 2 taken 36 times.
✓ Branch 3 taken 4756 times.
 4880 while (hull_.size() > 1 && CrossProduct(hull_[hull_.size() - 2], hull_.back(), p) <= 0.0) {
106 hull_.pop_back();
107 }
108
2/2
✓ Branch 0 taken 4620 times.
✓ Branch 1 taken 224 times.
 4844 hull_.push_back(p);
109 }
110
111 return true;
112 }
113
114 52 bool DergachevAGrahamScanTBB::PostProcessingImpl() {
115 52 GetOutput() = static_cast<int>(hull_.size());
116 52 return true;
117 }
118
119 } // namespace dergachev_a_graham_scan
120