GCC Code Coverage Report

Directory: ./
File: tasks/makovskiy_i_graham_hull/stl/src/ops_stl.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 103 104 99.0%
Functions: 14 14 100.0%
Branches: 94 134 70.1%
Line Branch Exec Source
1 #include "makovskiy_i_graham_hull/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cmath>
5 #include <cstddef>
6 #include <cstdint>
7 #include <future>
8 #include <thread>
9 #include <vector>
10
11 #include "makovskiy_i_graham_hull/common/include/common.hpp"
12
13 namespace makovskiy_i_graham_hull {
14
15 namespace {
16
17 double CrossProduct(const Point &o, const Point &a, const Point &b) {
18
2/2
✓ Branch 0 taken 10648 times.
✓ Branch 1 taken 15872 times.
 26520 return ((a.x - o.x) * (b.y - o.y)) - ((a.y - o.y) * (b.x - o.x));
19 }
20
21 double DistSq(const Point &a, const Point &b) {
22 32632 return ((a.x - b.x) * (a.x - b.x)) + ((a.y - b.y) * (a.y - b.y));
23 }
24
25 bool IsBetterMin(const Point &candidate, const Point &current_min) {
26
2/4
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 26552 times.
✗ Branch 3 not taken.
 26576 if (candidate.y < current_min.y - 1e-9) {
27 return true;
28 }
29
5/8
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 24 times.
✓ Branch 4 taken 480 times.
✓ Branch 5 taken 26072 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 480 times.
 26576 return (std::abs(candidate.y - current_min.y) <= 1e-9) && (candidate.x < current_min.x);
30 }
31
32 56 size_t FindMinPointIndexSTL(const std::vector<Point> &points) {
33 56 size_t n = points.size();
34 56 unsigned int num_threads = std::thread::hardware_concurrency();
35
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 if (num_threads == 0) {
36 num_threads = 4;
37 }
38
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 8 times.
 56 if (n < 1000) {
39 num_threads = 1;
40 }
41
42 56 std::vector<std::future<size_t>> futures;
43 56 size_t chunk = (n + num_threads - 1) / num_threads;
44
45 80 auto worker = [&points](size_t start, size_t end) {
46 size_t local_min = start;
47
2/2
✓ Branch 0 taken 26552 times.
✓ Branch 1 taken 80 times.
 26632 for (size_t j = start + 1; j < end; ++j) {
48
1/2
✓ Branch 0 taken 26552 times.
✗ Branch 1 not taken.
 26552 if (IsBetterMin(points[j], points[local_min])) {
49 local_min = j;
50 }
51 }
52 80 return local_min;
53 56 };
54
55
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 56 times.
 136 for (unsigned int i = 0; i < num_threads; ++i) {
56 80 size_t start = i * chunk;
57
1/2
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
 80 size_t end = std::min(start + chunk, n);
58
1/2
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
 80 if (start >= n) {
59 break;
60 }
61
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 160 futures.push_back(std::async(std::launch::async, worker, start, end));
62 }
63
64
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 size_t min_idx = futures[0].get();
65
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 56 times.
 80 for (size_t i = 1; i < futures.size(); ++i) {
66
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 size_t local_min = futures[i].get();
67 if (IsBetterMin(points[local_min], points[min_idx])) {
68 min_idx = local_min;
69 }
70 }
71
72 56 return min_idx;
73 56 }
74
75 template <typename RandomIt, typename Compare>
76
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 8 times.
 16 void StlParallelSortSub(RandomIt first, RandomIt last, Compare comp) {
77
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 8 times.
 16 if (last - first < 2048) {
78 8 std::sort(first, last, comp);
79 8 return;
80 }
81 8 auto pivot = *(first + ((last - first) / 2));
82
4/4
✓ Branch 0 taken 512 times.
✓ Branch 1 taken 6568 times.
✓ Branch 2 taken 12512 times.
✓ Branch 3 taken 6560 times.
 26160 RandomIt middle1 = std::partition(first, last, [pivot, comp](const auto &a) { return comp(a, pivot); });
83
3/4
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
✓ Branch 2 taken 19056 times.
✓ Branch 3 taken 8 times.
 19080 RandomIt middle2 = std::partition(middle1, last, [pivot, comp](const auto &a) { return !comp(pivot, a); });
84
85 16 auto future1 = std::async(std::launch::async, [first, middle1, comp]() { std::sort(first, middle1, comp); });
86 8 std::sort(middle2, last, comp);
87
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 future1.wait();
88 }
89
90 template <typename RandomIt, typename Compare>
91
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 8 times.
 56 void StlParallelSort(RandomIt first, RandomIt last, Compare comp) {
92
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 8 times.
 56 if (last - first < 2048) {
93 48 std::sort(first, last, comp);
94 48 return;
95 }
96 8 auto pivot = *(first + ((last - first) / 2));
97
3/4
✗ Branch 0 not taken.
✓ Branch 1 taken 240 times.
✓ Branch 2 taken 25920 times.
✓ Branch 3 taken 232 times.
 26400 RandomIt middle1 = std::partition(first, last, [pivot, comp](const auto &a) { return comp(a, pivot); });
98
3/4
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
✓ Branch 2 taken 26136 times.
✓ Branch 3 taken 8 times.
 26160 RandomIt middle2 = std::partition(middle1, last, [pivot, comp](const auto &a) { return !comp(pivot, a); });
99
100
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 16 auto future1 = std::async(std::launch::async, [first, middle1, comp]() { StlParallelSortSub(first, middle1, comp); });
101
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 StlParallelSortSub(middle2, last, comp);
102
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 future1.wait();
103 }
104
105
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 std::vector<Point> FilterPointsSTL(const std::vector<Point> &points, const Point &p0) {
106 size_t n = points.size();
107
108
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 if (n <= 2) {
109 ✗ return points;
110 }
111
112 56 std::vector<uint8_t> keep(n, 1);
113 56 unsigned int num_threads = std::thread::hardware_concurrency();
114
115
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 if (num_threads == 0) {
116 num_threads = 4;
117 }
118
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 8 times.
 56 if (n < 1000) {
119 num_threads = 1;
120 }
121
122 56 size_t num_elements = n - 2;
123 56 size_t chunk = (num_elements + num_threads - 1) / num_threads;
124 56 std::vector<std::future<void>> futures;
125
126 80 auto worker = [&points, &keep, &p0](size_t start, size_t end) {
127
2/2
✓ Branch 0 taken 26520 times.
✓ Branch 1 taken 80 times.
 26600 for (size_t j = start; j < end; ++j) {
128
2/2
✓ Branch 0 taken 10648 times.
✓ Branch 1 taken 15872 times.
 26520 if (std::abs(CrossProduct(p0, points[j], points[j + 1])) < 1e-9) {
129 10648 keep[j] = 0;
130 }
131 }
132 136 };
133
134
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 56 times.
 136 for (unsigned int i = 0; i < num_threads; ++i) {
135 80 size_t start = 1 + (i * chunk);
136
1/2
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
 80 size_t end = std::min(start + chunk, n - 1);
137
138
1/2
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
 80 if (start >= n - 1) {
139 break;
140 }
141
142
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 160 futures.push_back(std::async(std::launch::async, worker, start, end));
143 }
144
145
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 56 times.
 136 for (auto &f : futures) {
146
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 f.wait();
147 }
148
149 56 std::vector<Point> filtered;
150
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 filtered.reserve(n);
151
2/2
✓ Branch 0 taken 26632 times.
✓ Branch 1 taken 56 times.
 26688 for (size_t i = 0; i < n; ++i) {
152
2/2
✓ Branch 0 taken 15984 times.
✓ Branch 1 taken 10648 times.
 26632 if (keep[i] != 0) {
153 filtered.push_back(points[i]);
154 }
155 }
156 return filtered;
157 56 }
158
159 40 std::vector<Point> BuildHull(const std::vector<Point> &filtered) {
160
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 std::vector<Point> hull;
161 hull.push_back(filtered[0]);
162 hull.push_back(filtered[1]);
163 hull.push_back(filtered[2]);
164
165
2/2
✓ Branch 0 taken 15832 times.
✓ Branch 1 taken 40 times.
 15872 for (size_t i = 3; i < filtered.size(); ++i) {
166
3/4
✓ Branch 0 taken 31632 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 15800 times.
✓ Branch 3 taken 15832 times.
 31632 while (hull.size() > 1 && CrossProduct(hull[hull.size() - 2], hull.back(), filtered[i]) <= 1e-9) {
167 hull.pop_back();
168 }
169 hull.push_back(filtered[i]);
170 }
171 40 return hull;
172 }
173
174 } // namespace
175
176
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 ConvexHullGrahamSTL::ConvexHullGrahamSTL(const InType &in) {
177 SetTypeOfTask(GetStaticTypeOfTask());
178
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 GetInput() = in;
179 72 }
180
181 72 bool ConvexHullGrahamSTL::ValidationImpl() {
182 72 return true;
183 }
184
185 72 bool ConvexHullGrahamSTL::PreProcessingImpl() {
186 72 return true;
187 }
188
189 72 bool ConvexHullGrahamSTL::RunImpl() {
190 72 InType points = GetInput();
191
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 56 times.
 72 if (points.size() < 3) {
192
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 GetOutput() = points;
193 return true;
194 }
195
196
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 size_t min_idx = FindMinPointIndexSTL(points);
197
198 std::swap(points[0], points[min_idx]);
199 56 Point p0 = points[0];
200
201
2/2
✓ Branch 0 taken 32632 times.
✓ Branch 1 taken 410424 times.
 443056 auto comp = [p0](const Point &a, const Point &b) {
202 double cp = CrossProduct(p0, a, b);
203
2/2
✓ Branch 0 taken 32632 times.
✓ Branch 1 taken 410424 times.
 443056 if (std::abs(cp) < 1e-9) {
204 32632 return DistSq(p0, a) < DistSq(p0, b);
205 }
206 410424 return cp > 0;
207
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 };
208
209
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 StlParallelSort(points.begin() + 1, points.end(), comp);
210
211
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 InType filtered = FilterPointsSTL(points, p0);
212
213
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 40 times.
 56 if (filtered.size() < 3) {
214
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 GetOutput() = filtered;
215 return true;
216 }
217
218
1/4
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 40 GetOutput() = BuildHull(filtered);
219 40 return true;
220 }
221
222 72 bool ConvexHullGrahamSTL::PostProcessingImpl() {
223 72 return true;
224 }
225
226 } // namespace makovskiy_i_graham_hull
227