GCC Code Coverage Report

Directory: ./
File: tasks/nalitov_d_binary/seq/src/ops_seq.cpp
Date: 2026-01-27 01:59:34
Exec Total Coverage
Lines: 71 75 94.7%
Functions: 8 9 88.9%
Branches: 83 114 72.8%
Line Branch Exec Source
1 #include "nalitov_d_binary/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <array>
5 #include <cstddef>
6 #include <cstdint>
7 #include <queue>
8 #include <ranges>
9 #include <utility>
10 #include <vector>
11
12 #include "nalitov_d_binary/common/include/common.hpp"
13
14 namespace nalitov_d_binary {
15
16 namespace {
17
18 constexpr uint8_t kThreshold = 128;
19
20 [[nodiscard]] size_t ToIndex(int x, int y, int width) {
21
4/4
✓ Branch 0 taken 504 times.
✓ Branch 1 taken 1312 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);
22 }
23
24 48 void FloodFillComponent(int start_x, int start_y, int width, int height, const std::vector<uint8_t> &pixels,
25 std::vector<bool> &visited, std::vector<GridPoint> &component) {
26 48 const std::array<std::pair<int, int>, 4> directions = {std::make_pair(1, 0), std::make_pair(-1, 0),
27 std::make_pair(0, 1), std::make_pair(0, -1)};
28
29 std::queue<GridPoint> frontier;
30 frontier.emplace(start_x, start_y);
31
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 visited[ToIndex(start_x, start_y, width)] = true;
32
33
2/2
✓ Branch 0 taken 504 times.
✓ Branch 1 taken 48 times.
 552 while (!frontier.empty()) {
34 504 const GridPoint current = frontier.front();
35 frontier.pop();
36 component.push_back(current);
37
38
2/2
✓ Branch 0 taken 2016 times.
✓ Branch 1 taken 504 times.
 2520 for (const auto &[dx, dy] : directions) {
39 2016 const int next_x = current.x + dx;
40 2016 const int next_y = current.y + dy;
41
42
8/8
✓ Branch 0 taken 2008 times.
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 2000 times.
✓ Branch 3 taken 8 times.
✓ Branch 4 taken 1992 times.
✓ Branch 5 taken 8 times.
✓ Branch 6 taken 8 times.
✓ Branch 7 taken 1984 times.
 2016 if (next_x < 0 || next_x >= width || next_y < 0 || next_y >= height) {
43 1560 continue;
44 }
45
46 const size_t next_idx = ToIndex(next_x, next_y, width);
47
4/4
✓ Branch 0 taken 1000 times.
✓ Branch 1 taken 984 times.
✓ Branch 2 taken 544 times.
✓ Branch 3 taken 456 times.
 1984 if (visited[next_idx] || pixels[next_idx] == 0) {
48 1528 continue;
49 }
50
51 visited[next_idx] = true;
52 frontier.emplace(next_x, next_y);
53 }
54 }
55 48 }
56
57 } // namespace
58
59
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 NalitovDBinarySEQ::NalitovDBinarySEQ(const InType &in) : working_image_(in) {
60 SetTypeOfTask(GetStaticTypeOfTask());
61
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 GetInput() = in;
62 40 }
63
64 40 bool NalitovDBinarySEQ::ValidationImpl() {
65 const auto &input = GetInput();
66
2/4
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 40 times.
 40 const bool valid_dimensions = input.width > 0 && input.height > 0;
67 40 const bool size_matches = input.pixels.size() == static_cast<size_t>(input.width) * static_cast<size_t>(input.height);
68 40 return valid_dimensions && size_matches;
69 }
70
71 40 bool NalitovDBinarySEQ::PreProcessingImpl() {
72 40 working_image_ = GetInput();
73 ThresholdImage();
74 40 return true;
75 }
76
77 40 bool NalitovDBinarySEQ::RunImpl() {
78 40 DiscoverComponents();
79
80 working_image_.convex_hulls.clear();
81 40 working_image_.convex_hulls.reserve(working_image_.components.size());
82
83
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 40 times.
 88 for (const auto &component : working_image_.components) {
84
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 if (component.empty()) {
85 ✗ continue;
86 }
87
88
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 24 times.
 48 if (component.size() <= 2U) {
89 24 working_image_.convex_hulls.push_back(component);
90 } else {
91
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 48 working_image_.convex_hulls.push_back(BuildConvexHull(component));
92 }
93 }
94
95 40 GetOutput() = working_image_;
96 40 return true;
97 }
98
99 40 bool NalitovDBinarySEQ::PostProcessingImpl() {
100 40 return true;
101 }
102
103 ✗ void NalitovDBinarySEQ::ThresholdImage() {
104
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 1816 times.
✓ Branch 3 taken 40 times.
 1856 for (auto &pixel : working_image_.pixels) {
105
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 1312 times.
✓ Branch 3 taken 504 times.
 3128 pixel = pixel > kThreshold ? static_cast<uint8_t>(255) : static_cast<uint8_t>(0);
106 }
107 ✗ }
108
109 40 void NalitovDBinarySEQ::DiscoverComponents() {
110 40 const int width = working_image_.width;
111 40 const int height = working_image_.height;
112 40 const size_t total_pixels = static_cast<size_t>(width) * static_cast<size_t>(height);
113
114
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 40 times.
 40 std::vector<bool> visited(total_pixels, false);
115 working_image_.components.clear();
116
117
2/2
✓ Branch 0 taken 248 times.
✓ Branch 1 taken 40 times.
 288 for (int row = 0; row < height; ++row) {
118
2/2
✓ Branch 0 taken 1816 times.
✓ Branch 1 taken 248 times.
 2064 for (int col = 0; col < width; ++col) {
119 const size_t idx = ToIndex(col, row, width);
120
121
4/4
✓ Branch 0 taken 504 times.
✓ Branch 1 taken 1312 times.
✓ Branch 2 taken 456 times.
✓ Branch 3 taken 48 times.
 1816 if (working_image_.pixels[idx] == 0 || visited[idx]) {
122 1768 continue;
123 }
124
125 48 std::vector<GridPoint> component;
126
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 FloodFillComponent(col, row, width, height, working_image_.pixels, visited, component);
127
128
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 if (!component.empty()) {
129
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 working_image_.components.push_back(std::move(component));
130 }
131 }
132 }
133 40 }
134
135
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 std::vector<GridPoint> NalitovDBinarySEQ::BuildConvexHull(const std::vector<GridPoint> &points) {
136
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (points.size() <= 2U) {
137 ✗ return points;
138 }
139
140 24 std::vector<GridPoint> sorted_points = points;
141
142 std::ranges::sort(sorted_points, [](const GridPoint &lhs, const GridPoint &rhs) {
143
17/26
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 296 times.
✓ Branch 5 taken 112 times.
✓ Branch 6 taken 248 times.
✓ Branch 7 taken 64 times.
✓ Branch 8 taken 16 times.
✓ Branch 9 taken 8 times.
✓ Branch 10 taken 8 times.
✓ Branch 11 taken 8 times.
✗ Branch 12 not taken.
✓ Branch 13 taken 8 times.
✓ Branch 14 taken 8 times.
✗ Branch 15 not taken.
✓ Branch 16 taken 8 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✓ Branch 20 taken 704 times.
✓ Branch 21 taken 400 times.
✓ Branch 22 taken 224 times.
✓ Branch 23 taken 32 times.
✓ Branch 24 taken 512 times.
✓ Branch 25 taken 240 times.
 2896 return (lhs.x != rhs.x) ? (lhs.x < rhs.x) : (lhs.y < rhs.y);
144 });
145
146 auto unique_end = std::ranges::unique(sorted_points).begin();
147 sorted_points.erase(unique_end, sorted_points.end());
148
149
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (sorted_points.size() <= 2U) {
150 return sorted_points;
151 }
152
153 const auto cross = [](const GridPoint &a, const GridPoint &b, const GridPoint &c) {
154 1552 const std::int64_t abx = static_cast<std::int64_t>(b.x) - static_cast<std::int64_t>(a.x);
155 1552 const std::int64_t aby = static_cast<std::int64_t>(b.y) - static_cast<std::int64_t>(a.y);
156 1552 const std::int64_t bcx = static_cast<std::int64_t>(c.x) - static_cast<std::int64_t>(b.x);
157 1552 const std::int64_t bcy = static_cast<std::int64_t>(c.y) - static_cast<std::int64_t>(b.y);
158 1552 return (abx * bcy) - (aby * bcx);
159 };
160
161 24 std::vector<GridPoint> lower;
162
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 std::vector<GridPoint> upper;
163
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 lower.reserve(sorted_points.size());
164
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 upper.reserve(sorted_points.size());
165
166
2/2
✓ Branch 0 taken 480 times.
✓ Branch 1 taken 24 times.
 504 for (const auto &point : sorted_points) {
167
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() >= 2U && cross(lower[lower.size() - 2U], lower.back(), point) <= 0) {
168 lower.pop_back();
169 }
170 lower.push_back(point);
171 }
172
173
2/2
✓ Branch 0 taken 480 times.
✓ Branch 1 taken 24 times.
 504 for (const auto &point : std::ranges::reverse_view(sorted_points)) {
174
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() >= 2U && cross(upper[upper.size() - 2U], upper.back(), point) <= 0) {
175 upper.pop_back();
176 }
177 upper.push_back(point);
178 }
179
180 lower.pop_back();
181 upper.pop_back();
182
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 lower.insert(lower.end(), upper.begin(), upper.end());
183 return lower;
184 }
185
186 } // namespace nalitov_d_binary
187