GCC Code Coverage Report

Directory: ./
File: tasks/chernov_t_convex_hull_binary_components/seq/src/ops_seq.cpp
Date: 2026-01-27 01:59:34
Exec Total Coverage
Lines: 62 62 100.0%
Functions: 8 8 100.0%
Branches: 63 80 78.8%
Line Branch Exec Source
1 #include "chernov_t_convex_hull_binary_components/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <array>
5 #include <cstddef>
6 #include <cstdint>
7 #include <queue>
8 #include <utility>
9 #include <vector>
10
11 #include "chernov_t_convex_hull_binary_components/common/include/common.hpp"
12
13 namespace chernov_t_convex_hull_binary_components {
14
15
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 ChernovTConvexHullBinaryComponentsSEQ::ChernovTConvexHullBinaryComponentsSEQ(const InType &in) {
16 SetTypeOfTask(GetStaticTypeOfTask());
17 GetInput() = in;
18 72 GetOutput() = OutType{};
19 72 }
20
21 72 bool ChernovTConvexHullBinaryComponentsSEQ::ValidationImpl() {
22 const auto &[width, height, pixels] = GetInput();
23
2/4
✓ Branch 0 taken 72 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 72 times.
✗ Branch 3 not taken.
 72 if (width <= 0 || height <= 0) {
24 return false;
25 }
26
1/2
✓ Branch 0 taken 72 times.
✗ Branch 1 not taken.
 72 if (pixels.size() != static_cast<std::size_t>(width) * static_cast<std::size_t>(height)) {
27 return false;
28 }
29
1/2
✓ Branch 0 taken 528 times.
✗ Branch 1 not taken.
 528 return std::ranges::all_of(pixels, [](int p) { return p == 0 || p == 1; });
30 }
31
32 72 bool ChernovTConvexHullBinaryComponentsSEQ::PreProcessingImpl() {
33 72 return true;
34 }
35
36 72 bool ChernovTConvexHullBinaryComponentsSEQ::RunImpl() {
37 const auto &[width, height, pixels] = GetInput();
38 72 auto components = FindConnectedComponents(width, height, pixels);
39 72 OutType hulls;
40
2/2
✓ Branch 0 taken 152 times.
✓ Branch 1 taken 72 times.
 224 for (auto &comp : components) {
41
1/2
✓ Branch 0 taken 152 times.
✗ Branch 1 not taken.
 152 if (!comp.empty()) {
42
2/4
✓ Branch 1 taken 152 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 152 times.
✗ Branch 5 not taken.
 304 hulls.push_back(ConvexHull(comp));
43 }
44 }
45 72 GetOutput() = std::move(hulls);
46 72 return true;
47 72 }
48
49 72 bool ChernovTConvexHullBinaryComponentsSEQ::PostProcessingImpl() {
50 72 return true;
51 }
52
53 152 std::vector<std::pair<int, int>> ChernovTConvexHullBinaryComponentsSEQ::ExtractComponent(
54 int start_col, int start_row, const std::vector<int> &pixels, std::vector<std::vector<bool>> &visited, int width,
55 int height) {
56
1/2
✓ Branch 1 taken 152 times.
✗ Branch 2 not taken.
 152 std::vector<std::pair<int, int>> comp;
57 std::queue<std::pair<int, int>> q;
58 q.emplace(start_col, start_row);
59
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 152 times.
 152 visited[static_cast<std::size_t>(start_row)][static_cast<std::size_t>(start_col)] = true;
60
61 152 constexpr std::array<std::pair<int, int>, 4> kDirs = {{{0, -1}, {0, 1}, {-1, 0}, {1, 0}}};
62
2/2
✓ Branch 0 taken 280 times.
✓ Branch 1 taken 152 times.
 432 while (!q.empty()) {
63 auto [cx, cy] = q.front();
64 q.pop();
65
1/2
✓ Branch 1 taken 280 times.
✗ Branch 2 not taken.
 280 comp.emplace_back(cx, cy);
66
67
2/2
✓ Branch 0 taken 1120 times.
✓ Branch 1 taken 280 times.
 1400 for (const auto &[dx, dy] : kDirs) {
68 1120 int nx = cx + dx;
69 1120 int ny = cy + dy;
70
8/8
✓ Branch 0 taken 1040 times.
✓ Branch 1 taken 80 times.
✓ Branch 2 taken 960 times.
✓ Branch 3 taken 80 times.
✓ Branch 4 taken 808 times.
✓ Branch 5 taken 152 times.
✓ Branch 6 taken 656 times.
✓ Branch 7 taken 152 times.
 1120 if (nx >= 0 && nx < width && ny >= 0 && ny < height) {
71 656 std::size_t idx =
72
2/2
✓ Branch 0 taken 304 times.
✓ Branch 1 taken 352 times.
 656 (static_cast<std::size_t>(ny) * static_cast<std::size_t>(width)) + static_cast<std::size_t>(nx);
73
4/4
✓ Branch 0 taken 304 times.
✓ Branch 1 taken 352 times.
✓ Branch 2 taken 128 times.
✓ Branch 3 taken 176 times.
 656 if (pixels[idx] == 1 && !visited[static_cast<std::size_t>(ny)][static_cast<std::size_t>(nx)]) {
74 visited[static_cast<std::size_t>(ny)][static_cast<std::size_t>(nx)] = true;
75 q.emplace(nx, ny);
76 }
77 }
78 }
79 }
80 152 return comp;
81 }
82
83 72 std::vector<std::vector<std::pair<int, int>>> ChernovTConvexHullBinaryComponentsSEQ::FindConnectedComponents(
84 int width, int height, const std::vector<int> &pixels) {
85
1/2
✓ Branch 2 taken 72 times.
✗ Branch 3 not taken.
 72 std::vector<std::vector<bool>> visited(height, std::vector<bool>(width, false));
86 72 std::vector<std::vector<std::pair<int, int>>> components;
87
88
2/2
✓ Branch 0 taken 152 times.
✓ Branch 1 taken 72 times.
 224 for (int row = 0; row < height; ++row) {
89
2/2
✓ Branch 0 taken 528 times.
✓ Branch 1 taken 152 times.
 680 for (int col = 0; col < width; ++col) {
90 528 std::size_t idx =
91
2/2
✓ Branch 0 taken 280 times.
✓ Branch 1 taken 248 times.
 528 (static_cast<std::size_t>(row) * static_cast<std::size_t>(width)) + static_cast<std::size_t>(col);
92
4/4
✓ Branch 0 taken 280 times.
✓ Branch 1 taken 248 times.
✓ Branch 2 taken 152 times.
✓ Branch 3 taken 128 times.
 528 if (pixels[idx] == 1 && !visited[row][col]) {
93
1/2
✓ Branch 1 taken 152 times.
✗ Branch 2 not taken.
 152 auto comp = ExtractComponent(col, row, pixels, visited, width, height);
94 components.push_back(std::move(comp));
95 }
96 }
97 }
98 72 return components;
99 72 }
100
101
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 40 times.
 152 std::vector<std::pair<int, int>> ChernovTConvexHullBinaryComponentsSEQ::ConvexHull(
102 std::vector<std::pair<int, int>> pts) {
103
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 40 times.
 152 if (pts.size() <= 1U) {
104 return pts;
105 }
106
107 std::ranges::sort(pts);
108 auto [first, last] = std::ranges::unique(pts);
109 pts.erase(first, last);
110
111
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 40 times.
 40 if (pts.size() <= 2U) {
112 return pts;
113 }
114
115
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 std::vector<std::pair<int, int>> hull;
116
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 hull.reserve(pts.size() + 1);
117
118
2/2
✓ Branch 0 taken 168 times.
✓ Branch 1 taken 40 times.
 208 for (const auto &p : pts) {
119
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 144 times.
 232 while (hull.size() >= 2) {
120 const auto &a = hull[hull.size() - 2];
121 const auto &b = hull[hull.size() - 1];
122 88 std::int64_t cross =
123 88 (static_cast<std::int64_t>(b.first - a.first) * static_cast<std::int64_t>(p.second - a.second)) -
124 88 (static_cast<std::int64_t>(b.second - a.second) * static_cast<std::int64_t>(p.first - a.first));
125
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 24 times.
 88 if (cross > 0) {
126 break;
127 }
128 hull.pop_back();
129 }
130 hull.push_back(p);
131 }
132
133 std::size_t lower_len = hull.size();
134
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 40 times.
 168 for (auto it = pts.rbegin() + 1; it != pts.rend(); ++it) {
135
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 104 times.
 192 while (hull.size() > lower_len) {
136 const auto &a = hull[hull.size() - 2];
137 const auto &b = hull[hull.size() - 1];
138 std::int64_t cross =
139 88 (static_cast<std::int64_t>(b.first - a.first) * static_cast<std::int64_t>(it->second - a.second)) -
140 88 (static_cast<std::int64_t>(b.second - a.second) * static_cast<std::int64_t>(it->first - a.first));
141
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 24 times.
 88 if (cross > 0) {
142 break;
143 }
144 hull.pop_back();
145 }
146 hull.push_back(*it);
147 }
148
149
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 40 if (hull.size() > 1) {
150 hull.pop_back();
151 }
152 return hull;
153 }
154
155 } // namespace chernov_t_convex_hull_binary_components
156