GCC Code Coverage Report

Line	Branch	Exec	Source
1			#include "artyushkina_markirovka/all/include/ops_all.hpp"
2
3			#include <algorithm>
4			#include <cstddef>
5			#include <vector>
6
7			#include "artyushkina_markirovka/common/include/common.hpp"
8
9			namespace artyushkina_markirovka {
10
11			struct NeighborOffsetAll {
12			int di;
13			int dj;
14			int check_i_min;
15			int check_i_max;
16			int check_j_min;
17			int check_j_max;
18			};
19
20			namespace {
21
22			struct NeighborInfo {
23			int ni;
24			int nj;
25			int label;
26			};
27
28		✗	std::vector<NeighborOffsetAll> GetFirstPassNeighbors() {
29		✗	std::vector<NeighborOffsetAll> neighbors(4);
30		✗	neighbors[0] = {.di = -1, .dj = -1, .check_i_min = 1, .check_i_max = 0, .check_j_min = 1, .check_j_max = 0};
31		✗	neighbors[1] = {.di = -1, .dj = 0, .check_i_min = 1, .check_i_max = 0, .check_j_min = 0, .check_j_max = 0};
32		✗	neighbors[2] = {.di = -1, .dj = 1, .check_i_min = 1, .check_i_max = 0, .check_j_min = 0, .check_j_max = 1};
33		✗	neighbors[3] = {.di = 0, .dj = -1, .check_i_min = 0, .check_i_max = 0, .check_j_min = 1, .check_j_max = 0};
34		✗	return neighbors;
35			}
36
37			bool IsValidNeighborOffset(int i, int j, int rows, int cols, const NeighborOffsetAll &offset) {
38		✗	if (offset.check_i_min == 1 && i <= 0) {
39			return false;
40			}
41		✗	if (offset.check_i_max == 1 && i >= rows - 1) {
42			return false;
43			}
44		✗	if (offset.check_j_min == 1 && j <= 0) {
45			return false;
46			}
47		✗	if (offset.check_j_max == 1 && j >= cols - 1) {
48			return false;
49			}
50			return true;
51			}
52
53		✗	NeighborInfo GetNeighborInfo(int i, int j, int rows, int cols, const std::vector<std::vector<int>> &labels,
54			const NeighborOffsetAll &offset) {
55			NeighborInfo info = {.ni = -1, .nj = -1, .label = 0};
56			if (!IsValidNeighborOffset(i, j, rows, cols, offset)) {
57		✗	return info;
58			}
59		✗	info.ni = i + offset.di;
60		✗	info.nj = j + offset.dj;
61		✗	info.label = labels[static_cast<size_t>(info.ni)][static_cast<size_t>(info.nj)];
62		✗	return info;
63			}
64
65		✗	void FindMinLabelFromNeighbors(int i, int j, int rows, int cols, const std::vector<std::vector<int>> &labels,
66			const std::vector<NeighborOffsetAll> &neighbors, int &min_label, bool &has_neighbors) {
67		✗	for (const auto &offset : neighbors) {
68		✗	NeighborInfo info = GetNeighborInfo(i, j, rows, cols, labels, offset);
69		✗	if (info.label != 0) {
70		✗	has_neighbors = true;
71		✗	min_label = (std::min)(info.label, min_label);
72			}
73			}
74		✗	}
75
76		✗	void UnionNeighborLabels(int i, int j, int rows, int cols, std::vector<std::vector<int>> &labels,
77			std::vector<int> &equivalent_labels, const std::vector<NeighborOffsetAll> &neighbors,
78			int min_label) {
79		✗	for (const auto &offset : neighbors) {
80		✗	NeighborInfo info = GetNeighborInfo(i, j, rows, cols, labels, offset);
81		✗	if (info.label != 0 && info.label != min_label) {
82		✗	MarkingComponentsALL::UnionLabels(equivalent_labels, info.label, min_label);
83			}
84			}
85		✗	}
86
87		✗	void AssignNewLabel(int i, int j, int &next_label, std::vector<std::vector<int>> &labels,
88			std::vector<int> &equivalent_labels) {
89		✗	labels[static_cast<size_t>(i)][static_cast<size_t>(j)] = next_label;
90			equivalent_labels.push_back(next_label);
91		✗	++next_label;
92		✗	}
93
94			void AssignExistingLabel(int i, int j, int min_label, std::vector<std::vector<int>> &labels) {
95		✗	labels[static_cast<size_t>(i)][static_cast<size_t>(j)] = min_label;
96			}
97
98			} // namespace
99
100		✗	MarkingComponentsALL::MarkingComponentsALL(const InType &in) {
101			SetTypeOfTask(GetStaticTypeOfTask());
102		✗	GetInput() = in;
103		✗	GetOutput() = OutType();
104		✗	}
105
106		✗	bool MarkingComponentsALL::ValidationImpl() {
107		✗	return GetInput().size() >= 2;
108			}
109
110		✗	bool MarkingComponentsALL::PreProcessingImpl() {
111			const auto &input = GetInput();
112		✗	rows_ = static_cast<int>(input[0]);
113		✗	cols_ = static_cast<int>(input[1]);
114
115			labels_.clear();
116		✗	labels_.resize(static_cast<size_t>(rows_));
117		✗	for (int i = 0; i < rows_; ++i) {
118		✗	labels_[static_cast<size_t>(i)].resize(static_cast<size_t>(cols_), 0);
119			}
120
121			equivalent_labels_.clear();
122		✗	equivalent_labels_.push_back(0);
123
124		✗	return true;
125			}
126
127		✗	int MarkingComponentsALL::FindRoot(std::vector<int> &parent, int label) {
128			int root = label;
129		✗	while (parent[static_cast<size_t>(root)] != root) {
130			root = parent[static_cast<size_t>(root)];
131			}
132			int current = label;
133		✗	while (current != root) {
134		✗	int next = parent[static_cast<size_t>(current)];
135		✗	parent[static_cast<size_t>(current)] = root;
136			current = next;
137			}
138		✗	return root;
139			}
140
141		✗	void MarkingComponentsALL::UnionLabels(std::vector<int> &parent, int label1, int label2) {
142			int root1 = FindRoot(parent, label1);
143			int root2 = FindRoot(parent, label2);
144		✗	if (root1 != root2) {
145		✗	if (root1 < root2) {
146		✗	parent[static_cast<size_t>(root2)] = root1;
147			} else {
148		✗	parent[static_cast<size_t>(root1)] = root2;
149			}
150			}
151		✗	}
152
153		✗	void MarkingComponentsALL::FirstPass() {
154			const auto &input = GetInput();
155		✗	int next_label = 1;
156		✗	auto neighbors = GetFirstPassNeighbors();
157
158		✗	for (int i = 0; i < rows_; ++i) {
159		✗	for (int j = 0; j < cols_; ++j) {
160		✗	size_t idx = (static_cast<size_t>(i) * static_cast<size_t>(cols_)) + static_cast<size_t>(j) + 2;
161
162		✗	if (input[idx] == 255) {
163		✗	continue;
164			}
165
166		✗	int min_label = next_label;
167		✗	bool has_neighbors = false;
168		✗	FindMinLabelFromNeighbors(i, j, rows_, cols_, labels_, neighbors, min_label, has_neighbors);
169
170		✗	if (!has_neighbors) {
171		✗	AssignNewLabel(i, j, next_label, labels_, equivalent_labels_);
172			} else {
173		✗	AssignExistingLabel(i, j, min_label, labels_);
174		✗	UnionNeighborLabels(i, j, rows_, cols_, labels_, equivalent_labels_, neighbors, min_label);
175			}
176			}
177			}
178		✗	}
179
180		✗	void MarkingComponentsALL::SecondPass() {
181		✗	int label_count = static_cast<int>(equivalent_labels_.size());
182
183		✗	for (int i = 0; i < rows_; ++i) {
184		✗	for (int j = 0; j < cols_; ++j) {
185		✗	if (labels_[static_cast<size_t>(i)][static_cast<size_t>(j)] != 0) {
186		✗	labels_[static_cast<size_t>(i)][static_cast<size_t>(j)] =
187			FindRoot(equivalent_labels_, labels_[static_cast<size_t>(i)][static_cast<size_t>(j)]);
188			}
189			}
190			}
191
192		✗	std::vector<int> remap(static_cast<size_t>(label_count), 0);
193			int current_label = 1;
194		✗	for (int i = 1; i < label_count; ++i) {
195		✗	if (equivalent_labels_[static_cast<size_t>(i)] == i) {
196		✗	remap[static_cast<size_t>(i)] = current_label;
197		✗	++current_label;
198			}
199			}
200
201		✗	for (int i = 0; i < rows_; ++i) {
202		✗	for (int j = 0; j < cols_; ++j) {
203		✗	if (labels_[static_cast<size_t>(i)][static_cast<size_t>(j)] != 0) {
204		✗	labels_[static_cast<size_t>(i)][static_cast<size_t>(j)] =
205		✗	remap[static_cast<size_t>(labels_[static_cast<size_t>(i)][static_cast<size_t>(j)])];
206			}
207			}
208			}
209		✗	}
210
211		✗	bool MarkingComponentsALL::RunImpl() {
212			const auto &input = GetInput();
213		✗	if (input.size() < 2 || rows_ == 0 || cols_ == 0) {
214			return false;
215			}
216		✗	FirstPass();
217		✗	SecondPass();
218		✗	return true;
219			}
220
221		✗	bool MarkingComponentsALL::PostProcessingImpl() {
222			OutType &output = GetOutput();
223			output.clear();
224		✗	output.reserve((static_cast<size_t>(rows_) * static_cast<size_t>(cols_)) + 2);
225		✗	output.push_back(rows_);
226		✗	output.push_back(cols_);
227		✗	for (int i = 0; i < rows_; ++i) {
228		✗	for (int j = 0; j < cols_; ++j) {
229		✗	output.push_back(labels_[static_cast<size_t>(i)][static_cast<size_t>(j)]);
230			}
231			}
232		✗	return true;
233			}
234
235			} // namespace artyushkina_markirovka
236