GCC Code Coverage Report

Directory: ./
File: tasks/makovskiy_i_graham_hull/omp/src/ops_omp.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 54 54 100.0%
Functions: 10 10 100.0%
Branches: 36 48 75.0%
Line Branch Exec Source
1 #include "makovskiy_i_graham_hull/omp/include/ops_omp.hpp"
2
3 #include <algorithm>
4 #include <cmath>
5 #include <cstddef>
6 #include <cstdint>
7 #include <vector>
8
9 #include "makovskiy_i_graham_hull/common/include/common.hpp"
10
11 namespace makovskiy_i_graham_hull {
12
13 namespace {
14
15 double CrossProduct(const Point &o, const Point &a, const Point &b) {
16 236104 return ((a.x - o.x) * (b.y - o.y)) - ((a.y - o.y) * (b.x - o.x));
17 }
18
19 double DistSq(const Point &a, const Point &b) {
20 16676 return ((a.x - b.x) * (a.x - b.x)) + ((a.y - b.y) * (a.y - b.y));
21 }
22
23 28 size_t FindMinPointIndexOMP(const std::vector<Point> &points) {
24 size_t min_idx = 0;
25 size_t n = points.size();
26 28 #pragma omp parallel default(none) shared(points, n, min_idx)
27 {
28 size_t local_min = 0;
29 #pragma omp for
30 for (size_t i = 1; i < n; ++i) {
31 if (points[i].y < points[local_min].y - 1e-9 ||
32 (std::abs(points[i].y - points[local_min].y) <= 1e-9 && points[i].x < points[local_min].x)) {
33 local_min = i;
34 }
35 }
36 #pragma omp critical
37 {
38 if (points[local_min].y < points[min_idx].y - 1e-9 ||
39 (std::abs(points[local_min].y - points[min_idx].y) <= 1e-9 && points[local_min].x < points[min_idx].x)) {
40 min_idx = local_min;
41 }
42 }
43 }
44 28 return min_idx;
45 }
46
47 template <typename RandomIt, typename Compare>
48
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 12 times.
 52 void OmpQuickSort(RandomIt first, RandomIt last, Compare comp) {
49
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 12 times.
 52 if (last - first < 2048) {
50 40 std::sort(first, last, comp);
51 40 return;
52 }
53 12 auto pivot = *(first + ((last - first) / 2));
54
4/4
✓ Branch 0 taken 6052 times.
✓ Branch 1 taken 4752 times.
✓ Branch 2 taken 20264 times.
✓ Branch 3 taken 4740 times.
 35820 RandomIt middle1 = std::partition(first, last, [pivot, comp](const auto &a) { return comp(a, pivot); });
55
3/4
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 24980 times.
✓ Branch 3 taken 12 times.
 25028 RandomIt middle2 = std::partition(middle1, last, [pivot, comp](const auto &a) { return !comp(pivot, a); });
56
57 12 #pragma omp task default(none) firstprivate(first, middle1, comp)
58 OmpQuickSort(first, middle1, comp);
59
60 12 #pragma omp task default(none) firstprivate(middle2, last, comp)
61 OmpQuickSort(middle2, last, comp);
62
63 12 #pragma omp taskwait
64 }
65
66 28 std::vector<Point> FilterPointsOMP(const std::vector<Point> &points, const Point &p0) {
67 size_t n = points.size();
68 28 std::vector<uint8_t> keep(n, 1);
69
70 28 #pragma omp parallel for default(none) shared(n, points, keep, p0)
71 for (size_t i = 1; i < n - 1; ++i) {
72 if (std::abs(CrossProduct(p0, points[i], points[i + 1])) < 1e-9) {
73 keep[i] = 0;
74 }
75 }
76
77 28 std::vector<Point> filtered;
78
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 filtered.reserve(n);
79
2/2
✓ Branch 0 taken 13316 times.
✓ Branch 1 taken 28 times.
 13344 for (size_t i = 0; i < n; ++i) {
80
2/2
✓ Branch 0 taken 7992 times.
✓ Branch 1 taken 5324 times.
 13316 if (keep[i] != 0) {
81 filtered.push_back(points[i]);
82 }
83 }
84 28 return filtered;
85 }
86
87 20 std::vector<Point> BuildHull(const std::vector<Point> &filtered) {
88
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 std::vector<Point> hull;
89 hull.push_back(filtered[0]);
90 hull.push_back(filtered[1]);
91 hull.push_back(filtered[2]);
92
93
2/2
✓ Branch 0 taken 7916 times.
✓ Branch 1 taken 20 times.
 7936 for (size_t i = 3; i < filtered.size(); ++i) {
94
3/4
✓ Branch 0 taken 15816 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 7900 times.
✓ Branch 3 taken 7916 times.
 15816 while (hull.size() > 1 && CrossProduct(hull[hull.size() - 2], hull.back(), filtered[i]) <= 1e-9) {
95 hull.pop_back();
96 }
97 hull.push_back(filtered[i]);
98 }
99 20 return hull;
100 }
101
102 } // namespace
103
104
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 ConvexHullGrahamOMP::ConvexHullGrahamOMP(const InType &in) {
105 SetTypeOfTask(GetStaticTypeOfTask());
106
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 GetInput() = in;
107 36 }
108
109 36 bool ConvexHullGrahamOMP::ValidationImpl() {
110 36 return true;
111 }
112
113 36 bool ConvexHullGrahamOMP::PreProcessingImpl() {
114 36 return true;
115 }
116
117 36 bool ConvexHullGrahamOMP::RunImpl() {
118 36 InType points = GetInput();
119
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 28 times.
 36 if (points.size() < 3) {
120
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 GetOutput() = points;
121 return true;
122 }
123
124 28 size_t min_idx = FindMinPointIndexOMP(points);
125
126 std::swap(points[0], points[min_idx]);
127 28 Point p0 = points[0];
128
129
2/2
✓ Branch 0 taken 16676 times.
✓ Branch 1 taken 203612 times.
 220288 auto comp = [p0](const Point &a, const Point &b) {
130 double cp = CrossProduct(p0, a, b);
131
2/2
✓ Branch 0 taken 16676 times.
✓ Branch 1 taken 203612 times.
 220288 if (std::abs(cp) < 1e-9) {
132 16676 return DistSq(p0, a) < DistSq(p0, b);
133 }
134 203612 return cp > 0;
135 28 };
136
137 28 #pragma omp parallel default(none) shared(points, comp)
138 {
139 #pragma omp single nowait
140 OmpQuickSort(points.begin() + 1, points.end(), comp);
141 }
142
143
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 InType filtered = FilterPointsOMP(points, p0);
144
145
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 20 times.
 28 if (filtered.size() < 3) {
146
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 GetOutput() = filtered;
147 return true;
148 }
149
150
1/4
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 20 GetOutput() = BuildHull(filtered);
151 20 return true;
152 }
153
154 36 bool ConvexHullGrahamOMP::PostProcessingImpl() {
155 36 return true;
156 }
157
158 } // namespace makovskiy_i_graham_hull
159