GCC Code Coverage Report

Directory: ./
File: tasks/iskhakov_d_graham_convex_hull/seq/src/ops_seq.cpp
Date: 2026-01-27 01:59:34
Exec Total Coverage
Lines: 43 45 95.6%
Functions: 9 9 100.0%
Branches: 42 56 75.0%
Line Branch Exec Source
1 #include "iskhakov_d_graham_convex_hull/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <cmath>
5 #include <cstddef>
6 #include <utility>
7 #include <vector>
8
9 #include "iskhakov_d_graham_convex_hull/common/include/common.hpp"
10
11 namespace iskhakov_d_graham_convex_hull {
12
13 namespace {
14
15 constexpr double kEpsilon = 1e-9;
16
17 double ComputeOrientation(const Point &p, const Point &q, const Point &r) {
18
2/2
✓ Branch 0 taken 272 times.
✓ Branch 1 taken 608 times.
 880 return ((q.x - p.x) * (r.y - p.y)) - ((q.y - p.y) * (r.x - p.x));
19 }
20
21 double ComputeDistanceSquared(const Point &a, const Point &b) {
22 456 return ((a.x - b.x) * (a.x - b.x)) + ((a.y - b.y) * (a.y - b.y));
23 }
24
25 128 std::size_t FindMinPointIndex(const std::vector<Point> &points) {
26 std::size_t min_index = 0;
27
2/2
✓ Branch 0 taken 1008 times.
✓ Branch 1 taken 128 times.
 1136 for (std::size_t i = 1; i < points.size(); ++i) {
28
4/4
✓ Branch 0 taken 936 times.
✓ Branch 1 taken 72 times.
✓ Branch 2 taken 152 times.
✓ Branch 3 taken 784 times.
 1008 if (points[i].y < points[min_index].y ||
29
4/4
✓ Branch 0 taken 152 times.
✓ Branch 1 taken 784 times.
✓ Branch 2 taken 8 times.
✓ Branch 3 taken 144 times.
 936 (std::abs(points[i].y - points[min_index].y) < kEpsilon && points[i].x < points[min_index].x)) {
30 min_index = i;
31 }
32 }
33 128 return min_index;
34 }
35
36 128 std::vector<Point> FilterCollinearPoints(const std::vector<Point> &points, const Point &pivot) {
37
1/2
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
 128 std::vector<Point> filtered;
38
1/2
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
 128 filtered.reserve(points.size());
39 filtered.push_back(points[0]);
40
41
2/2
✓ Branch 0 taken 736 times.
✓ Branch 1 taken 128 times.
 864 for (std::size_t i = 1; i < points.size(); ++i) {
42
4/4
✓ Branch 0 taken 880 times.
✓ Branch 1 taken 128 times.
✓ Branch 2 taken 272 times.
✓ Branch 3 taken 608 times.
 1008 while (i + 1 < points.size() && std::abs(ComputeOrientation(pivot, points[i], points[i + 1])) < kEpsilon) {
43 ++i;
44 }
45 filtered.push_back(points[i]);
46 }
47
48 128 return filtered;
49 }
50
51
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 96 times.
 128 std::vector<Point> BuildConvexHull(const std::vector<Point> &filtered) {
52
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 96 times.
 128 if (filtered.size() < 3) {
53 32 return filtered;
54 }
55
56
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 std::vector<Point> hull;
57
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 hull.reserve(filtered.size());
58 hull.push_back(filtered[0]);
59 hull.push_back(filtered[1]);
60
61
2/2
✓ Branch 0 taken 608 times.
✓ Branch 1 taken 96 times.
 704 for (std::size_t i = 2; i < filtered.size(); ++i) {
62
1/2
✓ Branch 0 taken 864 times.
✗ Branch 1 not taken.
 864 while (hull.size() >= 2) {
63 const std::size_t last = hull.size() - 1;
64 const double orient = ComputeOrientation(hull[last - 1], hull[last], filtered[i]);
65
66
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 608 times.
 864 if (orient > kEpsilon) {
67 break;
68 }
69
70 hull.pop_back();
71 }
72 hull.push_back(filtered[i]);
73 }
74
75 return hull;
76 }
77
78 } // namespace
79
80
1/2
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
 128 IskhakovDGrahamConvexHullSEQ::IskhakovDGrahamConvexHullSEQ(const InType &in) {
81 SetTypeOfTask(GetStaticTypeOfTask());
82
1/2
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
 128 GetInput() = in;
83 128 GetOutput() = OutType{};
84 128 }
85
86 128 bool IskhakovDGrahamConvexHullSEQ::ValidationImpl() {
87 128 return GetInput().size() >= 3;
88 }
89
90 128 bool IskhakovDGrahamConvexHullSEQ::PreProcessingImpl() {
91 128 return true;
92 }
93
94
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 128 times.
 128 bool IskhakovDGrahamConvexHullSEQ::RunImpl() {
95 const std::vector<Point> &input_points = GetInput();
96
97
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 128 times.
 128 if (input_points.size() < 3) {
98 ✗ GetOutput() = input_points;
99 ✗ return true;
100 }
101
102 128 std::vector<Point> points{input_points};
103 128 const std::size_t min_index = FindMinPointIndex(points);
104 std::swap(points[0], points[min_index]);
105 128 const Point pivot = points[0];
106
107 4192 std::sort(points.begin() + 1, points.end(), [&pivot](const Point &a, const Point &b) {
108
2/2
✓ Branch 0 taken 456 times.
✓ Branch 1 taken 3608 times.
 4064 const double orient = ComputeOrientation(pivot, a, b);
109
2/2
✓ Branch 0 taken 456 times.
✓ Branch 1 taken 3608 times.
 4064 if (std::abs(orient) < kEpsilon) {
110 const double dist_a = ComputeDistanceSquared(a, pivot);
111 const double dist_b = ComputeDistanceSquared(b, pivot);
112 456 return dist_a < dist_b;
113 }
114 3608 return orient > 0.0;
115 });
116
117
1/2
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
 128 const std::vector<Point> filtered = FilterCollinearPoints(points, pivot);
118
119
2/6
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 128 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 256 GetOutput() = BuildConvexHull(filtered);
120 return true;
121 }
122
123 128 bool IskhakovDGrahamConvexHullSEQ::PostProcessingImpl() {
124 128 return true;
125 }
126
127 } // namespace iskhakov_d_graham_convex_hull
128