GCC Code Coverage Report

Line	Branch	Exec	Source
1			#include "ilin_a_algorithm_graham/tbb/include/ops_tbb.hpp"
2
3			#include <tbb/blocked_range.h>
4			#include <tbb/parallel_reduce.h>
5			#include <tbb/parallel_sort.h>
6
7			#include <cmath>
8			#include <cstddef>
9			#include <utility>
10			#include <vector>
11
12			#include "ilin_a_algorithm_graham/common/include/common.hpp"
13
14			namespace ilin_a_algorithm_graham {
15
16			namespace {
17			double Orient(const Point &p, const Point &q, const Point &r) {
18		✗	return ((q.x - p.x) * (r.y - p.y)) - ((q.y - p.y) * (r.x - p.x));
19			}
20
21			double DistanceSq(const Point &p, const Point &q) {
22		✗	double dx = p.x - q.x;
23		✗	double dy = p.y - q.y;
24		✗	return (dx * dx) + (dy * dy);
25			}
26
27		✗	Point FindLowestLeftmost(const std::vector<Point> &points) {
28		✗	return tbb::parallel_reduce(tbb::blocked_range<size_t>(0, points.size()), points[0],
29		✗	[&](const tbb::blocked_range<size_t> &r, Point init) {
30		✗	for (size_t i = r.begin(); i < r.end(); ++i) {
31		✗	if (points[i].y < init.y || (points[i].y == init.y && points[i].x < init.x)) {
32		✗	init = points[i];
33			}
34			}
35			return init;
36		✗	}, [](const Point &a, const Point &b) {
37		✗	if (a.y < b.y || (a.y == b.y && a.x < b.x)) {
38		✗	return a;
39			}
40		✗	return b;
41		✗	});
42			}
43
44			class PointComparator {
45			public:
46		✗	explicit PointComparator(const Point &p0) : p0_(p0) {}
47
48		✗	bool operator()(const Point &a, const Point &b) const {
49			double o = Orient(p0_, a, b);
50		✗	if (o != 0.0) {
51		✗	return o > 0;
52			}
53		✗	return DistanceSq(p0_, a) < DistanceSq(p0_, b);
54			}
55
56			private:
57			Point p0_;
58			};
59			} // namespace
60
61		✗	IlinAGrahamTBB::IlinAGrahamTBB(const InType &in) {
62			SetTypeOfTask(GetStaticTypeOfTask());
63			GetInput() = in;
64		✗	}
65
66		✗	bool IlinAGrahamTBB::ValidationImpl() {
67		✗	return !GetInput().points.empty();
68			}
69
70		✗	bool IlinAGrahamTBB::PreProcessingImpl() {
71		✗	points_ = GetInput().points;
72			hull_.clear();
73		✗	return true;
74			}
75
76		✗	bool IlinAGrahamTBB::RunImpl() {
77		✗	if (points_.size() < 3) {
78		✗	hull_ = points_;
79		✗	return true;
80			}
81
82		✗	Point p0 = FindLowestLeftmost(points_);
83
84		✗	std::vector<Point> sorted;
85		✗	sorted.reserve(points_.size());
86		✗	for (const Point &p : points_) {
87		✗	if (p.x != p0.x || p.y != p0.y) {
88			sorted.push_back(p);
89			}
90			}
91
92		✗	tbb::parallel_sort(sorted.begin(), sorted.end(), PointComparator(p0));
93
94		✗	std::vector<Point> stack;
95		✗	stack.reserve(sorted.size() + 1);
96			stack.push_back(p0);
97			stack.push_back(sorted[0]);
98
99		✗	for (size_t i = 1; i < sorted.size(); ++i) {
100		✗	while (stack.size() >= 2) {
101		✗	Point p = stack[stack.size() - 2];
102		✗	Point q = stack[stack.size() - 1];
103		✗	if (Orient(p, q, sorted[i]) <= 0.0) {
104			stack.pop_back();
105			} else {
106			break;
107			}
108			}
109			stack.push_back(sorted[i]);
110			}
111
112		✗	hull_ = std::move(stack);
113			return true;
114			}
115
116		✗	bool IlinAGrahamTBB::PostProcessingImpl() {
117		✗	GetOutput() = hull_;
118		✗	return true;
119			}
120
121			} // namespace ilin_a_algorithm_graham
122