GCC Code Coverage Report

Directory: ./
File: tasks/perepelkin_i_convex_hull_graham_scan/omp/src/ops_omp.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 42 52 80.8%
Functions: 8 9 88.9%
Branches: 29 102 28.4%
Line Branch Exec Source
1 #include "perepelkin_i_convex_hull_graham_scan/omp/include/ops_omp.hpp"
2
3 #include <omp.h>
4
5 #include <algorithm>
6 #include <cmath>
7 #include <cstddef>
8 #include <utility>
9 #include <vector>
10
11 #include "perepelkin_i_convex_hull_graham_scan/common/include/common.hpp"
12 #include "util/include/util.hpp"
13
14 namespace perepelkin_i_convex_hull_graham_scan {
15
16
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 PerepelkinIConvexHullGrahamScanOMP::PerepelkinIConvexHullGrahamScanOMP(const InType &in) {
17 SetTypeOfTask(GetStaticTypeOfTask());
18
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 GetInput() = in;
19 48 GetOutput() = std::vector<std::pair<double, double>>();
20 48 }
21
22 48 bool PerepelkinIConvexHullGrahamScanOMP::ValidationImpl() {
23 48 return GetOutput().empty();
24 }
25
26 48 bool PerepelkinIConvexHullGrahamScanOMP::PreProcessingImpl() {
27 48 return true;
28 }
29
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 40 times.
 48 bool PerepelkinIConvexHullGrahamScanOMP::RunImpl() {
30 const auto &data = GetInput();
31
32
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 40 times.
 48 if (data.size() < 2) {
33 8 GetOutput() = data;
34 8 return true;
35 }
36
37 40 std::vector<std::pair<double, double>> pts = data;
38
39 // Find pivot
40
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 size_t pivot_idx = FindPivotParallel(pts);
41
42 std::pair<double, double> pivot = pts[pivot_idx];
43 pts.erase(pts.begin() + static_cast<std::ptrdiff_t>(pivot_idx));
44
45 // Parallel sorting
46
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 ParallelSort(pts, pivot);
47
48 // Sequential hull construction
49
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 std::vector<std::pair<double, double>> hull;
50
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 hull.reserve(pts.size() + 1);
51
52 hull.push_back(pivot);
53 hull.push_back(pts[0]);
54
55
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 40 times.
 168 for (size_t i = 1; i < pts.size(); i++) {
56
4/4
✓ Branch 0 taken 168 times.
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 40 times.
✓ Branch 3 taken 104 times.
 336 while (hull.size() >= 2 && Orientation(hull[hull.size() - 2], hull[hull.size() - 1], pts[i]) <= 0) {
57 hull.pop_back();
58 }
59
60 hull.push_back(pts[i]);
61 }
62
63 GetOutput() = std::move(hull);
64 return true;
65 }
66
67 40 size_t PerepelkinIConvexHullGrahamScanOMP::FindPivotParallel(const std::vector<std::pair<double, double>> &pts) {
68 size_t pivot_idx = 0;
69
70 40 #pragma omp parallel default(none) shared(pts, pivot_idx) num_threads(ppc::util::GetNumThreads())
71 {
72 size_t local_idx = pivot_idx;
73
74 #pragma omp for nowait
75 for (size_t i = 1; i < pts.size(); i++) {
76 if (pts[i].second < pts[local_idx].second ||
77 (pts[i].second == pts[local_idx].second && pts[i].first < pts[local_idx].first)) {
78 local_idx = i;
79 }
80 }
81
82 #pragma omp critical
83 {
84 if (pts[local_idx].second < pts[pivot_idx].second ||
85 (pts[local_idx].second == pts[pivot_idx].second && pts[local_idx].first < pts[pivot_idx].first)) {
86 pivot_idx = local_idx;
87 }
88 }
89 }
90
91 40 return pivot_idx;
92 }
93
94 40 void PerepelkinIConvexHullGrahamScanOMP::ParallelSort(std::vector<std::pair<double, double>> &data,
95 const std::pair<double, double> &pivot) {
96 size_t n = data.size();
97 40 int threads = ppc::util::GetNumThreads();
98
99
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 40 if (n < 10000) {
100
4/24
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 92 times.
✓ Branch 5 taken 108 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✓ Branch 22 taken 20 times.
✓ Branch 23 taken 108 times.
 328 std::ranges::sort(data, [&](const auto &a, const auto &b) { return AngleCmp(a, b, pivot); });
101 40 return;
102 }
103
104 ✗ std::vector<int> start(threads + 1);
105 ✗ for (int i = 0; i <= threads; i++) {
106 ✗ start[i] = static_cast<int>(i * n / threads);
107 }
108
109 ✗ #pragma omp parallel default(none) shared(data, start, pivot) num_threads(ppc::util::GetNumThreads())
110 {
111 int tid = omp_get_thread_num();
112 std::sort(data.begin() + start[tid], data.begin() + start[tid + 1],
113 ✗ [&](const auto &a, const auto &b) { return AngleCmp(a, b, pivot); });
114 }
115
116 // Merge sorted segments
117 ✗ for (int size = 1; size < threads; size *= 2) {
118 ✗ #pragma omp parallel for default(none) shared(data, start, threads, size, pivot) num_threads(ppc::util::GetNumThreads())
119 for (int i = 0; i < threads; i += 2 * size) {
120 if (i + size >= threads) {
121 continue;
122 }
123
124 int left = start[i];
125 int mid = start[i + size];
126 int right = start[std::min(i + (2 * size), threads)];
127
128 std::inplace_merge(data.begin() + left, data.begin() + mid, data.begin() + right,
129 ✗ [&](const auto &a, const auto &b) { return AngleCmp(a, b, pivot); });
130 }
131 }
132 }
133
134 ✗ double PerepelkinIConvexHullGrahamScanOMP::Orientation(const std::pair<double, double> &p,
135 const std::pair<double, double> &q,
136 const std::pair<double, double> &r) {
137
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
✓ Branch 3 taken 144 times.
 168 double val = ((q.first - p.first) * (r.second - p.second)) - ((q.second - p.second) * (r.first - p.first));
138
139
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
✓ Branch 3 taken 144 times.
 168 if (std::abs(val) < 1e-9) {
140 ✗ return 0.0;
141 }
142
143 return val;
144 }
145
146 328 bool PerepelkinIConvexHullGrahamScanOMP::AngleCmp(const std::pair<double, double> &a,
147 const std::pair<double, double> &b,
148 const std::pair<double, double> &pivot) {
149 328 double dx1 = a.first - pivot.first;
150 328 double dy1 = a.second - pivot.second;
151 328 double dx2 = b.first - pivot.first;
152 328 double dy2 = b.second - pivot.second;
153
154
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 256 times.
 328 double cross = (dx1 * dy2) - (dy1 * dx2);
155
156
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 256 times.
 328 if (std::abs(cross) < 1e-9) {
157 72 double dist1 = (dx1 * dx1) + (dy1 * dy1);
158 72 double dist2 = (dx2 * dx2) + (dy2 * dy2);
159 72 return dist1 < dist2;
160 }
161
162 256 return cross > 0;
163 }
164
165 48 bool PerepelkinIConvexHullGrahamScanOMP::PostProcessingImpl() {
166 48 return true;
167 }
168
169 } // namespace perepelkin_i_convex_hull_graham_scan
170