GCC Code Coverage Report

Directory: ./
File: tasks/shkenev_i_constra_hull_for_binary_image/stl/src/ops_stl.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 85 91 93.4%
Functions: 9 11 81.8%
Branches: 117 190 61.6%
Line Branch Exec Source
1 #include "shkenev_i_constra_hull_for_binary_image/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <array>
5 #include <atomic>
6 #include <cstddef>
7 #include <cstdint>
8 #include <thread>
9 #include <utility>
10 #include <vector>
11
12 #include "shkenev_i_constra_hull_for_binary_image/common/include/common.hpp"
13 #include "util/include/util.hpp"
14
15 namespace shkenev_i_constra_hull_for_binary_image {
16
17 namespace {
18
19 // 1
20 constexpr uint8_t kThreshold = 128;
21
22 constexpr std::array<std::pair<int, int>, 4> kDirs = {std::pair{1, 0}, std::pair{-1, 0}, std::pair{0, 1},
23 std::pair{0, -1}};
24
25 inline bool InBounds(int x, int y, int w, int h) {
26 4016 return x >= 0 && x < w && y >= 0 && y < h;
27 }
28
29 inline int64_t Cross(const Point &a, const Point &b, const Point &c) {
30 1552 return (static_cast<int64_t>(b.x - a.x) * static_cast<int64_t>(c.y - a.y)) -
31 1552 (static_cast<int64_t>(b.y - a.y) * static_cast<int64_t>(c.x - a.x));
32 }
33
34 } // namespace
35
36
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 ShkenevIConstrHullSTL::ShkenevIConstrHullSTL(const InType &in) : work_(in) {
37 SetTypeOfTask(GetStaticTypeOfTask());
38
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 GetInput() = in;
39 40 }
40
41 40 bool ShkenevIConstrHullSTL::ValidationImpl() {
42 const auto &in = GetInput();
43
2/4
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 40 times.
 40 return in.width > 0 && in.height > 0 &&
44
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 40 times.
 40 in.pixels.size() == static_cast<size_t>(in.width) * static_cast<size_t>(in.height);
45 }
46
47 40 bool ShkenevIConstrHullSTL::PreProcessingImpl() {
48 40 work_ = GetInput();
49 ThresholdImage();
50 40 return true;
51 }
52
53 ✗ void ShkenevIConstrHullSTL::ThresholdImage() {
54
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 1816 times.
✓ Branch 3 taken 40 times.
 1856 for (auto &pixel : work_.pixels) {
55
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 1312 times.
✓ Branch 3 taken 504 times.
 3128 pixel = (pixel > kThreshold) ? 255 : 0;
56 }
57 ✗ }
58
59 ✗ size_t ShkenevIConstrHullSTL::Index(int x, int y, int width) {
60
4/4
✓ Branch 0 taken 1360 times.
✓ Branch 1 taken 456 times.
✓ Branch 2 taken 1000 times.
✓ Branch 3 taken 984 times.
 3800 return (static_cast<size_t>(y) * static_cast<size_t>(width)) + static_cast<size_t>(x);
61 }
62
63 48 void ShkenevIConstrHullSTL::ExploreComponent(int start_x, int start_y, int width, int height,
64 std::vector<uint8_t> &visited, std::vector<Point> &component) {
65 48 std::vector<Point> stack;
66
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 stack.reserve(256);
67
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 component.reserve(256);
68
69
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 stack.emplace_back(start_x, start_y);
70 48 visited[Index(start_x, start_y, width)] = 1;
71
72
2/2
✓ Branch 0 taken 504 times.
✓ Branch 1 taken 48 times.
 552 while (!stack.empty()) {
73
1/2
✓ Branch 0 taken 504 times.
✗ Branch 1 not taken.
 504 Point current = stack.back();
74 stack.pop_back();
75
76 component.push_back(current);
77
78
2/2
✓ Branch 0 taken 2016 times.
✓ Branch 1 taken 504 times.
 2520 for (const auto &[delta_x, delta_y] : kDirs) {
79 2016 int neighbor_x = current.x + delta_x;
80
2/2
✓ Branch 0 taken 2000 times.
✓ Branch 1 taken 16 times.
 2016 int neighbor_y = current.y + delta_y;
81
82
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 1984 times.
 2000 if (!InBounds(neighbor_x, neighbor_y, width, height)) {
83 1560 continue;
84 }
85
86 size_t idx = Index(neighbor_x, neighbor_y, width);
87
88
4/4
✓ Branch 0 taken 1000 times.
✓ Branch 1 taken 984 times.
✓ Branch 2 taken 456 times.
✓ Branch 3 taken 544 times.
 1984 if (visited[idx] != 0U || work_.pixels[idx] == 0) {
89 1528 continue;
90 }
91
92 456 visited[idx] = 1;
93
1/2
✓ Branch 1 taken 456 times.
✗ Branch 2 not taken.
 456 stack.emplace_back(neighbor_x, neighbor_y);
94 }
95 }
96 48 }
97
98 40 void ShkenevIConstrHullSTL::FindComponents() {
99 40 int width = work_.width;
100 40 int height = work_.height;
101
102
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 40 times.
 40 std::vector<uint8_t> visited(static_cast<size_t>(width) * static_cast<size_t>(height), 0);
103 work_.components.clear();
104
105
2/2
✓ Branch 0 taken 248 times.
✓ Branch 1 taken 40 times.
 288 for (int row = 0; row < height; ++row) {
106
2/2
✓ Branch 0 taken 1816 times.
✓ Branch 1 taken 248 times.
 2064 for (int col = 0; col < width; ++col) {
107 size_t idx = Index(col, row, width);
108
109
4/4
✓ Branch 0 taken 1360 times.
✓ Branch 1 taken 456 times.
✓ Branch 2 taken 1312 times.
✓ Branch 3 taken 48 times.
 1816 if (visited[idx] != 0U || work_.pixels[idx] == 0) {
110 1768 continue;
111 }
112
113 48 std::vector<Point> component;
114
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 ExploreComponent(col, row, width, height, visited, component);
115
116
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 if (!component.empty()) {
117
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 work_.components.emplace_back(std::move(component));
118 }
119 }
120 }
121 40 }
122
123 40 bool ShkenevIConstrHullSTL::RunImpl() {
124 40 FindComponents();
125
126 40 auto &components = work_.components;
127
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 40 times.
 40 auto &hulls = work_.convex_hulls;
128
129
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 40 times.
 40 if (components.empty()) {
130 ✗ GetOutput() = work_;
131 ✗ return true;
132 }
133
134 40 hulls.resize(components.size());
135
136 40 int num_threads = std::min<int>(ppc::util::GetNumThreads(), static_cast<int>(components.size()));
137 40 std::vector<std::thread> threads;
138
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 threads.reserve(static_cast<size_t>(num_threads));
139
140 40 std::atomic<size_t> current_index{0};
141
142
2/2
✓ Branch 0 taken 46 times.
✓ Branch 1 taken 40 times.
 86 for (int thread_id = 0; thread_id < num_threads; ++thread_id) {
143
1/2
✓ Branch 1 taken 46 times.
✗ Branch 2 not taken.
 92 threads.emplace_back([&]() {
144 while (true) {
145
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 46 times.
 94 size_t idx = current_index.fetch_add(1, std::memory_order_relaxed);
146
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 46 times.
 94 if (idx >= components.size()) {
147 break;
148 }
149
150 const auto &component = components[idx];
151
152
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 24 times.
 48 if (component.size() <= 2) {
153 24 hulls[idx] = component;
154 } else {
155 48 hulls[idx] = BuildHull(component);
156 }
157 }
158 46 });
159 }
160
161
2/2
✓ Branch 0 taken 46 times.
✓ Branch 1 taken 40 times.
 86 for (auto &thread : threads) {
162
1/2
✓ Branch 1 taken 46 times.
✗ Branch 2 not taken.
 46 thread.join();
163 }
164
165
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 GetOutput() = work_;
166 return true;
167 40 }
168
169 24 std::vector<Point> ShkenevIConstrHullSTL::BuildHull(const std::vector<Point> &pts_in) {
170 24 std::vector<Point> pts = pts_in;
171
172
39/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 taken 136 times.
✓ Branch 13 taken 200 times.
✓ Branch 14 taken 120 times.
✓ Branch 15 taken 80 times.
✓ Branch 16 taken 56 times.
✓ Branch 17 taken 64 times.
✓ Branch 18 taken 184 times.
✓ Branch 19 taken 160 times.
✓ Branch 20 taken 40 times.
✓ Branch 21 taken 144 times.
✓ Branch 22 taken 40 times.
✗ Branch 23 not taken.
✓ Branch 24 taken 8 times.
✓ Branch 25 taken 16 times.
✓ Branch 26 taken 8 times.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
✓ Branch 29 taken 16 times.
✗ Branch 30 not taken.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✓ Branch 33 taken 8 times.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 36 not taken.
✓ Branch 37 taken 8 times.
✗ Branch 38 not taken.
✗ Branch 39 not taken.
✗ Branch 40 not taken.
✗ Branch 41 not taken.
✓ Branch 42 taken 8 times.
✓ Branch 43 taken 8 times.
✗ Branch 44 not taken.
✓ Branch 45 taken 8 times.
✗ Branch 46 not taken.
✗ Branch 47 not taken.
✓ Branch 48 taken 8 times.
✗ Branch 49 not taken.
✗ Branch 50 not taken.
✓ Branch 51 taken 8 times.
✗ 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 taken 576 times.
✓ Branch 61 taken 344 times.
✓ Branch 62 taken 296 times.
✓ Branch 63 taken 48 times.
✓ Branch 64 taken 144 times.
✓ Branch 65 taken 152 times.
✓ Branch 66 taken 16 times.
✓ Branch 67 taken 240 times.
✓ Branch 68 taken 32 times.
✓ Branch 69 taken 208 times.
✗ Branch 70 not taken.
✓ Branch 71 taken 32 times.
✓ Branch 72 taken 568 times.
✓ Branch 73 taken 440 times.
✓ Branch 74 taken 336 times.
✓ Branch 75 taken 104 times.
✓ Branch 76 taken 200 times.
✓ Branch 77 taken 136 times.
 2888 std::ranges::sort(pts, [](const Point &a, const Point &b) { return (a.x < b.x) || (a.x == b.x && a.y < b.y); });
173
174 auto [first, last] =
175
3/8
✓ Branch 0 taken 352 times.
✓ Branch 1 taken 104 times.
✓ Branch 2 taken 352 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 456 std::ranges::unique(pts, [](const Point &a, const Point &b) { return a.x == b.x && a.y == b.y; });
176 pts.erase(first, last);
177
178
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (pts.size() <= 2) {
179 ✗ return pts;
180 }
181
182 24 std::vector<Point> lower;
183
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 std::vector<Point> upper;
184
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 lower.reserve(pts.size());
185
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 upper.reserve(pts.size());
186
187
2/2
✓ Branch 0 taken 480 times.
✓ Branch 1 taken 24 times.
 504 for (const auto &point : pts) {
188
4/4
✓ Branch 0 taken 776 times.
✓ Branch 1 taken 120 times.
✓ Branch 2 taken 416 times.
✓ Branch 3 taken 360 times.
 896 while (lower.size() >= 2 && Cross(lower[lower.size() - 2], lower.back(), point) <= 0) {
189 lower.pop_back();
190 }
191 lower.push_back(point);
192 }
193
194
2/2
✓ Branch 0 taken 480 times.
✓ Branch 1 taken 24 times.
 504 for (int i = static_cast<int>(pts.size()) - 1; i >= 0; --i) {
195 480 const auto &point = pts[i];
196
4/4
✓ Branch 0 taken 776 times.
✓ Branch 1 taken 120 times.
✓ Branch 2 taken 360 times.
✓ Branch 3 taken 416 times.
 896 while (upper.size() >= 2 && Cross(upper[upper.size() - 2], upper.back(), point) <= 0) {
197 upper.pop_back();
198 }
199 upper.push_back(point);
200 }
201
202 lower.pop_back();
203 upper.pop_back();
204
205
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 lower.insert(lower.end(), upper.begin(), upper.end());
206 return lower;
207 }
208
209 40 bool ShkenevIConstrHullSTL::PostProcessingImpl() {
210 40 return true;
211 }
212
213 } // namespace shkenev_i_constra_hull_for_binary_image
214