GCC Code Coverage Report

Directory: ./
File: tasks/chyokotov_a_convex_hull_finding/seq/src/ops_seq.cpp
Date: 2026-01-10 02:40:41
Exec Total Coverage
Lines: 59 60 98.3%
Functions: 8 9 88.9%
Branches: 78 94 83.0%
Line Branch Exec Source
1 #include "chyokotov_a_convex_hull_finding/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <array>
5 #include <climits>
6 #include <cstddef>
7 #include <queue>
8 #include <utility>
9 #include <vector>
10
11 #include "chyokotov_a_convex_hull_finding/common/include/common.hpp"
12
13 namespace chyokotov_a_convex_hull_finding {
14
15
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 ChyokotovConvexHullFindingSEQ::ChyokotovConvexHullFindingSEQ(const InType &in) {
16 SetTypeOfTask(GetStaticTypeOfTask());
17 GetInput().clear();
18
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 GetInput().reserve(in.size());
19
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 48 times.
 160 for (const auto &row : in) {
20
1/2
✓ Branch 1 taken 112 times.
✗ Branch 2 not taken.
 112 GetInput().push_back(row);
21 }
22
23 GetOutput().clear();
24 48 }
25
26
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 40 times.
 48 bool ChyokotovConvexHullFindingSEQ::ValidationImpl() {
27 const auto &input = GetInput();
28
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 40 times.
 48 if (input.empty()) {
29 return true;
30 }
31
32
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 40 times.
 152 for (size_t i = 0; i < input.size(); ++i) {
33
2/2
✓ Branch 0 taken 360 times.
✓ Branch 1 taken 112 times.
 472 for (size_t j = 0; j < input[0].size(); ++j) {
34
3/4
✓ Branch 0 taken 224 times.
✓ Branch 1 taken 136 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 224 times.
 360 if (input[i][j] != 1 && input[i][j] != 0) {
35 return false;
36 }
37 }
38 }
39
40 size_t length_row = input[0].size();
41 return std::ranges::all_of(input, [length_row](const auto &row) { return row.size() == length_row; });
42 }
43
44
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 bool ChyokotovConvexHullFindingSEQ::PreProcessingImpl() {
45 GetOutput().clear();
46 48 return true;
47 }
48
49 80 std::vector<std::pair<int, int>> ChyokotovConvexHullFindingSEQ::Bfs(int start_x, int start_y,
50 const std::vector<std::vector<int>> &picture,
51 std::vector<std::vector<bool>> &visited) {
52
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 std::vector<std::pair<int, int>> component;
53 std::queue<std::pair<int, int>> queue;
54
55
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 const std::array<std::pair<int, int>, 4> directions = {{{0, -1}, {0, 1}, {-1, 0}, {1, 0}}};
56
57 queue.emplace(start_x, start_y);
58
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 80 times.
 80 visited[start_y][start_x] = true;
59
60
2/2
✓ Branch 0 taken 136 times.
✓ Branch 1 taken 80 times.
 216 while (!queue.empty()) {
61 auto [current_x, current_y] = queue.front();
62 queue.pop();
63
64
1/2
✓ Branch 1 taken 136 times.
✗ Branch 2 not taken.
 136 component.emplace_back(current_x, current_y);
65
66
2/2
✓ Branch 0 taken 544 times.
✓ Branch 1 taken 136 times.
 680 for (const auto &[dx, dy] : directions) {
67 544 int neighbor_x = current_x + dx;
68 544 int neighbor_y = current_y + dy;
69
70
6/6
✓ Branch 0 taken 504 times.
✓ Branch 1 taken 40 times.
✓ Branch 2 taken 464 times.
✓ Branch 3 taken 40 times.
✓ Branch 4 taken 432 times.
✓ Branch 5 taken 32 times.
 544 if (neighbor_x >= 0 && std::cmp_less(neighbor_x, static_cast<int>(picture[0].size())) && neighbor_y >= 0 &&
71
2/2
✓ Branch 0 taken 392 times.
✓ Branch 1 taken 40 times.
 432 std::cmp_less(neighbor_y, static_cast<int>(picture.size()))) {
72
4/4
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 248 times.
✓ Branch 2 taken 56 times.
✓ Branch 3 taken 88 times.
 392 if (picture[neighbor_y][neighbor_x] == 1 && !visited[neighbor_y][neighbor_x]) {
73 visited[neighbor_y][neighbor_x] = true;
74 queue.emplace(neighbor_x, neighbor_y);
75 }
76 }
77 }
78 }
79
80 80 return component;
81 }
82
83 40 std::vector<std::vector<std::pair<int, int>>> ChyokotovConvexHullFindingSEQ::FindComponent() {
84 40 auto picture = GetInput();
85 40 int rows = static_cast<int>(picture.size());
86 40 int cols = static_cast<int>(picture[0].size());
87
88 40 std::vector<std::vector<std::pair<int, int>>> components;
89
2/4
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 40 times.
✗ Branch 5 not taken.
 40 std::vector<std::vector<bool>> visited(rows, std::vector<bool>(cols, false));
90
91
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 40 times.
 152 for (int row_idx = 0; row_idx < rows; ++row_idx) {
92
2/2
✓ Branch 0 taken 360 times.
✓ Branch 1 taken 112 times.
 472 for (int col_idx = 0; col_idx < cols; ++col_idx) {
93
4/4
✓ Branch 0 taken 136 times.
✓ Branch 1 taken 224 times.
✓ Branch 2 taken 80 times.
✓ Branch 3 taken 56 times.
 360 if (picture[row_idx][col_idx] == 1 && !visited[row_idx][col_idx]) {
94
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 auto component = Bfs(col_idx, row_idx, picture, visited);
95
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 components.emplace_back(std::move(component));
96 }
97 }
98 }
99
100 40 return components;
101 40 }
102
103 ✗ int ChyokotovConvexHullFindingSEQ::Cross(const std::pair<int, int> &o, const std::pair<int, int> &a,
104 const std::pair<int, int> &b) {
105
4/4
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 16 times.
✓ Branch 2 taken 16 times.
✓ Branch 3 taken 16 times.
 64 return ((a.first - o.first) * (b.second - o.second)) - ((a.second - o.second) * (b.first - o.first));
106 }
107
108
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 16 times.
 80 std::vector<std::pair<int, int>> ChyokotovConvexHullFindingSEQ::ConvexHull(std::vector<std::pair<int, int>> x) {
109 80 int n = static_cast<int>(x.size());
110
111
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 16 times.
 80 if (n <= 2) {
112 return x;
113 }
114
115 16 std::ranges::sort(x.begin(), x.end());
116
117 16 std::vector<std::pair<int, int>> hull(2 * static_cast<size_t>(n));
118 int k = 0;
119
120
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 16 times.
 80 for (int i = 0; i < n; i++) {
121
4/4
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 48 times.
✓ Branch 2 taken 16 times.
✓ Branch 3 taken 16 times.
 80 while (k >= 2 && Cross(hull[k - 2], hull[k - 1], x[i]) <= 0) {
122 k--;
123 }
124 64 hull[k++] = x[i];
125 }
126
127
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 16 times.
 64 for (int i = n - 2, tk = k + 1; i >= 0; i--) {
128
4/4
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 32 times.
✓ Branch 2 taken 16 times.
✓ Branch 3 taken 16 times.
 64 while (k >= tk && Cross(hull[k - 2], hull[k - 1], x[i]) <= 0) {
129 k--;
130 }
131 48 hull[k++] = x[i];
132 }
133
134
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 hull.resize(k - 1);
135 return hull;
136 }
137
138
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 8 times.
 48 bool ChyokotovConvexHullFindingSEQ::RunImpl() {
139 auto &picture = GetInput();
140
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 8 times.
 48 if (picture.empty()) {
141 return true;
142 }
143 auto &output = GetOutput();
144 40 auto components = FindComponent();
145
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 40 times.
 120 for (auto &i : components) {
146
2/4
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 80 times.
✗ Branch 5 not taken.
 160 output.push_back(ConvexHull(i));
147 }
148
149 return true;
150 40 }
151
152 48 bool ChyokotovConvexHullFindingSEQ::PostProcessingImpl() {
153 48 return true;
154 }
155
156 } // namespace chyokotov_a_convex_hull_finding
157