GCC Code Coverage Report

Directory: ./
File: tasks/artyushkina_markirovka/seq/src/ops_seq.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 51 54 94.4%
Functions: 8 10 80.0%
Branches: 57 70 81.4%
Line Branch Exec Source
1 #include "artyushkina_markirovka/seq/include/ops_seq.hpp"
2
3 #include <array>
4 #include <cstddef>
5 #include <queue>
6 #include <utility>
7
8 #include "artyushkina_markirovka/common/include/common.hpp"
9
10 namespace artyushkina_markirovka {
11
12 struct NeighborOffset {
13 int di;
14 int dj;
15 bool check_i_min;
16 bool check_i_max;
17 bool check_j_min;
18 bool check_j_max;
19 };
20
21 const std::array<NeighborOffset, 8> kNeighbors = {
22 {NeighborOffset{
23 .di = -1, .dj = -1, .check_i_min = true, .check_i_max = false, .check_j_min = true, .check_j_max = false},
24 NeighborOffset{
25 .di = -1, .dj = 0, .check_i_min = true, .check_i_max = false, .check_j_min = false, .check_j_max = false},
26 NeighborOffset{
27 .di = -1, .dj = 1, .check_i_min = true, .check_i_max = false, .check_j_min = false, .check_j_max = true},
28 NeighborOffset{
29 .di = 0, .dj = -1, .check_i_min = false, .check_i_max = false, .check_j_min = true, .check_j_max = false},
30 NeighborOffset{
31 .di = 0, .dj = 1, .check_i_min = false, .check_i_max = false, .check_j_min = false, .check_j_max = true},
32 NeighborOffset{
33 .di = 1, .dj = -1, .check_i_min = false, .check_i_max = true, .check_j_min = true, .check_j_max = false},
34 NeighborOffset{
35 .di = 1, .dj = 0, .check_i_min = false, .check_i_max = true, .check_j_min = false, .check_j_max = false},
36 NeighborOffset{
37 .di = 1, .dj = 1, .check_i_min = false, .check_i_max = true, .check_j_min = false, .check_j_max = true}}};
38
39
1/2
✓ Branch 1 taken 44 times.
✗ Branch 2 not taken.
 44 MarkingComponentsSEQ::MarkingComponentsSEQ(const InType &in) {
40 SetTypeOfTask(GetStaticTypeOfTask());
41
1/2
✓ Branch 1 taken 44 times.
✗ Branch 2 not taken.
 44 GetInput() = in;
42 44 GetOutput() = OutType();
43 44 }
44
45 44 bool MarkingComponentsSEQ::ValidationImpl() {
46 44 return GetInput().size() >= 2;
47 }
48
49
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 44 times.
 44 bool MarkingComponentsSEQ::PreProcessingImpl() {
50 const auto &input = GetInput();
51 44 rows_ = input[0];
52
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 44 times.
 44 cols_ = input[1];
53
54 labels_.clear();
55 44 labels_.reserve(rows_);
56
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 44 times.
 156 for (int i = 0; i < rows_; ++i) {
57 112 labels_.emplace_back(cols_, 0);
58 }
59
60 equivalent_labels_.clear();
61 44 equivalent_labels_.push_back(0);
62
63 44 return true;
64 }
65
66 ✗ int MarkingComponentsSEQ::FindRoot(int /*label*/) {
67 ✗ return 0;
68 }
69
70 ✗ void MarkingComponentsSEQ::UnionLabels(int /*label1*/, int /*label2*/) {}
71
72 1536 bool MarkingComponentsSEQ::IsValidNeighbor(int i, int j, const NeighborOffset &offset) const {
73
4/4
✓ Branch 0 taken 576 times.
✓ Branch 1 taken 960 times.
✓ Branch 2 taken 300 times.
✓ Branch 3 taken 276 times.
 1536 if (offset.check_i_min && i <= 0) {
74 return false;
75 }
76
4/4
✓ Branch 0 taken 576 times.
✓ Branch 1 taken 684 times.
✓ Branch 2 taken 348 times.
✓ Branch 3 taken 228 times.
 1260 if (offset.check_i_max && i >= rows_ - 1) {
77 return false;
78 }
79
4/4
✓ Branch 0 taken 408 times.
✓ Branch 1 taken 624 times.
✓ Branch 2 taken 240 times.
✓ Branch 3 taken 168 times.
 1032 if (offset.check_j_min && j <= 0) {
80 return false;
81 }
82
4/4
✓ Branch 0 taken 408 times.
✓ Branch 1 taken 456 times.
✓ Branch 2 taken 128 times.
✓ Branch 3 taken 280 times.
 864 if (offset.check_j_max && j >= cols_ - 1) {
83 128 return false;
84 }
85 return true;
86 }
87
88 1536 void MarkingComponentsSEQ::ProcessNeighbor(int i, int j, const NeighborOffset &offset, int label,
89 std::queue<std::pair<int, int>> &q) {
90
2/2
✓ Branch 0 taken 800 times.
✓ Branch 1 taken 736 times.
 1536 if (!IsValidNeighbor(i, j, offset)) {
91 800 return;
92 }
93
94 736 int ni = i + offset.di;
95 736 int nj = j + offset.dj;
96
97 const auto &input = GetInput();
98
2/2
✓ Branch 0 taken 424 times.
✓ Branch 1 taken 312 times.
 736 std::size_t idx = (static_cast<std::size_t>(ni) * static_cast<std::size_t>(cols_)) + static_cast<std::size_t>(nj) + 2;
99
100
4/4
✓ Branch 0 taken 424 times.
✓ Branch 1 taken 312 times.
✓ Branch 2 taken 142 times.
✓ Branch 3 taken 282 times.
 736 if (input[idx] == 0 && labels_[ni][nj] == 0) {
101 142 labels_[ni][nj] = label;
102 q.emplace(ni, nj);
103 }
104 }
105
106 50 void MarkingComponentsSEQ::BFS(int start_i, int start_j, int label) {
107 std::queue<std::pair<int, int>> q;
108 q.emplace(start_i, start_j);
109 50 labels_[start_i][start_j] = label;
110
111
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 50 times.
 242 while (!q.empty()) {
112 auto [i, j] = q.front();
113 q.pop();
114
115
2/2
✓ Branch 0 taken 1536 times.
✓ Branch 1 taken 192 times.
 1728 for (const auto &offset : kNeighbors) {
116
1/2
✓ Branch 1 taken 1536 times.
✗ Branch 2 not taken.
 1536 ProcessNeighbor(i, j, offset, label, q);
117 }
118 }
119 50 }
120
121
1/2
✓ Branch 0 taken 44 times.
✗ Branch 1 not taken.
 44 bool MarkingComponentsSEQ::RunImpl() {
122 const auto &input = GetInput();
123
3/6
✓ Branch 0 taken 44 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 44 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 44 times.
✗ Branch 5 not taken.
 44 if (input.size() < 2 || rows_ == 0 || cols_ == 0) {
124 return false;
125 }
126
127 int current_label = 1;
128
129
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 44 times.
 156 for (int i = 0; i < rows_; ++i) {
130
2/2
✓ Branch 0 taken 340 times.
✓ Branch 1 taken 112 times.
 452 for (int j = 0; j < cols_; ++j) {
131 340 std::size_t idx =
132
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 148 times.
 340 (static_cast<std::size_t>(i) * static_cast<std::size_t>(cols_)) + static_cast<std::size_t>(j) + 2;
133
134
4/4
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 148 times.
✓ Branch 2 taken 50 times.
✓ Branch 3 taken 142 times.
 340 if (input[idx] == 0 && labels_[i][j] == 0) {
135 50 BFS(i, j, current_label);
136 50 ++current_label;
137 }
138 }
139 }
140
141 return true;
142 }
143
144
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 44 times.
 44 bool MarkingComponentsSEQ::PostProcessingImpl() {
145 OutType &output = GetOutput();
146 output.clear();
147
148 44 output.reserve((static_cast<std::size_t>(rows_) * static_cast<std::size_t>(cols_)) + 2);
149
150
1/2
✓ Branch 0 taken 44 times.
✗ Branch 1 not taken.
 44 output.push_back(rows_);
151
1/2
✓ Branch 0 taken 44 times.
✗ Branch 1 not taken.
 44 output.push_back(cols_);
152
153
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 44 times.
 156 for (int i = 0; i < rows_; ++i) {
154
2/2
✓ Branch 0 taken 340 times.
✓ Branch 1 taken 112 times.
 452 for (int j = 0; j < cols_; ++j) {
155
1/2
✓ Branch 0 taken 340 times.
✗ Branch 1 not taken.
 340 output.push_back(labels_[i][j]);
156 }
157 }
158
159 44 return true;
160 }
161
162 } // namespace artyushkina_markirovka
163