GCC Code Coverage Report

Directory: ./
File: tasks/pankov_a_path_dejikstra/stl/src/ops_stl.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 59 59 100.0%
Functions: 7 7 100.0%
Branches: 49 90 54.4%
Line Branch Exec Source
1 #include "pankov_a_path_dejikstra/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <functional>
6 #include <queue>
7 #include <thread>
8 #include <utility>
9 #include <vector>
10
11 #include "pankov_a_path_dejikstra/common/include/common.hpp"
12 #include "util/include/util.hpp"
13
14 namespace pankov_a_path_dejikstra {
15 namespace {
16
17 using AdjList = std::vector<std::vector<std::pair<Vertex, Weight>>>;
18
19 24 OutType DijkstraSeq(Vertex source, const AdjList &adjacency) {
20
1/2
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
 24 OutType distance(adjacency.size(), kInfinity);
21 using QueueNode = std::pair<Weight, Vertex>;
22 std::priority_queue<QueueNode, std::vector<QueueNode>, std::greater<>> min_queue;
23
24
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 distance[source] = 0;
25
1/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 24 min_queue.emplace(0, source);
26
27
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 24 times.
 168 while (!min_queue.empty()) {
28 144 const auto [current_dist, u] = min_queue.top();
29 144 min_queue.pop();
30
31
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 120 times.
 144 if (current_dist != distance[u]) {
32 24 continue;
33 }
34
35
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 120 times.
 248 for (const auto &[v, weight] : adjacency[u]) {
36
3/4
✓ Branch 0 taken 128 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 120 times.
✓ Branch 3 taken 8 times.
 128 if (current_dist <= kInfinity - weight && current_dist + weight < distance[v]) {
37 120 distance[v] = current_dist + weight;
38
1/2
✓ Branch 1 taken 120 times.
✗ Branch 2 not taken.
 120 min_queue.emplace(distance[v], v);
39 }
40 }
41 }
42
43 24 return distance;
44 }
45
46 } // namespace
47
48
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 PankovAPathDejikstraSTL::PankovAPathDejikstraSTL(const InType &in) {
49 SetTypeOfTask(GetStaticTypeOfTask());
50 GetInput() = in;
51 GetOutput().clear();
52 24 }
53
54 24 bool PankovAPathDejikstraSTL::ValidationImpl() {
55 const InType &input = GetInput();
56
2/4
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
 24 if (input.n == 0 || input.source >= input.n) {
57 return false;
58 }
59
60 const auto edge_valid = [&input](const Edge &e) {
61 128 const auto [from, to, weight] = e;
62
3/6
✓ Branch 0 taken 128 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 128 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 128 times.
✗ Branch 5 not taken.
 128 return from < input.n && to < input.n && weight >= 0;
63 };
64 return std::ranges::all_of(input.edges, edge_valid);
65 }
66
67 24 bool PankovAPathDejikstraSTL::PreProcessingImpl() {
68 const InType &input = GetInput();
69 24 adjacency_.assign(input.n, {});
70
71 24 std::vector<Edge> sorted_edges = input.edges;
72
4/22
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✓ Branch 18 taken 16 times.
✓ Branch 19 taken 88 times.
✓ Branch 20 taken 8 times.
✓ Branch 21 taken 88 times.
 200 std::ranges::sort(sorted_edges, [](const Edge &lhs, const Edge &rhs) { return std::get<0>(lhs) < std::get<0>(rhs); });
73
74
1/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 24 std::vector<std::size_t> offsets(input.n + 1, 0);
75 std::size_t edge_idx = 0;
76
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 24 times.
 152 for (Vertex from = 0; from < input.n; from++) {
77 128 offsets[from] = edge_idx;
78
4/4
✓ Branch 0 taken 200 times.
✓ Branch 1 taken 56 times.
✓ Branch 2 taken 128 times.
✓ Branch 3 taken 72 times.
 256 while (edge_idx < sorted_edges.size() && std::get<0>(sorted_edges[edge_idx]) == from) {
79 128 edge_idx++;
80 }
81 }
82 24 offsets[input.n] = edge_idx;
83
84
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 const int num_threads = ppc::util::GetNumThreads();
85
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 if (num_threads <= 0) {
86 return false;
87 }
88
89 auto &adjacency = adjacency_;
90 24 const std::size_t chunk =
91 24 (input.n + static_cast<std::size_t>(num_threads) - 1) / static_cast<std::size_t>(num_threads);
92
93 54 auto worker = [&](std::size_t begin, std::size_t end) {
94
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 54 times.
 182 for (std::size_t from = begin; from < end; ++from) {
95 128 const std::size_t b = offsets[from];
96 128 const std::size_t e = offsets[from + 1];
97 128 adjacency[from].reserve(e - b);
98
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 128 times.
 256 for (std::size_t i = b; i < e; i++) {
99 128 const auto &[edge_from, to, weight] = sorted_edges[i];
100 (void)edge_from;
101 128 adjacency[from].emplace_back(to, weight);
102 }
103 }
104 78 };
105
106 24 std::vector<std::thread> threads;
107
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 threads.reserve(static_cast<std::size_t>(num_threads));
108
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 24 times.
 84 for (int tid = 0; tid < num_threads; ++tid) {
109 60 const std::size_t begin = static_cast<std::size_t>(tid) * chunk;
110
2/2
✓ Branch 0 taken 54 times.
✓ Branch 1 taken 6 times.
 60 const std::size_t end = std::min(begin + chunk, input.n);
111
2/2
✓ Branch 0 taken 54 times.
✓ Branch 1 taken 6 times.
 60 if (begin < end) {
112
1/2
✓ Branch 1 taken 54 times.
✗ Branch 2 not taken.
 54 threads.emplace_back(worker, begin, end);
113 }
114 }
115
2/2
✓ Branch 0 taken 54 times.
✓ Branch 1 taken 24 times.
 78 for (auto &th : threads) {
116
1/2
✓ Branch 1 taken 54 times.
✗ Branch 2 not taken.
 54 th.join();
117 }
118
119 GetOutput().clear();
120 return true;
121 24 }
122
123
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 bool PankovAPathDejikstraSTL::RunImpl() {
124 const InType &input = GetInput();
125
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 if (adjacency_.size() != input.n) {
126 return false;
127 }
128 48 GetOutput() = DijkstraSeq(input.source, adjacency_);
129 24 return GetOutput().size() == input.n;
130 }
131
132 24 bool PankovAPathDejikstraSTL::PostProcessingImpl() {
133 24 return GetOutput().size() == GetInput().n;
134 }
135
136 } // namespace pankov_a_path_dejikstra
137