GCC Code Coverage Report

Directory: ./
File: tasks/egorova_l_binary_convex_hull/seq/src/ops_seq.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 63 65 96.9%
Functions: 10 10 100.0%
Branches: 56 82 68.3%
Line Branch Exec Source
1 #include "egorova_l_binary_convex_hull/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <cstdint>
6 #include <stack>
7 #include <tuple>
8 #include <utility> // для std::move
9 #include <vector>
10
11 #include "egorova_l_binary_convex_hull/common/include/common.hpp"
12
13 namespace {
14
15 using Point = egorova_l_binary_convex_hull::Point;
16
17 int64_t CrossProduct(const Point &a, const Point &b, const Point &c) {
18 1344 return (static_cast<int64_t>(b.x - a.x) * (c.y - a.y)) - (static_cast<int64_t>(b.y - a.y) * (c.x - a.x));
19 }
20
21 // Helper function for building lower hull
22 72 void BuildLowerHull(const std::vector<Point> &points, size_t n, std::vector<Point> &hull) {
23
2/2
✓ Branch 0 taken 616 times.
✓ Branch 1 taken 72 times.
 688 for (size_t i = 0; i < n; ++i) {
24
2/2
✓ Branch 0 taken 672 times.
✓ Branch 1 taken 360 times.
 1032 while (hull.size() >= 2) {
25 const Point &a = hull[hull.size() - 2];
26 const Point &b = hull.back();
27
2/2
✓ Branch 0 taken 416 times.
✓ Branch 1 taken 256 times.
 672 if (CrossProduct(a, b, points[i]) <= 0) {
28 hull.pop_back();
29 } else {
30 break;
31 }
32 }
33 hull.push_back(points[i]);
34 }
35 72 }
36
37 // Helper function for building upper hull
38 72 void BuildUpperHull(const std::vector<Point> &points, size_t n, size_t lower_size, std::vector<Point> &hull) {
39
2/2
✓ Branch 0 taken 544 times.
✓ Branch 1 taken 72 times.
 616 for (size_t i = n - 1; i > 0; --i) {
40 544 const size_t idx = i - 1;
41
2/2
✓ Branch 0 taken 672 times.
✓ Branch 1 taken 288 times.
 960 while (hull.size() > lower_size) {
42 const Point &a = hull[hull.size() - 2];
43 const Point &b = hull.back();
44
2/2
✓ Branch 0 taken 416 times.
✓ Branch 1 taken 256 times.
 672 if (CrossProduct(a, b, points[idx]) <= 0) {
45 hull.pop_back();
46 } else {
47 break;
48 }
49 }
50 hull.push_back(points[idx]);
51 }
52 72 }
53
54
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 72 times.
 72 void BuildConvexHull(std::vector<Point> &points, std::vector<Point> &hull) {
55 const size_t n = points.size();
56
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 72 times.
 72 if (n <= 2) {
57 ✗ hull.assign(points.begin(), points.end());
58 ✗ return;
59 }
60
61 // Sort points in-place
62 std::ranges::sort(points,
63 [](const Point &lhs, const Point &rhs) { return std::tie(lhs.x, lhs.y) < std::tie(rhs.x, rhs.y); });
64
65 hull.clear();
66 72 hull.reserve(n + 1); // Reserve space to avoid reallocations
67
68 // Build lower hull
69 72 BuildLowerHull(points, n, hull);
70
71 // Build upper hull
72 const size_t lower_size = hull.size();
73 72 BuildUpperHull(points, n, lower_size, hull);
74
75 // Remove the last point if it's the same as the first (closed polygon)
76
3/6
✓ Branch 0 taken 72 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 72 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 72 times.
✗ Branch 5 not taken.
 72 if (hull.size() > 1 && hull.front().x == hull.back().x && hull.front().y == hull.back().y) {
77 hull.pop_back();
78 }
79 }
80
81 // Helper function to process a single direction
82 2464 inline void TryAddNeighbor(const std::vector<uint8_t> &image, int width, int height, int next_x, int next_y, int label,
83 std::vector<int> &labels, std::stack<Point> &stack) {
84
2/4
✓ Branch 0 taken 2464 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2464 times.
✗ Branch 3 not taken.
 2464 if (next_x >= 0 && next_x < width && next_y >= 0 && next_y < height) {
85
2/2
✓ Branch 0 taken 1600 times.
✓ Branch 1 taken 864 times.
 2464 const size_t next_index = (static_cast<size_t>(next_y) * static_cast<size_t>(width)) + static_cast<size_t>(next_x);
86
4/4
✓ Branch 0 taken 1600 times.
✓ Branch 1 taken 864 times.
✓ Branch 2 taken 544 times.
✓ Branch 3 taken 1056 times.
 2464 if (image[next_index] != 0 && labels[next_index] == 0) {
87 544 labels[next_index] = label;
88 544 stack.push({next_x, next_y});
89 }
90 }
91 2464 }
92
93 72 void ProcessComponent(const std::vector<uint8_t> &image, int width, int height, int start_x, int start_y, int label,
94 std::vector<int> &labels, std::vector<Point> &component_points) {
95 std::stack<Point> stack;
96
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 stack.push({start_x, start_y});
97
98
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 72 times.
 72 const size_t start_index = (static_cast<size_t>(start_y) * static_cast<size_t>(width)) + static_cast<size_t>(start_x);
99
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 72 times.
 72 labels[start_index] = label;
100
101 component_points.clear();
102
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 component_points.reserve(100); // Reserve some space to avoid reallocations
103
104
2/2
✓ Branch 0 taken 616 times.
✓ Branch 1 taken 72 times.
 688 while (!stack.empty()) {
105
1/2
✓ Branch 0 taken 616 times.
✗ Branch 1 not taken.
 616 const Point current = stack.top();
106 stack.pop();
107 component_points.push_back(current);
108
109 // Process all 4 directions using helper function
110
1/2
✓ Branch 1 taken 616 times.
✗ Branch 2 not taken.
 616 TryAddNeighbor(image, width, height, current.x + 1, current.y, label, labels, stack);
111
1/2
✓ Branch 1 taken 616 times.
✗ Branch 2 not taken.
 616 TryAddNeighbor(image, width, height, current.x - 1, current.y, label, labels, stack);
112
1/2
✓ Branch 1 taken 616 times.
✗ Branch 2 not taken.
 616 TryAddNeighbor(image, width, height, current.x, current.y + 1, label, labels, stack);
113
1/2
✓ Branch 1 taken 616 times.
✗ Branch 2 not taken.
 616 TryAddNeighbor(image, width, height, current.x, current.y - 1, label, labels, stack);
114 }
115 72 }
116
117 } // namespace
118
119 namespace egorova_l_binary_convex_hull {
120
121
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 BinaryConvexHullSEQ::BinaryConvexHullSEQ(const InType &in) {
122 SetTypeOfTask(GetStaticTypeOfTask());
123 GetInput() = in;
124 56 }
125
126 56 bool BinaryConvexHullSEQ::ValidationImpl() {
127 const auto &input = GetInput();
128
3/6
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 56 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 56 times.
 56 return input.width > 0 && input.height > 0 && !input.data.empty();
129 }
130
131
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 bool BinaryConvexHullSEQ::PreProcessingImpl() {
132 GetOutput().clear();
133 56 return true;
134 }
135
136 56 bool BinaryConvexHullSEQ::RunImpl() {
137 56 const int width = GetInput().width;
138 56 const int height = GetInput().height;
139 56 const auto &image = GetInput().data;
140 56 const size_t image_size = static_cast<size_t>(width) * static_cast<size_t>(height);
141
142
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 56 times.
 56 std::vector<int> labels(image_size, 0);
143 int label_counter = 0;
144
145 // Clear output and reserve some space
146 auto &output = GetOutput();
147 output.clear();
148
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 output.reserve(10); // Reserve space for expected number of components
149
150
2/2
✓ Branch 0 taken 840 times.
✓ Branch 1 taken 56 times.
 896 for (int row = 0; row < height; ++row) {
151
2/2
✓ Branch 0 taken 15400 times.
✓ Branch 1 taken 840 times.
 16240 for (int col = 0; col < width; ++col) {
152
2/2
✓ Branch 0 taken 616 times.
✓ Branch 1 taken 14784 times.
 15400 const size_t index = (static_cast<size_t>(row) * static_cast<size_t>(width)) + static_cast<size_t>(col);
153
4/4
✓ Branch 0 taken 616 times.
✓ Branch 1 taken 14784 times.
✓ Branch 2 taken 72 times.
✓ Branch 3 taken 544 times.
 15400 if (image[index] != 0 && labels[index] == 0) {
154 72 ++label_counter;
155 72 std::vector<Point> component_points;
156
157
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 ProcessComponent(image, width, height, col, row, label_counter, labels, component_points);
158
159
1/2
✓ Branch 0 taken 72 times.
✗ Branch 1 not taken.
 72 if (!component_points.empty()) {
160 72 std::vector<Point> hull;
161
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 BuildConvexHull(component_points, hull);
162 output.push_back(std::move(hull));
163 }
164 }
165 }
166 }
167 56 return true;
168 }
169
170 56 bool BinaryConvexHullSEQ::PostProcessingImpl() {
171 56 return true;
172 }
173
174 } // namespace egorova_l_binary_convex_hull
175