GCC Code Coverage Report

Directory: ./
File: tasks/nalitov_d_dijkstras_algorithm_seq/seq/src/ops_seq.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 49 55 89.1%
Functions: 7 7 100.0%
Branches: 33 52 63.5%
Line Branch Exec Source
1 #include "nalitov_d_dijkstras_algorithm_seq/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <limits>
5 #include <vector>
6
7 #include "nalitov_d_dijkstras_algorithm_seq/common/include/common.hpp"
8
9 namespace nalitov_d_dijkstras_algorithm_seq {
10
11 namespace {
12
13 inline bool SafeAdd(InType a, InType b, InType &result) {
14
3/4
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 72 times.
✓ Branch 2 taken 104 times.
✗ Branch 3 not taken.
 176 if (a > 0 && b > std::numeric_limits<InType>::max() - a) {
15 return false;
16 }
17 if (a < 0 && b < std::numeric_limits<InType>::min() - a) {
18 return false;
19 }
20 176 result = a + b;
21 return true;
22 }
23
24 inline InType GetEdgeWeight(InType from, InType to) {
25 if (from == to) {
26 return 0;
27 }
28
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 176 times.
 176 return (from > to) ? (from - to) : (to - from);
29 }
30
31 96 InType FindMinDistanceVertex(const std::vector<InType> &distances, const std::vector<bool> &processed,
32 InType k_infinity) {
33 InType min_distance = k_infinity;
34 InType current_vertex = -1;
35 96 const auto num_vertices = static_cast<InType>(distances.size());
36
37
2/2
✓ Branch 0 taken 448 times.
✓ Branch 1 taken 96 times.
 544 for (InType vertex_idx = 0; vertex_idx < num_vertices; ++vertex_idx) {
38
4/4
✓ Branch 0 taken 272 times.
✓ Branch 1 taken 176 times.
✓ Branch 2 taken 176 times.
✓ Branch 3 taken 96 times.
 448 if (!processed[vertex_idx] && distances[vertex_idx] < min_distance) {
39 min_distance = distances[vertex_idx];
40 current_vertex = vertex_idx;
41 }
42 }
43
44 96 return current_vertex;
45 }
46
47 96 void RelaxEdges(InType current_vertex, std::vector<InType> &distances, const std::vector<bool> &processed,
48 InType k_infinity) {
49 96 const auto num_vertices = static_cast<InType>(distances.size());
50
51
2/2
✓ Branch 0 taken 448 times.
✓ Branch 1 taken 96 times.
 544 for (InType neighbor = 0; neighbor < num_vertices; ++neighbor) {
52
3/4
✓ Branch 0 taken 176 times.
✓ Branch 1 taken 272 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 176 times.
 448 if (processed[neighbor] || neighbor == current_vertex) {
53 272 continue;
54 }
55
56 const InType edge_weight = GetEdgeWeight(current_vertex, neighbor);
57
58
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 176 times.
 176 if (distances[current_vertex] == k_infinity) {
59 ✗ continue;
60 }
61
62 InType new_distance = 0;
63 ✗ if (!SafeAdd(distances[current_vertex], edge_weight, new_distance)) {
64 ✗ continue;
65 }
66
67
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 176 times.
 176 distances[neighbor] = std::min(new_distance, distances[neighbor]);
68 }
69 96 }
70
71 OutType CalculateTotalDistance(const std::vector<InType> &distances, InType k_infinity) {
72 OutType total_sum = 0;
73 24 const auto num_vertices = static_cast<InType>(distances.size());
74
75
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 24 times.
 120 for (InType vertex_idx = 0; vertex_idx < num_vertices; ++vertex_idx) {
76
1/2
✓ Branch 0 taken 96 times.
✗ Branch 1 not taken.
 96 if (distances[vertex_idx] != k_infinity) {
77
1/2
✓ Branch 0 taken 96 times.
✗ Branch 1 not taken.
 96 if (total_sum > std::numeric_limits<OutType>::max() - distances[vertex_idx]) {
78 return -1; // Overflow indicator
79 }
80 96 total_sum += distances[vertex_idx];
81 }
82 }
83
84 return total_sum;
85 }
86
87 } // namespace
88
89 24 NalitovDDijkstrasAlgorithmSeq::NalitovDDijkstrasAlgorithmSeq(const InType &in) {
90 SetTypeOfTask(GetStaticTypeOfTask());
91 24 GetInput() = in;
92 GetOutput() = 0;
93 24 }
94
95 24 bool NalitovDDijkstrasAlgorithmSeq::ValidationImpl() {
96 24 const InType n = GetInput();
97
98 constexpr InType kMaxVertices = 10000;
99
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 if (n <= 0 || n > kMaxVertices) {
100 return false;
101 }
102
103
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (GetOutput() != 0) {
104 ✗ return false;
105 }
106
107 return true;
108 }
109
110 24 bool NalitovDDijkstrasAlgorithmSeq::PreProcessingImpl() {
111 24 GetOutput() = 0;
112 24 return true;
113 }
114
115 24 bool NalitovDDijkstrasAlgorithmSeq::RunImpl() {
116 24 const InType n = GetInput();
117
118
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 if (n <= 0) {
119 return false;
120 }
121
122
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (n == 1) {
123 ✗ GetOutput() = 0;
124 ✗ return true;
125 }
126
127 if (n < 2) {
128 return false;
129 }
130
131 24 const InType k_infinity = std::numeric_limits<InType>::max();
132 24 std::vector<InType> distances(n, k_infinity);
133
2/6
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 24 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 24 std::vector<bool> processed(n, false);
134
135
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (distances.empty()) {
136 return false;
137 }
138 24 distances[0] = 0;
139
140
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 24 times.
 120 for (InType iteration = 0; iteration < n; ++iteration) {
141 96 const InType current_vertex = FindMinDistanceVertex(distances, processed, k_infinity);
142
143
2/4
✓ Branch 0 taken 96 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 96 times.
✗ Branch 3 not taken.
 96 if (current_vertex == -1 || distances[current_vertex] == k_infinity) {
144 break;
145 }
146
147 processed[current_vertex] = true;
148 96 RelaxEdges(current_vertex, distances, processed, k_infinity);
149 }
150
151 const OutType total_sum = CalculateTotalDistance(distances, k_infinity);
152
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (total_sum < 0) {
153 return false; // Overflow occurred
154 }
155
156 24 GetOutput() = total_sum;
157 24 return true;
158 }
159
160 24 bool NalitovDDijkstrasAlgorithmSeq::PostProcessingImpl() {
161 24 return GetOutput() >= 0;
162 }
163
164 } // namespace nalitov_d_dijkstras_algorithm_seq
165