GCC Code Coverage Report

Directory: ./
File: tasks/ivanova_p_marking_components_on_binary_image/stl/src/ops_stl.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 135 156 86.5%
Functions: 13 23 56.5%
Branches: 113 162 69.8%
Line Branch Exec Source
1 #include "ivanova_p_marking_components_on_binary_image/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <string>
6 #include <thread>
7 #include <vector>
8
9 #include "ivanova_p_marking_components_on_binary_image/common/include/common.hpp"
10 #include "ivanova_p_marking_components_on_binary_image/data/image_generator.hpp"
11 #include "util/include/util.hpp"
12
13 namespace ivanova_p_marking_components_on_binary_image {
14
15 114 IvanovaPMarkingComponentsOnBinaryImageSTL::IvanovaPMarkingComponentsOnBinaryImageSTL(const InType &in) {
16 SetTypeOfTask(GetStaticTypeOfTask());
17 114 GetInput() = in;
18 114 GetOutput() = OutType();
19
20 114 test_image.width = 0;
21
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 10 times.
 114 test_image.height = 0;
22 test_image.data.clear();
23 114 }
24
25 114 bool IvanovaPMarkingComponentsOnBinaryImageSTL::ValidationImpl() {
26
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 114 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 114 if (test_image.width <= 0 || test_image.height <= 0) {
27 114 int test_case = GetInput();
28
29
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 82 times.
 114 if (test_case >= 11 && test_case <= 14) {
30 std::string filename;
31
4/4
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 8 times.
✓ Branch 3 taken 8 times.
 32 switch (test_case) {
32 case 11:
33 filename = "tasks/ivanova_p_marking_components_on_binary_image/data/image.txt";
34 break;
35 case 12:
36 filename = "tasks/ivanova_p_marking_components_on_binary_image/data/image2.txt";
37 break;
38 case 13:
39 filename = "tasks/ivanova_p_marking_components_on_binary_image/data/image3.txt";
40 break;
41 case 14:
42 filename = "tasks/ivanova_p_marking_components_on_binary_image/data/image4.txt";
43 break;
44 default:
45 filename = "";
46 break;
47 }
48
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 64 test_image = LoadImageFromTxt(filename);
49 } else {
50 int size = ExtractImageSize(test_case);
51 164 test_image = CreateTestImage(size, size, test_case);
52 }
53 }
54
55
3/6
✓ Branch 0 taken 114 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 114 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 114 times.
✗ Branch 5 not taken.
 114 if (test_image.width <= 0 || test_image.height <= 0 || test_image.data.empty()) {
56 return false;
57 }
58
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 114 times.
 114 if (test_image.data.size() != static_cast<size_t>(test_image.width) * static_cast<size_t>(test_image.height)) {
59 ✗ return false;
60 }
61 return true;
62 }
63
64 114 bool IvanovaPMarkingComponentsOnBinaryImageSTL::PreProcessingImpl() {
65
2/4
✓ Branch 0 taken 114 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 114 times.
 114 if (test_image.width <= 0 || test_image.height <= 0) {
66 ✗ int test_case = GetInput();
67
68 ✗ if (test_case >= 11 && test_case <= 14) {
69 std::string filename;
70 ✗ switch (test_case) {
71 case 11:
72 filename = "tasks/ivanova_p_marking_components_on_binary_image/data/image.txt";
73 break;
74 case 12:
75 filename = "tasks/ivanova_p_marking_components_on_binary_image/data/image2.txt";
76 break;
77 case 13:
78 filename = "tasks/ivanova_p_marking_components_on_binary_image/data/image3.txt";
79 break;
80 case 14:
81 filename = "tasks/ivanova_p_marking_components_on_binary_image/data/image4.txt";
82 break;
83 default:
84 filename = "";
85 break;
86 }
87 ✗ test_image = LoadImageFromTxt(filename);
88 } else {
89 int size = ExtractImageSize(test_case);
90 ✗ test_image = CreateTestImage(size, size, test_case);
91 }
92 }
93
94 input_image_ = test_image;
95 114 width_ = input_image_.width;
96 114 height_ = input_image_.height;
97
98 114 int total_pixels = width_ * height_;
99 114 labels_.assign(total_pixels, 0);
100
101 // Инициализация глобального вектора DSU
102 114 int num_threads = ppc::util::GetNumThreads();
103 114 parent_.resize((static_cast<size_t>(num_threads) * static_cast<size_t>(total_pixels)) + 1);
104
2/2
✓ Branch 0 taken 2042934 times.
✓ Branch 1 taken 114 times.
 2043048 for (size_t i = 0; i < parent_.size(); ++i) {
105 2042934 parent_[i] = static_cast<int>(i);
106 }
107
108 114 current_label_ = 0;
109 114 return true;
110 }
111
112 ✗ int IvanovaPMarkingComponentsOnBinaryImageSTL::FindRoot(int label) {
113 int root = label;
114
6/8
✓ Branch 0 taken 16842 times.
✓ Branch 1 taken 59104 times.
✓ Branch 2 taken 130 times.
✓ Branch 3 taken 1170 times.
✓ Branch 4 taken 1080 times.
✓ Branch 5 taken 1170 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 79496 while (parent_[root] != root) {
115 root = parent_[root];
116 }
117
118 int current = label;
119
4/8
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 59104 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1170 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 1170 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 61446 while (parent_[current] != root) {
120 int next = parent_[current];
121 2 parent_[current] = root;
122 current = next;
123 }
124 ✗ return root;
125 }
126
127 1170 void IvanovaPMarkingComponentsOnBinaryImageSTL::UnionLabels(int label1, int label2) {
128 int root1 = FindRoot(label1);
129 int root2 = FindRoot(label2);
130
131
2/2
✓ Branch 0 taken 92 times.
✓ Branch 1 taken 1078 times.
 1170 if (root1 != root2) {
132
2/2
✓ Branch 0 taken 84 times.
✓ Branch 1 taken 8 times.
 92 if (root1 < root2) {
133 84 parent_[root2] = root1;
134 } else {
135 8 parent_[root1] = root2;
136 }
137 }
138 1170 }
139
140 ✗ void IvanovaPMarkingComponentsOnBinaryImageSTL::ProcessPixel(int /*xx*/, int /*yy*/, int /*idx*/) {}
141
142 ✗ int IvanovaPMarkingComponentsOnBinaryImageSTL::FindLocalRootStl(int label, const std::vector<int> &local_parent) {
143 int root = label;
144
3/10
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
✓ Branch 2 taken 24 times.
✓ Branch 3 taken 32 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
 56 while (local_parent[root] != root) {
145 root = local_parent[root];
146 }
147 ✗ return root;
148 }
149
150 ✗ void IvanovaPMarkingComponentsOnBinaryImageSTL::UnionLocalLabelsStl(int label1, int label2,
151 std::vector<int> &local_parent) {
152 int root1 = FindLocalRootStl(label1, local_parent);
153 int root2 = FindLocalRootStl(label2, local_parent);
154
2/4
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 32 if (root1 != root2) {
155
1/4
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 8 if (root1 < root2) {
156 8 local_parent[root2] = root1;
157 } else {
158 ✗ local_parent[root1] = root2;
159 }
160 }
161 ✗ }
162
163 821128 void IvanovaPMarkingComponentsOnBinaryImageSTL::ProcessStripePixelStl(int xx, int yy, int idx, int start_row,
164 std::vector<int> &local_parent,
165 int &local_label) {
166
2/2
✓ Branch 0 taken 59104 times.
✓ Branch 1 taken 762024 times.
 821128 if (input_image_.data[idx] == 0) {
167 return;
168 }
169
170
2/2
✓ Branch 0 taken 59016 times.
✓ Branch 1 taken 88 times.
 59104 int left_label = (xx > 0) ? labels_[idx - 1] : 0;
171
2/2
✓ Branch 0 taken 57334 times.
✓ Branch 1 taken 1770 times.
 59104 int top_label = (yy > start_row) ? labels_[idx - width_] : 0;
172
173 59104 bool left_exists = (left_label != 0);
174 59104 bool top_exists = (top_label != 0);
175
176
2/2
✓ Branch 0 taken 388 times.
✓ Branch 1 taken 58716 times.
 59104 if (!left_exists && !top_exists) {
177 388 local_label++;
178 388 labels_[idx] = local_label;
179 } else {
180
2/2
✓ Branch 0 taken 3716 times.
✓ Branch 1 taken 55000 times.
 58716 int label = left_exists ? left_label : top_label;
181 58716 labels_[idx] = label;
182
183
4/4
✓ Branch 0 taken 50602 times.
✓ Branch 1 taken 8114 times.
✓ Branch 2 taken 32 times.
✓ Branch 3 taken 50570 times.
 58716 if (left_exists && top_exists && left_label != top_label) {
184 UnionLocalLabelsStl(left_label, top_label, local_parent);
185 }
186 }
187 }
188
189 ✗ void IvanovaPMarkingComponentsOnBinaryImageSTL::InitializeLocalParentStl(std::vector<int> &local_parent,
190 int max_labels) {
191 278 local_parent.resize(static_cast<size_t>(max_labels));
192
2/4
✓ Branch 0 taken 6088154 times.
✓ Branch 1 taken 278 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 6088432 for (int i = 0; i < max_labels; ++i) {
193 6088154 local_parent[static_cast<size_t>(i)] = i;
194 }
195 ✗ }
196
197 278 void IvanovaPMarkingComponentsOnBinaryImageSTL::ProcessStripeStl(int start_row, int end_row,
198 std::vector<int> &local_parent, int &local_label) {
199
2/2
✓ Branch 0 taken 8384 times.
✓ Branch 1 taken 278 times.
 8662 for (int yy = start_row; yy < end_row; ++yy) {
200
2/2
✓ Branch 0 taken 821128 times.
✓ Branch 1 taken 8384 times.
 829512 for (int xx = 0; xx < width_; ++xx) {
201 821128 int idx = (yy * width_) + xx;
202 821128 ProcessStripePixelStl(xx, yy, idx, start_row, local_parent, local_label);
203 }
204 }
205 278 }
206
207 114 void IvanovaPMarkingComponentsOnBinaryImageSTL::MergeBoundariesStl(int num_threads, int rows_per_thread) {
208
2/2
✓ Branch 0 taken 170 times.
✓ Branch 1 taken 114 times.
 284 for (int thread_id = 0; thread_id < num_threads - 1; ++thread_id) {
209 170 int boundary_row = (thread_id + 1) * rows_per_thread;
210
2/2
✓ Branch 0 taken 164 times.
✓ Branch 1 taken 6 times.
 170 if (boundary_row >= height_) {
211 6 continue;
212 }
213
214
2/2
✓ Branch 0 taken 12446 times.
✓ Branch 1 taken 164 times.
 12610 for (int xx = 0; xx < width_; ++xx) {
215 12446 int top_idx = ((boundary_row - 1) * width_) + xx;
216 12446 int bottom_idx = (boundary_row * width_) + xx;
217
218
2/2
✓ Branch 0 taken 1162 times.
✓ Branch 1 taken 11284 times.
 12446 int top_label = labels_[top_idx];
219 12446 int bottom_label = labels_[bottom_idx];
220
221
3/4
✓ Branch 0 taken 1162 times.
✓ Branch 1 taken 11284 times.
✓ Branch 2 taken 1162 times.
✗ Branch 3 not taken.
 12446 if (top_label != 0 && bottom_label != 0 && top_label != bottom_label) {
222 1162 UnionLabels(top_label, bottom_label);
223 }
224 }
225 }
226 114 }
227
228 114 void IvanovaPMarkingComponentsOnBinaryImageSTL::MergeLocalParentsStl(const std::vector<std::vector<int>> &local_parents,
229 const std::vector<int> &local_labels,
230 int num_threads, int total_pixels) {
231
2/2
✓ Branch 0 taken 284 times.
✓ Branch 1 taken 114 times.
 398 for (int thread_id = 0; thread_id < num_threads; ++thread_id) {
232
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 278 times.
 284 if (local_parents[static_cast<size_t>(thread_id)].empty()) {
233 6 continue;
234 }
235
236 278 int start_lbl = (thread_id * total_pixels) + 1;
237 278 int end_lbl = local_labels[static_cast<size_t>(thread_id)];
238
239
2/2
✓ Branch 0 taken 388 times.
✓ Branch 1 taken 278 times.
 666 for (int label = start_lbl; label <= end_lbl; ++label) {
240
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 380 times.
 388 int p = local_parents[static_cast<size_t>(thread_id)][static_cast<size_t>(label)];
241
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 380 times.
 388 if (p != label) {
242 8 UnionLabels(label, p);
243 }
244 }
245 }
246 114 }
247
248 114 void IvanovaPMarkingComponentsOnBinaryImageSTL::FirstPass() {
249 114 int num_threads = ppc::util::GetNumThreads();
250 114 int rows_per_thread = (height_ + num_threads - 1) / num_threads;
251 114 int total_pixels = width_ * height_;
252
253 114 std::vector<std::vector<int>> local_parents(num_threads);
254
1/2
✓ Branch 1 taken 114 times.
✗ Branch 2 not taken.
 114 std::vector<int> local_labels(num_threads, 0);
255 114 std::vector<std::thread> threads;
256
257
1/2
✓ Branch 1 taken 114 times.
✗ Branch 2 not taken.
 114 threads.reserve(static_cast<size_t>(num_threads));
258 // Фаза 1: Параллельная обработка полос через стандартные потоки
259
2/2
✓ Branch 0 taken 284 times.
✓ Branch 1 taken 114 times.
 398 for (int thread_id = 0; thread_id < num_threads; ++thread_id) {
260 284 threads.emplace_back(
261
1/2
✓ Branch 1 taken 284 times.
✗ Branch 2 not taken.
 284 [this, thread_id, rows_per_thread, &local_parents, &local_labels, num_threads, total_pixels]() {
262 284 int start_row = thread_id * rows_per_thread;
263
2/2
✓ Branch 0 taken 278 times.
✓ Branch 1 taken 6 times.
 284 int end_row = std::min(start_row + rows_per_thread, height_);
264
2/2
✓ Branch 0 taken 278 times.
✓ Branch 1 taken 6 times.
 284 if (start_row >= height_) {
265 return;
266 }
267
268 278 int max_possible_labels = (num_threads * total_pixels) + 1;
269 278 InitializeLocalParentStl(local_parents[thread_id], max_possible_labels);
270
271 278 int &local_label = local_labels[static_cast<size_t>(thread_id)];
272 278 local_label = thread_id * total_pixels;
273
274 278 ProcessStripeStl(start_row, end_row, local_parents[thread_id], local_label);
275 });
276 }
277
278
2/2
✓ Branch 0 taken 284 times.
✓ Branch 1 taken 114 times.
 398 for (auto &thread : threads) {
279
1/2
✓ Branch 1 taken 284 times.
✗ Branch 2 not taken.
 284 thread.join();
280 }
281
282 // Фаза 2: Последовательное объединение смежных границ между полосами
283 114 MergeBoundariesStl(num_threads, rows_per_thread);
284
285 // Фаза 3: Перенос локальных отношений эквивалентности в глобальный вектор
286 114 MergeLocalParentsStl(local_parents, local_labels, num_threads, total_pixels);
287
288 114 current_label_ = 0;
289
2/2
✓ Branch 0 taken 284 times.
✓ Branch 1 taken 114 times.
 398 for (int thread_id = 0; thread_id < num_threads; ++thread_id) {
290
2/2
✓ Branch 0 taken 250 times.
✓ Branch 1 taken 34 times.
 534 current_label_ = std::max(current_label_, local_labels[static_cast<size_t>(thread_id)]);
291 }
292 228 }
293
294 112 void IvanovaPMarkingComponentsOnBinaryImageSTL::SecondPass() {
295 112 int num_threads = ppc::util::GetNumThreads();
296 112 int total_pixels = width_ * height_;
297
298 // Убран локальный unordered_map, заменен плоским вектором разметки
299 112 std::vector<int> new_labels((static_cast<size_t>(num_threads) * static_cast<size_t>(total_pixels)) + 1, 0);
300 int next_label = 1;
301
302
2/2
✓ Branch 0 taken 801128 times.
✓ Branch 1 taken 112 times.
 801240 for (int &label : labels_) {
303
2/2
✓ Branch 0 taken 59104 times.
✓ Branch 1 taken 742024 times.
 801128 if (label != 0) {
304 int root = FindRoot(label);
305
306
2/2
✓ Branch 0 taken 296 times.
✓ Branch 1 taken 58808 times.
 59104 if (new_labels[static_cast<size_t>(root)] == 0) {
307 296 new_labels[static_cast<size_t>(root)] = next_label++;
308 }
309
310 59104 label = new_labels[static_cast<size_t>(root)];
311 }
312 }
313
314
1/2
✓ Branch 0 taken 112 times.
✗ Branch 1 not taken.
 112 current_label_ = next_label - 1;
315 112 }
316
317 ✗ void IvanovaPMarkingComponentsOnBinaryImageSTL::InitLabelsStl(int /*unused*/, int /*unused*/) {}
318 ✗ void IvanovaPMarkingComponentsOnBinaryImageSTL::MergeHorizontalPairsStl(int /*unused*/) {}
319 ✗ void IvanovaPMarkingComponentsOnBinaryImageSTL::MergeVerticalPairsStl(int /*unused*/) {}
320 ✗ void IvanovaPMarkingComponentsOnBinaryImageSTL::FinalizeRootsStl(int /*unused*/, int /*unused*/) {}
321 ✗ void IvanovaPMarkingComponentsOnBinaryImageSTL::NormalizeLabelsStl(int /*unused*/) {}
322
323 114 bool IvanovaPMarkingComponentsOnBinaryImageSTL::RunImpl() {
324 114 int total_pixels = width_ * height_;
325
1/2
✓ Branch 0 taken 114 times.
✗ Branch 1 not taken.
 114 if (total_pixels <= 0) {
326 return false;
327 }
328
329 114 FirstPass();
330
331
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 2 times.
 114 if (current_label_ > 0) {
332 112 SecondPass();
333 }
334
335 return true;
336 }
337
338
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 114 times.
 114 bool IvanovaPMarkingComponentsOnBinaryImageSTL::PostProcessingImpl() {
339 OutType &output = GetOutput();
340 output.clear();
341
342
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 114 times.
 114 output.push_back(width_);
343
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 114 times.
 114 output.push_back(height_);
344
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 114 times.
 114 output.push_back(current_label_);
345
346
4/4
✓ Branch 0 taken 820024 times.
✓ Branch 1 taken 1104 times.
✓ Branch 2 taken 821128 times.
✓ Branch 3 taken 114 times.
 821242 for (int label : labels_) {
347 output.push_back(label);
348 }
349
350 114 return true;
351 }
352
353 } // namespace ivanova_p_marking_components_on_binary_image
354