GCC Code Coverage Report

Directory: ./
File: tasks/konstantinov_s_graham/omp/src/ops_omp.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 82 87 94.3%
Functions: 11 13 84.6%
Branches: 63 112 56.2%
Line Branch Exec Source
1 #include "konstantinov_s_graham/omp/include/ops_omp.hpp"
2
3 #include <omp.h>
4
5 #include <algorithm>
6 #include <cstddef>
7 #include <ranges>
8 #include <utility>
9 #include <vector>
10
11 #include "konstantinov_s_graham/common/include/common.hpp"
12
13 namespace konstantinov_s_graham {
14
15
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 KonstantinovAGrahamOMP::KonstantinovAGrahamOMP(const InType &in) {
16 SetTypeOfTask(GetStaticTypeOfTask());
17 GetInput() = in;
18 40 }
19
20 40 bool KonstantinovAGrahamOMP::ValidationImpl() {
21 40 return GetInput().first.size() == GetInput().second.size();
22 }
23
24 40 bool KonstantinovAGrahamOMP::PreProcessingImpl() {
25 40 return true;
26 }
27
28 40 void KonstantinovAGrahamOMP::RemoveDuplicates(std::vector<double> &xs, std::vector<double> &ys) {
29
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 std::vector<std::pair<double, double>> pts;
30
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 pts.reserve(xs.size());
31
2/2
✓ Branch 0 taken 176 times.
✓ Branch 1 taken 40 times.
 216 for (size_t i = 0; i < xs.size(); ++i) {
32
1/2
✓ Branch 1 taken 176 times.
✗ Branch 2 not taken.
 176 pts.emplace_back(xs[i], ys[i]);
33 }
34
35 std::ranges::sort(pts, [](const auto &a, const auto &b) {
36
4/24
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 208 times.
✓ Branch 5 taken 36 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 124 times.
✓ Branch 23 taken 16 times.
 384 if (std::abs(a.first - b.first) > kKEps) {
37 332 return a.first < b.first;
38 }
39 52 return a.second < b.second;
40 });
41
42 auto new_end = std::ranges::unique(pts, [](const auto &a, const auto &b) {
43
8/8
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 92 times.
✓ Branch 2 taken 24 times.
✓ Branch 3 taken 8 times.
✓ Branch 4 taken 8 times.
✓ Branch 5 taken 8 times.
✓ Branch 6 taken 4 times.
✓ Branch 7 taken 4 times.
 140 return std::abs(a.first - b.first) < kKEps && std::abs(a.second - b.second) < kKEps;
44 });
45
46 pts.erase(new_end.begin(), pts.end());
47
48
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 xs.resize(pts.size());
49
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 ys.resize(pts.size());
50
51
2/2
✓ Branch 0 taken 164 times.
✓ Branch 1 taken 40 times.
 204 for (size_t i = 0; i < pts.size(); ++i) {
52 164 xs[i] = pts[i].first;
53 164 ys[i] = pts[i].second;
54 }
55 40 }
56
57 ✗ size_t KonstantinovAGrahamOMP::FindAnchorIndex(const std::vector<double> &xs, const std::vector<double> &ys) {
58 size_t idx = 0;
59 28 #pragma omp parallel default(none) shared(xs, ys, idx)
60 {
61 size_t local_idx = idx;
62
63 #pragma omp for nowait
64 for (size_t i = 1; i < xs.size(); ++i) {
65 if (ys[i] < ys[local_idx] - kKEps || (std::abs(ys[i] - ys[local_idx]) < kKEps && xs[i] < xs[local_idx] - kKEps)) {
66 local_idx = i;
67 }
68 }
69
70 #pragma omp critical
71 {
72 if (ys[local_idx] < ys[idx] - kKEps ||
73 (std::abs(ys[local_idx] - ys[idx]) < kKEps && xs[local_idx] < xs[idx] - kKEps)) {
74 idx = local_idx;
75 }
76 }
77 }
78
79 ✗ return idx;
80 }
81
82 ✗ double KonstantinovAGrahamOMP::Dist2(const std::vector<double> &xs, const std::vector<double> &ys, size_t i, size_t j) {
83 28 const double dx = xs[j] - xs[i];
84 28 const double dy = ys[j] - ys[i];
85 28 return (dx * dx) + (dy * dy);
86 }
87
88 440 double KonstantinovAGrahamOMP::CrossVal(const std::vector<double> &xs, const std::vector<double> &ys, size_t i,
89 size_t j, size_t k) {
90 440 const double ax = xs[j] - xs[i];
91 440 const double ay = ys[j] - ys[i];
92 440 const double bx = xs[k] - xs[i];
93 440 const double by = ys[k] - ys[i];
94 440 return (ax * by) - (ay * bx);
95 }
96
97 28 std::vector<size_t> KonstantinovAGrahamOMP::CollectAndSortIndices(const std::vector<double> &xs,
98 const std::vector<double> &ys, size_t anchor_idx) {
99 28 std::vector<size_t> idxs(xs.size() - 1);
100 28 #pragma omp parallel for default(none) shared(xs, idxs, anchor_idx)
101 for (size_t i = 0; i < xs.size(); ++i) {
102 if (i < anchor_idx) {
103 idxs[i] = i;
104 } else if (i > anchor_idx) {
105 idxs[i - 1] = i;
106 }
107 }
108
109 212 std::ranges::sort(idxs, [&](size_t a, size_t b) {
110
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 184 times.
 212 double cr = CrossVal(xs, ys, anchor_idx, a, b);
111
112
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 184 times.
 212 if (std::abs(cr) < kKEps) {
113 28 return Dist2(xs, ys, anchor_idx, a) < Dist2(xs, ys, anchor_idx, b);
114 }
115
116 184 return cr > 0;
117 });
118
119 28 return idxs;
120 }
121
122
1/2
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
 28 bool KonstantinovAGrahamOMP::AllCollinearWithAnchor(const std::vector<double> &xs, const std::vector<double> &ys,
123 size_t anchor_idx, const std::vector<size_t> &sorted_idxs) {
124
1/2
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
 28 if (sorted_idxs.empty()) {
125 return true;
126 }
127
128 28 bool result = true;
129 28 #pragma omp parallel for default(none) shared(xs, ys, sorted_idxs, anchor_idx, result)
130 for (size_t i = 1; i < sorted_idxs.size(); ++i) {
131 if (std::abs(CrossVal(xs, ys, anchor_idx, sorted_idxs[0], sorted_idxs[i])) > kKEps) {
132 #pragma omp atomic write
133 result = false;
134 }
135 }
136
137 28 return result;
138 }
139
140 24 std::vector<std::pair<double, double>> KonstantinovAGrahamOMP::BuildHullFromSorted(
141 const std::vector<double> &xs, const std::vector<double> &ys, size_t anchor_idx,
142 const std::vector<size_t> &sorted_idxs) {
143
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 std::vector<size_t> stack;
144
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 stack.reserve(sorted_idxs.size() + 1);
145 stack.push_back(anchor_idx);
146
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 if (!sorted_idxs.empty()) {
147 stack.push_back(sorted_idxs[0]);
148 }
149
150
2/2
✓ Branch 0 taken 92 times.
✓ Branch 1 taken 24 times.
 116 for (size_t i = 1; i < sorted_idxs.size(); ++i) {
151 92 size_t cur = sorted_idxs[i];
152
1/2
✓ Branch 0 taken 132 times.
✗ Branch 1 not taken.
 132 while (stack.size() >= 2) {
153
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 92 times.
 132 size_t q = stack.back();
154 132 size_t p = stack[stack.size() - 2];
155 132 double cr = CrossVal(xs, ys, p, q, cur);
156
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 92 times.
 132 if (cr <= kKEps) {
157 stack.pop_back();
158 } else {
159 break;
160 }
161 }
162 stack.push_back(cur);
163 }
164
165
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 std::vector<std::pair<double, double>> hull;
166
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 hull.reserve(stack.size());
167
3/4
✓ Branch 1 taken 100 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 100 times.
✓ Branch 4 taken 24 times.
 124 for (size_t id : stack) {
168
1/2
✓ Branch 1 taken 100 times.
✗ Branch 2 not taken.
 100 hull.emplace_back(xs[id], ys[id]);
169 }
170 24 return hull;
171 }
172
173 40 bool KonstantinovAGrahamOMP::RunImpl() {
174 const InType &inp = GetInput();
175 40 auto xs = inp.first;
176
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 auto ys = inp.second;
177
178
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 RemoveDuplicates(xs, ys);
179
180
3/4
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 36 times.
 40 if (xs.size() != ys.size() || xs.empty()) {
181 GetOutput() = {};
182 return true;
183 }
184
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 28 times.
 36 if (xs.size() < 3) {
185
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 std::vector<std::pair<double, double>> out;
186
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 out.reserve(xs.size());
187
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 8 times.
 20 for (size_t i = 0; i < xs.size(); ++i) {
188
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 out.emplace_back(xs[i], ys[i]);
189 }
190
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 GetOutput() = out;
191 return true;
192 }
193
194 size_t anchor = FindAnchorIndex(xs, ys);
195
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 std::vector<size_t> sorted_idxs = CollectAndSortIndices(xs, ys, anchor);
196
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
 28 if (sorted_idxs.empty()) {
197 ✗ GetOutput() = {{xs[anchor], ys[anchor]}};
198 ✗ return true;
199 }
200
201
2/2
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 24 times.
 28 if (AllCollinearWithAnchor(xs, ys, anchor, sorted_idxs)) {
202
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 size_t far_idx = sorted_idxs.back();
203 4 GetOutput() = {{xs[anchor], ys[anchor]}, {xs[far_idx], ys[far_idx]}};
204 4 return true;
205 }
206
207
1/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 24 GetOutput() = BuildHullFromSorted(xs, ys, anchor, sorted_idxs);
208
209 24 return true;
210 }
211
212 40 bool KonstantinovAGrahamOMP::PostProcessingImpl() {
213 40 return true;
214 }
215
216 } // namespace konstantinov_s_graham
217