GCC Code Coverage Report

Directory: ./
File: tasks/dergachev_a_graham_scan/stl/src/ops_stl.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 73 77 94.8%
Functions: 10 10 100.0%
Branches: 80 122 65.6%
Line Branch Exec Source
1 #include "dergachev_a_graham_scan/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cmath>
5 #include <cstddef>
6 #include <thread>
7 #include <utility>
8 #include <vector>
9
10 #include "dergachev_a_graham_scan/common/include/common.hpp"
11 #include "util/include/util.hpp"
12
13 namespace dergachev_a_graham_scan {
14
15 namespace {
16
17 using Pt = std::pair<double, double>;
18
19 double CrossProduct(const Pt &o, const Pt &a, const Pt &b) {
20 155184 return ((a.first - o.first) * (b.second - o.second)) - ((a.second - o.second) * (b.first - o.first));
21 }
22
23 double DistSquared(const Pt &a, const Pt &b) {
24 ✗ double dx = a.first - b.first;
25 ✗ double dy = a.second - b.second;
26 ✗ return (dx * dx) + (dy * dy);
27 }
28
29 const double kPi = std::acos(-1.0);
30
31 bool IsLowerLeft(const Pt &a, const Pt &b) {
32
12/18
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 38 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 38 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 62 times.
✓ Branch 7 taken 24 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 24 times.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✓ Branch 12 taken 3342 times.
✓ Branch 13 taken 6116 times.
✓ Branch 14 taken 10 times.
✓ Branch 15 taken 6106 times.
✓ Branch 16 taken 2 times.
✓ Branch 17 taken 8 times.
 9600 return a.second < b.second || (a.second == b.second && a.first < b.first);
33 }
34
35 int FindLocalPivot(const std::vector<Pt> &pts, int start, int end) {
36 int best = start;
37
4/4
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 20 times.
✓ Branch 2 taken 9458 times.
✓ Branch 3 taken 154 times.
 9688 for (int i = start + 1; i < end; i++) {
38
4/4
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 38 times.
✓ Branch 2 taken 3342 times.
✓ Branch 3 taken 6116 times.
 9514 if (IsLowerLeft(pts[i], pts[best])) {
39 best = i;
40 }
41 }
42 return best;
43 }
44
45
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 68 times.
 88 int FindPivotParallel(const std::vector<Pt> &pts, int num_threads) {
46 88 int n = static_cast<int>(pts.size());
47
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 68 times.
 88 if (n < num_threads * 2) {
48 return FindLocalPivot(pts, 0, n);
49 }
50
51 68 int chunk = n / num_threads;
52 68 std::vector<int> local_results(num_threads);
53 68 std::vector<std::thread> threads;
54
55
2/2
✓ Branch 0 taken 154 times.
✓ Branch 1 taken 68 times.
 222 for (int thread_idx = 0; thread_idx < num_threads; thread_idx++) {
56 154 int lo = thread_idx * chunk;
57
2/2
✓ Branch 0 taken 86 times.
✓ Branch 1 taken 68 times.
 154 int hi = (thread_idx == num_threads - 1) ? n : ((thread_idx + 1) * chunk);
58 154 threads.emplace_back(
59
1/2
✓ Branch 1 taken 154 times.
✗ Branch 2 not taken.
 308 [&pts, &local_results, thread_idx, lo, hi]() { local_results[thread_idx] = FindLocalPivot(pts, lo, hi); });
60 }
61
2/2
✓ Branch 0 taken 154 times.
✓ Branch 1 taken 68 times.
 222 for (auto &th : threads) {
62
1/2
✓ Branch 1 taken 154 times.
✗ Branch 2 not taken.
 154 th.join();
63 }
64
65 68 int best = local_results[0];
66
2/2
✓ Branch 0 taken 86 times.
✓ Branch 1 taken 68 times.
 154 for (int thread_idx = 1; thread_idx < num_threads; thread_idx++) {
67
2/2
✓ Branch 0 taken 62 times.
✓ Branch 1 taken 24 times.
 86 if (IsLowerLeft(pts[local_results[thread_idx]], pts[best])) {
68 best = local_results[thread_idx];
69 }
70 }
71 return best;
72 68 }
73
74 38 void GeneratePointsParallel(Pt *data, double step, int n, int num_threads) {
75 38 int chunk = n / num_threads;
76 38 std::vector<std::thread> threads;
77
2/2
✓ Branch 0 taken 108 times.
✓ Branch 1 taken 38 times.
 146 for (int ti = 0; ti < num_threads; ti++) {
78 108 int lo = ti * chunk;
79
2/2
✓ Branch 0 taken 70 times.
✓ Branch 1 taken 38 times.
 108 int hi = (ti == num_threads - 1) ? n : (ti + 1) * chunk;
80
1/2
✓ Branch 1 taken 108 times.
✗ Branch 2 not taken.
 108 threads.emplace_back([data, step, lo, hi]() {
81
2/2
✓ Branch 0 taken 7100 times.
✓ Branch 1 taken 108 times.
 7208 for (int i = lo; i < hi; i++) {
82 7100 data[i] = {std::cos(step * i), std::sin(step * i)};
83 }
84 108 });
85 }
86
2/2
✓ Branch 0 taken 108 times.
✓ Branch 1 taken 38 times.
 146 for (auto &th : threads) {
87
1/2
✓ Branch 1 taken 108 times.
✗ Branch 2 not taken.
 108 th.join();
88 }
89 38 }
90
91 } // namespace
92
93 104 DergachevAGrahamScanSTL::DergachevAGrahamScanSTL(const InType &in) {
94 SetTypeOfTask(GetStaticTypeOfTask());
95 104 GetInput() = in;
96 GetOutput() = 0;
97 104 }
98
99 104 bool DergachevAGrahamScanSTL::ValidationImpl() {
100 104 return GetInput() >= 0;
101 }
102
103
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 104 times.
 104 bool DergachevAGrahamScanSTL::PreProcessingImpl() {
104 hull_.clear();
105 104 int n = GetInput();
106
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 96 times.
 104 if (n <= 0) {
107 points_.clear();
108 8 return true;
109 }
110 96 points_.resize(n);
111 96 double step = (2.0 * kPi) / n;
112
113 96 const int num_threads = ppc::util::GetNumThreads();
114
4/4
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 34 times.
✓ Branch 3 taken 38 times.
 96 if (num_threads > 1 && n > num_threads * 2) {
115 38 GeneratePointsParallel(points_.data(), step, n, num_threads);
116 } else {
117
2/2
✓ Branch 0 taken 2524 times.
✓ Branch 1 taken 58 times.
 2582 for (int i = 0; i < n; i++) {
118 2524 points_[static_cast<std::size_t>(i)] = {std::cos(step * i), std::sin(step * i)};
119 }
120 }
121
122
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 24 times.
 96 if (n > 3) {
123 72 points_.emplace_back(0.0, 0.0);
124 }
125 return true;
126 }
127
128
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 104 times.
 104 bool DergachevAGrahamScanSTL::RunImpl() {
129 hull_.clear();
130
2/2
✓ Branch 1 taken 88 times.
✓ Branch 2 taken 16 times.
 104 std::vector<Pt> pts(points_.begin(), points_.end());
131 104 int n = static_cast<int>(pts.size());
132
133
3/4
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 88 times.
 104 if (n <= 1 || std::all_of(pts.begin() + 1, pts.end(),
134
3/28
✗ Branch 0 not taken.
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ 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 taken 8 times.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✓ Branch 25 taken 8 times.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
 88 [&](const Pt &pt) { return pt.first == pts[0].first && pt.second == pts[0].second; })) {
135
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 8 times.
 16 if (!pts.empty()) {
136
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
 8 hull_.push_back(pts[0]);
137 }
138 16 return true;
139 }
140
141
1/2
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
 88 const int num_threads = ppc::util::GetNumThreads();
142
143
1/2
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
 88 int pivot_idx = FindPivotParallel(pts, num_threads);
144 88 std::swap(pts[0], pts[static_cast<std::size_t>(pivot_idx)]);
145
146 Pt pivot = pts[0];
147 145688 std::sort(pts.begin() + 1, pts.end(), [&pivot](const Pt &a, const Pt &b) {
148 145600 double cross = CrossProduct(pivot, a, b);
149
1/2
✓ Branch 0 taken 145600 times.
✗ Branch 1 not taken.
 145600 if (cross != 0.0) {
150 145600 return cross > 0.0;
151 }
152 ✗ return DistSquared(pivot, a) < DistSquared(pivot, b);
153 });
154
155
2/2
✓ Branch 0 taken 9688 times.
✓ Branch 1 taken 88 times.
 9776 for (const auto &p : pts) {
156
4/4
✓ Branch 0 taken 9584 times.
✓ Branch 1 taken 176 times.
✓ Branch 2 taken 9512 times.
✓ Branch 3 taken 72 times.
 9760 while (hull_.size() > 1 && CrossProduct(hull_[hull_.size() - 2], hull_.back(), p) <= 0.0) {
157 hull_.pop_back();
158 }
159
2/2
✓ Branch 0 taken 9240 times.
✓ Branch 1 taken 448 times.
 9688 hull_.push_back(p);
160 }
161
162 return true;
163 }
164
165 104 bool DergachevAGrahamScanSTL::PostProcessingImpl() {
166 104 GetOutput() = static_cast<int>(hull_.size());
167 104 return true;
168 }
169
170 } // namespace dergachev_a_graham_scan
171