GCC Code Coverage Report

Directory: ./
File: tasks/konstantinov_s_graham/tbb/src/ops_tbb.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 101 105 96.2%
Functions: 16 17 94.1%
Branches: 89 146 61.0%
Line Branch Exec Source
1 #include "konstantinov_s_graham/tbb/include/ops_tbb.hpp"
2
3 #include <tbb/blocked_range.h>
4 #include <tbb/parallel_for.h>
5 #include <tbb/parallel_reduce.h>
6
7 #include <algorithm>
8 #include <cmath>
9 #include <cstddef>
10 #include <ranges>
11 #include <utility>
12 #include <vector>
13
14 #include "konstantinov_s_graham/common/include/common.hpp"
15
16 namespace konstantinov_s_graham {
17
18
2/2
✓ Branch 0 taken 116 times.
✓ Branch 1 taken 8 times.
 124 bool KonstantinovAGrahamTBB::IsLowerAnchor(const std::vector<double> &xs, const std::vector<double> &ys, size_t lhs,
19 size_t rhs) {
20
2/2
✓ Branch 0 taken 116 times.
✓ Branch 1 taken 8 times.
 124 if (ys[lhs] < ys[rhs] - kKEps) {
21 return true;
22 }
23
24
3/4
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 100 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 16 times.
 116 if (std::abs(ys[lhs] - ys[rhs]) < kKEps && xs[lhs] < xs[rhs] - kKEps) {
25 ✗ return true;
26 }
27
28 return false;
29 }
30
31
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 KonstantinovAGrahamTBB::KonstantinovAGrahamTBB(const InType &in) {
32 SetTypeOfTask(GetStaticTypeOfTask());
33 GetInput() = in;
34 40 }
35
36 40 bool KonstantinovAGrahamTBB::ValidationImpl() {
37 40 return GetInput().first.size() == GetInput().second.size();
38 }
39
40 40 bool KonstantinovAGrahamTBB::PreProcessingImpl() {
41 40 return true;
42 }
43
44 40 void KonstantinovAGrahamTBB::RemoveDuplicates(std::vector<double> &xs, std::vector<double> &ys) {
45
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 std::vector<std::pair<double, double>> pts;
46
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 pts.reserve(xs.size());
47
48
2/2
✓ Branch 0 taken 176 times.
✓ Branch 1 taken 40 times.
 216 for (size_t i = 0; i < xs.size(); ++i) {
49
1/2
✓ Branch 1 taken 176 times.
✗ Branch 2 not taken.
 176 pts.emplace_back(xs[i], ys[i]);
50 }
51
52 std::ranges::sort(pts, [](const auto &a, const auto &b) {
53
4/24
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 208 times.
✓ Branch 5 taken 36 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✓ Branch 22 taken 124 times.
✓ Branch 23 taken 16 times.
 384 if (std::abs(a.first - b.first) > kKEps) {
54 332 return a.first < b.first;
55 }
56 52 return a.second < b.second;
57 });
58
59 const auto new_end = std::ranges::unique(pts, [](const auto &a, const auto &b) {
60
8/8
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 92 times.
✓ Branch 2 taken 24 times.
✓ Branch 3 taken 8 times.
✓ Branch 4 taken 8 times.
✓ Branch 5 taken 8 times.
✓ Branch 6 taken 4 times.
✓ Branch 7 taken 4 times.
 140 return std::abs(a.first - b.first) < kKEps && std::abs(a.second - b.second) < kKEps;
61 });
62
63 pts.erase(new_end.begin(), pts.end());
64
65
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 xs.resize(pts.size());
66
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 ys.resize(pts.size());
67
68
2/2
✓ Branch 0 taken 164 times.
✓ Branch 1 taken 40 times.
 204 for (size_t i = 0; i < pts.size(); ++i) {
69 164 xs[i] = pts[i].first;
70 164 ys[i] = pts[i].second;
71 }
72 40 }
73
74 28 size_t KonstantinovAGrahamTBB::FindAnchorIndex(const std::vector<double> &xs, const std::vector<double> &ys) {
75 56 return tbb::parallel_reduce(tbb::blocked_range<size_t>(1, xs.size()), size_t{0},
76 124 [&xs, &ys](const tbb::blocked_range<size_t> &range, size_t local_idx) {
77
2/2
✓ Branch 0 taken 124 times.
✓ Branch 1 taken 124 times.
 248 for (size_t i = range.begin(); i < range.end(); ++i) {
78
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 116 times.
 124 if (IsLowerAnchor(xs, ys, i, local_idx)) {
79 local_idx = i;
80 }
81 }
82 124 return local_idx;
83
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 28 }, [&xs, &ys](size_t left, size_t right) { return IsLowerAnchor(xs, ys, left, right) ? left : right; });
84 }
85
86 ✗ double KonstantinovAGrahamTBB::Dist2(const std::vector<double> &xs, const std::vector<double> &ys, size_t i, size_t j) {
87 28 const double dx = xs[j] - xs[i];
88 28 const double dy = ys[j] - ys[i];
89 28 return (dx * dx) + (dy * dy);
90 }
91
92 372 double KonstantinovAGrahamTBB::CrossVal(const std::vector<double> &xs, const std::vector<double> &ys, size_t i,
93 size_t j, size_t k) {
94 372 const double ax = xs[j] - xs[i];
95 372 const double ay = ys[j] - ys[i];
96 372 const double bx = xs[k] - xs[i];
97 372 const double by = ys[k] - ys[i];
98 372 return (ax * by) - (ay * bx);
99 }
100
101 28 std::vector<size_t> KonstantinovAGrahamTBB::CollectAndSortIndices(const std::vector<double> &xs,
102 const std::vector<double> &ys, size_t anchor_idx) {
103 28 std::vector<size_t> idxs(xs.size() - 1);
104
105
1/4
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 180 tbb::parallel_for(tbb::blocked_range<size_t>(0, xs.size()), [&idxs, anchor_idx](const tbb::blocked_range<size_t> &r) {
106
2/2
✓ Branch 0 taken 152 times.
✓ Branch 1 taken 152 times.
 304 for (size_t i = r.begin(); i < r.end(); ++i) {
107
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 144 times.
 152 if (i < anchor_idx) {
108 8 idxs[i] = i;
109
2/2
✓ Branch 0 taken 116 times.
✓ Branch 1 taken 28 times.
 144 } else if (i > anchor_idx) {
110 116 idxs[i - 1] = i;
111 }
112 }
113 152 });
114
115 212 std::ranges::sort(idxs, [&xs, &ys, anchor_idx](size_t a, size_t b) {
116
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 184 times.
 212 const double cr = CrossVal(xs, ys, anchor_idx, a, b);
117
118
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 184 times.
 212 if (std::abs(cr) < kKEps) {
119 28 return Dist2(xs, ys, anchor_idx, a) < Dist2(xs, ys, anchor_idx, b);
120 }
121
122 184 return cr > 0;
123 });
124
125 28 return idxs;
126 }
127
128
1/2
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
 28 bool KonstantinovAGrahamTBB::AllCollinearWithAnchor(const std::vector<double> &xs, const std::vector<double> &ys,
129 size_t anchor_idx, const std::vector<size_t> &sorted_idxs) {
130
1/2
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
 28 if (sorted_idxs.empty()) {
131 return true;
132 }
133
134 56 return tbb::parallel_reduce(tbb::blocked_range<size_t>(1, sorted_idxs.size()), true,
135 124 [&xs, &ys, anchor_idx, &sorted_idxs](const tbb::blocked_range<size_t> &r, bool local_ok) {
136
4/4
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 28 times.
✓ Branch 2 taken 28 times.
✓ Branch 3 taken 68 times.
 124 for (size_t i = r.begin(); i < r.end() && local_ok; ++i) {
137
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 4 times.
 28 if (std::abs(CrossVal(xs, ys, anchor_idx, sorted_idxs[0], sorted_idxs[i])) > kKEps) {
138 local_ok = false;
139 }
140 }
141 96 return local_ok;
142 28 }, [](bool lhs, bool rhs) { return lhs && rhs; });
143 }
144
145 24 std::vector<std::pair<double, double>> KonstantinovAGrahamTBB::BuildHullFromSorted(
146 const std::vector<double> &xs, const std::vector<double> &ys, size_t anchor_idx,
147 const std::vector<size_t> &sorted_idxs) {
148
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 std::vector<size_t> stack;
149
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 stack.reserve(sorted_idxs.size() + 1);
150 stack.push_back(anchor_idx);
151
152
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 if (!sorted_idxs.empty()) {
153 stack.push_back(sorted_idxs[0]);
154 }
155
156
2/2
✓ Branch 0 taken 92 times.
✓ Branch 1 taken 24 times.
 116 for (size_t i = 1; i < sorted_idxs.size(); ++i) {
157 92 const size_t cur = sorted_idxs[i];
158
159
1/2
✓ Branch 0 taken 132 times.
✗ Branch 1 not taken.
 132 while (stack.size() >= 2) {
160
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 92 times.
 132 const size_t q = stack.back();
161 132 const size_t p = stack[stack.size() - 2];
162
163 132 const double cr = CrossVal(xs, ys, p, q, cur);
164
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 92 times.
 132 if (cr <= kKEps) {
165 stack.pop_back();
166 } else {
167 break;
168 }
169 }
170
171 stack.push_back(cur);
172 }
173
174
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 std::vector<std::pair<double, double>> hull;
175
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 hull.reserve(stack.size());
176
177
3/4
✓ Branch 1 taken 100 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 100 times.
✓ Branch 4 taken 24 times.
 124 for (size_t id : stack) {
178
1/2
✓ Branch 1 taken 100 times.
✗ Branch 2 not taken.
 100 hull.emplace_back(xs[id], ys[id]);
179 }
180
181 24 return hull;
182 }
183
184 40 bool KonstantinovAGrahamTBB::RunImpl() {
185 const InType &inp = GetInput();
186 40 auto xs = inp.first;
187
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 auto ys = inp.second;
188
189
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 RemoveDuplicates(xs, ys);
190
191
3/4
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 36 times.
 40 if (xs.size() != ys.size() || xs.empty()) {
192 GetOutput() = {};
193 return true;
194 }
195
196
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 28 times.
 36 if (xs.size() < 3) {
197
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 std::vector<std::pair<double, double>> out;
198
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 out.reserve(xs.size());
199
200
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 8 times.
 20 for (size_t i = 0; i < xs.size(); ++i) {
201
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 out.emplace_back(xs[i], ys[i]);
202 }
203
204
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 GetOutput() = out;
205 return true;
206 }
207
208
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 const size_t anchor = FindAnchorIndex(xs, ys);
209
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 std::vector<size_t> sorted_idxs = CollectAndSortIndices(xs, ys, anchor);
210
211
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
 28 if (sorted_idxs.empty()) {
212 ✗ GetOutput() = {{xs[anchor], ys[anchor]}};
213 ✗ return true;
214 }
215
216
3/4
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 4 times.
✓ Branch 4 taken 24 times.
 28 if (AllCollinearWithAnchor(xs, ys, anchor, sorted_idxs)) {
217
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 const size_t far_idx = sorted_idxs.back();
218 4 GetOutput() = {{xs[anchor], ys[anchor]}, {xs[far_idx], ys[far_idx]}};
219 4 return true;
220 }
221
222
1/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 24 GetOutput() = BuildHullFromSorted(xs, ys, anchor, sorted_idxs);
223 24 return true;
224 }
225
226 40 bool KonstantinovAGrahamTBB::PostProcessingImpl() {
227 40 return true;
228 }
229
230 } // namespace konstantinov_s_graham
231