GCC Code Coverage Report

Directory: ./
File: tasks/gaivoronskiy_m_grachem_method/mpi/src/ops_mpi.cpp
Date: 2026-01-27 01:59:34
Exec Total Coverage
Lines: 137 142 96.5%
Functions: 14 15 93.3%
Branches: 120 180 66.7%
Line Branch Exec Source
1 #include "gaivoronskiy_m_grachem_method/mpi/include/ops_mpi.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <cmath>
7 #include <cstddef>
8 #include <stack>
9 #include <vector>
10
11 #include "gaivoronskiy_m_grachem_method/common/include/common.hpp"
12
13 namespace gaivoronskiy_m_grachem_method {
14
15 namespace {
16 int Orientation(const Point &p, const Point &q, const Point &r) {
17
4/4
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 128 times.
✓ Branch 2 taken 12 times.
✓ Branch 3 taken 97 times.
 238 double val = ((q.y - p.y) * (r.x - q.x)) - ((q.x - p.x) * (r.y - q.y));
18 constexpr double kEps = 1e-9;
19
6/6
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 128 times.
✓ Branch 2 taken 12 times.
✓ Branch 3 taken 97 times.
✓ Branch 4 taken 23 times.
✓ Branch 5 taken 484 times.
 745 if (std::abs(val) < kEps) {
20 return 0;
21 }
22
4/4
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 84 times.
✓ Branch 2 taken 198 times.
✓ Branch 3 taken 286 times.
 612 return (val > 0) ? 1 : 2;
23 }
24
25 double DistSquare(const Point &p1, const Point &p2) {
26 23 return ((p1.x - p2.x) * (p1.x - p2.x)) + ((p1.y - p2.y) * (p1.y - p2.y));
27 }
28
29
2/2
✓ Branch 0 taken 23 times.
✓ Branch 1 taken 484 times.
 507 bool Compare(const Point &p1, const Point &p2, const Point &p0) {
30 int o = Orientation(p0, p1, p2);
31 if (o == 0) {
32 23 return DistSquare(p0, p1) < DistSquare(p0, p2);
33 }
34 484 return (o == 2);
35 }
36 } // namespace
37
38
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 GaivoronskiyMGrahamScanMPI::GaivoronskiyMGrahamScanMPI(const InType &in) {
39 SetTypeOfTask(GetStaticTypeOfTask());
40
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 GetInput() = in;
41 GetOutput().clear();
42 12 }
43
44 12 bool GaivoronskiyMGrahamScanMPI::ValidationImpl() {
45 12 int rank = 0;
46 12 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
47
48
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 if (rank == 0) {
49 6 return GetInput().size() >= 3;
50 }
51 return true;
52 }
53
54 12 bool GaivoronskiyMGrahamScanMPI::PreProcessingImpl() {
55 12 int rank = 0;
56 12 int size = 0;
57 12 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
58 12 MPI_Comm_size(MPI_COMM_WORLD, &size);
59
60 12 int n_points = 0;
61
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 if (rank == 0) {
62 6 points_ = GetInput();
63 6 n_points = static_cast<int>(points_.size());
64 }
65
66 12 MPI_Bcast(&n_points, 1, MPI_INT, 0, MPI_COMM_WORLD);
67
68 12 int base_size = n_points / size;
69 12 int remainder = n_points % size;
70
71 12 std::vector<int> send_counts(size);
72
1/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 12 std::vector<int> displs(size);
73
74
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 12 times.
 36 for (int i = 0; i < size; i++) {
75
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 6 times.
 42 send_counts[i] = (base_size + (i < remainder ? 1 : 0)) * 2;
76 24 displs[i] = (i * base_size + std::min(i, remainder)) * 2;
77 }
78
79
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 int local_size = send_counts[rank] / 2;
80
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 local_points_.resize(local_size);
81
82 12 std::vector<double> flat_points;
83
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 if (rank == 0) {
84
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 flat_points.resize(static_cast<size_t>(n_points) * 2);
85
2/2
✓ Branch 0 taken 93 times.
✓ Branch 1 taken 6 times.
 99 for (int i = 0; i < n_points; i++) {
86 93 flat_points[static_cast<size_t>(i) * 2] = points_[i].x;
87 93 flat_points[(static_cast<size_t>(i) * 2) + 1] = points_[i].y;
88 }
89 }
90
91
1/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 12 std::vector<double> local_flat(static_cast<size_t>(local_size) * 2);
92
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 MPI_Scatterv(flat_points.data(), send_counts.data(), displs.data(), MPI_DOUBLE, local_flat.data(), send_counts[rank],
93 MPI_DOUBLE, 0, MPI_COMM_WORLD);
94
95
2/2
✓ Branch 0 taken 93 times.
✓ Branch 1 taken 12 times.
 105 for (int i = 0; i < local_size; i++) {
96 93 local_points_[i].x = local_flat[static_cast<size_t>(i) * 2];
97 93 local_points_[i].y = local_flat[(static_cast<size_t>(i) * 2) + 1];
98 }
99
100 12 return true;
101 }
102
103 18 std::vector<double> GaivoronskiyMGrahamScanMPI::PointsToFlat(const std::vector<Point> &points) {
104 18 std::vector<double> flat_data(points.size() * 2);
105
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 18 times.
 106 for (size_t i = 0; i < points.size(); i++) {
106 88 flat_data[(i * 2)] = points[i].x;
107 88 flat_data[(i * 2) + 1] = points[i].y;
108 }
109 18 return flat_data;
110 }
111
112 12 std::vector<Point> GaivoronskiyMGrahamScanMPI::FlatToPoints(const std::vector<double> &flat_data, int num_points) {
113 12 std::vector<Point> points(num_points);
114
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 12 times.
 100 for (int i = 0; i < num_points; i++) {
115 88 points[i].x = flat_data[static_cast<size_t>(i) * 2];
116 88 points[i].y = flat_data[(static_cast<size_t>(i) * 2) + 1];
117 }
118 12 return points;
119 }
120
121 12 void GaivoronskiyMGrahamScanMPI::GatherAndMergeHulls(const std::vector<Point> &local_hull, int rank, int size) {
122 12 int local_hull_size = static_cast<int>(local_hull.size());
123
1/2
✓ Branch 2 taken 12 times.
✗ Branch 3 not taken.
 12 std::vector<int> hull_sizes(size);
124
125
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 MPI_Gather(&local_hull_size, 1, MPI_INT, hull_sizes.data(), 1, MPI_INT, 0, MPI_COMM_WORLD);
126
127
1/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 12 std::vector<int> displs(size);
128
1/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 12 std::vector<int> recv_counts(size);
129 int total_hull_points = 0;
130
131
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 if (rank == 0) {
132
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 6 times.
 18 for (int i = 0; i < size; i++) {
133 12 recv_counts[i] = hull_sizes[i] * 2;
134 12 displs[i] = total_hull_points * 2;
135 12 total_hull_points += hull_sizes[i];
136 }
137 }
138
139
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 std::vector<double> local_hull_flat = PointsToFlat(local_hull);
140
141 12 std::vector<double> all_hulls_flat;
142
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 if (rank == 0) {
143
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 all_hulls_flat.resize(static_cast<size_t>(total_hull_points) * 2);
144 }
145
146
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 MPI_Gatherv(local_hull_flat.data(), local_hull_size * 2, MPI_DOUBLE, all_hulls_flat.data(), recv_counts.data(),
147 displs.data(), MPI_DOUBLE, 0, MPI_COMM_WORLD);
148
149
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 if (rank == 0) {
150
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 std::vector<Point> combined_points = FlatToPoints(all_hulls_flat, total_hull_points);
151
2/6
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 6 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 12 hull_ = GrahamScan(combined_points);
152 }
153 12 }
154
155 12 void GaivoronskiyMGrahamScanMPI::BroadcastResult(int rank) {
156 12 int result_size = 0;
157
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 if (rank == 0) {
158 6 result_size = static_cast<int>(hull_.size());
159 }
160 12 MPI_Bcast(&result_size, 1, MPI_INT, 0, MPI_COMM_WORLD);
161
162
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 if (rank != 0) {
163 6 hull_.resize(result_size);
164 }
165
166 12 std::vector<double> result_flat;
167
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 if (rank == 0) {
168
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 12 result_flat = PointsToFlat(hull_);
169 } else {
170
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 result_flat.resize(static_cast<size_t>(result_size) * 2);
171 }
172
173
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 MPI_Bcast(result_flat.data(), result_size * 2, MPI_DOUBLE, 0, MPI_COMM_WORLD);
174
175
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 if (rank != 0) {
176
1/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 12 hull_ = FlatToPoints(result_flat, result_size);
177 }
178 12 }
179
180 12 bool GaivoronskiyMGrahamScanMPI::RunImpl() {
181 12 int rank = 0;
182 12 int size = 0;
183 12 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
184 12 MPI_Comm_size(MPI_COMM_WORLD, &size);
185
186
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 std::vector<Point> local_hull;
187
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 if (!local_points_.empty()) {
188
1/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 24 local_hull = GrahamScan(local_points_);
189 }
190
191
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 GatherAndMergeHulls(local_hull, rank, size);
192
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 BroadcastResult(rank);
193
194
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 GetOutput() = hull_;
195
196 12 return true;
197 }
198
199 12 bool GaivoronskiyMGrahamScanMPI::PostProcessingImpl() {
200 12 return GetOutput().size() >= 3;
201 }
202
203 14 size_t GaivoronskiyMGrahamScanMPI::FindLowestPoint(const std::vector<Point> &pts) {
204 size_t min_idx = 0;
205
2/2
✓ Branch 0 taken 123 times.
✓ Branch 1 taken 14 times.
 137 for (size_t i = 1; i < pts.size(); i++) {
206
6/6
✓ Branch 0 taken 100 times.
✓ Branch 1 taken 23 times.
✓ Branch 2 taken 7 times.
✓ Branch 3 taken 93 times.
✓ Branch 4 taken 6 times.
✓ Branch 5 taken 1 times.
 123 if (pts[i].y < pts[min_idx].y || (pts[i].y == pts[min_idx].y && pts[i].x < pts[min_idx].x)) {
207 min_idx = i;
208 }
209 }
210 14 return min_idx;
211 }
212
213 14 size_t GaivoronskiyMGrahamScanMPI::RemoveCollinearPoints(std::vector<Point> &pts, const Point &p0) {
214 size_t m = 1;
215
2/2
✓ Branch 0 taken 111 times.
✓ Branch 1 taken 14 times.
 125 for (size_t i = 1; i < pts.size(); i++) {
216
4/4
✓ Branch 0 taken 109 times.
✓ Branch 1 taken 14 times.
✓ Branch 2 taken 12 times.
✓ Branch 3 taken 97 times.
 123 while (i < pts.size() - 1 && Orientation(p0, pts[i], pts[i + 1]) == 0) {
217 i++;
218 }
219 111 pts[m] = pts[i];
220 111 m++;
221 }
222 14 return m;
223 }
224
225 13 std::vector<Point> GaivoronskiyMGrahamScanMPI::BuildConvexHull(const std::vector<Point> &pts, size_t num_points) {
226 std::stack<Point> s;
227 s.push(pts[0]);
228 s.push(pts[1]);
229 s.push(pts[2]);
230
231
2/2
✓ Branch 0 taken 84 times.
✓ Branch 1 taken 13 times.
 97 for (size_t i = 3; i < num_points; i++) {
232
1/2
✓ Branch 0 taken 84 times.
✗ Branch 1 not taken.
 84 Point top = s.top();
233 s.pop();
234
1/2
✓ Branch 0 taken 129 times.
✗ Branch 1 not taken.
 129 while (!s.empty() && Orientation(s.top(), top, pts[i]) != 2) {
235
1/2
✓ Branch 0 taken 45 times.
✗ Branch 1 not taken.
 45 top = s.top();
236 s.pop();
237 }
238 s.push(top);
239 s.push(pts[i]);
240 }
241
242 13 std::vector<Point> result;
243
2/2
✓ Branch 0 taken 78 times.
✓ Branch 1 taken 13 times.
 91 while (!s.empty()) {
244 result.push_back(s.top());
245 s.pop();
246 }
247
248 std::ranges::reverse(result);
249 13 return result;
250 }
251
252
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 18 times.
 18 std::vector<Point> GaivoronskiyMGrahamScanMPI::GrahamScan(const std::vector<Point> &points) {
253
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 18 times.
 18 if (points.empty()) {
254 ✗ return {};
255 }
256
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 14 times.
 18 if (points.size() < 3) {
257 4 return points;
258 }
259
260 14 std::vector<Point> pts = points;
261
262 14 size_t min_idx = FindLowestPoint(pts);
263 std::swap(pts[0], pts[min_idx]);
264 14 const Point p0_local = pts[0];
265
266 14 std::sort(pts.begin() + 1, pts.end(),
267
14/24
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 250 times.
✓ Branch 5 taken 90 times.
✓ Branch 6 taken 10 times.
✓ Branch 7 taken 23 times.
✓ Branch 8 taken 15 times.
✓ Branch 9 taken 23 times.
✓ Branch 10 taken 2 times.
✓ Branch 11 taken 1 times.
✓ Branch 12 taken 1 times.
✓ Branch 13 taken 1 times.
✗ Branch 14 not taken.
✓ Branch 15 taken 1 times.
✓ Branch 16 taken 1 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✓ Branch 22 taken 19 times.
✓ Branch 23 taken 70 times.
 503 [&p0_local](const Point &p1, const Point &p2) { return Compare(p1, p2, p0_local); });
268
269 14 size_t m = RemoveCollinearPoints(pts, p0_local);
270
271
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 13 times.
 14 if (m < 3) {
272 return pts;
273 }
274
275
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 return BuildConvexHull(pts, m);
276 }
277
278 ✗ std::vector<Point> GaivoronskiyMGrahamScanMPI::MergeHulls(const std::vector<Point> &hull1,
279 const std::vector<Point> &hull2) {
280 ✗ std::vector<Point> combined = hull1;
281 ✗ combined.insert(combined.end(), hull2.begin(), hull2.end());
282 ✗ return GrahamScan(combined);
283 }
284
285 } // namespace gaivoronskiy_m_grachem_method
286