GCC Code Coverage Report

Directory: ./
File: tasks/ilin_a_algorithm_graham/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 79 86 91.9%
Functions: 8 8 100.0%
Branches: 56 104 53.8%
Line Branch Exec Source
1 #include "ilin_a_algorithm_graham/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4 #include <tbb/blocked_range.h>
5 #include <tbb/parallel_reduce.h>
6 #include <tbb/parallel_sort.h>
7
8 #include <array>
9 #include <cstddef>
10 #include <utility>
11 #include <vector>
12
13 #include "ilin_a_algorithm_graham/common/include/common.hpp"
14
15 namespace ilin_a_algorithm_graham {
16
17 namespace {
18 double Orient(const Point &p, const Point &q, const Point &r) {
19 330 return ((q.x - p.x) * (r.y - p.y)) - ((q.y - p.y) * (r.x - p.x));
20 }
21
22 double DistanceSq(const Point &p, const Point &q) {
23 58 double dx = p.x - q.x;
24 58 double dy = p.y - q.y;
25 58 return (dx * dx) + (dy * dy);
26 }
27
28 6 Point FindLowestLeftmostParallel(const std::vector<Point> &points) {
29 6 return tbb::parallel_reduce(tbb::blocked_range<size_t>(0, points.size()), points[0],
30 6 [&](const tbb::blocked_range<size_t> &r, Point init) {
31
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 36 times.
 72 for (size_t i = r.begin(); i < r.end(); ++i) {
32
4/6
✓ Branch 0 taken 36 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 12 times.
✓ Branch 3 taken 24 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 12 times.
 36 if (points[i].y < init.y || (points[i].y == init.y && points[i].x < init.x)) {
33 ✗ init = points[i];
34 }
35 }
36 return init;
37 6 }, [](const Point &a, const Point &b) {
38 ✗ if (a.y < b.y || (a.y == b.y && a.x < b.x)) {
39 ✗ return a;
40 }
41 ✗ return b;
42 6 });
43 }
44
45 class PointComparator {
46 public:
47
2/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 6 times.
✗ Branch 5 not taken.
 12 explicit PointComparator(const Point &p0) : p0_(p0) {}
48
49 242 bool operator()(const Point &a, const Point &b) const {
50 double o = Orient(p0_, a, b);
51
2/2
✓ Branch 0 taken 184 times.
✓ Branch 1 taken 58 times.
 242 if (o != 0.0) {
52 184 return o > 0;
53 }
54 58 return DistanceSq(p0_, a) < DistanceSq(p0_, b);
55 }
56
57 private:
58 Point p0_;
59 };
60
61
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 void GrahamScan(const std::vector<Point> &sorted, const Point &p0, std::vector<Point> &hull) {
62
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 if (sorted.empty()) {
63 hull.push_back(p0);
64 ✗ return;
65 }
66 6 hull.reserve(sorted.size() + 1);
67 hull.push_back(p0);
68 hull.push_back(sorted[0]);
69
70
2/2
✓ Branch 0 taken 54 times.
✓ Branch 1 taken 6 times.
 60 for (size_t i = 1; i < sorted.size(); ++i) {
71
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 6 times.
 94 while (hull.size() >= 2) {
72 88 Point p = hull[hull.size() - 2];
73
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 48 times.
 88 Point q = hull[hull.size() - 1];
74
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 48 times.
 88 if (Orient(p, q, sorted[i]) <= 0.0) {
75 hull.pop_back();
76 } else {
77 break;
78 }
79 }
80 hull.push_back(sorted[i]);
81 }
82 }
83 } // namespace
84
85
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 IlinAGrahamALL::IlinAGrahamALL(const InType &in) {
86 SetTypeOfTask(GetStaticTypeOfTask());
87 GetInput() = in;
88 6 }
89
90 6 bool IlinAGrahamALL::ValidationImpl() {
91 6 return !GetInput().points.empty();
92 }
93
94 6 bool IlinAGrahamALL::PreProcessingImpl() {
95 6 points_ = GetInput().points;
96 hull_.clear();
97 6 return true;
98 }
99
100 6 bool IlinAGrahamALL::RunImpl() {
101 6 int rank = -1;
102 6 int size = -1;
103 6 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
104 6 MPI_Comm_size(MPI_COMM_WORLD, &size);
105
106
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 if (points_.size() < 3) {
107 ✗ hull_ = points_;
108 ✗ return true;
109 }
110
111 6 Point local_p0 = FindLowestLeftmostParallel(points_);
112
113 6 std::array<double, 2> local_min = {local_p0.y, local_p0.x};
114 6 std::array<double, 2> global_min = {};
115
116 6 MPI_Allreduce(local_min.data(), global_min.data(), 2, MPI_DOUBLE, MPI_MIN, MPI_COMM_WORLD);
117
118 Point global_p0{};
119 6 global_p0.y = global_min[0];
120 6 global_p0.x = global_min[1];
121
122
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 std::vector<Point> sorted;
123
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 sorted.reserve(points_.size());
124
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 6 times.
 42 for (const Point &p : points_) {
125
4/4
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 6 times.
✓ Branch 3 taken 6 times.
 36 if (p.x != global_p0.x || p.y != global_p0.y) {
126 sorted.push_back(p);
127 }
128 }
129
130
2/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 6 times.
✗ Branch 5 not taken.
 6 tbb::parallel_sort(sorted.begin(), sorted.end(), PointComparator(global_p0));
131
132 6 int local_count = static_cast<int>(sorted.size());
133
1/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 6 std::vector<int> counts(size);
134
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.
 6 std::vector<int> displs(size);
135
136
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Allgather(&local_count, 1, MPI_INT, counts.data(), 1, MPI_INT, MPI_COMM_WORLD);
137
138 int total_count = 0;
139
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 6 times.
 18 for (int i = 0; i < size; ++i) {
140 12 displs[i] = total_count;
141 12 total_count += counts[i];
142 }
143
144
1/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 6 std::vector<double> send_buffer(static_cast<size_t>(local_count) * 2);
145
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 6 times.
 36 for (int i = 0; i < local_count; ++i) {
146 30 send_buffer[(static_cast<size_t>(i) * 2)] = sorted[i].x;
147 30 send_buffer[(static_cast<size_t>(i) * 2) + 1] = sorted[i].y;
148 }
149
150
1/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 6 std::vector<double> recv_buffer(static_cast<size_t>(total_count) * 2);
151
1/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 6 std::vector<int> recv_counts(size);
152
1/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 6 std::vector<int> recv_displs(size);
153
154
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 6 times.
 18 for (int i = 0; i < size; ++i) {
155 12 recv_counts[i] = counts[i] * 2;
156 12 recv_displs[i] = displs[i] * 2;
157 }
158
159
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Allgatherv(send_buffer.data(), local_count * 2, MPI_DOUBLE, recv_buffer.data(), recv_counts.data(),
160 recv_displs.data(), MPI_DOUBLE, MPI_COMM_WORLD);
161
162 6 std::vector<Point> global_sorted;
163
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 global_sorted.reserve(static_cast<size_t>(total_count));
164
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 6 times.
 66 for (int i = 0; i < total_count; ++i) {
165
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 size_t idx = (static_cast<size_t>(i) * 2);
166
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 global_sorted.push_back({recv_buffer[idx], recv_buffer[idx + 1]});
167 }
168
169
1/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 6 tbb::parallel_sort(global_sorted.begin(), global_sorted.end(), PointComparator(global_p0));
170
171 6 std::vector<Point> hull;
172
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 GrahamScan(global_sorted, global_p0, hull);
173
174 6 hull_ = std::move(hull);
175
176 return true;
177 }
178
179
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 bool IlinAGrahamALL::PostProcessingImpl() {
180
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (hull_.empty()) {
181 return false;
182 }
183 6 GetOutput() = hull_;
184 6 return true;
185 }
186
187 } // namespace ilin_a_algorithm_graham
188