GCC Code Coverage Report

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