GCC Code Coverage Report

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