GCC Code Coverage Report

Directory: ./
File: tasks/yurkin_g_graham_scan/omp/src/ops_omp.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 41 43 95.3%
Functions: 5 5 100.0%
Branches: 50 146 34.2%
Line Branch Exec Source
1 #include "yurkin_g_graham_scan/omp/include/ops_omp.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <ranges>
6 #include <vector>
7
8 #if defined(__cpp_lib_execution) && (__cpp_lib_execution >= 201603)
9 # include <execution>
10 #endif
11
12 #include "yurkin_g_graham_scan/common/include/common.hpp"
13
14 namespace yurkin_g_graham_scan {
15
16
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 YurkinGGrahamScanOMP::YurkinGGrahamScanOMP(const InType &in) {
17 SetTypeOfTask(GetStaticTypeOfTask());
18
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 GetInput() = in;
19 GetOutput().clear();
20 4 }
21
22 4 bool YurkinGGrahamScanOMP::ValidationImpl() {
23 4 return !GetInput().empty();
24 }
25
26
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 bool YurkinGGrahamScanOMP::PreProcessingImpl() {
27 auto &pts = GetInput();
28
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 if (pts.empty()) {
29 return true;
30 }
31
32 // Сортировка по x, затем по y. При наличии поддержки execution policy
33 // используем параллельную политику для ускорения.
34 #if defined(__cpp_lib_execution) && (__cpp_lib_execution >= 201603)
35 std::sort(std::execution::par, pts.begin(), pts.end(), [](const Point &a, const Point &b) {
36
4/42
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ 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 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 30 not taken.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 36 not taken.
✗ Branch 37 not taken.
✓ Branch 38 taken 20 times.
✓ Branch 39 taken 8 times.
✓ Branch 40 taken 52 times.
✓ Branch 41 taken 20 times.
 100 if (a.x != b.x) {
37 72 return a.x < b.x;
38 }
39 28 return a.y < b.y;
40 });
41 #else
42 std::sort(pts.begin(), pts.end(), [](const Point &a, const Point &b) {
43 if (a.x != b.x) {
44 return a.x < b.x;
45 }
46 return a.y < b.y;
47 });
48 #endif
49
50 // Удаление дубликатов (последовательный проход)
51
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 std::vector<Point> tmp;
52
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 tmp.reserve(pts.size());
53
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 4 times.
 36 for (const auto &p : pts) {
54
6/6
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 16 times.
✓ Branch 3 taken 12 times.
✓ Branch 4 taken 12 times.
✓ Branch 5 taken 4 times.
 32 if (tmp.empty() || tmp.back().x != p.x || tmp.back().y != p.y) {
55 tmp.push_back(p);
56 }
57 }
58 pts.swap(tmp);
59
60
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 return !pts.empty();
61 }
62
63 namespace { // helper: cross product
64 long double Cross(const Point &o, const Point &a, const Point &b) {
65 48 return (static_cast<long double>(a.x - o.x) * static_cast<long double>(b.y - o.y)) -
66 48 (static_cast<long double>(a.y - o.y) * static_cast<long double>(b.x - o.x));
67 }
68 } // namespace
69
70 4 bool YurkinGGrahamScanOMP::RunImpl() {
71 4 const InType pts_in = GetInput();
72 const std::size_t n = pts_in.size();
73
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
 4 if (n == 0) {
74 GetOutput().clear();
75 ✗ return true;
76 }
77
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
 4 if (n == 1) {
78 ✗ GetOutput() = pts_in;
79 return true;
80 }
81
82 // Локальная копия точек; сортировка для надёжности (PreProcessing уже сортировал)
83
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 InType pts = pts_in;
84 #if defined(__cpp_lib_execution) && (__cpp_lib_execution >= 201603)
85 std::sort(std::execution::par, pts.begin(), pts.end(), [](const Point &a, const Point &b) {
86
4/42
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ 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 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 30 not taken.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 36 not taken.
✗ Branch 37 not taken.
✓ Branch 38 taken 20 times.
✓ Branch 39 taken 4 times.
✓ Branch 40 taken 12 times.
✓ Branch 41 taken 12 times.
 48 if (a.x != b.x) {
87 32 return a.x < b.x;
88 }
89 16 return a.y < b.y;
90 });
91 #else
92 std::sort(pts.begin(), pts.end(), [](const Point &a, const Point &b) {
93 if (a.x != b.x) {
94 return a.x < b.x;
95 }
96 return a.y < b.y;
97 });
98 #endif
99
100 // Построение нижней оболочки
101
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 OutType lower;
102
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 lower.reserve(pts.size());
103
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 4 times.
 32 for (const auto &p : pts) {
104
4/4
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 20 times.
✓ Branch 2 taken 16 times.
✓ Branch 3 taken 8 times.
 44 while (lower.size() >= 2 && Cross(lower[lower.size() - 2], lower[lower.size() - 1], p) <= 0) {
105 lower.pop_back();
106 }
107 lower.push_back(p);
108 }
109
110 // Построение верхней оболочки (range-based обратный проход)
111 4 OutType upper;
112
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 upper.reserve(pts.size());
113
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 4 times.
 32 for (const auto &p : std::ranges::reverse_view(pts)) {
114
4/4
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 20 times.
✓ Branch 2 taken 8 times.
✓ Branch 3 taken 16 times.
 44 while (upper.size() >= 2 && Cross(upper[upper.size() - 2], upper[upper.size() - 1], p) <= 0) {
115 upper.pop_back();
116 }
117 upper.push_back(p);
118 }
119
120 // Объединение (без дублирования крайних точек)
121
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 OutType hull;
122
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 hull.reserve(lower.size() + upper.size());
123
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 4 times.
 16 for (const auto &pt : lower) {
124 hull.push_back(pt);
125 }
126
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 for (std::size_t i = 1; i + 1 < upper.size(); ++i) {
127 hull.push_back(upper[i]);
128 }
129
130
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 GetOutput() = hull;
131 return true;
132 }
133
134
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 bool YurkinGGrahamScanOMP::PostProcessingImpl() {
135
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 if (GetInput().empty()) {
136 return true;
137 }
138 4 return !GetOutput().empty();
139 }
140
141 } // namespace yurkin_g_graham_scan
142