GCC Code Coverage Report

Directory: ./
File: tasks/ilin_a_algorithm_graham/omp/src/ops_omp.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 38 40 95.0%
Functions: 7 7 100.0%
Branches: 20 28 71.4%
Line Branch Exec Source
1 #include "ilin_a_algorithm_graham/omp/include/ops_omp.hpp"
2
3 #include <algorithm>
4 #include <cmath>
5 #include <cstddef>
6 #include <utility>
7 #include <vector>
8
9 #include "ilin_a_algorithm_graham/common/include/common.hpp"
10
11 namespace ilin_a_algorithm_graham {
12
13 namespace {
14 double Orient(const Point &p, const Point &q, const Point &r) {
15 200 return ((q.x - p.x) * (r.y - p.y)) - ((q.y - p.y) * (r.x - p.x));
16 }
17
18 double DistanceSq(const Point &p, const Point &q) {
19 16 double dx = p.x - q.x;
20 16 double dy = p.y - q.y;
21 16 return (dx * dx) + (dy * dy);
22 }
23
24 12 Point FindLowestLeftmost(const std::vector<Point> &points) {
25 12 Point p0 = points[0];
26
27 12 #pragma omp parallel default(none) shared(points, p0)
28 {
29 Point local_p0 = p0;
30 #pragma omp for nowait
31 for (size_t i = 1; i < points.size(); ++i) {
32 if (points[i].y < local_p0.y || (points[i].y == local_p0.y && points[i].x < local_p0.x)) {
33 local_p0 = points[i];
34 }
35 }
36 #pragma omp critical
37 {
38 if (local_p0.y < p0.y || (local_p0.y == p0.y && local_p0.x < p0.x)) {
39 p0 = local_p0;
40 }
41 }
42 }
43 12 return p0;
44 }
45
46 class PointComparator {
47 public:
48 12 explicit PointComparator(const Point &p0) : p0_(p0) {}
49
50 132 bool operator()(const Point &a, const Point &b) const {
51 double o = Orient(p0_, a, b);
52
2/2
✓ Branch 0 taken 116 times.
✓ Branch 1 taken 16 times.
 132 if (o != 0.0) {
53 116 return o > 0;
54 }
55 16 return DistanceSq(p0_, a) < DistanceSq(p0_, b);
56 }
57
58 private:
59 Point p0_;
60 };
61 } // namespace
62
63
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 IlinAGrahamOMP::IlinAGrahamOMP(const InType &in) {
64 SetTypeOfTask(GetStaticTypeOfTask());
65 GetInput() = in;
66 12 }
67
68 12 bool IlinAGrahamOMP::ValidationImpl() {
69 12 return !GetInput().points.empty();
70 }
71
72 12 bool IlinAGrahamOMP::PreProcessingImpl() {
73 12 points_ = GetInput().points;
74 hull_.clear();
75 12 return true;
76 }
77
78
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 bool IlinAGrahamOMP::RunImpl() {
79
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 if (points_.size() < 3) {
80 ✗ hull_ = points_;
81 ✗ return true;
82 }
83
84 12 Point p0 = FindLowestLeftmost(points_);
85
86
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 std::vector<Point> sorted;
87
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 sorted.reserve(points_.size());
88
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 12 times.
 84 for (const Point &p : points_) {
89
4/4
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 48 times.
✓ Branch 2 taken 12 times.
✓ Branch 3 taken 12 times.
 72 if (p.x != p0.x || p.y != p0.y) {
90 sorted.push_back(p);
91 }
92 }
93
94 std::ranges::sort(sorted, PointComparator(p0));
95
96
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 std::vector<Point> stack;
97
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 stack.reserve(sorted.size() + 1);
98 stack.push_back(p0);
99 stack.push_back(sorted[0]);
100
101
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 12 times.
 60 for (size_t i = 1; i < sorted.size(); ++i) {
102
1/2
✓ Branch 0 taken 68 times.
✗ Branch 1 not taken.
 68 while (stack.size() >= 2) {
103 68 Point p = stack[stack.size() - 2];
104 68 Point q = stack[stack.size() - 1];
105
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 48 times.
 68 if (Orient(p, q, sorted[i]) <= 0.0) {
106 stack.pop_back();
107 } else {
108 break;
109 }
110 }
111 stack.push_back(sorted[i]);
112 }
113
114 12 hull_ = std::move(stack);
115 return true;
116 }
117
118 12 bool IlinAGrahamOMP::PostProcessingImpl() {
119 12 GetOutput() = hull_;
120 12 return true;
121 }
122
123 } // namespace ilin_a_algorithm_graham
124