GCC Code Coverage Report

Line	Branch	Exec	Source
1			#include "urin_o_graham_passage/tbb/include/ops_tbb.hpp"
2
3			#include <tbb/blocked_range.h>
4			#include <tbb/concurrent_vector.h>
5			#include <tbb/parallel_for.h>
6			#include <tbb/parallel_reduce.h>
7
8			#include <algorithm>
9			#include <atomic>
10			#include <cmath>
11			#include <cstddef>
12			#include <vector>
13
14			#include "urin_o_graham_passage/common/include/common.hpp"
15
16			namespace urin_o_graham_passage {
17
18		✗	UrinOGrahamPassageTBB::UrinOGrahamPassageTBB(const InType &in) {
19			SetTypeOfTask(GetStaticTypeOfTask());
20		✗	GetInput() = in;
21		✗	GetOutput() = OutType();
22		✗	}
23
24		✗	bool UrinOGrahamPassageTBB::ValidationImpl() {
25			const auto &points = GetInput();
26
27		✗	if (points.size() < 3) {
28			return false;
29			}
30
31			const Point &first = points[0];
32		✗	for (size_t i = 1; i < points.size(); ++i) {
33			if (points[i] != first) {
34			return true;
35			}
36			}
37
38			return false;
39			}
40
41		✗	bool UrinOGrahamPassageTBB::PreProcessingImpl() {
42			GetOutput().clear();
43		✗	return true;
44			}
45
46		✗	Point UrinOGrahamPassageTBB::FindLowestPoint(const InType &points) {
47		✗	Point lowest = points[0];
48
49		✗	for (size_t i = 1; i < points.size(); ++i) {
50		✗	if (points[i].y < lowest.y - 1e-10 ||
51		✗	(std::abs(points[i].y - lowest.y) < 1e-10 && points[i].x < lowest.x - 1e-10)) {
52		✗	lowest = points[i];
53			}
54			}
55
56		✗	return lowest;
57			}
58
59		✗	Point UrinOGrahamPassageTBB::FindLowestPointParallel(const InType &points) {
60			// Используем parallel_reduce для поиска минимальной точки
61		✗	return tbb::parallel_reduce(tbb::blocked_range<size_t>(0, points.size()), points[0],
62		✗	[&points](const tbb::blocked_range<size_t> &range, Point current_min) {
63		✗	for (size_t i = range.begin(); i < range.end(); ++i) {
64		✗	if (points[i].y < current_min.y - 1e-10 ||
65		✗	(std::abs(points[i].y - current_min.y) < 1e-10 && points[i].x < current_min.x - 1e-10)) {
66		✗	current_min = points[i];
67			}
68			}
69		✗	return current_min;
70		✗	}, [](const Point &a, const Point &b) {
71		✗	if (a.y < b.y - 1e-10 || (std::abs(a.y - b.y) < 1e-10 && a.x < b.x - 1e-10)) {
72		✗	return a;
73			}
74		✗	return b;
75		✗	});
76			}
77
78		✗	double UrinOGrahamPassageTBB::PolarAngle(const Point &base, const Point &p) {
79		✗	double dx = p.x - base.x;
80		✗	double dy = p.y - base.y;
81
82		✗	if (std::abs(dx) < 1e-10 && std::abs(dy) < 1e-10) {
83			return -1e10;
84			}
85
86		✗	return std::atan2(dy, dx);
87			}
88
89		✗	int UrinOGrahamPassageTBB::Orientation(const Point &p, const Point &q, const Point &r) {
90		✗	double val = ((q.x - p.x) * (r.y - p.y)) - ((q.y - p.y) * (r.x - p.x));
91
92		✗	if (std::abs(val) < 1e-10) {
93			return 0;
94			}
95		✗	return (val > 0) ? 1 : -1;
96			}
97
98		✗	double UrinOGrahamPassageTBB::DistanceSquared(const Point &p1, const Point &p2) {
99		✗	double dx = p2.x - p1.x;
100		✗	double dy = p2.y - p1.y;
101		✗	return (dx * dx) + (dy * dy);
102			}
103
104		✗	std::vector<Point> UrinOGrahamPassageTBB::PrepareOtherPointsParallel(const InType &points, const Point &p0) {
105			// Используем concurrent_vector для потокобезопасной вставки
106			tbb::concurrent_vector<Point> other_points_concurrent;
107
108		✗	tbb::parallel_for(tbb::blocked_range<size_t>(0, points.size()),
109		✗	[&points, &p0, &other_points_concurrent](const tbb::blocked_range<size_t> &range) {
110		✗	for (size_t i = range.begin(); i < range.end(); ++i) {
111		✗	if (points[i] != p0) {
112		✗	other_points_concurrent.push_back(points[i]);
113			}
114			}
115		✗	});
116
117			// Преобразуем concurrent_vector в обычный vector для сортировки
118		✗	std::vector<Point> other_points(other_points_concurrent.begin(), other_points_concurrent.end());
119
120			// Сортировка - последовательная (остаётся доминирующей операцией)
121		✗	std::ranges::sort(other_points, [&p0](const Point &a, const Point &b) {
122		✗	double angle_a = PolarAngle(p0, a);
123		✗	double angle_b = PolarAngle(p0, b);
124
125		✗	if (std::abs(angle_a - angle_b) < 1e-10) {
126		✗	return DistanceSquared(p0, a) < DistanceSquared(p0, b);
127			}
128		✗	return angle_a < angle_b;
129			});
130
131		✗	return other_points;
132			}
133
134		✗	bool UrinOGrahamPassageTBB::AreAllCollinear(const Point &p0, const std::vector<Point> &points) {
135		✗	std::atomic<bool> all_collinear{true};
136
137		✗	tbb::parallel_for(tbb::blocked_range<size_t>(1, points.size()),
138		✗	[&points, &p0, &all_collinear](const tbb::blocked_range<size_t> &range) {
139		✗	for (size_t i = range.begin(); i < range.end() && all_collinear.load(); ++i) {
140		✗	if (Orientation(p0, points[0], points[i]) != 0) {
141		✗	all_collinear.store(false);
142			}
143			}
144		✗	});
145
146		✗	return all_collinear.load();
147			}
148
149		✗	std::vector<Point> UrinOGrahamPassageTBB::BuildConvexHull(const Point &p0, const std::vector<Point> &points) {
150		✗	std::vector<Point> hull;
151		✗	hull.reserve(points.size() + 1);
152			hull.push_back(p0);
153			hull.push_back(points[0]);
154
155			// Построение оболочки - последовательный алгоритм (зависит от предыдущих шагов)
156		✗	for (size_t i = 1; i < points.size(); ++i) {
157		✗	while (hull.size() >= 2) {
158			const Point &p = hull[hull.size() - 2];
159			const Point &q = hull.back();
160			if (Orientation(p, q, points[i]) <= 0) {
161			hull.pop_back();
162			} else {
163			break;
164			}
165			}
166			hull.push_back(points[i]);
167			}
168
169		✗	return hull;
170			}
171
172		✗	bool UrinOGrahamPassageTBB::RunImpl() {
173			const InType &points = GetInput();
174
175		✗	if (points.size() < 3) {
176			return false;
177			}
178
179			// Параллельный поиск самой нижней точки
180		✗	Point p0 = FindLowestPointParallel(points);
181
182			// Параллельная подготовка точек (исключая p0)
183		✗	std::vector<Point> other_points = PrepareOtherPointsParallel(points, p0);
184		✗	if (other_points.empty()) {
185			return false;
186			}
187
188			// Параллельная проверка на коллинеарность
189		✗	if (AreAllCollinear(p0, other_points)) {
190		✗	GetOutput() = {p0, other_points.back()};
191		✗	return true;
192			}
193
194			// Построение оболочки - последовательно
195		✗	GetOutput() = BuildConvexHull(p0, other_points);
196		✗	return true;
197			}
198
199		✗	bool UrinOGrahamPassageTBB::PostProcessingImpl() {
200		✗	return !GetOutput().empty();
201			}
202
203			} // namespace urin_o_graham_passage
204