GCC Code Coverage Report

Directory: ./
File: tasks/perepelkin_i_convex_hull_graham_scan/stl/src/ops_stl.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 87 91 95.6%
Functions: 12 14 85.7%
Branches: 80 134 59.7%
Line Branch Exec Source
1 #include "perepelkin_i_convex_hull_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 "perepelkin_i_convex_hull_graham_scan/common/include/common.hpp"
11 #include "util/include/util.hpp"
12
13 namespace perepelkin_i_convex_hull_graham_scan {
14
15
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 PerepelkinIConvexHullGrahamScanSTL::PerepelkinIConvexHullGrahamScanSTL(const InType &in) {
16 SetTypeOfTask(GetStaticTypeOfTask());
17
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 GetInput() = in;
18 96 GetOutput() = std::vector<std::pair<double, double>>();
19 96 }
20
21 96 bool PerepelkinIConvexHullGrahamScanSTL::ValidationImpl() {
22 96 return GetOutput().empty();
23 }
24
25 96 bool PerepelkinIConvexHullGrahamScanSTL::PreProcessingImpl() {
26 96 return true;
27 }
28
29
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 80 times.
 96 bool PerepelkinIConvexHullGrahamScanSTL::RunImpl() {
30 const auto &data = GetInput();
31
32
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 80 times.
 96 if (data.size() < 2) {
33 16 GetOutput() = data;
34 16 return true;
35 }
36
37 80 std::vector<std::pair<double, double>> pts = data;
38
39 // Find pivot
40
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 size_t pivot_idx = FindPivotParallel(pts);
41
42 std::pair<double, double> pivot = pts[pivot_idx];
43 pts.erase(pts.begin() + static_cast<std::ptrdiff_t>(pivot_idx));
44
45 // Parallel sorting
46
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 ParallelSort(pts, pivot);
47
48 // Sequential hull construction
49 80 std::vector<std::pair<double, double>> hull;
50
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 HullConstruction(hull, pts, pivot);
51
52 GetOutput() = std::move(hull);
53 return true;
54 }
55
56 80 size_t PerepelkinIConvexHullGrahamScanSTL::FindPivotParallel(const std::vector<std::pair<double, double>> &pts) {
57 80 const int threads = std::min(ppc::util::GetNumThreads(), static_cast<int>(pts.size()));
58
59 // Partitioning
60 80 std::vector<int> start(threads + 1);
61 DataPartitioning(pts.size(), threads, start);
62
63 // Parallel search
64
1/4
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 80 std::vector<size_t> local_idx(threads, 0);
65 {
66
1/4
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 80 std::vector<std::jthread> workers(threads);
67
68
2/2
✓ Branch 0 taken 194 times.
✓ Branch 1 taken 80 times.
 274 for (int tid = 0; tid < threads; tid++) {
69
1/2
✓ Branch 1 taken 194 times.
✗ Branch 2 not taken.
 194 workers.emplace_back([&, tid]() {
70 194 size_t begin = start[tid];
71 194 size_t end = start[tid + 1];
72
73 size_t local = begin;
74
75
2/2
✓ Branch 0 taken 222 times.
✓ Branch 1 taken 194 times.
 416 for (size_t i = begin + 1; i < end; i++) {
76
4/4
✓ Branch 0 taken 168 times.
✓ Branch 1 taken 54 times.
✓ Branch 2 taken 54 times.
✓ Branch 3 taken 114 times.
 222 if (pts[i].second < pts[local].second ||
77
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 28 times.
 54 (pts[i].second == pts[local].second && pts[i].first < pts[local].first)) {
78 local = i;
79 }
80 }
81
82 194 local_idx[tid] = local;
83 194 });
84 }
85 80 }
86
87 // Sequential reduction
88 size_t pivot_idx = 0;
89
90
2/2
✓ Branch 0 taken 194 times.
✓ Branch 1 taken 80 times.
 274 for (int tid = 0; tid < threads; tid++) {
91
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 50 times.
 194 size_t i = local_idx[tid];
92
93
4/4
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 50 times.
✓ Branch 2 taken 74 times.
✓ Branch 3 taken 70 times.
 194 if (pts[i].second < pts[pivot_idx].second ||
94
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 56 times.
 74 (pts[i].second == pts[pivot_idx].second && pts[i].first < pts[pivot_idx].first)) {
95 pivot_idx = i;
96 }
97 }
98
99 80 return pivot_idx;
100 }
101
102 80 void PerepelkinIConvexHullGrahamScanSTL::ParallelSort(std::vector<std::pair<double, double>> &data,
103 const std::pair<double, double> &pivot) {
104 80 const int threads = std::min(ppc::util::GetNumThreads(), static_cast<int>(data.size()));
105
106 // Partitioning
107 80 std::vector<int> start(threads + 1);
108 DataPartitioning(data.size(), threads, start);
109
110 // Parallel local sorting
111 {
112
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 std::vector<std::jthread> workers(threads);
113
114
2/2
✓ Branch 0 taken 184 times.
✓ Branch 1 taken 80 times.
 264 for (int tid = 0; tid < threads; tid++) {
115
1/2
✓ Branch 1 taken 184 times.
✗ Branch 2 not taken.
 184 workers.emplace_back([&, tid]() {
116 184 std::sort(data.begin() + start[tid], data.begin() + start[tid + 1],
117
4/24
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 56 times.
✓ Branch 5 taken 116 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 36 times.
✓ Branch 23 taken 116 times.
 324 [&](const auto &a, const auto &b) { return AngleCmp(a, b, pivot); });
118 184 });
119 }
120 80 }
121
122 // Merge sorted segments
123
2/2
✓ Branch 0 taken 90 times.
✓ Branch 1 taken 80 times.
 170 for (int size = 1; size < threads; size *= 2) {
124
1/4
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 90 std::vector<std::jthread> workers(threads);
125
126
2/2
✓ Branch 0 taken 126 times.
✓ Branch 1 taken 90 times.
 216 for (int i = 0; i < threads; i += 2 * size) {
127
2/2
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 104 times.
 126 if (i + size >= threads) {
128 22 continue;
129 }
130
131
1/2
✓ Branch 1 taken 104 times.
✗ Branch 2 not taken.
 104 workers.emplace_back([&, i, size]() {
132
2/2
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 82 times.
 104 int left = start[i];
133 104 int mid = start[i + size];
134
2/2
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 82 times.
 126 int right = start[std::min(i + (2 * size), threads)];
135
136 104 std::inplace_merge(data.begin() + left, data.begin() + mid, data.begin() + right,
137
4/10
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 40 times.
✓ Branch 5 taken 48 times.
✓ Branch 6 taken 56 times.
✓ Branch 7 taken 78 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
 222 [&](const auto &a, const auto &b) { return AngleCmp(a, b, pivot); });
138 104 });
139 }
140 90 }
141 80 }
142
143 ✗ void PerepelkinIConvexHullGrahamScanSTL::DataPartitioning(size_t total_size, const int &threads,
144 std::vector<int> &start) {
145 160 size_t base = total_size / threads;
146 160 size_t rem = total_size % threads;
147
148 size_t offset = 0;
149
150
4/6
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 184 times.
✓ Branch 3 taken 80 times.
✓ Branch 4 taken 194 times.
✓ Branch 5 taken 80 times.
 538 for (int i = 0; i < threads; i++) {
151
4/6
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 28 times.
✓ Branch 3 taken 156 times.
✓ Branch 4 taken 54 times.
✓ Branch 5 taken 140 times.
 378 start[i] = static_cast<int>(offset);
152
153 size_t extra = std::cmp_less(i, rem) ? 1 : 0;
154 378 offset += base + extra;
155 }
156
157
2/4
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 80 times.
✗ Branch 5 not taken.
 160 start[threads] = static_cast<int>(total_size);
158 ✗ }
159
160 80 void PerepelkinIConvexHullGrahamScanSTL::HullConstruction(std::vector<std::pair<double, double>> &hull,
161 const std::vector<std::pair<double, double>> &pts,
162 const std::pair<double, double> &pivot) {
163 80 hull.reserve(pts.size() + 1);
164
165 hull.push_back(pivot);
166 hull.push_back(pts[0]);
167
168
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 80 times.
 336 for (size_t i = 1; i < pts.size(); i++) {
169
4/4
✓ Branch 0 taken 336 times.
✓ Branch 1 taken 48 times.
✓ Branch 2 taken 80 times.
✓ Branch 3 taken 208 times.
 672 while (hull.size() >= 2 && Orientation(hull[hull.size() - 2], hull[hull.size() - 1], pts[i]) <= 0) {
170 hull.pop_back();
171 }
172
173 hull.push_back(pts[i]);
174 }
175 80 }
176
177 ✗ double PerepelkinIConvexHullGrahamScanSTL::Orientation(const std::pair<double, double> &p,
178 const std::pair<double, double> &q,
179 const std::pair<double, double> &r) {
180
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 48 times.
✓ Branch 3 taken 288 times.
 336 double val = ((q.first - p.first) * (r.second - p.second)) - ((q.second - p.second) * (r.first - p.first));
181
182
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 48 times.
✓ Branch 3 taken 288 times.
 336 if (std::abs(val) < 1e-9) {
183 ✗ return 0.0;
184 }
185
186 return val;
187 }
188
189 546 bool PerepelkinIConvexHullGrahamScanSTL::AngleCmp(const std::pair<double, double> &a,
190 const std::pair<double, double> &b,
191 const std::pair<double, double> &pivot) {
192 546 double dx1 = a.first - pivot.first;
193 546 double dy1 = a.second - pivot.second;
194 546 double dx2 = b.first - pivot.first;
195 546 double dy2 = b.second - pivot.second;
196
197
2/2
✓ Branch 0 taken 122 times.
✓ Branch 1 taken 424 times.
 546 double cross = (dx1 * dy2) - (dy1 * dx2);
198
199
2/2
✓ Branch 0 taken 122 times.
✓ Branch 1 taken 424 times.
 546 if (std::abs(cross) < 1e-9) {
200 122 double dist1 = (dx1 * dx1) + (dy1 * dy1);
201 122 double dist2 = (dx2 * dx2) + (dy2 * dy2);
202 122 return dist1 < dist2;
203 }
204
205 424 return cross > 0;
206 }
207
208 96 bool PerepelkinIConvexHullGrahamScanSTL::PostProcessingImpl() {
209 96 return true;
210 }
211
212 } // namespace perepelkin_i_convex_hull_graham_scan
213