GCC Code Coverage Report

Directory: ./
File: tasks/peterson_r_graham_scan_seq/seq/src/ops_seq.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 50 71 70.4%
Functions: 9 13 69.2%
Branches: 29 58 50.0%
Line Branch Exec Source
1 #include "peterson_r_graham_scan_seq/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <cmath>
5 #include <cstddef>
6 #include <numbers>
7 #include <utility>
8 #include <vector>
9
10 #include "peterson_r_graham_scan_seq/common/include/common.hpp"
11
12 namespace peterson_r_graham_scan_seq {
13
14 namespace {
15 constexpr double kTolerance = 1e-12;
16
17 double CalculateOrientation(const Point2D &origin, const Point2D &a, const Point2D &b) {
18 // Добавлены скобки для явного указания порядка операций
19 184 return ((a.coord_x - origin.coord_x) * (b.coord_y - origin.coord_y)) -
20 184 ((a.coord_y - origin.coord_y) * (b.coord_x - origin.coord_x));
21 }
22
23 double CalculateSquaredDistance(const Point2D &first, const Point2D &second) {
24 ✗ const double dx = first.coord_x - second.coord_x;
25 ✗ const double dy = first.coord_y - second.coord_y;
26 // Добавлены скобки для явного указания порядка операций
27 ✗ return (dx * dx) + (dy * dy);
28 }
29
30 // Убрана ссылка на const в члене класса
31 class PointComparator {
32 public:
33 explicit PointComparator(const Point2D *reference) : origin_ptr_(reference) {}
34
35 112 bool operator()(const Point2D &lhs, const Point2D &rhs) const {
36
1/2
✓ Branch 0 taken 112 times.
✗ Branch 1 not taken.
 112 const double orientation = CalculateOrientation(*origin_ptr_, lhs, rhs);
37
1/2
✓ Branch 0 taken 112 times.
✗ Branch 1 not taken.
 112 if (std::abs(orientation) > kTolerance) {
38 112 return orientation > 0;
39 }
40 ✗ return CalculateSquaredDistance(*origin_ptr_, lhs) < CalculateSquaredDistance(*origin_ptr_, rhs);
41 }
42
43 private:
44 const Point2D *origin_ptr_; // Используем указатель вместо ссылки
45 };
46 } // namespace
47
48 24 PetersonGrahamScanner::PetersonGrahamScanner(const InputValue &in) {
49 SetTypeOfTask(GetStaticTypeOfTask());
50 24 GetInput() = in;
51 GetOutput() = 0;
52 24 }
53
54 ✗ void PetersonGrahamScanner::LoadPoints(const PointSet &points) {
55 ✗ input_points_ = points;
56 ✗ external_data_provided_ = true;
57 ✗ }
58
59 ✗ PointSet PetersonGrahamScanner::GetConvexHull() const {
60 ✗ return hull_points_;
61 }
62
63 24 bool PetersonGrahamScanner::ValidationImpl() {
64 24 return GetInput() >= 0;
65 }
66
67
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 bool PetersonGrahamScanner::PreProcessingImpl() {
68 hull_points_.clear();
69
70
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 if (!external_data_provided_) {
71 input_points_.clear();
72 24 const int count = GetInput();
73
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 if (count <= 0) {
74 return true;
75 }
76
77 24 input_points_.reserve(count);
78 24 const double angle_step = 2.0 * std::numbers::pi / count;
79
80
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 24 times.
 144 for (int i = 0; i < count; ++i) {
81 120 const double angle = angle_step * i;
82 120 input_points_.emplace_back(std::cos(angle), std::sin(angle));
83 }
84 }
85
86 return true;
87 }
88
89
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 bool PetersonGrahamScanner::RunImpl() {
90 hull_points_.clear();
91 24 const int total_points = static_cast<int>(input_points_.size());
92
93
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 if (total_points == 0) {
94 return true;
95 }
96
97
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (AreAllPointsIdentical(input_points_)) {
98 ✗ hull_points_.push_back(input_points_.front());
99 ✗ return true;
100 }
101
102
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (total_points < 3) {
103 ✗ hull_points_ = input_points_;
104 ✗ return true;
105 }
106
107 // Find the point with minimum y (and leftmost if tie)
108 24 const std::size_t lowest_idx = FindLowestPoint(input_points_);
109 std::swap(input_points_[0], input_points_[lowest_idx]);
110
111 // Sort remaining points by polar angle
112 24 SortByAngle(input_points_);
113
114 // Graham scan algorithm
115 24 std::vector<Point2D> stack;
116
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 stack.reserve(total_points);
117 stack.push_back(input_points_[0]);
118 stack.push_back(input_points_[1]);
119
120
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 24 times.
 96 for (int i = 2; i < total_points; ++i) {
121
1/2
✓ Branch 0 taken 72 times.
✗ Branch 1 not taken.
 72 while (stack.size() >= 2) {
122 const Point2D &second_last = stack[stack.size() - 2];
123 const Point2D &last = stack.back();
124
125
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 72 times.
 72 if (CalculateOrientation(second_last, last, input_points_[i]) <= kTolerance) {
126 stack.pop_back();
127 } else {
128 break;
129 }
130 }
131
1/2
✓ Branch 0 taken 72 times.
✗ Branch 1 not taken.
 72 stack.push_back(input_points_[i]);
132 }
133
134 24 hull_points_ = std::move(stack);
135 return true;
136 }
137
138 24 bool PetersonGrahamScanner::PostProcessingImpl() {
139 24 GetOutput() = GetInput();
140 24 return true;
141 }
142
143 ✗ double PetersonGrahamScanner::ComputeOrientation(const Point2D &origin, const Point2D &a, const Point2D &b) {
144 ✗ return CalculateOrientation(origin, a, b);
145 }
146
147 ✗ double PetersonGrahamScanner::ComputeDistanceSq(const Point2D &p1, const Point2D &p2) {
148 ✗ return CalculateSquaredDistance(p1, p2);
149 }
150
151
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 bool PetersonGrahamScanner::AreAllPointsIdentical(const PointSet &points) {
152
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (points.empty()) {
153 return true;
154 }
155
156 const Point2D &reference = points[0];
157
158
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 for (std::size_t i = 1; i < points.size(); ++i) {
159
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 24 if (std::abs(points[i].coord_x - reference.coord_x) > kTolerance ||
160 ✗ std::abs(points[i].coord_y - reference.coord_y) > kTolerance) {
161 return false;
162 }
163 }
164
165 return true;
166 }
167
168 24 std::size_t PetersonGrahamScanner::FindLowestPoint(const PointSet &points) {
169 std::size_t lowest = 0;
170
171
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 24 times.
 120 for (std::size_t i = 1; i < points.size(); ++i) {
172
3/4
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 56 times.
 96 if (points[i].coord_y < points[lowest].coord_y ||
173
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 (std::abs(points[i].coord_y - points[lowest].coord_y) < kTolerance &&
174 ✗ points[i].coord_x < points[lowest].coord_x)) {
175 lowest = i;
176 }
177 }
178
179 24 return lowest;
180 }
181
182
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 void PetersonGrahamScanner::SortByAngle(PointSet &points) {
183
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (points.size() < 2) {
184 ✗ return;
185 }
186
187 24 const Point2D origin = points[0];
188 PointComparator comparator(&origin); // Передаем указатель
189 24 std::sort(points.begin() + 1, points.end(), comparator);
190 }
191
192 } // namespace peterson_r_graham_scan_seq
193