GCC Code Coverage Report

Directory: ./
File: tasks/shkenev_i_constra_hull_for_binary_image/all/src/ops_all.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 105 108 97.2%
Functions: 11 12 91.7%
Branches: 118 170 69.4%
Line Branch Exec Source
1 #include "shkenev_i_constra_hull_for_binary_image/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4 #include <tbb/parallel_for.h>
5
6 #include <algorithm>
7 #include <array>
8 #include <cstddef>
9 #include <cstdint>
10 #include <queue>
11 #include <ranges>
12 #include <utility>
13 #include <vector>
14
15 #include "shkenev_i_constra_hull_for_binary_image/common/include/common.hpp"
16
17 namespace shkenev_i_constra_hull_for_binary_image {
18
19 namespace {
20
21 constexpr std::uint8_t kThreshold = 128;
22 constexpr std::array<std::pair<int, int>, 4> kDirs = {{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}};
23
24 bool InBounds(int x, int y, int width, int height) {
25 502 return x >= 0 && x < width && y >= 0 && y < height;
26 }
27
28 bool IsForeground(std::uint8_t pixel) {
29 return pixel > kThreshold;
30 }
31
32 std::int64_t Cross(const Point &a, const Point &b, const Point &c) {
33 194 return (static_cast<std::int64_t>(b.x - a.x) * static_cast<std::int64_t>(c.y - b.y)) -
34 194 (static_cast<std::int64_t>(b.y - a.y) * static_cast<std::int64_t>(c.x - b.x));
35 }
36
37 5 std::vector<int> SerializeHulls(const std::vector<std::vector<Point>> &hulls) {
38 5 std::vector<int> flat;
39
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 flat.reserve(1);
40
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 flat.push_back(static_cast<int>(hulls.size()));
41
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 5 times.
 11 for (const auto &hull : hulls) {
42
1/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 6 flat.push_back(static_cast<int>(hull.size()));
43
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 6 times.
 19 for (const auto &point : hull) {
44
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 10 times.
 13 flat.push_back(point.x);
45
1/2
✓ Branch 0 taken 13 times.
✗ Branch 1 not taken.
 13 flat.push_back(point.y);
46 }
47 }
48 5 return flat;
49 }
50
51
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 10 times.
 10 std::vector<std::vector<Point>> DeserializeHulls(const std::vector<int> &flat) {
52
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 10 times.
 10 if (flat.empty()) {
53 ✗ return {};
54 }
55
56 std::size_t pos = 0;
57 10 const int hull_count = flat[pos++];
58
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 std::vector<std::vector<Point>> hulls;
59
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 hulls.reserve(static_cast<std::size_t>(std::max(0, hull_count)));
60
61
3/4
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 12 times.
 22 for (int hull_idx = 0; hull_idx < hull_count && pos < flat.size(); ++hull_idx) {
62
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 const int point_count = flat[pos++];
63
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 std::vector<Point> hull;
64
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 hull.reserve(static_cast<std::size_t>(std::max(0, point_count)));
65
66
3/4
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 12 times.
✓ Branch 2 taken 26 times.
✗ Branch 3 not taken.
 38 for (int point_idx = 0; point_idx < point_count && (pos + 1) < flat.size(); ++point_idx) {
67
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 26 hull.emplace_back(flat[pos], flat[pos + 1]);
68 26 pos += 2;
69 }
70 hulls.push_back(std::move(hull));
71 }
72
73 return hulls;
74 10 }
75
76 } // namespace
77
78 ✗ size_t ShkenevIConstrHullALL::Index(int x, int y, int width) {
79
4/4
✓ Branch 0 taken 63 times.
✓ Branch 1 taken 164 times.
✓ Branch 2 taken 125 times.
✓ Branch 3 taken 123 times.
 475 return (static_cast<size_t>(y) * static_cast<size_t>(width)) + static_cast<size_t>(x);
80 }
81
82
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 ShkenevIConstrHullALL::ShkenevIConstrHullALL(const InType &in) : work_(in) {
83 SetTypeOfTask(GetStaticTypeOfTask());
84
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 GetInput() = in;
85 10 }
86
87 10 bool ShkenevIConstrHullALL::ValidationImpl() {
88 const auto &in = GetInput();
89
2/4
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 10 times.
 10 return in.width > 0 && in.height > 0 &&
90
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 10 times.
 10 in.pixels.size() == static_cast<size_t>(in.width) * static_cast<size_t>(in.height);
91 }
92
93 10 bool ShkenevIConstrHullALL::PreProcessingImpl() {
94 10 work_ = GetInput();
95 work_.components.clear();
96 work_.convex_hulls.clear();
97
98 10 auto &pixels = work_.pixels;
99 10 tbb::parallel_for(static_cast<size_t>(0), pixels.size(), [&](size_t idx) {
100
4/4
✓ Branch 0 taken 90 times.
✓ Branch 1 taken 20 times.
✓ Branch 2 taken 238 times.
✓ Branch 3 taken 106 times.
 782 pixels[idx] = IsForeground(pixels[idx]) ? static_cast<std::uint8_t>(255) : static_cast<std::uint8_t>(0);
101 });
102
103 10 return true;
104 }
105
106 6 void ShkenevIConstrHullALL::BFS(int sx, int sy, int width, int height, std::vector<std::uint8_t> &visited,
107 std::vector<Point> &component) {
108 std::queue<Point> queue;
109 queue.emplace(sx, sy);
110 6 visited[Index(sx, sy, width)] = 1;
111
112
2/2
✓ Branch 0 taken 63 times.
✓ Branch 1 taken 6 times.
 69 while (!queue.empty()) {
113 63 const Point current = queue.front();
114 queue.pop();
115 component.push_back(current);
116
117
2/2
✓ Branch 0 taken 252 times.
✓ Branch 1 taken 63 times.
 315 for (auto [dx, dy] : kDirs) {
118 252 const int next_x = current.x + dx;
119
2/2
✓ Branch 0 taken 250 times.
✓ Branch 1 taken 2 times.
 252 const int next_y = current.y + dy;
120
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 248 times.
 250 if (!InBounds(next_x, next_y, width, height)) {
121 195 continue;
122 }
123
124 const size_t next_idx = Index(next_x, next_y, width);
125
4/4
✓ Branch 0 taken 125 times.
✓ Branch 1 taken 123 times.
✓ Branch 2 taken 57 times.
✓ Branch 3 taken 68 times.
 248 if (visited[next_idx] != 0U || work_.pixels[next_idx] == 0) {
126 191 continue;
127 }
128
129
1/2
✓ Branch 1 taken 57 times.
✗ Branch 2 not taken.
 57 visited[next_idx] = 1;
130 queue.emplace(next_x, next_y);
131 }
132 }
133 6 }
134
135 5 void ShkenevIConstrHullALL::FindComponentsTBB() {
136 5 const int width = work_.width;
137 5 const int height = work_.height;
138
139
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 5 times.
 5 std::vector<std::uint8_t> visited(static_cast<size_t>(width) * static_cast<size_t>(height), 0);
140 work_.components.clear();
141
142
2/2
✓ Branch 0 taken 31 times.
✓ Branch 1 taken 5 times.
 36 for (int row = 0; row < height; ++row) {
143
2/2
✓ Branch 0 taken 227 times.
✓ Branch 1 taken 31 times.
 258 for (int col = 0; col < width; ++col) {
144 const size_t idx = Index(col, row, width);
145
4/4
✓ Branch 0 taken 63 times.
✓ Branch 1 taken 164 times.
✓ Branch 2 taken 57 times.
✓ Branch 3 taken 6 times.
 227 if (work_.pixels[idx] == 0 || visited[idx] != 0U) {
146 221 continue;
147 }
148
149 6 std::vector<Point> component;
150
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 BFS(col, row, width, height, visited, component);
151
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (!component.empty()) {
152
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 work_.components.push_back(std::move(component));
153 }
154 }
155 }
156 5 }
157
158
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 3 std::vector<Point> ShkenevIConstrHullALL::BuildHull(const std::vector<Point> &points) {
159
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 3 if (points.size() <= 2) {
160 ✗ return points;
161 }
162
163 3 std::vector<Point> pts = points;
164
17/26
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 37 times.
✓ Branch 5 taken 14 times.
✓ Branch 6 taken 31 times.
✓ Branch 7 taken 8 times.
✓ Branch 8 taken 2 times.
✓ Branch 9 taken 1 times.
✓ Branch 10 taken 1 times.
✓ Branch 11 taken 1 times.
✗ Branch 12 not taken.
✓ Branch 13 taken 1 times.
✓ Branch 14 taken 1 times.
✗ Branch 15 not taken.
✓ Branch 16 taken 1 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✓ Branch 20 taken 88 times.
✓ Branch 21 taken 50 times.
✓ Branch 22 taken 28 times.
✓ Branch 23 taken 4 times.
✓ Branch 24 taken 64 times.
✓ Branch 25 taken 30 times.
 362 std::ranges::sort(pts, [](const Point &a, const Point &b) { return (a.x != b.x) ? (a.x < b.x) : (a.y < b.y); });
165
166 auto [first, last] = std::ranges::unique(pts);
167 pts.erase(first, last);
168
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 3 if (pts.size() <= 2) {
169 return pts;
170 }
171
172 3 std::vector<Point> lower;
173
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 std::vector<Point> upper;
174
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 lower.reserve(pts.size());
175
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 upper.reserve(pts.size());
176
177
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 3 times.
 63 for (const auto &point : pts) {
178
4/4
✓ Branch 0 taken 97 times.
✓ Branch 1 taken 15 times.
✓ Branch 2 taken 52 times.
✓ Branch 3 taken 45 times.
 112 while (lower.size() >= 2 && Cross(lower[lower.size() - 2], lower.back(), point) <= 0) {
179 lower.pop_back();
180 }
181 lower.push_back(point);
182 }
183
184
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 3 times.
 63 for (const auto &point : std::ranges::reverse_view(pts)) {
185
4/4
✓ Branch 0 taken 97 times.
✓ Branch 1 taken 15 times.
✓ Branch 2 taken 45 times.
✓ Branch 3 taken 52 times.
 112 while (upper.size() >= 2 && Cross(upper[upper.size() - 2], upper.back(), point) <= 0) {
186 upper.pop_back();
187 }
188 upper.push_back(point);
189 }
190
191 lower.pop_back();
192 upper.pop_back();
193
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 lower.insert(lower.end(), upper.begin(), upper.end());
194 return lower;
195 }
196
197 10 bool ShkenevIConstrHullALL::RunImpl() {
198 10 int rank = 0;
199 10 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
200
201
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 if (rank == 0) {
202 5 FindComponentsTBB();
203
204 5 auto &components = work_.components;
205 5 auto &hulls = work_.convex_hulls;
206 5 hulls.resize(components.size());
207
208 5 tbb::parallel_for(static_cast<size_t>(0), components.size(), [&](size_t idx) {
209
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 const auto &component = components[idx];
210
3/4
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
✓ Branch 5 taken 6 times.
✗ Branch 6 not taken.
 6 hulls[idx] = (component.size() <= 2) ? component : BuildHull(component);
211 6 });
212 }
213
214 10 std::vector<int> flat_hulls;
215
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 if (rank == 0) {
216
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 10 flat_hulls = SerializeHulls(work_.convex_hulls);
217 }
218
219 10 int flat_size = static_cast<int>(flat_hulls.size());
220
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 MPI_Bcast(&flat_size, 1, MPI_INT, 0, MPI_COMM_WORLD);
221
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 if (rank != 0) {
222
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 flat_hulls.resize(static_cast<std::size_t>(flat_size));
223 }
224
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 MPI_Bcast(flat_hulls.data(), flat_size, MPI_INT, 0, MPI_COMM_WORLD);
225
226
3/6
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 5 times.
✓ Branch 6 taken 5 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 10 work_.convex_hulls = DeserializeHulls(flat_hulls);
227 work_.components.clear();
228
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 MPI_Barrier(MPI_COMM_WORLD);
229
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 GetOutput() = work_;
230 10 return true;
231 }
232
233 10 bool ShkenevIConstrHullALL::PostProcessingImpl() {
234 10 return true;
235 }
236
237 } // namespace shkenev_i_constra_hull_for_binary_image
238