GCC Code Coverage Report

Directory: ./
File: tasks/shemetov_d_radix_odd_even_mergesort/seq/src/ops_seq.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 60 60 100.0%
Functions: 7 7 100.0%
Branches: 47 52 90.4%
Line Branch Exec Source
1 #include "shemetov_d_radix_odd_even_mergesort/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <climits>
5 #include <cstddef>
6 #include <vector>
7
8 #include "shemetov_d_radix_odd_even_mergesort/common/include/common.hpp"
9
10 namespace shemetov_d_radix_odd_even_mergesort {
11
12
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 ShemetovDRadixOddEvenMergeSortSEQ::ShemetovDRadixOddEvenMergeSortSEQ(const InType &in) {
13 SetTypeOfTask(GetStaticTypeOfTask());
14 GetInput() = in;
15 96 }
16
17 160 void ShemetovDRadixOddEvenMergeSortSEQ::RadixSort(std::vector<int> &array, size_t left, size_t right) {
18
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 16 times.
 160 if (left >= right) {
19 return;
20 }
21
22 144 int maximum = *std::ranges::max_element(array.begin(), array.end());
23
24 144 size_t segment = right - left + 1;
25
26 144 this->buffer_.resize(segment);
27
1/2
✓ Branch 0 taken 432 times.
✗ Branch 1 not taken.
 432 for (size_t merge_shift = 0; merge_shift < 32; merge_shift += 8) {
28 432 this->position_.assign(256, 0);
29
30
2/2
✓ Branch 0 taken 3424 times.
✓ Branch 1 taken 432 times.
 3856 for (size_t i = left; i <= right; i += 1) {
31 3424 int apply_bitmask = (array[i] >> merge_shift) & 0xFF;
32
33 3424 this->position_[apply_bitmask] += 1;
34 }
35
36
2/2
✓ Branch 0 taken 110160 times.
✓ Branch 1 taken 432 times.
 110592 for (size_t i = 1; i < 256; i += 1) {
37 110160 this->position_[i] += this->position_[i - 1];
38 }
39
40
2/2
✓ Branch 0 taken 3424 times.
✓ Branch 1 taken 432 times.
 3856 for (size_t i = segment; i > 0; i -= 1) {
41 3424 size_t current_index = left + i - 1;
42 3424 int apply_bitmask = (array[current_index] >> merge_shift) & 0xFF;
43
44 3424 this->buffer_[this->position_[apply_bitmask] -= 1] = array[current_index];
45 }
46
47
2/2
✓ Branch 0 taken 3424 times.
✓ Branch 1 taken 432 times.
 3856 for (size_t i = 0; i < segment; i += 1) {
48 3424 array[left + i] = this->buffer_[i];
49 }
50
51
2/2
✓ Branch 0 taken 288 times.
✓ Branch 1 taken 144 times.
 432 if ((maximum >> merge_shift) < 256) {
52 break;
53 }
54 }
55 }
56
57 80 void ShemetovDRadixOddEvenMergeSortSEQ::OddEvenMerge(std::vector<int> &array, size_t start_offset, size_t segment) {
58
1/2
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
 80 if (segment <= 1) {
59 return;
60 }
61
62 80 size_t padding = segment / 2;
63
2/2
✓ Branch 0 taken 520 times.
✓ Branch 1 taken 80 times.
 600 for (size_t i = 0; i < padding; i += 1) {
64
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 432 times.
 520 if (array[start_offset + i] > array[start_offset + padding + i]) {
65 std::swap(array[start_offset + i], array[start_offset + padding + i]);
66 }
67 }
68
69
2/2
✓ Branch 0 taken 176 times.
✓ Branch 1 taken 80 times.
 256 for (padding = segment / 4; padding > 0; padding /= 2) {
70 176 size_t step = padding * 2;
71
72
2/2
✓ Branch 0 taken 704 times.
✓ Branch 1 taken 176 times.
 880 for (size_t start_position = padding; start_position + padding < segment; start_position += step) {
73
2/2
✓ Branch 0 taken 1192 times.
✓ Branch 1 taken 704 times.
 1896 for (size_t i = 0; i < padding; i += 1) {
74
2/2
✓ Branch 0 taken 344 times.
✓ Branch 1 taken 848 times.
 1192 if (array[start_offset + start_position + i] > array[start_offset + start_position + i + padding]) {
75 std::swap(array[start_offset + start_position + i], array[start_offset + start_position + i + padding]);
76 }
77 }
78 }
79 }
80 }
81
82 96 bool ShemetovDRadixOddEvenMergeSortSEQ::ValidationImpl() {
83 const auto &[size, array] = GetInput();
84
3/4
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 88 times.
 96 return size > 0 && static_cast<size_t>(size) == array.size();
85 }
86
87
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 8 times.
 96 bool ShemetovDRadixOddEvenMergeSortSEQ::PreProcessingImpl() {
88 const auto &[size, array] = GetInput();
89
90
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 8 times.
 96 if (size == 0) {
91 return true;
92 }
93
94 88 array_ = array;
95
96 88 offset_ = *std::ranges::min_element(array_.begin(), array_.end());
97 88 size_ = static_cast<size_t>(size);
98 88 power_ = 1;
99
100
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 88 times.
 344 while (power_ < size_) {
101 256 power_ *= 2;
102 }
103
104
2/2
✓ Branch 0 taken 736 times.
✓ Branch 1 taken 88 times.
 824 for (size_t i = 0; i < size_; i += 1) {
105 736 array_[i] -= offset_;
106 }
107
108
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 40 times.
 88 if (power_ > size_) {
109 48 array_.resize(power_, INT_MAX);
110 }
111
112 return true;
113 }
114
115 96 bool ShemetovDRadixOddEvenMergeSortSEQ::RunImpl() {
116
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 16 times.
 96 if (power_ <= 1) {
117 return true;
118 }
119
120 80 size_t middle = power_ / 2;
121 80 RadixSort(array_, 0, middle - 1);
122 80 RadixSort(array_, middle, power_ - 1);
123
124 80 OddEvenMerge(array_, 0, power_);
125
126 80 return true;
127 }
128
129 96 bool ShemetovDRadixOddEvenMergeSortSEQ::PostProcessingImpl() {
130
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 88 times.
 96 if (size_ == 0) {
131 return true;
132 }
133
134 88 array_.resize(size_);
135
136
2/2
✓ Branch 0 taken 736 times.
✓ Branch 1 taken 88 times.
 824 for (size_t i = 0; i < size_; i += 1) {
137 736 array_[i] += offset_;
138 }
139
140
1/2
✓ Branch 0 taken 88 times.
✗ Branch 1 not taken.
 88 if (!std::ranges::is_sorted(array_.begin(), array_.end())) {
141 return false;
142 }
143
144 88 GetOutput() = array_;
145 88 return true;
146 }
147
148 } // namespace shemetov_d_radix_odd_even_mergesort
149