GCC Code Coverage Report

Directory: ./
File: tasks/konstantinov_s_graham/stl/src/ops_stl.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 145 156 92.9%
Functions: 18 22 81.8%
Branches: 146 232 62.9%
Line Branch Exec Source
1 #include "konstantinov_s_graham/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <atomic>
5 #include <cmath>
6 #include <cstddef>
7 #include <ranges>
8 #include <thread>
9 #include <utility>
10 #include <vector>
11
12 #include "konstantinov_s_graham/common/include/common.hpp"
13
14 namespace konstantinov_s_graham {
15
16
2/2
✓ Branch 0 taken 224 times.
✓ Branch 1 taken 32 times.
 256 bool KonstantinovAGrahamSTL::IsLowerAnchor(const std::vector<double> &xs, const std::vector<double> &ys, size_t lhs,
17 size_t rhs) {
18
2/2
✓ Branch 0 taken 224 times.
✓ Branch 1 taken 32 times.
 256 if (ys[lhs] < ys[rhs] - kKEps) {
19 return true;
20 }
21
22
3/4
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 184 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 40 times.
 224 if (std::abs(ys[lhs] - ys[rhs]) < kKEps && xs[lhs] < xs[rhs] - kKEps) {
23 ✗ return true;
24 }
25
26 return false;
27 }
28
29 ✗ size_t KonstantinovAGrahamSTL::GetThreadCount(size_t n) {
30
3/6
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 56 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 56 times.
✗ Branch 8 not taken.
 168 const size_t hw = std::max<size_t>(1, static_cast<size_t>(std::thread::hardware_concurrency()));
31 ✗ return std::min(hw, n);
32 }
33
34 ✗ size_t KonstantinovAGrahamSTL::FindLocalAnchor(const std::vector<double> &xs, const std::vector<double> &ys,
35 size_t begin, size_t end) {
36 size_t best = begin;
37
38
4/6
✓ Branch 0 taken 184 times.
✓ Branch 1 taken 48 times.
✓ Branch 2 taken 48 times.
✓ Branch 3 taken 24 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 304 for (size_t i = begin + 1; i < end; ++i) {
39
4/6
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 168 times.
✓ Branch 2 taken 16 times.
✓ Branch 3 taken 32 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 232 if (IsLowerAnchor(xs, ys, i, best)) {
40 best = i;
41 }
42 }
43
44 ✗ return best;
45 }
46
47
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 KonstantinovAGrahamSTL::KonstantinovAGrahamSTL(const InType &in) {
48 SetTypeOfTask(GetStaticTypeOfTask());
49 GetInput() = in;
50 80 }
51
52 80 bool KonstantinovAGrahamSTL::ValidationImpl() {
53 80 return GetInput().first.size() == GetInput().second.size();
54 }
55
56 80 bool KonstantinovAGrahamSTL::PreProcessingImpl() {
57 80 return true;
58 }
59
60 80 void KonstantinovAGrahamSTL::RemoveDuplicates(std::vector<double> &xs, std::vector<double> &ys) {
61
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 std::vector<std::pair<double, double>> pts;
62
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 pts.reserve(xs.size());
63
64
2/2
✓ Branch 0 taken 352 times.
✓ Branch 1 taken 80 times.
 432 for (size_t i = 0; i < xs.size(); ++i) {
65
1/2
✓ Branch 1 taken 352 times.
✗ Branch 2 not taken.
 352 pts.emplace_back(xs[i], ys[i]);
66 }
67
68 std::ranges::sort(pts, [](const auto &lhs, const auto &rhs) {
69
4/24
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 416 times.
✓ Branch 5 taken 72 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 248 times.
✓ Branch 23 taken 32 times.
 768 if (std::abs(lhs.first - rhs.first) > kKEps) {
70 664 return lhs.first < rhs.first;
71 }
72
73 104 return lhs.second < rhs.second;
74 });
75
76 const auto unique_end = std::ranges::unique(pts, [](const auto &lhs, const auto &rhs) {
77
8/8
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 184 times.
✓ Branch 2 taken 48 times.
✓ Branch 3 taken 16 times.
✓ Branch 4 taken 16 times.
✓ Branch 5 taken 16 times.
✓ Branch 6 taken 8 times.
✓ Branch 7 taken 8 times.
 280 return std::abs(lhs.first - rhs.first) < kKEps && std::abs(lhs.second - rhs.second) < kKEps;
78 });
79
80 pts.erase(unique_end.begin(), pts.end());
81
82
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 xs.resize(pts.size());
83
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 ys.resize(pts.size());
84
85
2/2
✓ Branch 0 taken 328 times.
✓ Branch 1 taken 80 times.
 408 for (size_t i = 0; i < pts.size(); ++i) {
86 328 xs[i] = pts[i].first;
87 328 ys[i] = pts[i].second;
88 }
89 80 }
90
91
1/2
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
 56 size_t KonstantinovAGrahamSTL::FindAnchorIndex(const std::vector<double> &xs, const std::vector<double> &ys) {
92
1/2
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
 56 if (xs.empty()) {
93 return 0;
94 }
95
96 const size_t thread_count = GetThreadCount(xs.size());
97
98
3/4
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 48 times.
✓ Branch 3 taken 8 times.
 56 if (thread_count <= 1 || xs.size() < (thread_count * 2)) {
99 return FindLocalAnchor(xs, ys, 0, xs.size());
100 }
101
102 8 std::vector<size_t> local_results(thread_count);
103 8 std::vector<std::thread> workers;
104
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 workers.reserve(thread_count);
105
106 8 const size_t block_size = (xs.size() + thread_count - 1) / thread_count;
107
108
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 8 times.
 40 for (size_t thread_idx = 0; thread_idx < thread_count; ++thread_idx) {
109 32 const size_t begin = thread_idx * block_size;
110
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 24 times.
 32 const size_t end = std::min(xs.size(), begin + block_size);
111
112
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 24 times.
 32 if (begin >= end) {
113 8 local_results[thread_idx] = 0;
114 8 continue;
115 }
116
117 24 workers.emplace_back(
118
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 48 [&, thread_idx, begin, end]() { local_results[thread_idx] = FindLocalAnchor(xs, ys, begin, end); });
119 }
120
121
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 8 times.
 32 for (auto &worker : workers) {
122
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 worker.join();
123 }
124
125 8 size_t best = local_results[0];
126
127
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 8 times.
 32 for (size_t thread_idx = 1; thread_idx < thread_count; ++thread_idx) {
128
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (IsLowerAnchor(xs, ys, local_results[thread_idx], best)) {
129 best = local_results[thread_idx];
130 }
131 }
132
133 return best;
134 8 }
135
136 ✗ double KonstantinovAGrahamSTL::Dist2(const std::vector<double> &xs, const std::vector<double> &ys, size_t i, size_t j) {
137 56 const double dx = xs[j] - xs[i];
138 56 const double dy = ys[j] - ys[i];
139 56 return (dx * dx) + (dy * dy);
140 }
141
142 768 double KonstantinovAGrahamSTL::CrossVal(const std::vector<double> &xs, const std::vector<double> &ys, size_t i,
143 size_t j, size_t k) {
144 768 const double ax = xs[j] - xs[i];
145 768 const double ay = ys[j] - ys[i];
146 768 const double bx = xs[k] - xs[i];
147 768 const double by = ys[k] - ys[i];
148 768 return (ax * by) - (ay * bx);
149 }
150
151 56 std::vector<size_t> KonstantinovAGrahamSTL::CollectAndSortIndices(const std::vector<double> &xs,
152 const std::vector<double> &ys, size_t anchor_idx) {
153 56 std::vector<size_t> idxs(xs.size() - 1);
154
155 const size_t thread_count = GetThreadCount(xs.size());
156
157
3/4
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 48 times.
✓ Branch 3 taken 8 times.
 56 if (thread_count <= 1 || xs.size() < (thread_count * 2)) {
158 FillIndexRange(idxs, 0, xs.size(), anchor_idx);
159 } else {
160
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 FillIndicesParallel(idxs, xs.size(), anchor_idx, thread_count);
161 }
162
163 424 std::ranges::sort(idxs, [&xs, &ys, anchor_idx](size_t lhs, size_t rhs) {
164
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 368 times.
 424 const double cross = CrossVal(xs, ys, anchor_idx, lhs, rhs);
165
166
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 368 times.
 424 if (std::abs(cross) < kKEps) {
167 56 return Dist2(xs, ys, anchor_idx, lhs) < Dist2(xs, ys, anchor_idx, rhs);
168 }
169
170 368 return cross > 0;
171 });
172
173 56 return idxs;
174 }
175
176 80 bool KonstantinovAGrahamSTL::CheckCollinearRange(const std::vector<double> &xs, const std::vector<double> &ys,
177 size_t anchor_idx, const std::vector<size_t> &sorted_idxs,
178 size_t begin, size_t end) {
179
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 8 times.
 88 for (size_t i = begin; i < end; ++i) {
180
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 72 times.
 80 if (std::abs(CrossVal(xs, ys, anchor_idx, sorted_idxs[0], sorted_idxs[i])) > kKEps) {
181 return false;
182 }
183 }
184
185 return true;
186 }
187
188 ✗ void KonstantinovAGrahamSTL::FillIndexRange(std::vector<size_t> &idxs, size_t begin, size_t end, size_t anchor_idx) {
189
4/6
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 232 times.
✓ Branch 5 taken 48 times.
 376 for (size_t i = begin; i < end; ++i) {
190
3/6
✗ Branch 0 not taken.
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 16 times.
✓ Branch 5 taken 216 times.
 304 if (i < anchor_idx) {
191 16 idxs[i] = i;
192
4/6
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 168 times.
✓ Branch 5 taken 48 times.
 288 } else if (i > anchor_idx) {
193 232 idxs[i - 1] = i;
194 }
195 }
196 ✗ }
197
198 8 void KonstantinovAGrahamSTL::FillIndicesParallel(std::vector<size_t> &idxs, size_t point_count, size_t anchor_idx,
199 size_t thread_count) {
200 8 std::vector<std::thread> workers;
201
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 workers.reserve(thread_count);
202
203 8 const size_t block_size = (point_count + thread_count - 1) / thread_count;
204
205
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 8 times.
 40 for (size_t thread_idx = 0; thread_idx < thread_count; ++thread_idx) {
206 32 const size_t begin = thread_idx * block_size;
207
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 24 times.
 32 const size_t end = std::min(point_count, begin + block_size);
208
209
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 24 times.
 32 if (begin >= end) {
210 8 continue;
211 }
212
213
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 48 workers.emplace_back([&, begin, end]() { FillIndexRange(idxs, begin, end, anchor_idx); });
214 }
215
216
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 8 times.
 32 for (auto &worker : workers) {
217
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 worker.join();
218 }
219 8 }
220
221
1/2
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
 56 bool KonstantinovAGrahamSTL::AllCollinearWithAnchor(const std::vector<double> &xs, const std::vector<double> &ys,
222 size_t anchor_idx, const std::vector<size_t> &sorted_idxs) {
223
1/2
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
 56 if (sorted_idxs.empty()) {
224 return true;
225 }
226
227 const size_t thread_count = GetThreadCount(sorted_idxs.size());
228
229
3/4
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 48 times.
✓ Branch 3 taken 8 times.
 56 if (thread_count <= 1 || sorted_idxs.size() < (thread_count * 2)) {
230 48 return CheckCollinearRange(xs, ys, anchor_idx, sorted_idxs, 1, sorted_idxs.size());
231 }
232
233 8 std::atomic<bool> result{true};
234
235 8 std::vector<std::thread> workers;
236
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 workers.reserve(thread_count);
237
238 8 const size_t block_size = (sorted_idxs.size() + thread_count - 1) / thread_count;
239
240
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 8 times.
 40 for (size_t thread_idx = 0; thread_idx < thread_count; ++thread_idx) {
241
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
 32 const size_t begin = std::max<size_t>(1, thread_idx * block_size);
242
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
 32 const size_t end = std::min(sorted_idxs.size(), begin + block_size);
243
244
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
 32 if (begin >= end) {
245 ✗ continue;
246 }
247
248
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 workers.emplace_back([&, begin, end]() {
249
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
 32 if (!CheckCollinearRange(xs, ys, anchor_idx, sorted_idxs, begin, end)) {
250 32 result.store(false);
251 }
252 32 });
253 }
254
255
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 8 times.
 40 for (auto &worker : workers) {
256
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 worker.join();
257 }
258
259 return result.load();
260 8 }
261
262 48 std::vector<std::pair<double, double>> KonstantinovAGrahamSTL::BuildHullFromSorted(
263 const std::vector<double> &xs, const std::vector<double> &ys, size_t anchor_idx,
264 const std::vector<size_t> &sorted_idxs) {
265
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 std::vector<size_t> stack;
266
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 stack.reserve(sorted_idxs.size() + 1);
267 stack.push_back(anchor_idx);
268
269
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 if (!sorted_idxs.empty()) {
270 stack.push_back(sorted_idxs[0]);
271 }
272
273
2/2
✓ Branch 0 taken 184 times.
✓ Branch 1 taken 48 times.
 232 for (size_t i = 1; i < sorted_idxs.size(); ++i) {
274 184 const size_t cur = sorted_idxs[i];
275
276
1/2
✓ Branch 0 taken 264 times.
✗ Branch 1 not taken.
 264 while (stack.size() >= 2) {
277
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 184 times.
 264 const size_t q = stack.back();
278 264 const size_t p = stack[stack.size() - 2];
279 264 const double cr = CrossVal(xs, ys, p, q, cur);
280
281
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 184 times.
 264 if (cr <= kKEps) {
282 stack.pop_back();
283 } else {
284 break;
285 }
286 }
287
288 stack.push_back(cur);
289 }
290
291
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 std::vector<std::pair<double, double>> hull;
292
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 hull.reserve(stack.size());
293
294
3/4
✓ Branch 1 taken 200 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 200 times.
✓ Branch 4 taken 48 times.
 248 for (size_t id : stack) {
295
1/2
✓ Branch 1 taken 200 times.
✗ Branch 2 not taken.
 200 hull.emplace_back(xs[id], ys[id]);
296 }
297
298 48 return hull;
299 }
300
301 80 bool KonstantinovAGrahamSTL::RunImpl() {
302 const InType &inp = GetInput();
303 80 auto xs = inp.first;
304
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 auto ys = inp.second;
305
306
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 RemoveDuplicates(xs, ys);
307
308
3/4
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 8 times.
✓ Branch 3 taken 72 times.
 80 if (xs.size() != ys.size() || xs.empty()) {
309 GetOutput() = {};
310 return true;
311 }
312
313
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 56 times.
 72 if (xs.size() < 3) {
314
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 std::vector<std::pair<double, double>> out;
315
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 out.reserve(xs.size());
316
317
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 16 times.
 40 for (size_t i = 0; i < xs.size(); ++i) {
318
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 out.emplace_back(xs[i], ys[i]);
319 }
320
321
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 GetOutput() = out;
322 return true;
323 }
324
325
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 const size_t anchor = FindAnchorIndex(xs, ys);
326
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 std::vector<size_t> sorted_idxs = CollectAndSortIndices(xs, ys, anchor);
327
328
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 if (sorted_idxs.empty()) {
329 ✗ GetOutput() = {{xs[anchor], ys[anchor]}};
330 ✗ return true;
331 }
332
333
3/4
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 8 times.
✓ Branch 4 taken 48 times.
 56 if (AllCollinearWithAnchor(xs, ys, anchor, sorted_idxs)) {
334
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 const size_t far_idx = sorted_idxs.back();
335 8 GetOutput() = {{xs[anchor], ys[anchor]}, {xs[far_idx], ys[far_idx]}};
336 8 return true;
337 }
338
339
1/4
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 48 GetOutput() = BuildHullFromSorted(xs, ys, anchor, sorted_idxs);
340 48 return true;
341 }
342
343 80 bool KonstantinovAGrahamSTL::PostProcessingImpl() {
344 80 return true;
345 }
346
347 } // namespace konstantinov_s_graham
348