GCC Code Coverage Report

Directory: ./
File: tasks/orehov_n_jarvis_pass/all/src/ops_all.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 94 107 87.9%
Functions: 9 14 64.3%
Branches: 66 98 67.3%
Line Branch Exec Source
1 #include "orehov_n_jarvis_pass/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4 #include <omp.h>
5
6 #include <algorithm>
7 #include <array>
8 #include <cmath>
9 #include <cstddef>
10 #include <set>
11 #include <utility>
12 #include <vector>
13
14 #include "orehov_n_jarvis_pass/common/include/common.hpp"
15
16 namespace orehov_n_jarvis_pass {
17
18 25 bool OrehovNJarvisPassALL::IsBetterPoint(const Point &current, const Point &candidate, const Point &best) {
19 double orient = CheckLeft(current, best, candidate);
20 25 if (orient > 0.0) {
21 return true;
22 }
23
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 15 times.
 16 if (orient == 0.0) {
24 double dx_c = candidate.x - current.x;
25 double dy_c = candidate.y - current.y;
26 1 double dist_c = (dx_c * dx_c) + (dy_c * dy_c);
27
28 double dx_b = best.x - current.x;
29 double dy_b = best.y - current.y;
30 1 double dist_b = (dx_b * dx_b) + (dy_b * dy_b);
31
32 1 return dist_c > dist_b;
33 }
34 return false;
35 }
36
37 14 OrehovNJarvisPassALL::BestState OrehovNJarvisPassALL::ReduceBestStates(const BestState &a, const BestState &b,
38 const Point &current) {
39
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 14 times.
 14 if (!a.valid) {
40 ✗ return b;
41 }
42
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 14 times.
 14 if (!b.valid) {
43 ✗ return a;
44 }
45
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 8 times.
 14 return BestState{.point = IsBetterPoint(current, b.point, a.point) ? b.point : a.point, .valid = true};
46 }
47
48
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 OrehovNJarvisPassALL::OrehovNJarvisPassALL(const InType &in) {
49 SetTypeOfTask(GetStaticTypeOfTask());
50
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 GetInput() = in;
51 6 GetOutput() = std::vector<Point>();
52 6 }
53
54 6 bool OrehovNJarvisPassALL::ValidationImpl() {
55 6 int rank = 0;
56 6 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
57
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (rank == 0) {
58 3 return !GetInput().empty();
59 }
60 return true;
61 }
62
63 6 bool OrehovNJarvisPassALL::PreProcessingImpl() {
64 6 int rank = 0;
65 6 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
66 6 int size = 0;
67 6 MPI_Comm_size(MPI_COMM_WORLD, &size);
68
69
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (rank == 0) {
70 3 std::set<Point> tmp(GetInput().begin(), GetInput().end());
71
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 input_.assign(tmp.begin(), tmp.end());
72 }
73
74
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 size_t vec_size = (rank == 0) ? input_.size() : 0;
75 6 MPI_Bcast(&vec_size, 1, MPI_UINT64_T, 0, MPI_COMM_WORLD);
76
77
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (rank != 0) {
78 3 input_.resize(vec_size);
79 }
80
81 6 std::vector<double> buffer(vec_size * 2);
82
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (rank == 0) {
83
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 3 times.
 13 for (size_t i = 0; i < vec_size; ++i) {
84 10 buffer[2 * i] = input_[i].x;
85 10 buffer[(2 * i) + 1] = input_[i].y;
86 }
87 }
88
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Bcast(buffer.data(), static_cast<int>(vec_size * 2), MPI_DOUBLE, 0, MPI_COMM_WORLD);
89
90
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (rank != 0) {
91
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 3 times.
 13 for (size_t i = 0; i < vec_size; ++i) {
92 10 input_[i].x = buffer[2 * i];
93 10 input_[i].y = buffer[(2 * i) + 1];
94 }
95 }
96 6 return true;
97 }
98
99
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 2 times.
 6 bool OrehovNJarvisPassALL::RunImpl() {
100
4/4
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 2 times.
 6 if (input_.size() == 1 || input_.size() == 2) {
101 4 res_ = input_;
102 4 return true;
103 }
104
105 2 Point current = FindFirstElem();
106
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
 2 res_.push_back(current);
107
108 while (true) {
109 10 Point next = FindNext(current);
110 if (next == res_[0]) {
111 break;
112 }
113
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 6 times.
 8 current = next;
114 res_.push_back(next);
115 8 }
116 2 return true;
117 }
118
119 ✗ OrehovNJarvisPassALL::BestState OrehovNJarvisPassALL::LocalFindBest(const Point &current, size_t start,
120 size_t end) const {
121 BestState local_best;
122 // Сохраняем this в константную переменную для shared
123 const auto *self = this;
124 10 #pragma omp parallel default(none) shared(local_best, start, end, current, self)
125 {
126 BestState thread_best;
127 #pragma omp for nowait
128 for (size_t i = start; i < end; ++i) {
129 const Point &p = self->input_[i];
130 if (p == current) {
131 continue;
132 }
133 if (!thread_best.valid || IsBetterPoint(current, p, thread_best.point)) {
134 thread_best.point = p;
135 thread_best.valid = true;
136 }
137 }
138 #pragma omp critical
139 {
140 if (thread_best.valid) {
141 if (!local_best.valid) {
142 local_best = thread_best;
143 } else {
144 local_best = ReduceBestStates(local_best, thread_best, current);
145 }
146 }
147 }
148 }
149 ✗ return local_best;
150 }
151
152 5 OrehovNJarvisPassALL::BestState OrehovNJarvisPassALL::GlobalReduce(const std::vector<double> &all_data, int size,
153 const Point &current) {
154 BestState global_best;
155
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 5 times.
 15 for (size_t i = 0; std::cmp_less(i, static_cast<size_t>(size)); ++i) {
156 10 double x = all_data[3 * i];
157 10 double y = all_data[(3 * i) + 1];
158 10 bool v = (all_data[(3 * i) + 2] != 0.0);
159
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 10 if (v) {
160
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 BestState proc_best{.point = Point(x, y), .valid = true};
161
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 if (!global_best.valid) {
162 5 global_best = proc_best;
163 } else {
164 5 global_best = ReduceBestStates(global_best, proc_best, current);
165 }
166 }
167 }
168 5 return global_best;
169 }
170
171 ✗ OrehovNJarvisPassALL::BestState OrehovNJarvisPassALL::FinalizeBestPoint(const double *global_data) {
172
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 10 return BestState{.point = Point(global_data[0], global_data[1]), .valid = (global_data[2] != 0.0)};
173 }
174
175
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 10 times.
 10 Point OrehovNJarvisPassALL::FindNext(Point current) const {
176 const size_t n = input_.size();
177
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 10 times.
 10 if (n == 0) {
178 ✗ return current;
179 }
180
181 10 int rank = 0;
182 10 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
183 10 int size = 0;
184 10 MPI_Comm_size(MPI_COMM_WORLD, &size);
185
186 10 size_t chunk = n / size;
187 10 size_t rest = n % size;
188
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 size_t start = (static_cast<size_t>(rank) * chunk) + std::min(static_cast<size_t>(rank), rest);
189
3/4
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
✓ Branch 2 taken 10 times.
✗ Branch 3 not taken.
 15 size_t end = start + chunk + (std::cmp_less(static_cast<size_t>(rank), rest) ? 1 : 0);
190
191 BestState local_best = LocalFindBest(current, start, end);
192
193
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 10 std::array<double, 3> local_data = {local_best.valid ? local_best.point.x : 0.0,
194
2/4
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 10 times.
 10 local_best.valid ? local_best.point.y : 0.0, local_best.valid ? 1.0 : 0.0};
195
196
1/2
✓ Branch 2 taken 10 times.
✗ Branch 3 not taken.
 10 std::vector<double> all_data(static_cast<size_t>(size) * 3);
197
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 MPI_Gather(local_data.data(), 3, MPI_DOUBLE, all_data.data(), 3, MPI_DOUBLE, 0, MPI_COMM_WORLD);
198
199 10 std::array<double, 3> global_data = {0.0, 0.0, 0.0};
200
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 if (rank == 0) {
201 5 BestState global_best = GlobalReduce(all_data, size, current);
202
1/2
✓ Branch 0 taken 5 times.
✗ Branch 1 not taken.
 5 if (global_best.valid) {
203 5 global_data[0] = global_best.point.x;
204 5 global_data[1] = global_best.point.y;
205 5 global_data[2] = 1.0;
206 }
207 }
208
209
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 MPI_Bcast(global_data.data(), 3, MPI_DOUBLE, 0, MPI_COMM_WORLD);
210 BestState final_best = FinalizeBestPoint(global_data.data());
211
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 10 return final_best.valid ? final_best.point : current;
212 }
213
214 ✗ double OrehovNJarvisPassALL::CheckLeft(Point a, Point b, Point c) {
215
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 9 times.
 25 return ((b.x - a.x) * (c.y - a.y)) - ((b.y - a.y) * (c.x - a.x));
216 }
217
218 ✗ Point OrehovNJarvisPassALL::FindFirstElem() const {
219 ✗ Point current = input_[0];
220
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 14 times.
✓ Branch 3 taken 2 times.
 16 for (const auto &f : input_) {
221
2/12
✗ 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 taken 14 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 14 times.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
 14 if (f.x < current.x || (f.y < current.y && f.x == current.x)) {
222 ✗ current = f;
223 }
224 }
225 ✗ return current;
226 }
227
228 ✗ double OrehovNJarvisPassALL::Distance(Point a, Point b) {
229 ✗ return std::sqrt(std::pow(a.y - b.y, 2) + std::pow(a.x - b.x, 2));
230 }
231
232 6 bool OrehovNJarvisPassALL::PostProcessingImpl() {
233 6 GetOutput() = res_;
234 6 return true;
235 }
236
237 } // namespace orehov_n_jarvis_pass
238