GCC Code Coverage Report

Directory: ./
File: tasks/vasiliev_m_shell_sort_batcher_merge/seq/src/ops_seq.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 61 61 100.0%
Functions: 9 9 100.0%
Branches: 54 74 73.0%
Line Branch Exec Source
1 #include "vasiliev_m_shell_sort_batcher_merge/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <cmath>
5 #include <cstddef>
6 #include <vector>
7
8 #include "vasiliev_m_shell_sort_batcher_merge/common/include/common.hpp"
9
10 namespace vasiliev_m_shell_sort_batcher_merge {
11
12
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 VasilievMShellSortBatcherMergeSEQ::VasilievMShellSortBatcherMergeSEQ(const InType &in) {
13 SetTypeOfTask(GetStaticTypeOfTask());
14
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 GetInput() = in;
15 48 GetOutput() = OutType{};
16 48 }
17
18 48 bool VasilievMShellSortBatcherMergeSEQ::ValidationImpl() {
19 48 return !GetInput().empty();
20 }
21
22
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 bool VasilievMShellSortBatcherMergeSEQ::PreProcessingImpl() {
23 GetOutput().clear();
24 48 return true;
25 }
26
27
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 bool VasilievMShellSortBatcherMergeSEQ::RunImpl() {
28 auto &vec = GetInput();
29 const size_t n = vec.size();
30
31
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 if (vec.empty()) {
32 return false;
33 }
34
35 48 size_t mid = n / 2;
36
37
1/2
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 std::vector<ValType> l(vec.begin(), vec.begin() + static_cast<std::ptrdiff_t>(mid));
38
1/4
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 48 std::vector<ValType> r(vec.begin() + static_cast<std::ptrdiff_t>(mid), vec.end());
39
40 48 ShellSort(l);
41 48 ShellSort(r);
42
43
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 std::vector<ValType> batcher_merged_vec = BatcherMerge(l, r);
44
45
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 GetOutput() = batcher_merged_vec;
46 return true;
47 }
48
49 96 void VasilievMShellSortBatcherMergeSEQ::ShellSort(std::vector<ValType> &vec) {
50 size_t n = vec.size();
51
2/2
✓ Branch 0 taken 136 times.
✓ Branch 1 taken 96 times.
 232 for (size_t gap = n / 2; gap > 0; gap /= 2) {
52
2/2
✓ Branch 0 taken 368 times.
✓ Branch 1 taken 136 times.
 504 for (size_t i = gap; i < n; i++) {
53 368 ValType tmp = vec[i];
54 size_t j = i;
55
4/4
✓ Branch 0 taken 456 times.
✓ Branch 1 taken 80 times.
✓ Branch 2 taken 168 times.
✓ Branch 3 taken 288 times.
 536 while (j >= gap && vec[j - gap] > tmp) {
56 168 vec[j] = vec[j - gap];
57 j -= gap;
58 }
59 368 vec[j] = tmp;
60 }
61 }
62 96 }
63
64 48 std::vector<ValType> VasilievMShellSortBatcherMergeSEQ::BatcherMerge(std::vector<ValType> &l, std::vector<ValType> &r) {
65 48 std::vector<ValType> even_l;
66 48 std::vector<ValType> odd_l;
67 48 std::vector<ValType> even_r;
68 48 std::vector<ValType> odd_r;
69
70
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 SplitEvenOdd(l, even_l, odd_l);
71
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 SplitEvenOdd(r, even_r, odd_r);
72
73
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 std::vector<ValType> even = Merge(even_l, even_r);
74
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 std::vector<ValType> odd = Merge(odd_l, odd_r);
75
76
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 std::vector<ValType> res;
77
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 res.reserve(l.size() + r.size());
78
79
3/4
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 200 times.
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 248 for (size_t i = 0; i < even.size() || i < odd.size(); i++) {
80
1/2
✓ Branch 0 taken 200 times.
✗ Branch 1 not taken.
 200 if (i < even.size()) {
81 res.push_back(even[i]);
82 }
83
2/2
✓ Branch 0 taken 136 times.
✓ Branch 1 taken 64 times.
 200 if (i < odd.size()) {
84 res.push_back(odd[i]);
85 }
86 }
87
88
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 48 times.
 176 for (size_t i = 1; i + 1 < res.size(); i += 2) {
89
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 48 times.
 128 if (res[i] > res[i + 1]) {
90 std::swap(res[i], res[i + 1]);
91 }
92 }
93
94 48 return res;
95 }
96
97 96 void VasilievMShellSortBatcherMergeSEQ::SplitEvenOdd(std::vector<ValType> &vec, std::vector<ValType> &even,
98 std::vector<ValType> &odd) {
99 96 even.reserve(even.size() + (vec.size() / 2) + 1);
100 96 odd.reserve(odd.size() + (vec.size() / 2));
101
102
2/2
✓ Branch 0 taken 200 times.
✓ Branch 1 taken 96 times.
 296 for (size_t i = 0; i < vec.size(); i += 2) {
103 even.push_back(vec[i]);
104
2/2
✓ Branch 0 taken 136 times.
✓ Branch 1 taken 64 times.
 200 if (i + 1 < vec.size()) {
105 odd.push_back(vec[i + 1]);
106 }
107 }
108 96 }
109
110 96 std::vector<ValType> VasilievMShellSortBatcherMergeSEQ::Merge(std::vector<ValType> &a, std::vector<ValType> &b) {
111 96 std::vector<ValType> merged;
112 size_t i = 0;
113 size_t j = 0;
114
4/4
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 248 times.
✓ Branch 2 taken 32 times.
✓ Branch 3 taken 216 times.
 312 while (i < a.size() && j < b.size()) {
115
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 88 times.
 216 if (a[i] <= b[j]) {
116
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 120 times.
 128 merged.push_back(a[i++]);
117 } else {
118
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 88 times.
 88 merged.push_back(b[j++]);
119 }
120 }
121
122
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 96 times.
 128 while (i < a.size()) {
123
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 16 times.
 32 merged.push_back(a[i++]);
124 }
125
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 96 times.
 184 while (j < b.size()) {
126
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 40 times.
 88 merged.push_back(b[j++]);
127 }
128
129 96 return merged;
130 }
131
132 48 bool VasilievMShellSortBatcherMergeSEQ::PostProcessingImpl() {
133 48 return true;
134 }
135
136 } // namespace vasiliev_m_shell_sort_batcher_merge
137