GCC Code Coverage Report

Directory: ./
File: tasks/smetanin_d_hoare_even_odd_batchelor/stl/src/ops_stl.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 55 55 100.0%
Functions: 9 9 100.0%
Branches: 34 42 81.0%
Line Branch Exec Source
1 #include "smetanin_d_hoare_even_odd_batchelor/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <stack>
5 #include <thread>
6 #include <utility>
7 #include <vector>
8
9 #include "smetanin_d_hoare_even_odd_batchelor/common/include/common.hpp"
10 #include "util/include/util.hpp"
11
12 namespace smetanin_d_hoare_even_odd_batchelor {
13
14 namespace {
15
16 constexpr int kTaskCutoff = 1000;
17
18 88856 int HoarePartition(std::vector<int> &arr, int lo, int hi) {
19 88856 int pivot = arr[lo + ((hi - lo) / 2)];
20 88856 int i = lo - 1;
21 88856 int j = hi + 1;
22 while (true) {
23 345681 ++i;
24
2/2
✓ Branch 0 taken 472800 times.
✓ Branch 1 taken 345681 times.
 818481 while (arr[i] < pivot) {
25 472800 ++i;
26 }
27 345681 --j;
28
2/2
✓ Branch 0 taken 485236 times.
✓ Branch 1 taken 345681 times.
 830917 while (arr[j] > pivot) {
29 485236 --j;
30 }
31
2/2
✓ Branch 0 taken 88856 times.
✓ Branch 1 taken 256825 times.
 345681 if (i >= j) {
32 88856 return j;
33 }
34 std::swap(arr[i], arr[j]);
35 }
36 }
37
38 88856 void OddEvenMerge(std::vector<int> &arr, int lo, int hi) {
39 88856 int n = hi - lo + 1;
40
2/2
✓ Branch 0 taken 217719 times.
✓ Branch 1 taken 88856 times.
 306575 for (int step = 1; step < n; step *= 2) {
41
2/2
✓ Branch 0 taken 1421095 times.
✓ Branch 1 taken 217719 times.
 1638814 for (int i = lo; i + step <= hi; i += step * 2) {
42
2/2
✓ Branch 0 taken 478772 times.
✓ Branch 1 taken 942323 times.
 1421095 if (arr[i] > arr[i + step]) {
43 std::swap(arr[i], arr[i + step]);
44 }
45 }
46 }
47 88856 }
48
49 46 void HoarSortBatcherSeq(std::vector<int> &arr, int lo, int hi) {
50 std::stack<std::pair<int, int>> stk;
51 stk.emplace(lo, hi);
52
2/2
✓ Branch 0 taken 177746 times.
✓ Branch 1 taken 46 times.
 177792 while (!stk.empty()) {
53 auto [l, r] = stk.top();
54 stk.pop();
55
2/2
✓ Branch 0 taken 88896 times.
✓ Branch 1 taken 88850 times.
 177746 if (l >= r) {
56 88896 continue;
57 }
58 88850 int p = HoarePartition(arr, l, r);
59
2/2
✓ Branch 0 taken 31060 times.
✓ Branch 1 taken 57790 times.
 88850 if ((p - l) > (r - p - 1)) {
60 stk.emplace(l, p);
61
1/2
✓ Branch 1 taken 31060 times.
✗ Branch 2 not taken.
 31060 stk.emplace(p + 1, r);
62 } else {
63
2/4
✓ Branch 1 taken 57790 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 57790 times.
✗ Branch 5 not taken.
 57790 stk.emplace(p + 1, r);
64 stk.emplace(l, p);
65 }
66 88850 OddEvenMerge(arr, l, r);
67 }
68 46 }
69
70 40 void HoarSortBatcherSTLImpl(std::vector<int> &arr, int lo, int hi, int num_threads) {
71
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 40 if (lo >= hi) {
72 34 return;
73 }
74
4/4
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 32 times.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 6 times.
 40 if (hi - lo < kTaskCutoff || num_threads <= 1) {
75 34 HoarSortBatcherSeq(arr, lo, hi);
76 34 return;
77 }
78 6 const int p = HoarePartition(arr, lo, hi);
79 6 OddEvenMerge(arr, lo, hi);
80 12 std::thread right([&arr, p, hi]() { HoarSortBatcherSeq(arr, p + 1, hi); });
81
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 HoarSortBatcherSeq(arr, lo, p);
82
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 right.join();
83 }
84
85 } // namespace
86
87
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 SmetaninDHoarSortSTL::SmetaninDHoarSortSTL(const InType &in) {
88 SetTypeOfTask(GetStaticTypeOfTask());
89
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 GetInput() = in;
90 56 }
91
92 56 bool SmetaninDHoarSortSTL::ValidationImpl() {
93 56 return true;
94 }
95
96 56 bool SmetaninDHoarSortSTL::PreProcessingImpl() {
97 56 GetOutput() = GetInput();
98 56 return true;
99 }
100
101
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 16 times.
 56 bool SmetaninDHoarSortSTL::RunImpl() {
102 auto &data = GetOutput();
103 56 int n = static_cast<int>(data.size());
104
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 16 times.
 56 if (n > 1) {
105 40 const int num_threads = std::max(1, ppc::util::GetNumThreads());
106 40 HoarSortBatcherSTLImpl(data, 0, n - 1, num_threads);
107 }
108 56 return true;
109 }
110
111 56 bool SmetaninDHoarSortSTL::PostProcessingImpl() {
112 56 return true;
113 }
114
115 } // namespace smetanin_d_hoare_even_odd_batchelor
116