GCC Code Coverage Report

Directory: ./
File: tasks/egorova_l_binary_convex_hull/stl/src/ops_stl.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 72 75 96.0%
Functions: 9 9 100.0%
Branches: 76 106 71.7%
Line Branch Exec Source
1 #include "egorova_l_binary_convex_hull/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <atomic>
5 #include <cstddef>
6 #include <cstdint>
7 #include <queue>
8 #include <thread>
9 #include <tuple>
10 #include <utility>
11 #include <vector>
12
13 #include "egorova_l_binary_convex_hull/common/include/common.hpp"
14 #include "util/include/util.hpp"
15
16 namespace egorova_l_binary_convex_hull {
17
18 namespace {
19
20 80 std::vector<Point> RunBFS(int start_col, int start_row, int w, int h, const std::vector<uint8_t> &data,
21 std::vector<bool> &visited) {
22
4/6
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 72 times.
✓ Branch 3 taken 8 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 8 times.
✗ Branch 7 not taken.
 80 static const std::vector<std::pair<int, int>> kDirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
23
24
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 std::vector<Point> component;
25 std::queue<std::pair<int, int>> q;
26
27 q.emplace(start_col, start_row);
28
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 80 times.
 80 visited[(static_cast<size_t>(start_row) * w) + start_col] = true;
29
30
2/2
✓ Branch 0 taken 672 times.
✓ Branch 1 taken 80 times.
 752 while (!q.empty()) {
31 auto [cx, cy] = q.front();
32 q.pop();
33
1/2
✓ Branch 1 taken 672 times.
✗ Branch 2 not taken.
 672 component.push_back({cx, cy});
34
35
2/2
✓ Branch 0 taken 2688 times.
✓ Branch 1 taken 672 times.
 3360 for (const auto &dir : kDirs) {
36 2688 int nx = cx + dir.first;
37 2688 int ny = cy + dir.second;
38
39
4/8
✓ Branch 0 taken 2688 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2688 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 2688 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 2688 times.
 2688 if (nx < 0 || nx >= w || ny < 0 || ny >= h) {
40 ✗ continue;
41 }
42
43
2/2
✓ Branch 0 taken 1696 times.
✓ Branch 1 taken 992 times.
 2688 const size_t nidx = (static_cast<size_t>(ny) * w) + nx;
44
4/4
✓ Branch 0 taken 1696 times.
✓ Branch 1 taken 992 times.
✓ Branch 2 taken 592 times.
✓ Branch 3 taken 1104 times.
 2688 if (data[nidx] != 0 && !visited[nidx]) {
45 visited[nidx] = true;
46 q.emplace(nx, ny);
47 }
48 }
49 }
50 80 return component;
51 }
52
53 int64_t Cross(const Point &o, const Point &a, const Point &b) {
54 1440 return (static_cast<int64_t>(a.x - o.x) * static_cast<int64_t>(b.y - o.y)) -
55
4/4
✓ Branch 0 taken 456 times.
✓ Branch 1 taken 256 times.
✓ Branch 2 taken 280 times.
✓ Branch 3 taken 448 times.
 1440 (static_cast<int64_t>(a.y - o.y) * static_cast<int64_t>(b.x - o.x));
56 }
57
58 } // namespace
59
60
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 BinaryConvexHullSTL::BinaryConvexHullSTL(const InType &in) {
61 SetTypeOfTask(GetStaticTypeOfTask());
62 GetInput() = in;
63 GetOutput() = {};
64 64 }
65
66 64 bool BinaryConvexHullSTL::ValidationImpl() {
67 const auto &img = GetInput();
68
2/4
✓ Branch 0 taken 64 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 64 times.
✗ Branch 3 not taken.
 64 if (img.width <= 0 || img.height <= 0) {
69 return false;
70 }
71 64 return static_cast<int>(img.data.size()) == img.width * img.height;
72 }
73
74 64 bool BinaryConvexHullSTL::PreProcessingImpl() {
75 64 components_ = FindComponents(GetInput());
76 64 return true;
77 }
78
79
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 56 times.
 64 bool BinaryConvexHullSTL::RunImpl() {
80 64 const int n = static_cast<int>(components_.size());
81
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 56 times.
 64 if (n == 0) {
82 GetOutput().clear();
83 8 return true;
84 }
85
86 56 const int num_threads = std::min(ppc::util::GetNumThreads(), n);
87 56 std::vector<std::vector<Point>> result(n);
88 56 std::atomic<int> next_idx(0);
89
90 72 auto worker = [&]() {
91 int i = 0;
92
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 72 times.
 152 while ((i = next_idx.fetch_add(1)) < n) {
93
1/2
✓ Branch 2 taken 80 times.
✗ Branch 3 not taken.
 160 result[i] = ConvexHull(components_[i]);
94 }
95 72 };
96
97 56 std::vector<std::thread> threads;
98
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 threads.reserve(num_threads);
99
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 56 times.
 128 for (int i = 0; i < num_threads; ++i) {
100
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 threads.emplace_back(worker);
101 }
102
103
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 56 times.
 128 for (auto &t : threads) {
104
1/2
✓ Branch 0 taken 72 times.
✗ Branch 1 not taken.
 72 if (t.joinable()) {
105
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 t.join();
106 }
107 }
108
109 56 GetOutput() = std::move(result);
110 return true;
111 56 }
112
113 64 bool BinaryConvexHullSTL::PostProcessingImpl() {
114 64 return true;
115 }
116
117 64 std::vector<std::vector<Point>> BinaryConvexHullSTL::FindComponents(const ImageData &img) {
118 64 const int w = img.width;
119 64 const int h = img.height;
120 64 std::vector<bool> visited(static_cast<size_t>(w) * h, false);
121 64 std::vector<std::vector<Point>> components;
122
123
2/2
✓ Branch 0 taken 920 times.
✓ Branch 1 taken 64 times.
 984 for (int row = 0; row < h; ++row) {
124
2/2
✓ Branch 0 taken 16200 times.
✓ Branch 1 taken 920 times.
 17120 for (int col = 0; col < w; ++col) {
125
2/2
✓ Branch 0 taken 672 times.
✓ Branch 1 taken 15528 times.
 16200 const size_t idx = (static_cast<size_t>(row) * w) + col;
126
4/4
✓ Branch 0 taken 672 times.
✓ Branch 1 taken 15528 times.
✓ Branch 2 taken 592 times.
✓ Branch 3 taken 80 times.
 16200 if (img.data[idx] == 0 || visited[idx]) {
127 16120 continue;
128 }
129
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 160 components.push_back(RunBFS(col, row, w, h, img.data, visited));
130 }
131 }
132
133 64 return components;
134 ✗ }
135
136
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 80 times.
 80 std::vector<Point> BinaryConvexHullSTL::ConvexHull(std::vector<Point> points) {
137 80 const int n = static_cast<int>(points.size());
138
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 80 times.
 80 if (n == 0) {
139 ✗ return {};
140 }
141
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 80 times.
 80 if (n == 1) {
142 return points;
143 }
144
145 std::ranges::sort(points, [](const Point &a, const Point &b) { return std::tie(a.x, a.y) < std::tie(b.x, b.y); });
146
147 auto [first, last] =
148
3/8
✓ Branch 0 taken 416 times.
✓ Branch 1 taken 176 times.
✓ Branch 2 taken 416 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 592 std::ranges::unique(points, [](const Point &a, const Point &b) { return a.x == b.x && a.y == b.y; });
149 points.erase(first, last);
150
151 80 const int m = static_cast<int>(points.size());
152
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 80 times.
 80 if (m <= 2) {
153 return points;
154 }
155
156 80 std::vector<Point> hull;
157
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 hull.reserve(static_cast<size_t>(2) * static_cast<size_t>(m));
158
159
2/2
✓ Branch 0 taken 672 times.
✓ Branch 1 taken 80 times.
 752 for (int i = 0; i < m; ++i) {
160
4/4
✓ Branch 0 taken 712 times.
✓ Branch 1 taken 416 times.
✓ Branch 2 taken 456 times.
✓ Branch 3 taken 256 times.
 1128 while (hull.size() >= 2 && Cross(hull[hull.size() - 2], hull.back(), points[i]) <= 0) {
161 hull.pop_back();
162 }
163
1/2
✓ Branch 0 taken 672 times.
✗ Branch 1 not taken.
 672 hull.push_back(points[i]);
164 }
165
166 const size_t lower_hull_size = hull.size();
167
2/2
✓ Branch 0 taken 592 times.
✓ Branch 1 taken 80 times.
 672 for (int i = m - 2; i >= 0; --i) {
168
4/4
✓ Branch 0 taken 728 times.
✓ Branch 1 taken 312 times.
✓ Branch 2 taken 280 times.
✓ Branch 3 taken 448 times.
 1040 while (hull.size() > lower_hull_size && Cross(hull[hull.size() - 2], hull.back(), points[i]) <= 0) {
169 hull.pop_back();
170 }
171
1/2
✓ Branch 0 taken 592 times.
✗ Branch 1 not taken.
 592 hull.push_back(points[i]);
172 }
173 hull.pop_back();
174
175 return hull;
176 }
177
178 } // namespace egorova_l_binary_convex_hull
179