GCC Code Coverage Report

Directory: ./
File: tasks/gaivoronskiy_m_grachem_method/seq/src/ops_seq.cpp
Date: 2026-01-27 01:59:34
Exec Total Coverage
Lines: 45 45 100.0%
Functions: 9 9 100.0%
Branches: 56 74 75.7%
Line Branch Exec Source
1 #include "gaivoronskiy_m_grachem_method/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <cmath>
5 #include <cstddef>
6 #include <stack>
7 #include <vector>
8
9 #include "gaivoronskiy_m_grachem_method/common/include/common.hpp"
10
11 namespace gaivoronskiy_m_grachem_method {
12
13 namespace {
14 int Orientation(const Point &p, const Point &q, const Point &r) {
15
4/4
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 912 times.
✓ Branch 2 taken 64 times.
✓ Branch 3 taken 584 times.
 1568 double val = ((q.y - p.y) * (r.x - q.x)) - ((q.x - p.x) * (r.y - q.y));
16 constexpr double kEps = 1e-9;
17
6/6
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 912 times.
✓ Branch 2 taken 64 times.
✓ Branch 3 taken 584 times.
✓ Branch 4 taken 112 times.
✓ Branch 5 taken 3376 times.
 5056 if (std::abs(val) < kEps) {
18 return 0;
19 }
20
4/4
✓ Branch 0 taken 376 times.
✓ Branch 1 taken 536 times.
✓ Branch 2 taken 1264 times.
✓ Branch 3 taken 2112 times.
 4288 return (val > 0) ? 1 : 2;
21 }
22
23 double DistSquare(const Point &p1, const Point &p2) {
24 112 return ((p1.x - p2.x) * (p1.x - p2.x)) + ((p1.y - p2.y) * (p1.y - p2.y));
25 }
26
27
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 3376 times.
 3488 bool Compare(const Point &p1, const Point &p2, const Point &p0) {
28 int o = Orientation(p0, p1, p2);
29 if (o == 0) {
30 112 return DistSquare(p0, p1) < DistSquare(p0, p2);
31 }
32 3376 return (o == 2);
33 }
34 } // namespace
35
36
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 GaivoronskiyMGrahamScanSEQ::GaivoronskiyMGrahamScanSEQ(const InType &in) {
37 SetTypeOfTask(GetStaticTypeOfTask());
38
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 GetInput() = in;
39 GetOutput().clear();
40 48 }
41
42 48 bool GaivoronskiyMGrahamScanSEQ::ValidationImpl() {
43 48 return GetInput().size() >= 3;
44 }
45
46 48 bool GaivoronskiyMGrahamScanSEQ::PreProcessingImpl() {
47 48 points_ = GetInput();
48 hull_.clear();
49 48 return !points_.empty();
50 }
51
52 48 size_t GaivoronskiyMGrahamScanSEQ::FindLowestPoint(const std::vector<Point> &pts) {
53 size_t min_idx = 0;
54
2/2
✓ Branch 0 taken 696 times.
✓ Branch 1 taken 48 times.
 744 for (size_t i = 1; i < pts.size(); i++) {
55
5/6
✓ Branch 0 taken 648 times.
✓ Branch 1 taken 48 times.
✓ Branch 2 taken 32 times.
✓ Branch 3 taken 616 times.
✓ Branch 4 taken 32 times.
✗ Branch 5 not taken.
 696 if (pts[i].y < pts[min_idx].y || (pts[i].y == pts[min_idx].y && pts[i].x < pts[min_idx].x)) {
56 min_idx = i;
57 }
58 }
59 48 return min_idx;
60 }
61
62 48 size_t GaivoronskiyMGrahamScanSEQ::RemoveCollinearPoints(std::vector<Point> &pts, const Point &p0) {
63 size_t m = 1;
64
2/2
✓ Branch 0 taken 632 times.
✓ Branch 1 taken 48 times.
 680 for (size_t i = 1; i < pts.size(); i++) {
65
4/4
✓ Branch 0 taken 648 times.
✓ Branch 1 taken 48 times.
✓ Branch 2 taken 64 times.
✓ Branch 3 taken 584 times.
 696 while (i < pts.size() - 1 && Orientation(p0, pts[i], pts[i + 1]) == 0) {
66 i++;
67 }
68 632 pts[m] = pts[i];
69 632 m++;
70 }
71 48 return m;
72 }
73
74 48 std::vector<Point> GaivoronskiyMGrahamScanSEQ::BuildConvexHull(const std::vector<Point> &pts, size_t num_points) {
75 std::stack<Point> s;
76 s.push(pts[0]);
77 s.push(pts[1]);
78 s.push(pts[2]);
79
80
2/2
✓ Branch 0 taken 536 times.
✓ Branch 1 taken 48 times.
 584 for (size_t i = 3; i < num_points; i++) {
81
1/2
✓ Branch 0 taken 536 times.
✗ Branch 1 not taken.
 536 Point top = s.top();
82 s.pop();
83
1/2
✓ Branch 0 taken 920 times.
✗ Branch 1 not taken.
 920 while (!s.empty() && Orientation(s.top(), top, pts[i]) != 2) {
84
1/2
✓ Branch 0 taken 384 times.
✗ Branch 1 not taken.
 384 top = s.top();
85 s.pop();
86 }
87 s.push(top);
88 s.push(pts[i]);
89 }
90
91 48 std::vector<Point> result;
92
2/2
✓ Branch 0 taken 296 times.
✓ Branch 1 taken 48 times.
 344 while (!s.empty()) {
93 result.push_back(s.top());
94 s.pop();
95 }
96
97 std::ranges::reverse(result);
98 48 return result;
99 }
100
101
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 bool GaivoronskiyMGrahamScanSEQ::RunImpl() {
102
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 if (points_.size() < 3) {
103 return false;
104 }
105
106 48 size_t min_idx = FindLowestPoint(points_);
107 std::swap(points_[0], points_[min_idx]);
108 48 const Point p0 = points_[0];
109
110 48 std::sort(points_.begin() + 1, points_.end(),
111
15/24
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 1296 times.
✓ Branch 5 taken 568 times.
✓ Branch 6 taken 200 times.
✓ Branch 7 taken 208 times.
✓ Branch 8 taken 552 times.
✓ Branch 9 taken 208 times.
✓ Branch 10 taken 32 times.
✓ Branch 11 taken 8 times.
✓ Branch 12 taken 8 times.
✓ Branch 13 taken 24 times.
✓ Branch 14 taken 8 times.
✓ Branch 15 taken 16 times.
✓ Branch 16 taken 8 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✓ Branch 22 taken 80 times.
✓ Branch 23 taken 272 times.
 3424 [&p0](const Point &p1, const Point &p2) { return Compare(p1, p2, p0); });
112
113 48 size_t m = RemoveCollinearPoints(points_, p0);
114
115
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 if (m < 3) {
116 return false;
117 }
118
119 96 hull_ = BuildConvexHull(points_, m);
120 48 GetOutput() = hull_;
121
122 return true;
123 }
124
125 48 bool GaivoronskiyMGrahamScanSEQ::PostProcessingImpl() {
126 48 return GetOutput().size() >= 3;
127 }
128
129 } // namespace gaivoronskiy_m_grachem_method
130