GCC Code Coverage Report

Directory: ./
File: tasks/peterson_r_graham_scan/tbb/src/ops_tbb.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 64 86 74.4%
Functions: 11 15 73.3%
Branches: 28 54 51.9%
Line Branch Exec Source
1 #include "peterson_r_graham_scan/tbb/include/ops_tbb.hpp"
2
3 #include <tbb/tbb.h>
4
5 #include <atomic>
6 #include <cmath>
7 #include <cstddef>
8 #include <numbers>
9 #include <utility>
10 #include <vector>
11
12 #include "peterson_r_graham_scan/tbb/include/common.hpp"
13
14 namespace peterson_r_graham_scan_tbb {
15
16 namespace {
17 constexpr double kTolerance = 0.0;
18
19 double CalculateOrientation(const Point2D &origin, const Point2D &a, const Point2D &b) {
20 92 return ((a.coord_x - origin.coord_x) * (b.coord_y - origin.coord_y)) -
21 92 ((a.coord_y - origin.coord_y) * (b.coord_x - origin.coord_x));
22 }
23
24 double CalculateSquaredDistance(const Point2D &first, const Point2D &second) {
25 ✗ const double dx = first.coord_x - second.coord_x;
26 ✗ const double dy = first.coord_y - second.coord_y;
27 ✗ return (dx * dx) + (dy * dy);
28 }
29
30 class PointComparator {
31 public:
32 12 explicit PointComparator(const Point2D *reference) : origin_ptr_(reference) {}
33
34 56 bool operator()(const Point2D &lhs, const Point2D &rhs) const {
35
1/2
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
 56 const double orientation = CalculateOrientation(*origin_ptr_, lhs, rhs);
36
1/2
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
 56 if (std::abs(orientation) > kTolerance) {
37 56 return orientation > 0;
38 }
39 ✗ return CalculateSquaredDistance(*origin_ptr_, lhs) < CalculateSquaredDistance(*origin_ptr_, rhs);
40 }
41
42 private:
43 const Point2D *origin_ptr_;
44 };
45 } // namespace
46
47 12 PetersonGrahamScannerTBB::PetersonGrahamScannerTBB(const InputValue &in) {
48 SetTypeOfTask(GetStaticTypeOfTask());
49 12 GetInput() = in;
50 GetOutput() = 0;
51 12 }
52
53 ✗ void PetersonGrahamScannerTBB::LoadPoints(const PointSet &points) {
54 ✗ input_points_ = points;
55 ✗ external_data_provided_ = true;
56 ✗ }
57
58 ✗ PointSet PetersonGrahamScannerTBB::GetConvexHull() const {
59 ✗ return hull_points_;
60 }
61
62 12 bool PetersonGrahamScannerTBB::ValidationImpl() {
63 12 return GetInput() >= 0;
64 }
65
66
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 bool PetersonGrahamScannerTBB::PreProcessingImpl() {
67 hull_points_.clear();
68
69
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 if (!external_data_provided_) {
70 input_points_.clear();
71 12 const int count = GetInput();
72
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 if (count <= 0) {
73 return true;
74 }
75
76 12 input_points_.resize(count);
77 12 const double angle_step = 2.0 * std::numbers::pi / count;
78
79 72 tbb::parallel_for(tbb::blocked_range<int>(0, count), [this, angle_step](const tbb::blocked_range<int> &range) {
80
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 60 times.
 120 for (int i = range.begin(); i != range.end(); ++i) {
81 60 const double angle = angle_step * i;
82 60 input_points_[i] = Point2D(std::cos(angle), std::sin(angle));
83 }
84 60 });
85 }
86
87 return true;
88 }
89
90
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 bool PetersonGrahamScannerTBB::AreAllPointsIdentical(const PointSet &points) {
91
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 if (points.empty()) {
92 return true;
93 }
94
95 const Point2D &reference = points[0];
96 12 std::atomic<bool> all_identical{true};
97
98 12 tbb::parallel_for(tbb::blocked_range<std::size_t>(1, points.size()),
99 60 [&points, &reference, &all_identical](const tbb::blocked_range<std::size_t> &range) {
100
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 48 times.
 96 for (std::size_t i = range.begin(); i != range.end(); ++i) {
101
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 48 if (std::abs(points[i].coord_x - reference.coord_x) > kTolerance ||
102 ✗ std::abs(points[i].coord_y - reference.coord_y) > kTolerance) {
103 48 all_identical.store(false);
104 }
105 }
106 48 });
107
108 12 return all_identical.load();
109 }
110
111 12 std::size_t PetersonGrahamScannerTBB::FindLowestPointParallel(const PointSet &points) {
112 struct LowestPointResult {
113 std::size_t index = 0;
114 double min_y = 0.0;
115 double min_x = 0.0;
116
117 LowestPointResult() = default;
118 12 LowestPointResult(std::size_t idx, double y, double x) : index(idx), min_y(y), min_x(x) {}
119 };
120
121 12 LowestPointResult result = tbb::parallel_reduce(
122 12 tbb::blocked_range<std::size_t>(0, points.size()), LowestPointResult(0, points[0].coord_y, points[0].coord_x),
123 12 [&points](const tbb::blocked_range<std::size_t> &range, LowestPointResult current_result) {
124
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 60 times.
 120 for (std::size_t i = range.begin(); i != range.end(); ++i) {
125
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 40 times.
 60 if (points[i].coord_y < current_result.min_y ||
126 (std::abs(points[i].coord_y - current_result.min_y) < kTolerance &&
127 points[i].coord_x < current_result.min_x)) {
128 20 current_result = LowestPointResult(i, points[i].coord_y, points[i].coord_x);
129 }
130 }
131 return current_result;
132 12 }, [](LowestPointResult lhs, LowestPointResult rhs) {
133 ✗ if (rhs.min_y < lhs.min_y || (std::abs(rhs.min_y - lhs.min_y) < kTolerance && rhs.min_x < lhs.min_x)) {
134 ✗ return rhs;
135 }
136 return lhs;
137 });
138
139 12 return result.index;
140 }
141
142
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 void PetersonGrahamScannerTBB::SortPointsByAngleParallel(PointSet &points) {
143
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 if (points.size() < 2) {
144 ✗ return;
145 }
146
147 12 const Point2D origin = points[0];
148 PointComparator comparator(&origin);
149 12 tbb::parallel_sort(points.begin() + 1, points.end(), comparator);
150 }
151
152
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 bool PetersonGrahamScannerTBB::RunImpl() {
153 hull_points_.clear();
154 12 const int total_points = static_cast<int>(input_points_.size());
155
156
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 if (total_points == 0) {
157 return true;
158 }
159
160
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 12 times.
 12 if (AreAllPointsIdentical(input_points_)) {
161 ✗ hull_points_.push_back(input_points_.front());
162 ✗ return true;
163 }
164
165
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 if (total_points < 3) {
166 ✗ hull_points_ = input_points_;
167 ✗ return true;
168 }
169
170 12 const std::size_t lowest_idx = FindLowestPointParallel(input_points_);
171 std::swap(input_points_[0], input_points_[lowest_idx]);
172
173 12 SortPointsByAngleParallel(input_points_);
174
175 12 std::vector<Point2D> stack;
176
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 stack.reserve(total_points);
177 stack.push_back(input_points_[0]);
178 stack.push_back(input_points_[1]);
179
180
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 12 times.
 48 for (int i = 2; i < total_points; ++i) {
181
1/2
✓ Branch 0 taken 36 times.
✗ Branch 1 not taken.
 36 while (static_cast<int>(stack.size()) >= 2) {
182 const Point2D &second_last = stack[stack.size() - 2];
183 const Point2D &last = stack.back();
184
185
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 36 times.
 36 if (CalculateOrientation(second_last, last, input_points_[i]) <= kTolerance) {
186 stack.pop_back();
187 } else {
188 break;
189 }
190 }
191
1/2
✓ Branch 0 taken 36 times.
✗ Branch 1 not taken.
 36 stack.push_back(input_points_[i]);
192 }
193
194 12 hull_points_ = std::move(stack);
195 return true;
196 }
197
198 12 bool PetersonGrahamScannerTBB::PostProcessingImpl() {
199 12 GetOutput() = static_cast<int>(hull_points_.size());
200 12 return true;
201 }
202
203 ✗ double PetersonGrahamScannerTBB::ComputeOrientation(const Point2D &origin, const Point2D &a, const Point2D &b) {
204 ✗ return CalculateOrientation(origin, a, b);
205 }
206
207 ✗ double PetersonGrahamScannerTBB::ComputeDistanceSq(const Point2D &p1, const Point2D &p2) {
208 ✗ return CalculateSquaredDistance(p1, p2);
209 }
210
211 } // namespace peterson_r_graham_scan_tbb
212