GCC Code Coverage Report

Directory: ./
File: tasks/tsarkov_k_jarvis_convex_hull/seq/src/ops_seq.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 51 51 100.0%
Functions: 9 9 100.0%
Branches: 35 46 76.1%
Line Branch Exec Source
1 #include "tsarkov_k_jarvis_convex_hull/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <cstdint>
6 #include <ranges>
7 #include <vector>
8
9 #include "tsarkov_k_jarvis_convex_hull/common/include/common.hpp"
10
11 namespace tsarkov_k_jarvis_convex_hull {
12
13 namespace {
14
15 std::int64_t CrossProduct(const Point &first_point, const Point &second_point, const Point &third_point) {
16 560 const std::int64_t vector_first_x =
17 560 static_cast<std::int64_t>(second_point.x) - static_cast<std::int64_t>(first_point.x);
18 560 const std::int64_t vector_first_y =
19 560 static_cast<std::int64_t>(second_point.y) - static_cast<std::int64_t>(first_point.y);
20 560 const std::int64_t vector_second_x =
21 560 static_cast<std::int64_t>(third_point.x) - static_cast<std::int64_t>(first_point.x);
22 560 const std::int64_t vector_second_y =
23 560 static_cast<std::int64_t>(third_point.y) - static_cast<std::int64_t>(first_point.y);
24
25 560 return (vector_first_x * vector_second_y) - (vector_first_y * vector_second_x);
26 }
27
28 std::int64_t SquaredDistance(const Point &first_point, const Point &second_point) {
29 const std::int64_t delta_x = static_cast<std::int64_t>(second_point.x) - static_cast<std::int64_t>(first_point.x);
30 const std::int64_t delta_y = static_cast<std::int64_t>(second_point.y) - static_cast<std::int64_t>(first_point.y);
31
32 232 return (delta_x * delta_x) + (delta_y * delta_y);
33 }
34
35 568 bool PointLess(const Point &first_point, const Point &second_point) {
36
2/2
✓ Branch 0 taken 440 times.
✓ Branch 1 taken 128 times.
 568 if (first_point.x != second_point.x) {
37 440 return first_point.x < second_point.x;
38 }
39 128 return first_point.y < second_point.y;
40 }
41
42 56 std::vector<Point> RemoveDuplicatePoints(const std::vector<Point> &input_points) {
43 56 std::vector<Point> unique_points = input_points;
44
45 std::ranges::sort(unique_points, PointLess);
46 unique_points.erase(std::ranges::unique(unique_points).begin(), unique_points.end());
47
48 56 return unique_points;
49 }
50
51 40 std::size_t FindLeftmostPointIndex(const std::vector<Point> &input_points) {
52 std::size_t leftmost_point_index = 0;
53
54
2/2
✓ Branch 0 taken 160 times.
✓ Branch 1 taken 40 times.
 200 for (std::size_t point_index = 1; point_index < input_points.size(); ++point_index) {
55 const Point &current_point = input_points[point_index];
56 const Point &leftmost_point = input_points[leftmost_point_index];
57
58
3/4
✓ Branch 0 taken 160 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 144 times.
✓ Branch 3 taken 16 times.
 160 if ((current_point.x < leftmost_point.x) ||
59
1/2
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
 16 ((current_point.x == leftmost_point.x) && (current_point.y < leftmost_point.y))) {
60 leftmost_point_index = point_index;
61 }
62 }
63
64 40 return leftmost_point_index;
65 }
66
67 136 std::size_t FindNextHullPointIndex(const std::vector<Point> &unique_points, std::size_t current_point_index) {
68
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 40 times.
 136 std::size_t next_point_index = (current_point_index == 0) ? 1 : 0;
69
70
2/2
✓ Branch 0 taken 696 times.
✓ Branch 1 taken 136 times.
 832 for (std::size_t point_index = 0; point_index < unique_points.size(); ++point_index) {
71
2/2
✓ Branch 0 taken 136 times.
✓ Branch 1 taken 560 times.
 696 if (point_index == current_point_index) {
72 136 continue;
73 }
74
75 const std::int64_t orientation =
76 CrossProduct(unique_points[current_point_index], unique_points[next_point_index], unique_points[point_index]);
77
78
2/2
✓ Branch 0 taken 424 times.
✓ Branch 1 taken 136 times.
 560 if (orientation < 0) {
79 next_point_index = point_index;
80
2/2
✓ Branch 0 taken 232 times.
✓ Branch 1 taken 192 times.
 424 } else if (orientation == 0) {
81 const std::int64_t current_distance =
82 SquaredDistance(unique_points[current_point_index], unique_points[next_point_index]);
83 const std::int64_t candidate_distance =
84 SquaredDistance(unique_points[current_point_index], unique_points[point_index]);
85
86
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 40 times.
 232 if (candidate_distance > current_distance) {
87 next_point_index = point_index;
88 }
89 }
90 }
91
92 136 return next_point_index;
93 }
94
95 } // namespace
96
97
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 TsarkovKJarvisConvexHullSEQ::TsarkovKJarvisConvexHullSEQ(const InType &input_points) {
98 SetTypeOfTask(GetStaticTypeOfTask());
99
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 GetInput() = input_points;
100 GetOutput().clear();
101 56 }
102
103
1/2
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
 56 bool TsarkovKJarvisConvexHullSEQ::ValidationImpl() {
104
2/4
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 56 times.
 56 return !GetInput().empty() && GetOutput().empty();
105 }
106
107
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 bool TsarkovKJarvisConvexHullSEQ::PreProcessingImpl() {
108 GetOutput().clear();
109 56 return true;
110 }
111
112 56 bool TsarkovKJarvisConvexHullSEQ::RunImpl() {
113 56 const std::vector<Point> unique_points = RemoveDuplicatePoints(GetInput());
114
115
1/2
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
 56 if (unique_points.empty()) {
116 return false;
117 }
118
119
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 48 times.
 56 if (unique_points.size() == 1) {
120
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 GetOutput() = unique_points;
121 return true;
122 }
123
124
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 40 times.
 48 if (unique_points.size() == 2) {
125
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 GetOutput() = unique_points;
126 return true;
127 }
128
129 40 const std::size_t start_point_index = FindLeftmostPointIndex(unique_points);
130 std::size_t current_point_index = start_point_index;
131
132 while (true) {
133 GetOutput().push_back(unique_points[current_point_index]);
134
135 136 current_point_index = FindNextHullPointIndex(unique_points, current_point_index);
136
137
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 40 times.
 136 if (current_point_index == start_point_index) {
138 break;
139 }
140 }
141
142 40 return !GetOutput().empty();
143 }
144
145 56 bool TsarkovKJarvisConvexHullSEQ::PostProcessingImpl() {
146 56 return true;
147 }
148
149 } // namespace tsarkov_k_jarvis_convex_hull
150