GCC Code Coverage Report

Directory: ./
File: tasks/orehov_n_jarvis_pass/stl/src/ops_stl.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 65 74 87.8%
Functions: 9 12 75.0%
Branches: 48 78 61.5%
Line Branch Exec Source
1 #include "orehov_n_jarvis_pass/stl/include/ops_stl.hpp"
2
3 #include <cmath>
4 #include <cstddef>
5 #include <set>
6 #include <thread>
7 #include <vector>
8
9 #include "orehov_n_jarvis_pass/common/include/common.hpp"
10
11 namespace orehov_n_jarvis_pass {
12
13 namespace {
14
15 struct BestState {
16 Point point;
17 bool valid = false;
18 };
19
20 bool IsBetterPoint(Point current, Point candidate, Point best) {
21 double orient = OrehovNJarvisPassSTL::CheckLeft(current, best, candidate);
22 200 if (orient > 0.0) {
23 return true;
24 }
25
3/4
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 56 times.
 112 if (orient == 0.0) {
26 double dx_c = candidate.x - current.x;
27 double dy_c = candidate.y - current.y;
28 8 double dist_c = (dx_c * dx_c) + (dy_c * dy_c);
29
30 double dx_b = best.x - current.x;
31 double dy_b = best.y - current.y;
32 8 double dist_b = (dx_b * dx_b) + (dy_b * dy_b);
33
34 return dist_c > dist_b;
35 }
36 return false;
37 }
38
39 160 BestState FindBestInRange(const std::vector<Point> &points, Point current, size_t start, size_t end) {
40 160 BestState local{.point = Point(), .valid = false};
41
2/2
✓ Branch 0 taken 280 times.
✓ Branch 1 taken 160 times.
 440 for (size_t j = start; j < end; ++j) {
42 const Point &p = points[j];
43 40 if (p == current) {
44 40 continue;
45 }
46
2/4
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 152 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 240 if (!local.valid || IsBetterPoint(current, p, local.point)) {
47 184 local.point = p;
48 184 local.valid = true;
49 }
50 }
51 160 return local;
52 }
53
54 160 BestState CombineBestStates(const BestState &a, const BestState &b, Point current) {
55
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 120 times.
 160 if (!a.valid) {
56 40 return b;
57 }
58
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 112 times.
 120 if (!b.valid) {
59 8 return a;
60 }
61
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
 112 return BestState{.point = IsBetterPoint(current, b.point, a.point) ? b.point : a.point, .valid = true};
62 }
63
64 } // namespace
65
66
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 OrehovNJarvisPassSTL::OrehovNJarvisPassSTL(const InType &in) {
67 SetTypeOfTask(GetStaticTypeOfTask());
68
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 GetInput() = in;
69 24 GetOutput() = std::vector<Point>();
70 24 }
71
72 24 bool OrehovNJarvisPassSTL::ValidationImpl() {
73 24 return (!GetInput().empty());
74 }
75
76 24 bool OrehovNJarvisPassSTL::PreProcessingImpl() {
77 24 std::set<Point> tmp(GetInput().begin(), GetInput().end());
78
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 input_.assign(tmp.begin(), tmp.end());
79 24 return true;
80 }
81
82
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 8 times.
 24 bool OrehovNJarvisPassSTL::RunImpl() {
83
4/4
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 8 times.
✓ Branch 3 taken 8 times.
 24 if (input_.size() == 1 || input_.size() == 2) {
84 16 res_ = input_;
85 16 return true;
86 }
87
88 8 Point current = FindFirstElem();
89
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
 8 res_.push_back(current);
90
91 while (true) {
92 40 Point next = FindNext(current);
93 if (next == res_[0]) {
94 break;
95 }
96
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 24 times.
 32 current = next;
97 res_.push_back(next);
98 32 }
99
100 8 return true;
101 }
102
103
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 40 times.
 40 Point OrehovNJarvisPassSTL::FindNext(Point current) const {
104 const size_t n = input_.size();
105
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 40 times.
 40 if (n == 0) {
106 ✗ return current;
107 }
108
109 40 unsigned int num_threads = std::thread::hardware_concurrency();
110 40 if (num_threads == 0) {
111 num_threads = 1;
112 }
113
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 40 times.
 40 if (num_threads > n) {
114 ✗ num_threads = static_cast<unsigned int>(n);
115 }
116
117 40 size_t chunk = n / num_threads;
118 40 size_t remainder = n % num_threads;
119 size_t start = 0;
120
121
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 std::vector<std::thread> threads;
122
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 std::vector<BestState> results(num_threads, BestState{.point = Point(), .valid = false});
123
124
2/2
✓ Branch 0 taken 160 times.
✓ Branch 1 taken 40 times.
 200 for (unsigned int i = 0; i < num_threads; ++i) {
125
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 120 times.
 160 size_t end = start + chunk + (i < remainder ? 1 : 0);
126 160 threads.emplace_back(
127
1/4
✓ Branch 1 taken 160 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 160 [this, &results, i, start, end, current]() { results[i] = FindBestInRange(input_, current, start, end); });
128 start = end;
129 }
130
131
2/2
✓ Branch 0 taken 160 times.
✓ Branch 1 taken 40 times.
 200 for (auto &t : threads) {
132
1/2
✓ Branch 1 taken 160 times.
✗ Branch 2 not taken.
 160 t.join();
133 }
134
135 40 BestState final_best{.point = Point(), .valid = false};
136
2/2
✓ Branch 0 taken 160 times.
✓ Branch 1 taken 40 times.
 200 for (const auto &best : results) {
137 160 final_best = CombineBestStates(final_best, best, current);
138 }
139
140
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 40 return final_best.valid ? final_best.point : current;
141 40 }
142
143 ✗ double OrehovNJarvisPassSTL::CheckLeft(Point a, Point b, Point c) {
144
4/4
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 56 times.
✓ Branch 2 taken 56 times.
✓ Branch 3 taken 32 times.
 200 return ((b.x - a.x) * (c.y - a.y)) - ((b.y - a.y) * (c.x - a.x));
145 }
146
147 ✗ Point OrehovNJarvisPassSTL::FindFirstElem() const {
148 ✗ Point current = input_[0];
149
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 56 times.
✓ Branch 3 taken 8 times.
 64 for (const auto &f : input_) {
150
2/12
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 56 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 56 times.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
 56 if (f.x < current.x || (f.y < current.y && f.x == current.x)) {
151 ✗ current = f;
152 }
153 }
154 ✗ return current;
155 }
156
157 ✗ double OrehovNJarvisPassSTL::Distance(Point a, Point b) {
158 ✗ return std::sqrt(std::pow(a.y - b.y, 2) + std::pow(a.x - b.x, 2));
159 }
160
161 24 bool OrehovNJarvisPassSTL::PostProcessingImpl() {
162 24 GetOutput() = res_;
163 24 return true;
164 }
165
166 } // namespace orehov_n_jarvis_pass
167