GCC Code Coverage Report

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