GCC Code Coverage Report

Directory: ./
File: tasks/yushkova_p_hoare_sorting_simple_merging/stl/src/ops_stl.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 59 69 85.5%
Functions: 11 12 91.7%
Branches: 46 84 54.8%
Line Branch Exec Source
1 #include "yushkova_p_hoare_sorting_simple_merging/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <exception>
5 #include <iterator>
6 #include <stack>
7 #include <thread>
8 #include <utility>
9 #include <vector>
10
11 #include "util/include/util.hpp"
12 #include "yushkova_p_hoare_sorting_simple_merging/common/include/common.hpp"
13
14 namespace yushkova_p_hoare_sorting_simple_merging {
15
16
1/2
✓ Branch 1 taken 136 times.
✗ Branch 2 not taken.
 136 YushkovaPHoareSortingSimpleMergingSTL::YushkovaPHoareSortingSimpleMergingSTL(const InType &in) {
17 SetTypeOfTask(GetStaticTypeOfTask());
18
1/2
✓ Branch 1 taken 136 times.
✗ Branch 2 not taken.
 136 GetInput() = in;
19 GetOutput().clear();
20 136 }
21
22 5392 int YushkovaPHoareSortingSimpleMergingSTL::HoarePartition(std::vector<int> &values, int left, int right) {
23 5392 const int pivot = values[left + ((right - left) / 2)];
24 5392 int i = left - 1;
25 5392 int j = right + 1;
26
27 while (true) {
28 10384 ++i;
29
2/2
✓ Branch 0 taken 7016 times.
✓ Branch 1 taken 10384 times.
 17400 while (values[i] < pivot) {
30 7016 ++i;
31 }
32
33 10384 --j;
34
2/2
✓ Branch 0 taken 9528 times.
✓ Branch 1 taken 10384 times.
 19912 while (values[j] > pivot) {
35 9528 --j;
36 }
37
38
2/2
✓ Branch 0 taken 5392 times.
✓ Branch 1 taken 4992 times.
 10384 if (i >= j) {
39 5392 return j;
40 }
41
42 std::swap(values[i], values[j]);
43 }
44 }
45
46 240 void YushkovaPHoareSortingSimpleMergingSTL::HoareQuickSort(std::vector<int> &values, int left, int right) {
47 std::stack<std::pair<int, int>> ranges;
48 ranges.emplace(left, right);
49
50
2/2
✓ Branch 0 taken 11024 times.
✓ Branch 1 taken 240 times.
 11264 while (!ranges.empty()) {
51 auto [current_left, current_right] = ranges.top();
52 ranges.pop();
53
54
2/2
✓ Branch 0 taken 5632 times.
✓ Branch 1 taken 5392 times.
 11024 if (current_left >= current_right) {
55 5632 continue;
56 }
57
58 5392 const int partition_index = HoarePartition(values, current_left, current_right);
59
60
2/2
✓ Branch 0 taken 600 times.
✓ Branch 1 taken 4792 times.
 5392 if ((partition_index - current_left) > (current_right - (partition_index + 1))) {
61 ranges.emplace(current_left, partition_index);
62
1/2
✓ Branch 1 taken 600 times.
✗ Branch 2 not taken.
 600 ranges.emplace(partition_index + 1, current_right);
63 } else {
64
2/4
✓ Branch 1 taken 4792 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4792 times.
✗ Branch 5 not taken.
 4792 ranges.emplace(partition_index + 1, current_right);
65 ranges.emplace(current_left, partition_index);
66 }
67 }
68 240 }
69
70 128 std::vector<int> YushkovaPHoareSortingSimpleMergingSTL::SimpleMerge(const std::vector<int> &left,
71 const std::vector<int> &right) {
72
1/2
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
 128 std::vector<int> merged;
73
1/2
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
 128 merged.reserve(left.size() + right.size());
74
1/2
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
 128 std::ranges::merge(left, right, std::back_inserter(merged));
75 128 return merged;
76 }
77
78
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 16 times.
 256 void YushkovaPHoareSortingSimpleMergingSTL::SortHalfIfNeeded(std::vector<int> &values) {
79
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 16 times.
 256 if (values.size() > 1) {
80 240 HoareQuickSort(values, 0, static_cast<int>(values.size()) - 1);
81 }
82 256 }
83
84 ✗ void YushkovaPHoareSortingSimpleMergingSTL::SortHalvesSequential(std::vector<int> &left, std::vector<int> &right) {
85
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 SortHalfIfNeeded(left);
86
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 SortHalfIfNeeded(right);
87 32 }
88
89
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 void YushkovaPHoareSortingSimpleMergingSTL::SortHalvesParallel(std::vector<int> &left, std::vector<int> &right) {
90 std::exception_ptr exception_ptr;
91 ✗ std::thread left_worker([&] {
92 try {
93
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 SortHalfIfNeeded(left);
94 ✗ } catch (...) {
95 ✗ exception_ptr = std::current_exception();
96 ✗ }
97
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 192 });
98
99 try {
100
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 SortHalfIfNeeded(right);
101 ✗ } catch (...) {
102 ✗ if (!exception_ptr) {
103 ✗ exception_ptr = std::current_exception();
104 }
105 ✗ }
106
107
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 left_worker.join();
108
109
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 96 times.
 96 if (exception_ptr) {
110 ✗ std::rethrow_exception(exception_ptr);
111 }
112 96 }
113
114 136 bool YushkovaPHoareSortingSimpleMergingSTL::ValidationImpl() {
115 136 return !GetInput().empty();
116 }
117
118 136 bool YushkovaPHoareSortingSimpleMergingSTL::PreProcessingImpl() {
119 136 GetOutput() = GetInput();
120 136 return true;
121 }
122
123
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 8 times.
 136 bool YushkovaPHoareSortingSimpleMergingSTL::RunImpl() {
124 std::vector<int> &values = GetOutput();
125
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 8 times.
 136 if (values.size() <= 1) {
126 return true;
127 }
128
129 128 const auto middle = static_cast<std::vector<int>::difference_type>(values.size() / 2);
130
1/2
✓ Branch 2 taken 128 times.
✗ Branch 3 not taken.
 128 std::vector<int> left(values.begin(), values.begin() + middle);
131
1/4
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 128 std::vector<int> right(values.begin() + middle, values.end());
132
133
1/2
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
 128 const int concurrency = std::max(1, ppc::util::GetNumThreads());
134
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 96 times.
 128 if (concurrency == 1) {
135 SortHalvesSequential(left, right);
136 } else {
137
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 SortHalvesParallel(left, right);
138 }
139
140
2/6
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 128 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 256 values = SimpleMerge(left, right);
141 return std::ranges::is_sorted(values);
142 }
143
144
1/2
✓ Branch 0 taken 136 times.
✗ Branch 1 not taken.
 136 bool YushkovaPHoareSortingSimpleMergingSTL::PostProcessingImpl() {
145
1/2
✓ Branch 0 taken 136 times.
✗ Branch 1 not taken.
 136 return !GetOutput().empty() && std::ranges::is_sorted(GetOutput());
146 }
147
148 } // namespace yushkova_p_hoare_sorting_simple_merging
149