GCC Code Coverage Report

Directory: ./
File: tasks/dorogin_v_bin_img_conv_hull_stl/stl/src/ops_stl.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 71 73 97.3%
Functions: 10 10 100.0%
Branches: 80 186 43.0%
Line Branch Exec Source
1 #include "dorogin_v_bin_img_conv_hull_stl/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <cstdint>
6 #include <queue>
7 #include <ranges>
8 #include <utility>
9 #include <vector>
10
11 #include "dorogin_v_bin_img_conv_hull_stl/common/include/common.hpp"
12
13 namespace nesterov_a_test_task_threads {
14 namespace {
15 inline bool InBounds(const int x, const int y, const int w, const int h) {
16 1120 return (x >= 0) && (y >= 0) && (x < w) && (y < h);
17 }
18
19 inline std::size_t Idx(const int x, const int y, const int w) {
20
5/6
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 368 times.
✓ Branch 3 taken 32 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 320 times.
✓ Branch 6 taken 192 times.
 1056 return (static_cast<std::size_t>(y) * static_cast<std::size_t>(w)) + static_cast<std::size_t>(x);
21 }
22
23 inline std::int64_t Cross(const Point &o, const Point &a, const Point &b) {
24 224 return (static_cast<std::int64_t>(a.x - o.x) * static_cast<std::int64_t>(b.y - o.y)) -
25 224 (static_cast<std::int64_t>(a.y - o.y) * static_cast<std::int64_t>(b.x - o.x));
26 }
27
28
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
 32 inline std::vector<Point> ConvexHullMonotonicChain(std::vector<Point> pts) {
29
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
 32 if (pts.empty()) {
30 ✗ return {};
31 }
32
9/78
✗ 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 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 30 not taken.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 36 not taken.
✗ Branch 37 not taken.
✗ Branch 38 not taken.
✗ Branch 39 not taken.
✗ Branch 40 not taken.
✗ Branch 41 not taken.
✗ Branch 42 not taken.
✗ Branch 43 not taken.
✗ Branch 44 not taken.
✗ Branch 45 not taken.
✗ Branch 46 not taken.
✗ Branch 47 not taken.
✗ Branch 48 not taken.
✗ Branch 49 not taken.
✗ Branch 50 not taken.
✗ Branch 51 not taken.
✗ Branch 52 not taken.
✗ Branch 53 not taken.
✗ Branch 54 not taken.
✗ Branch 55 not taken.
✗ Branch 56 not taken.
✗ Branch 57 not taken.
✗ Branch 58 not taken.
✗ Branch 59 not taken.
✗ Branch 60 not taken.
✗ Branch 61 not taken.
✗ Branch 62 not taken.
✗ Branch 63 not taken.
✗ Branch 64 not taken.
✗ Branch 65 not taken.
✗ Branch 66 not taken.
✓ Branch 67 taken 112 times.
✓ Branch 68 taken 32 times.
✓ Branch 69 taken 80 times.
✗ Branch 70 not taken.
✓ Branch 71 taken 32 times.
✓ Branch 72 taken 72 times.
✓ Branch 73 taken 112 times.
✓ Branch 74 taken 80 times.
✓ Branch 75 taken 32 times.
✗ Branch 76 not taken.
✓ Branch 77 taken 80 times.
 296 std::ranges::sort(pts, [](const Point &a, const Point &b) { return (a.x < b.x) || ((a.x == b.x) && (a.y < b.y)); });
33 const auto uniq =
34
3/8
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 32 times.
✓ Branch 2 taken 80 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 112 std::ranges::unique(pts, [](const Point &a, const Point &b) { return (a.x == b.x) && (a.y == b.y); });
35 pts.erase(uniq.begin(), pts.end());
36
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 24 times.
 32 if (pts.size() <= 1) {
37 return pts;
38 }
39
40
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 std::vector<Point> lower;
41
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 lower.reserve(pts.size());
42
2/2
✓ Branch 0 taken 136 times.
✓ Branch 1 taken 24 times.
 160 for (const auto &p : pts) {
43
4/4
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 88 times.
✓ Branch 2 taken 64 times.
✓ Branch 3 taken 48 times.
 200 while ((lower.size() >= 2) && (Cross(lower[lower.size() - 2], lower[lower.size() - 1], p) <= 0)) {
44 lower.pop_back();
45 }
46 lower.push_back(p);
47 }
48
49
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 std::vector<Point> upper;
50
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 upper.reserve(pts.size());
51
2/2
✓ Branch 0 taken 136 times.
✓ Branch 1 taken 24 times.
 160 for (std::size_t i = pts.size(); i-- > 0;) {
52 const auto &p = pts[i];
53
4/4
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 88 times.
✓ Branch 2 taken 48 times.
✓ Branch 3 taken 64 times.
 200 while ((upper.size() >= 2) && (Cross(upper[upper.size() - 2], upper[upper.size() - 1], p) <= 0)) {
54 upper.pop_back();
55 }
56 upper.push_back(p);
57 }
58
59 lower.pop_back();
60 upper.pop_back();
61
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 lower.insert(lower.end(), upper.begin(), upper.end());
62 return lower;
63 }
64
65
2/2
✓ Branch 0 taken 544 times.
✓ Branch 1 taken 32 times.
 576 inline void TryPush4(const BinaryImage &img, const int w, const int h, const int nx, const int ny,
66 std::vector<std::uint8_t> &vis, std::queue<Point> &q) {
67
2/2
✓ Branch 0 taken 512 times.
✓ Branch 1 taken 32 times.
 544 if (!InBounds(nx, ny, w, h)) {
68 return;
69 }
70 const std::size_t nid = Idx(nx, ny, w);
71
4/4
✓ Branch 0 taken 320 times.
✓ Branch 1 taken 192 times.
✓ Branch 2 taken 112 times.
✓ Branch 3 taken 208 times.
 512 if ((img.data[nid] == 1U) && (vis[nid] == 0U)) {
72 112 vis[nid] = 1U;
73 112 q.push(Point{.x = nx, .y = ny});
74 }
75 }
76
77 32 inline std::vector<Point> BfsComponent4(const BinaryImage &img, const int w, const int h, const int sx, const int sy,
78 std::vector<std::uint8_t> &vis) {
79
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 std::vector<Point> pts;
80 std::queue<Point> q;
81 const std::size_t sid = Idx(sx, sy, w);
82 32 vis[sid] = 1U;
83
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 q.push(Point{.x = sx, .y = sy});
84
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 32 times.
 176 while (!q.empty()) {
85 144 const Point p = q.front();
86 q.pop();
87 pts.push_back(p);
88
1/2
✓ Branch 1 taken 144 times.
✗ Branch 2 not taken.
 144 TryPush4(img, w, h, p.x + 1, p.y, vis, q);
89
1/2
✓ Branch 1 taken 144 times.
✗ Branch 2 not taken.
 144 TryPush4(img, w, h, p.x - 1, p.y, vis, q);
90
1/2
✓ Branch 1 taken 144 times.
✗ Branch 2 not taken.
 144 TryPush4(img, w, h, p.x, p.y + 1, vis, q);
91
1/2
✓ Branch 1 taken 144 times.
✗ Branch 2 not taken.
 144 TryPush4(img, w, h, p.x, p.y - 1, vis, q);
92 }
93 32 return pts;
94 }
95
96 24 inline std::vector<std::vector<Point>> ExtractComponents4(const BinaryImage &img) {
97 24 std::vector<std::vector<Point>> comps;
98
2/4
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
 24 if ((img.width <= 0) || (img.height <= 0)) {
99 return comps;
100 }
101 24 const std::size_t n = static_cast<std::size_t>(img.width) * static_cast<std::size_t>(img.height);
102
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 std::vector<std::uint8_t> vis(n, 0U);
103
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 24 times.
 128 for (int row = 0; row < img.height; ++row) {
104
2/2
✓ Branch 0 taken 512 times.
✓ Branch 1 taken 104 times.
 616 for (int col = 0; col < img.width; ++col) {
105 const std::size_t id = Idx(col, row, img.width);
106
4/4
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 368 times.
✓ Branch 2 taken 112 times.
✓ Branch 3 taken 32 times.
 512 if ((img.data[id] == 0U) || (vis[id] != 0U)) {
107 480 continue;
108 }
109
1/4
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 64 comps.push_back(BfsComponent4(img, img.width, img.height, col, row, vis));
110 }
111 }
112 return comps;
113 ✗ }
114
115 inline bool ValidateInput(const BinaryImage &img) {
116
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 if ((img.width <= 0) || (img.height <= 0)) {
117 return false;
118 }
119 48 const std::size_t need = static_cast<std::size_t>(img.width) * static_cast<std::size_t>(img.height);
120 48 return img.data.size() == need;
121 }
122
123 24 inline OutType SolveSTL(const BinaryImage &img) {
124 24 auto comps = ExtractComponents4(img);
125
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 OutType hulls;
126
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 hulls.resize(comps.size());
127
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 std::vector<std::size_t> indices(comps.size());
128
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 24 times.
 56 for (std::size_t i = 0; i < indices.size(); ++i) {
129 32 indices[i] = i;
130 }
131
3/4
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 32 times.
✓ Branch 4 taken 24 times.
 56 for (const std::size_t i : indices) {
132
1/4
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 64 hulls[i] = ConvexHullMonotonicChain(std::move(comps[i]));
133 }
134 24 return hulls;
135 24 }
136
137 } // namespace
138
139
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 NesterovATestTaskSTL::NesterovATestTaskSTL(const InType &in) {
140 SetTypeOfTask(GetStaticTypeOfTask());
141 GetInput() = in;
142 GetOutput().clear();
143 24 }
144
145
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 bool NesterovATestTaskSTL::ValidationImpl() {
146 48 return ValidateInput(GetInput());
147 }
148
149
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 bool NesterovATestTaskSTL::PreProcessingImpl() {
150 local_out_.clear();
151 24 return true;
152 }
153
154 24 bool NesterovATestTaskSTL::RunImpl() {
155
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 if (!ValidationImpl()) {
156 return false;
157 }
158
159 24 local_out_ = SolveSTL(GetInput());
160 24 return true;
161 }
162
163 24 bool NesterovATestTaskSTL::PostProcessingImpl() {
164 24 GetOutput() = local_out_;
165 24 return true;
166 }
167
168 } // namespace nesterov_a_test_task_threads
169