GCC Code Coverage Report

Directory: ./
File: tasks/litvyakov_d_shell_sort/stl/src/ops_stl.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 45 45 100.0%
Functions: 8 8 100.0%
Branches: 33 46 71.7%
Line Branch Exec Source
1 #include "litvyakov_d_shell_sort/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <cstdio>
6 #include <thread>
7 #include <vector>
8
9 #include "litvyakov_d_shell_sort/common/include/common.hpp"
10 #include "util/include/util.hpp"
11
12 namespace litvyakov_d_shell_sort {
13
14 60 void LitvyakovDShellSortSTL::BaseShellSort(std::vector<int>::iterator first, std::vector<int>::iterator last) {
15
2/2
✓ Branch 0 taken 278 times.
✓ Branch 1 taken 60 times.
 338 for (std::ptrdiff_t dist = (last - first) / 2; dist > 0; dist /= 2) {
16
2/2
✓ Branch 0 taken 59470 times.
✓ Branch 1 taken 278 times.
 59748 for (auto i = first + dist; i != last; ++i) {
17
4/4
✓ Branch 0 taken 106440 times.
✓ Branch 1 taken 4716 times.
✓ Branch 2 taken 51686 times.
✓ Branch 3 taken 54754 times.
 111156 for (auto j = i; j - first >= dist && (*j < *(j - dist)); j -= dist) {
18 std::swap(*j, *(j - dist));
19 }
20 }
21 }
22 60 }
23
24
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 std::vector<std::size_t> LitvyakovDShellSortSTL::GetBounds(std::size_t n, std::size_t parts) {
25
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 6 times.
 24 parts = std::max<std::size_t>(1, std::min(parts, n));
26
27 24 std::vector<std::size_t> bounds;
28
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 bounds.reserve(parts + 1);
29
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 bounds.push_back(0);
30
31 24 const std::size_t base = n / parts;
32 24 const std::size_t rem = n % parts;
33
34
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 24 times.
 84 for (std::size_t i = 0; i < parts; ++i) {
35
1/4
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 60 bounds.push_back(bounds.back() + base);
36
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 50 times.
 60 if (i < rem) {
37 10 bounds[i + 1]++;
38 }
39 }
40
41 24 return bounds;
42 }
43
44
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 LitvyakovDShellSortSTL::LitvyakovDShellSortSTL(const InType &in) {
45 SetTypeOfTask(GetStaticTypeOfTask());
46
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 GetInput() = in;
47 32 GetOutput() = std::vector<int>();
48 32 }
49
50 32 bool LitvyakovDShellSortSTL::ValidationImpl() {
51 const InType &vec = GetInput();
52 32 return !vec.empty();
53 }
54
55 32 bool LitvyakovDShellSortSTL::PreProcessingImpl() {
56 32 GetOutput() = GetInput();
57 32 return true;
58 }
59
60
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 8 times.
 32 bool LitvyakovDShellSortSTL::RunImpl() {
61 std::vector<int> &vec = GetOutput();
62
63
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 8 times.
 32 if (vec.size() <= 1) {
64 return true;
65 }
66
67 24 const auto threads = static_cast<std::size_t>(ppc::util::GetNumThreads());
68 const std::size_t parts_count = std::min<std::size_t>(threads, vec.size());
69 24 const auto bounds = GetBounds(vec.size(), parts_count);
70
71
1/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 24 std::vector<std::thread> thread_pool(parts_count);
72
73
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 24 times.
 84 for (std::size_t i = 0; i < parts_count; ++i) {
74 60 const std::size_t l = bounds[i];
75 60 const std::size_t r = bounds[i + 1];
76 60 thread_pool[i] = std::thread([&vec, l, r]() {
77 60 BaseShellSort(vec.begin() + static_cast<std::ptrdiff_t>(l), vec.begin() + static_cast<std::ptrdiff_t>(r));
78
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 });
79 }
80
81
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 24 times.
 84 for (auto &t : thread_pool) {
82
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 t.join();
83 }
84
85 // cppreference.com:
86 // void inplace_merge( BidirIt first, BidirIt middle, BidirIt last ),
87 // Merges two consecutive sorted ranges [first, middle) and [middle, last) into one sorted range [first, last).
88
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 24 times.
 60 for (std::size_t i = 1; i < parts_count; ++i) {
89 36 std::inplace_merge(vec.begin(), vec.begin() + static_cast<std::ptrdiff_t>(bounds[i]),
90 36 vec.begin() + static_cast<std::ptrdiff_t>(bounds[i + 1]));
91 }
92
93 return true;
94 24 }
95
96 32 bool LitvyakovDShellSortSTL::PostProcessingImpl() {
97 32 return true;
98 }
99
100 } // namespace litvyakov_d_shell_sort
101