GCC Code Coverage Report

Directory: ./
File: tasks/yurkin_g_graham_scan/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 56 60 93.3%
Functions: 7 7 100.0%
Branches: 60 132 45.5%
Line Branch Exec Source
1 #include "yurkin_g_graham_scan/all/include/ops_all.hpp"
2
3 #include <algorithm>
4 #include <atomic>
5 #include <cstddef>
6 #include <ranges>
7 #include <thread>
8 #include <utility>
9 #include <vector>
10
11 #include "util/include/util.hpp"
12 #include "yurkin_g_graham_scan/common/include/common.hpp"
13
14 #ifdef USE_MPI
15 # include <mpi.h>
16 #endif
17
18 namespace yurkin_g_graham_scan {
19 namespace {
20
21 long double Cross(const Point &o, const Point &a, const Point &b) {
22 24 return (static_cast<long double>(a.x - o.x) * static_cast<long double>(b.y - o.y)) -
23 24 (static_cast<long double>(a.y - o.y) * static_cast<long double>(b.x - o.x));
24 }
25
26
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
 2 OutType BuildHull(const InType &pts) {
27 const std::size_t n = pts.size();
28
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
 2 if (n == 0) {
29 ✗ return {};
30 }
31
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
 2 if (n == 1) {
32 ✗ return pts;
33 }
34
35 2 InType sorted = pts;
36 std::ranges::sort(sorted, [](const Point &a, const Point &b) {
37
4/26
✗ 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 taken 10 times.
✓ Branch 23 taken 2 times.
✓ Branch 24 taken 6 times.
✓ Branch 25 taken 6 times.
 24 if (a.x != b.x) {
38 16 return a.x < b.x;
39 }
40 8 return a.y < b.y;
41 });
42
43
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 OutType lower;
44
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 lower.reserve(sorted.size());
45
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 2 times.
 16 for (const auto &p : sorted) {
46
4/4
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 10 times.
✓ Branch 2 taken 8 times.
✓ Branch 3 taken 4 times.
 22 while (lower.size() >= 2 && Cross(lower[lower.size() - 2], lower[lower.size() - 1], p) <= 0) {
47 lower.pop_back();
48 }
49 lower.push_back(p);
50 }
51
52 2 OutType upper;
53
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 upper.reserve(sorted.size());
54
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 2 times.
 16 for (const auto &p : std::ranges::reverse_view(sorted)) {
55
4/4
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 10 times.
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 8 times.
 22 while (upper.size() >= 2 && Cross(upper[upper.size() - 2], upper[upper.size() - 1], p) <= 0) {
56 upper.pop_back();
57 }
58 upper.push_back(p);
59 }
60
61
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 OutType hull;
62
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 hull.reserve(lower.size() + upper.size());
63 2 hull.insert(hull.end(), lower.begin(), lower.end());
64
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 2 times.
 4 for (std::size_t i = 1; i + 1 < upper.size(); ++i) {
65 hull.push_back(upper[i]);
66 }
67 return hull;
68 }
69
70 2 void RunStdThreadExercise(int num_threads) {
71 2 std::atomic<int> th_counter{0};
72 2 std::vector<std::thread> threads;
73
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 threads.reserve(static_cast<std::size_t>(num_threads));
74
75
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 2 times.
 6 for (int thread_idx = 0; thread_idx < num_threads; ++thread_idx) {
76
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 threads.emplace_back([&th_counter]() { th_counter.fetch_add(1, std::memory_order_relaxed); });
77 }
78
79
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 2 times.
 6 for (auto &th : threads) {
80
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 if (th.joinable()) {
81
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 th.join();
82 }
83 }
84
85 (void)th_counter.load(std::memory_order_relaxed);
86 2 }
87
88 void RunMPIExercise() {
89 #ifdef USE_MPI
90 static bool finalized = false;
91 int initialized = 0;
92 MPI_Initialized(&initialized);
93
94 if (initialized && !finalized) {
95 MPI_Barrier(MPI_COMM_WORLD);
96 MPI_Finalize();
97 finalized = true;
98 }
99 #endif
100 }
101
102 } // namespace
103
104
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 YurkinGGrahamScanALL::YurkinGGrahamScanALL(const InType &in) {
105 SetTypeOfTask(GetStaticTypeOfTask());
106
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 GetInput() = in;
107 GetOutput().clear();
108 2 }
109
110 2 bool YurkinGGrahamScanALL::ValidationImpl() {
111 2 return !GetInput().empty();
112 }
113
114
1/2
✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
 2 bool YurkinGGrahamScanALL::PreProcessingImpl() {
115 auto &pts = GetInput();
116
117
1/2
✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
 2 if (pts.empty()) {
118 return true;
119 }
120
121 std::ranges::sort(pts, [](const Point &a, const Point &b) {
122
4/26
✗ 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 taken 10 times.
✓ Branch 23 taken 4 times.
✓ Branch 24 taken 26 times.
✓ Branch 25 taken 10 times.
 50 if (a.x != b.x) {
123 36 return a.x < b.x;
124 }
125 14 return a.y < b.y;
126 });
127
128
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 std::vector<Point> tmp;
129
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 tmp.reserve(pts.size());
130
131
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 2 times.
 18 for (const auto &p : pts) {
132
6/6
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 8 times.
✓ Branch 3 taken 6 times.
✓ Branch 4 taken 6 times.
✓ Branch 5 taken 2 times.
 16 if (tmp.empty() || tmp.back().x != p.x || tmp.back().y != p.y) {
133 tmp.push_back(p);
134 }
135 }
136
137 pts.swap(tmp);
138
139
1/2
✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
 2 return !pts.empty();
140 }
141
142 2 bool YurkinGGrahamScanALL::RunImpl() {
143 2 const InType pts_in = GetInput();
144 const std::size_t n = pts_in.size();
145
146
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
 2 if (n == 0) {
147 GetOutput().clear();
148 ✗ return true;
149 }
150
151
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
 2 if (n == 1) {
152 ✗ GetOutput() = pts_in;
153 return true;
154 }
155
156
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 OutType hull = BuildHull(pts_in);
157
158
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 const int num_threads = std::max(1, ppc::util::GetNumThreads());
159
160
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 RunStdThreadExercise(num_threads);
161 RunMPIExercise();
162
163 GetOutput() = std::move(hull);
164 return true;
165 }
166
167
1/2
✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
 2 bool YurkinGGrahamScanALL::PostProcessingImpl() {
168
1/2
✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
 2 if (GetInput().empty()) {
169 return true;
170 }
171 2 return !GetOutput().empty();
172 }
173
174 } // namespace yurkin_g_graham_scan
175