GCC Code Coverage Report

Directory: ./
File: tasks/ovchinnikov_m_shell_sort_batcher_merge/stl/src/ops_stl.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 85 87 97.7%
Functions: 12 12 100.0%
Branches: 62 90 68.9%
Line Branch Exec Source
1 #include "ovchinnikov_m_shell_sort_batcher_merge/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <limits>
6 #include <thread>
7 #include <utility>
8 #include <vector>
9
10 #include "ovchinnikov_m_shell_sort_batcher_merge/common/include/common.hpp"
11
12 namespace ovchinnikov_m_shell_sort_batcher_merge {
13
14 namespace {
15
16 std::size_t NextPowerOfTwo(std::size_t value) {
17 std::size_t power = 1;
18
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 48 times.
 168 while (power < value) {
19 120 power <<= 1;
20 }
21 return power;
22 }
23
24 88 std::vector<int> MergeSorted(const std::vector<int> &first, const std::vector<int> &second) {
25
1/2
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
 88 std::vector<int> merged;
26
1/2
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
 88 merged.reserve(first.size() + second.size());
27
28 std::size_t left_index = 0;
29 std::size_t right_index = 0;
30
4/4
✓ Branch 0 taken 200 times.
✓ Branch 1 taken 64 times.
✓ Branch 2 taken 24 times.
✓ Branch 3 taken 176 times.
 264 while (left_index < first.size() && right_index < second.size()) {
31
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 48 times.
 176 if (first[left_index] <= second[right_index]) {
32 merged.push_back(first[left_index]);
33 128 ++left_index;
34 } else {
35 merged.push_back(second[right_index]);
36 48 ++right_index;
37 }
38 }
39
40
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 88 times.
 112 while (left_index < first.size()) {
41 merged.push_back(first[left_index]);
42 24 ++left_index;
43 }
44
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 88 times.
 192 while (right_index < second.size()) {
45 merged.push_back(second[right_index]);
46 104 ++right_index;
47 }
48
49 88 return merged;
50 }
51
52 bool IsEvenPosition(std::size_t index) {
53 576 return (index % 2) == 0;
54 }
55
56 80 void SplitByParity(const std::vector<int> &input, std::vector<int> &even, std::vector<int> &odd) {
57 80 even.reserve((input.size() + 1) / 2);
58 80 odd.reserve(input.size() / 2);
59
2/2
✓ Branch 0 taken 288 times.
✓ Branch 1 taken 80 times.
 368 for (std::size_t i = 0; i < input.size(); ++i) {
60
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 144 times.
 288 if (IsEvenPosition(i)) {
61 even.push_back(input[i]);
62 } else {
63 odd.push_back(input[i]);
64 }
65 }
66 80 }
67
68 40 std::vector<int> InterleaveByParity(const std::vector<int> &even, const std::vector<int> &odd) {
69 40 std::vector<int> merged(even.size() + odd.size());
70 std::size_t even_index = 0;
71 std::size_t odd_index = 0;
72
2/2
✓ Branch 0 taken 288 times.
✓ Branch 1 taken 40 times.
 328 for (std::size_t i = 0; i < merged.size(); ++i) {
73
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 144 times.
 288 if (IsEvenPosition(i)) {
74 144 merged[i] = even[even_index];
75 144 ++even_index;
76 } else {
77 144 merged[i] = odd[odd_index];
78 144 ++odd_index;
79 }
80 }
81 40 return merged;
82 }
83
84 48 std::pair<std::vector<int>, std::vector<int>> SplitInHalf(const std::vector<int> &data) {
85 48 const auto middle = data.begin() + static_cast<std::ptrdiff_t>(data.size() / 2);
86
1/2
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 std::vector<int> left(data.begin(), middle);
87
1/4
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 48 std::vector<int> right(middle, data.end());
88 48 return {std::move(left), std::move(right)};
89 }
90
91 40 void CompareExchangeOddPairs(std::vector<int> &data) {
92
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 40 times.
 144 for (std::size_t i = 1; i + 1 < data.size(); i += 2) {
93
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 80 times.
 104 if (data[i] > data[i + 1]) {
94 std::swap(data[i], data[i + 1]);
95 }
96 }
97 40 }
98
99 } // namespace
100
101
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 OvchinnikovMShellSortBatcherMergeSTL::OvchinnikovMShellSortBatcherMergeSTL(const InType &in) {
102 SetTypeOfTask(GetStaticTypeOfTask());
103
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 GetInput() = in;
104 64 }
105
106 96 void OvchinnikovMShellSortBatcherMergeSTL::ShellSort(std::vector<int> &data) {
107 const std::size_t n = data.size();
108
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 96 times.
 240 for (std::size_t gap = n / 2; gap > 0; gap /= 2) {
109
2/2
✓ Branch 0 taken 336 times.
✓ Branch 1 taken 144 times.
 480 for (std::size_t i = gap; i < n; ++i) {
110 336 const int temp = data[i];
111 std::size_t j = i;
112
4/4
✓ Branch 0 taken 392 times.
✓ Branch 1 taken 72 times.
✓ Branch 2 taken 128 times.
✓ Branch 3 taken 264 times.
 464 while (j >= gap && data[j - gap] > temp) {
113 128 data[j] = data[j - gap];
114 j -= gap;
115 }
116 336 data[j] = temp;
117 }
118 }
119 96 }
120
121
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 std::vector<int> OvchinnikovMShellSortBatcherMergeSTL::BatcherOddEvenMerge(const std::vector<int> &left,
122 const std::vector<int> &right) {
123
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 if (left.empty()) {
124 ✗ return right;
125 }
126
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 if (right.empty()) {
127 ✗ return left;
128 }
129
130
3/4
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 8 times.
✓ Branch 3 taken 40 times.
 48 if (left.size() != right.size() || left.size() <= 1) {
131 8 return MergeSorted(left, right);
132 }
133
134 40 std::vector<int> left_even;
135 40 std::vector<int> left_odd;
136 40 std::vector<int> right_even;
137 40 std::vector<int> right_odd;
138
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 SplitByParity(left, left_even, left_odd);
139
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 SplitByParity(right, right_even, right_odd);
140
141
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 std::vector<int> merged_even = MergeSorted(left_even, right_even);
142
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 std::vector<int> merged_odd = MergeSorted(left_odd, right_odd);
143
144
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 std::vector<int> merged = InterleaveByParity(merged_even, merged_odd);
145 40 CompareExchangeOddPairs(merged);
146 return merged;
147 }
148
149 64 bool OvchinnikovMShellSortBatcherMergeSTL::ValidationImpl() {
150 64 return true;
151 }
152
153 64 bool OvchinnikovMShellSortBatcherMergeSTL::PreProcessingImpl() {
154 64 data_ = GetInput();
155 64 return true;
156 }
157
158
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 16 times.
 64 bool OvchinnikovMShellSortBatcherMergeSTL::RunImpl() {
159 constexpr std::size_t kMinSizeToSort = 2;
160
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 16 times.
 64 if (data_.size() < kMinSizeToSort) {
161 return true;
162 }
163
164 const std::size_t original_size = data_.size();
165 const std::size_t padded_size = NextPowerOfTwo(original_size);
166 48 data_.resize(padded_size, std::numeric_limits<int>::max());
167
168 48 auto halves = SplitInHalf(data_);
169 auto &left = halves.first;
170 auto &right = halves.second;
171
172
1/2
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 96 std::thread left_thread([&left]() { ShellSort(left); });
173
1/4
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 96 std::thread right_thread([&right]() { ShellSort(right); });
174
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 left_thread.join();
175
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 right_thread.join();
176
177
1/4
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 48 data_ = BatcherOddEvenMerge(left, right);
178
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 data_.resize(original_size);
179 return true;
180 48 }
181
182
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 8 times.
 64 bool OvchinnikovMShellSortBatcherMergeSTL::PostProcessingImpl() {
183
1/2
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
 56 if (!std::ranges::is_sorted(data_.begin(), data_.end())) {
184 return false;
185 }
186 64 GetOutput() = data_;
187 64 return true;
188 }
189
190 } // namespace ovchinnikov_m_shell_sort_batcher_merge
191