GCC Code Coverage Report

Directory: ./
File: tasks/shkenev_i_constra_hull_for_binary_image/tbb/src/ops_tbb.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 77 79 97.5%
Functions: 11 12 91.7%
Branches: 84 112 75.0%
Line Branch Exec Source
1 #include "shkenev_i_constra_hull_for_binary_image/tbb/include/ops_tbb.hpp"
2
3 #include <tbb/blocked_range.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 // 12
22 constexpr uint8_t kThreshold = 128;
23
24 constexpr std::array<std::pair<int, int>, 4> kDirs = {{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}};
25
26 int64_t Cross(const Point &a, const Point &b, const Point &c) {
27 776 return (static_cast<int64_t>(b.x - a.x) * (c.y - b.y)) - (static_cast<int64_t>(b.y - a.y) * (c.x - b.x));
28 }
29
30 inline bool InBounds(int x, int y, int w, int h) {
31 2008 return x >= 0 && x < w && y >= 0 && y < h;
32 }
33
34 } // namespace
35
36
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 ShkenevIConstrHullTBB::ShkenevIConstrHullTBB(const InType &in) : work_(in) {
37 SetTypeOfTask(GetStaticTypeOfTask());
38
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 GetInput() = in;
39 20 }
40
41 20 bool ShkenevIConstrHullTBB::ValidationImpl() {
42 const auto &in = GetInput();
43
2/4
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 20 times.
 20 return in.width > 0 && in.height > 0 &&
44
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20 times.
 20 in.pixels.size() == static_cast<size_t>(in.width) * static_cast<size_t>(in.height);
45 }
46
47 20 bool ShkenevIConstrHullTBB::PreProcessingImpl() {
48 20 work_ = GetInput();
49 work_.components.clear();
50 work_.convex_hulls.clear();
51
52 20 ThresholdImage();
53 20 return true;
54 }
55
56 20 void ShkenevIConstrHullTBB::ThresholdImage() {
57 20 auto &p = work_.pixels;
58
59 20 tbb::parallel_for(tbb::blocked_range<size_t>(0, p.size()), [&](const auto &r) {
60
4/4
✓ Branch 0 taken 416 times.
✓ Branch 1 taken 416 times.
✓ Branch 2 taken 492 times.
✓ Branch 3 taken 492 times.
 1816 for (size_t i = r.begin(); i < r.end(); ++i) {
61
4/4
✓ Branch 0 taken 328 times.
✓ Branch 1 taken 88 times.
✓ Branch 2 taken 328 times.
✓ Branch 3 taken 164 times.
 1564 p[i] = (p[i] > kThreshold) ? 255 : 0;
62 }
63 });
64 20 }
65
66 252 void ShkenevIConstrHullTBB::AddNeighbors(const Point &current, int width, int height, std::vector<uint8_t> &visited,
67 std::queue<Point> &queue) {
68
2/2
✓ Branch 0 taken 1008 times.
✓ Branch 1 taken 252 times.
 1260 for (auto [dx, dy] : kDirs) {
69 1008 int neighbor_x = current.x + dx;
70
2/2
✓ Branch 0 taken 1000 times.
✓ Branch 1 taken 8 times.
 1008 int neighbor_y = current.y + dy;
71
72
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 992 times.
 1000 if (!InBounds(neighbor_x, neighbor_y, width, height)) {
73 780 continue;
74 }
75
76 size_t neighbor_idx = Index(neighbor_x, neighbor_y, width);
77
78
4/4
✓ Branch 0 taken 500 times.
✓ Branch 1 taken 492 times.
✓ Branch 2 taken 228 times.
✓ Branch 3 taken 272 times.
 992 if (visited[neighbor_idx] != 0U || work_.pixels[neighbor_idx] == 0) {
79 764 continue;
80 }
81
82 228 visited[neighbor_idx] = 1;
83 queue.emplace(neighbor_x, neighbor_y);
84 }
85 252 }
86
87 24 std::vector<Point> ShkenevIConstrHullTBB::ExtractComponent(int start_x, int start_y, int width, int height,
88 std::vector<uint8_t> &visited) {
89
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 std::vector<Point> component;
90 std::queue<Point> queue;
91 24 size_t start_idx = Index(start_x, start_y, width);
92
93 queue.emplace(start_x, start_y);
94 24 visited[start_idx] = 1;
95
96
2/2
✓ Branch 0 taken 252 times.
✓ Branch 1 taken 24 times.
 276 while (!queue.empty()) {
97 252 auto current = queue.front();
98 queue.pop();
99 component.push_back(current);
100
1/2
✓ Branch 1 taken 252 times.
✗ Branch 2 not taken.
 252 AddNeighbors(current, width, height, visited, queue);
101 }
102
103 24 return component;
104 }
105
106 20 void ShkenevIConstrHullTBB::FindComponents() {
107 20 const int width = work_.width;
108 20 const int height = work_.height;
109
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 20 times.
 20 std::vector<uint8_t> visited(static_cast<size_t>(width) * height, 0);
110 work_.components.clear();
111
112
2/2
✓ Branch 0 taken 124 times.
✓ Branch 1 taken 20 times.
 144 for (int y_coord = 0; y_coord < height; ++y_coord) {
113
2/2
✓ Branch 0 taken 908 times.
✓ Branch 1 taken 124 times.
 1032 for (int x_coord = 0; x_coord < width; ++x_coord) {
114 size_t idx = Index(x_coord, y_coord, width);
115
116
4/4
✓ Branch 0 taken 680 times.
✓ Branch 1 taken 228 times.
✓ Branch 2 taken 656 times.
✓ Branch 3 taken 24 times.
 908 if (visited[idx] != 0U || work_.pixels[idx] == 0) {
117 884 continue;
118 }
119
120
1/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 48 work_.components.push_back(ExtractComponent(x_coord, y_coord, width, height, visited));
121 }
122 }
123 20 }
124
125 20 bool ShkenevIConstrHullTBB::RunImpl() {
126 20 FindComponents();
127
128 20 auto &comps = work_.components;
129 20 auto &hulls = work_.convex_hulls;
130
131 20 hulls.resize(comps.size());
132
133 44 tbb::parallel_for(tbb::blocked_range<size_t>(0, comps.size()), [&](const auto &r) {
134
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 24 times.
 48 for (size_t i = r.begin(); i < r.end(); ++i) {
135
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 const auto &comp = comps[i];
136
137
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 if (comp.size() <= 2) {
138 12 hulls[i] = comp;
139 } else {
140 24 hulls[i] = BuildHull(comp);
141 }
142 }
143 24 });
144
145 20 GetOutput() = work_;
146 20 return true;
147 }
148
149
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 std::vector<Point> ShkenevIConstrHullTBB::BuildHull(const std::vector<Point> &points) {
150
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 if (points.size() <= 2) {
151 ✗ return points;
152 }
153
154 12 std::vector<Point> pts = points;
155
156
17/26
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 148 times.
✓ Branch 5 taken 56 times.
✓ Branch 6 taken 124 times.
✓ Branch 7 taken 32 times.
✓ Branch 8 taken 8 times.
✓ Branch 9 taken 4 times.
✓ Branch 10 taken 4 times.
✓ Branch 11 taken 4 times.
✗ Branch 12 not taken.
✓ Branch 13 taken 4 times.
✓ Branch 14 taken 4 times.
✗ Branch 15 not taken.
✓ Branch 16 taken 4 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✓ Branch 20 taken 352 times.
✓ Branch 21 taken 200 times.
✓ Branch 22 taken 112 times.
✓ Branch 23 taken 16 times.
✓ Branch 24 taken 256 times.
✓ Branch 25 taken 120 times.
 1448 std::ranges::sort(pts, [](auto &a, auto &b) { return (a.x != b.x) ? (a.x < b.x) : (a.y < b.y); });
157
158 auto [first, last] = std::ranges::unique(pts);
159 pts.erase(first, last);
160
161
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 if (pts.size() <= 2) {
162 return pts;
163 }
164
165 12 std::vector<Point> lower;
166
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 std::vector<Point> upper;
167
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 lower.reserve(pts.size());
168
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 upper.reserve(pts.size());
169
170
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 12 times.
 252 for (auto &point : pts) {
171
4/4
✓ Branch 0 taken 388 times.
✓ Branch 1 taken 60 times.
✓ Branch 2 taken 208 times.
✓ Branch 3 taken 180 times.
 448 while (lower.size() >= 2 && Cross(lower[lower.size() - 2], lower.back(), point) <= 0) {
172 lower.pop_back();
173 }
174 lower.push_back(point);
175 }
176
177
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 12 times.
 252 for (auto &point : std::ranges::reverse_view(pts)) {
178
4/4
✓ Branch 0 taken 388 times.
✓ Branch 1 taken 60 times.
✓ Branch 2 taken 180 times.
✓ Branch 3 taken 208 times.
 448 while (upper.size() >= 2 && Cross(upper[upper.size() - 2], upper.back(), point) <= 0) {
179 upper.pop_back();
180 }
181 upper.push_back(point);
182 }
183
184 lower.pop_back();
185 upper.pop_back();
186
187
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 lower.insert(lower.end(), upper.begin(), upper.end());
188 return lower;
189 }
190
191 ✗ size_t ShkenevIConstrHullTBB::Index(int x, int y, int width) {
192
5/6
✓ Branch 0 taken 680 times.
✓ Branch 1 taken 228 times.
✓ Branch 3 taken 24 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 500 times.
✓ Branch 6 taken 492 times.
 1924 return (static_cast<size_t>(y) * static_cast<size_t>(width)) + static_cast<size_t>(x);
193 }
194
195 20 bool ShkenevIConstrHullTBB::PostProcessingImpl() {
196 20 return true;
197 }
198
199 } // namespace shkenev_i_constra_hull_for_binary_image
200