GCC Code Coverage Report

Directory: ./
File: tasks/peterson_r_graham_scan_omp/omp/src/ops_omp.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 55 74 74.3%
Functions: 10 14 71.4%
Branches: 21 40 52.5%
Line Branch Exec Source
1 #include "peterson_r_graham_scan_omp/omp/include/ops_omp.hpp"
2
3 #include <omp.h>
4
5 #include <algorithm>
6 #include <cmath>
7 #include <cstddef>
8 #include <numbers>
9 #include <utility>
10 #include <vector>
11
12 #include "peterson_r_graham_scan_omp/common/include/common.hpp"
13
14 namespace peterson_r_graham_scan_omp {
15
16 namespace {
17 constexpr double kTolerance = 1e-12;
18
19 double CalculateOrientation(const Point2D &origin, const Point2D &a, const Point2D &b) {
20 100 return ((a.coord_x - origin.coord_x) * (b.coord_y - origin.coord_y)) -
21 100 ((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 explicit PointComparator(const Point2D *reference) : origin_ptr_(reference) {}
33
34 64 bool operator()(const Point2D &lhs, const Point2D &rhs) const {
35
1/2
✓ Branch 0 taken 64 times.
✗ Branch 1 not taken.
 64 const double orientation = CalculateOrientation(*origin_ptr_, lhs, rhs);
36
1/2
✓ Branch 0 taken 64 times.
✗ Branch 1 not taken.
 64 if (std::abs(orientation) > kTolerance) {
37 64 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
46 } // namespace
47
48 12 PetersonGrahamScannerOMP::PetersonGrahamScannerOMP(const InputValue &in) {
49 SetTypeOfTask(GetStaticTypeOfTask());
50 12 GetInput() = in;
51 GetOutput() = 0;
52 12 }
53
54 ✗ void PetersonGrahamScannerOMP::LoadPoints(const PointSet &points) {
55 ✗ input_points_ = points;
56 ✗ external_data_provided_ = true;
57 ✗ }
58
59 ✗ PointSet PetersonGrahamScannerOMP::GetConvexHull() const {
60 ✗ return hull_points_;
61 }
62
63 12 bool PetersonGrahamScannerOMP::ValidationImpl() {
64 12 return GetInput() >= 0;
65 }
66
67
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 bool PetersonGrahamScannerOMP::PreProcessingImpl() {
68 hull_points_.clear();
69
70
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 if (!external_data_provided_) {
71 input_points_.clear();
72 12 const int count = GetInput();
73
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 if (count <= 0) {
74 return true;
75 }
76
77 12 input_points_.resize(count);
78 12 const double angle_step = 2.0 * std::numbers::pi / count;
79
80 #ifdef _MSC_VER
81 # pragma omp parallel for
82 #else
83 12 # pragma omp parallel for default(none) shared(input_points_, count, angle_step)
84 #endif
85 for (int i = 0; i < count; ++i) {
86 const double angle = angle_step * i;
87 input_points_[i] = Point2D(std::cos(angle), std::sin(angle));
88 }
89 }
90
91 return true;
92 }
93
94
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 bool PetersonGrahamScannerOMP::AreAllPointsIdentical(const PointSet &points) {
95
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 if (points.empty()) {
96 return true;
97 }
98
99 const Point2D &reference = points[0];
100 12 const int num_points = static_cast<int>(points.size());
101
102 bool all_identical = true;
103
104 #ifdef _MSC_VER
105 # pragma omp parallel for reduction(&& : all_identical)
106 #else
107 12 # pragma omp parallel for default(none) shared(points, reference, num_points, kTolerance) reduction(&& : all_identical)
108 #endif
109 for (int i = 1; i < num_points; ++i) {
110 if (std::abs(points[i].coord_x - reference.coord_x) > kTolerance ||
111 std::abs(points[i].coord_y - reference.coord_y) > kTolerance) {
112 all_identical = false;
113 }
114 }
115
116 12 return all_identical;
117 }
118
119 12 std::size_t PetersonGrahamScannerOMP::FindLowestPointParallel(const PointSet &points) {
120 12 const int total_points = static_cast<int>(points.size());
121 int lowest_idx = 0;
122
123 #ifdef _MSC_VER
124 # pragma omp parallel
125 #else
126 12 # pragma omp parallel default(none) shared(points, total_points, kTolerance, lowest_idx)
127 #endif
128 {
129 int local_lowest = 0;
130
131 #pragma omp for nowait
132 for (int i = 1; i < total_points; ++i) {
133 if (points[i].coord_y < points[local_lowest].coord_y ||
134 (std::abs(points[i].coord_y - points[local_lowest].coord_y) < kTolerance &&
135 points[i].coord_x < points[local_lowest].coord_x)) {
136 local_lowest = i;
137 }
138 }
139
140 #pragma omp critical
141 {
142 if (points[local_lowest].coord_y < points[lowest_idx].coord_y ||
143 (std::abs(points[local_lowest].coord_y - points[lowest_idx].coord_y) < kTolerance &&
144 points[local_lowest].coord_x < points[lowest_idx].coord_x)) {
145 lowest_idx = local_lowest;
146 }
147 }
148 }
149
150 12 return static_cast<std::size_t>(lowest_idx);
151 }
152
153 84 void PetersonGrahamScannerOMP::ParallelMergeSort(PointSet &points, int left, int right, const Point2D &origin) {
154
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 48 times.
 84 if (left >= right) {
155 return;
156 }
157
158 36 int mid = left + ((right - left) / 2);
159
160 #ifdef _MSC_VER
161 # pragma omp task shared(points)
162 #else
163 36 # pragma omp task default(none) shared(points, left, mid, right, origin)
164 #endif
165 ParallelMergeSort(points, left, mid, origin);
166
167 #ifdef _MSC_VER
168 # pragma omp task shared(points)
169 #else
170 36 # pragma omp task default(none) shared(points, left, mid, right, origin)
171 #endif
172 ParallelMergeSort(points, mid + 1, right, origin);
173
174 36 #pragma omp taskwait
175
176 PointComparator comp(&origin);
177 36 std::inplace_merge(points.begin() + left, points.begin() + mid + 1, points.begin() + right + 1, comp);
178 }
179
180
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 void PetersonGrahamScannerOMP::SortPointsByAngleParallel(PointSet &points) {
181
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 if (points.size() < 2) {
182 ✗ return;
183 }
184
185 12 const Point2D origin = points[0];
186
187 #ifdef _MSC_VER
188 # pragma omp parallel
189 #else
190 12 # pragma omp parallel default(none) shared(points, origin)
191 #endif
192 {
193 #pragma omp single
194 {
195 ParallelMergeSort(points, 1, static_cast<int>(points.size()) - 1, origin);
196 }
197 }
198 }
199
200
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 bool PetersonGrahamScannerOMP::RunImpl() {
201 hull_points_.clear();
202 12 const int total_points = static_cast<int>(input_points_.size());
203
204
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 if (total_points == 0) {
205 return true;
206 }
207
208
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 12 times.
 12 if (AreAllPointsIdentical(input_points_)) {
209 ✗ hull_points_.push_back(input_points_.front());
210 ✗ return true;
211 }
212
213
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 if (total_points < 3) {
214 ✗ hull_points_ = input_points_;
215 ✗ return true;
216 }
217
218 12 const std::size_t lowest_idx = FindLowestPointParallel(input_points_);
219 std::swap(input_points_[0], input_points_[lowest_idx]);
220
221 12 SortPointsByAngleParallel(input_points_);
222
223 12 std::vector<Point2D> stack;
224
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 stack.reserve(total_points);
225 stack.push_back(input_points_[0]);
226 stack.push_back(input_points_[1]);
227
228
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 12 times.
 48 for (int i = 2; i < total_points; ++i) {
229
1/2
✓ Branch 0 taken 36 times.
✗ Branch 1 not taken.
 36 while (static_cast<int>(stack.size()) >= 2) {
230 const Point2D &second_last = stack[stack.size() - 2];
231 const Point2D &last = stack.back();
232
233
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 36 times.
 36 if (CalculateOrientation(second_last, last, input_points_[i]) <= kTolerance) {
234 stack.pop_back();
235 } else {
236 break;
237 }
238 }
239
1/2
✓ Branch 0 taken 36 times.
✗ Branch 1 not taken.
 36 stack.push_back(input_points_[i]);
240 }
241
242 12 hull_points_ = std::move(stack);
243 return true;
244 }
245
246 12 bool PetersonGrahamScannerOMP::PostProcessingImpl() {
247 12 GetOutput() = GetInput();
248 12 return true;
249 }
250
251 ✗ double PetersonGrahamScannerOMP::ComputeOrientation(const Point2D &origin, const Point2D &a, const Point2D &b) {
252 ✗ return CalculateOrientation(origin, a, b);
253 }
254
255 ✗ double PetersonGrahamScannerOMP::ComputeDistanceSq(const Point2D &p1, const Point2D &p2) {
256 ✗ return CalculateSquaredDistance(p1, p2);
257 }
258
259 } // namespace peterson_r_graham_scan_omp
260