GCC Code Coverage Report

Directory: src/
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 90.2% 166 / 0 / 184
Functions: 54.5% 12 / 0 / 22
Branches: 71.9% 174 / 6 / 248
ds/rmq.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include <functional>
4 #include <vector>
5 #include <cassert>
6 #include <cstdint>
7
8 namespace wala {
9
10 template <typename T, class Compare = std::less<T>> class RangeMinQuery : private Compare {
11 static const int BUCKET_SIZE = 32;
12 static const int BUCKET_SIZE_LOG = 5;
13 static_assert(BUCKET_SIZE == (1 << BUCKET_SIZE_LOG), "BUCKET_SIZE should be a power of 2");
14 static const int CACHE_LINE_ALIGNMENT = 64;
15 int n = 0;
16 std::vector<T> data;
17 std::vector<T> pref_data;
18 std::vector<T> suff_data;
19 std::vector<T> sparse_table;
20 std::vector<uint32_t> range_mask;
21
22 private:
23 35641617 int num_buckets() const {
24 16391717 return n >> BUCKET_SIZE_LOG;
25 }
26 673 int num_levels() const {
27
6/10
wala::RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::num_levels() const:
✓ Branch 5 → 6 taken 17 times.
✓ Branch 5 → 12 taken 12 times.
✗ Branch 9 → 10 not taken.
✓ Branch 9 → 11 taken 17 times.
wala::RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::num_levels() const:
✓ Branch 5 → 6 taken 17 times.
✓ Branch 5 → 12 taken 12 times.
✗ Branch 9 → 10 not taken.
✓ Branch 9 → 11 taken 17 times.
wala::RangeMinQuery<int, std::less<int> >::num_levels() const:
✗ Branch 3 → 4 not taken.
✗ Branch 3 → 6 not taken.
 741 return num_buckets() ? 32 - __builtin_clz(num_buckets()) : 0;
28 }
29 74 int sparse_table_size() const {
30 148 return num_buckets() * num_levels();
31 }
32
33 private:
34
4/4
✓ Branch 6 → 7 taken 7636595 times.
✓ Branch 6 → 8 taken 8480170 times.
✓ Branch 42 → 43 taken 2757611 times.
✓ Branch 42 → 44 taken 3658852 times.
 22808520 const T& min(const T& a, const T& b) const {
35
8/12
None:
✓ Branch 6 → 7 taken 7636595 times.
✓ Branch 6 → 8 taken 8480170 times.
✓ Branch 42 → 43 taken 2757611 times.
✓ Branch 42 → 44 taken 3658852 times.
✓ Branch 45 → 46 taken 147587 times.
✓ Branch 45 → 47 taken 127613 times.
✓ Branch 221 → 222 taken 48 times.
✓ Branch 221 → 223 taken 44 times.
wala::RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::min(std::pair<int, int> const&, std::pair<int, int> const&) const:
✗ Branch 3 → 4 not taken.
✗ Branch 3 → 5 not taken.
wala::RangeMinQuery<int, std::less<int> >::min(int const&, int const&) const:
✗ Branch 3 → 4 not taken.
✗ Branch 3 → 5 not taken.
 23083812 return Compare::operator()(a, b) ? a : b;
36 }
37
6/6
✓ Branch 24 → 25 taken 15051158 times.
✓ Branch 24 → 26 taken 1744471 times.
✓ Branch 31 → 32 taken 10633161 times.
✓ Branch 31 → 33 taken 6162468 times.
✓ Branch 36 → 37 taken 1700391 times.
✓ Branch 36 → 38 taken 15094975 times.
 66240937 void setmin(T& a, const T& b) const {
38
10/14
None:
✓ Branch 24 → 25 taken 15051158 times.
✓ Branch 24 → 26 taken 1744471 times.
✓ Branch 31 → 32 taken 10633161 times.
✓ Branch 31 → 33 taken 6162468 times.
✓ Branch 36 → 37 taken 1700391 times.
✓ Branch 36 → 38 taken 15094975 times.
wala::RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::setmin(std::pair<int, int>&, std::pair<int, int> const&) const:
✗ Branch 3 → 4 not taken.
✗ Branch 3 → 5 not taken.
✓ Branch 7 → 8 taken 94532 times.
✓ Branch 7 → 10 taken 138652 times.
wala::RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::setmin(std::pair<int, int>&, std::pair<int, int> const&) const:
✓ Branch 7 → 8 taken 110598 times.
✓ Branch 7 → 10 taken 122586 times.
wala::RangeMinQuery<int, std::less<int> >::setmin(int&, int const&) const:
✗ Branch 3 → 4 not taken.
✗ Branch 3 → 5 not taken.
 51319360 if (Compare::operator()(b, a)) a = b;
39 466368 }
40
41 148 template <typename Vec> static int get_size(const Vec& v) { using std::size; return int(size(v)); }
42
43 public:
44
1/1
✓ Branch 12 → 13 taken 25 times.
 25 RangeMinQuery() {}
45
1/2
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 52 times.
 74 template <typename Vec> explicit RangeMinQuery(const Vec& data_, const Compare& comp_ = Compare())
46 : Compare(comp_)
47 74 , n(get_size(data_))
48
2/3
wala::RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 16 → 17 taken 11 times.
wala::RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 16 → 17 taken 11 times.
wala::RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✗ Branch 5 → 6 not taken.
 74 , data(n)
49
3/4
wala::RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 24 → 25 taken 11 times.
wala::RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 24 → 25 taken 11 times.
wala::RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 5 → 6 taken 52 times.
✗ Branch 9 → 10 not taken.
 74 , pref_data(n)
50
3/4
wala::RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 32 → 33 taken 11 times.
wala::RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 32 → 33 taken 11 times.
wala::RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 6 → 7 taken 52 times.
✗ Branch 13 → 14 not taken.
 74 , suff_data(n)
51
5/7
wala::RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 40 → 41 taken 11 times.
wala::RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 40 → 41 taken 11 times.
wala::RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 7 → 8 taken 40 times.
✓ Branch 7 → 9 taken 12 times.
✓ Branch 9 → 10 taken 52 times.
✗ Branch 17 → 18 not taken.
✗ Branch 18 → 19 not taken.
 114 , sparse_table(sparse_table_size())
52
3/4
wala::RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 48 → 49 taken 11 times.
wala::RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 48 → 49 taken 11 times.
wala::RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 10 → 11 taken 52 times.
✗ Branch 22 → 23 not taken.
 74 , range_mask(n)
53 {
54
6/8
wala::RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 63 → 51 taken 897 times.
✓ Branch 63 → 104 taken 11 times.
wala::RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 63 → 51 taken 897 times.
✓ Branch 63 → 104 taken 11 times.
wala::RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 13 → 12 taken 17337442 times.
✓ Branch 13 → 22 taken 52 times.
✗ Branch 28 → 25 not taken.
✗ Branch 28 → 29 not taken.
 17339310 for (int i = 0; i < n; i++) data[i] = data_[i];
55
6/8
wala::RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 106 → 64 taken 897 times.
✓ Branch 106 → 132 taken 11 times.
wala::RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 106 → 64 taken 897 times.
✓ Branch 106 → 132 taken 11 times.
wala::RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 22 → 14 taken 17337442 times.
✓ Branch 22 → 27 taken 52 times.
✗ Branch 47 → 30 not taken.
✗ Branch 47 → 48 not taken.
 17339310 for (int i = 0; i < n; i++) {
56
6/8
wala::RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 64 → 65 taken 861 times.
✓ Branch 64 → 96 taken 36 times.
wala::RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 64 → 65 taken 861 times.
✓ Branch 64 → 96 taken 36 times.
wala::RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 14 → 15 taken 16795629 times.
✓ Branch 14 → 20 taken 541813 times.
✗ Branch 30 → 31 not taken.
✗ Branch 30 → 44 not taken.
 17339236 if (i & (BUCKET_SIZE-1)) {
57 16797351 uint32_t m = range_mask[i-1];
58
12/18
wala::RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 72 → 73 taken 1543 times.
✓ Branch 72 → 88 taken 83 times.
✓ Branch 87 → 88 taken 778 times.
✓ Branch 87 → 95 taken 765 times.
wala::RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 72 → 73 taken 1538 times.
✓ Branch 72 → 88 taken 91 times.
✓ Branch 87 → 88 taken 770 times.
✓ Branch 87 → 95 taken 768 times.
wala::RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 16 → 17 taken 25728620 times.
✓ Branch 16 → 19 taken 1744471 times.
✓ Branch 17 → 18 taken 10677462 times.
✓ Branch 17 → 19 taken 15051158 times.
✗ Branch 34 → 35 not taken.
✗ Branch 34 → 40 not taken.
✗ Branch 38 → 39 not taken.
✗ Branch 38 → 40 not taken.
✗ Branch 41 → 33 not taken.
✗ Branch 41 → 42 not taken.
 27479427 while (m && !Compare::operator()(data[(i | (BUCKET_SIZE-1)) - __builtin_clz(m)], data[i])) {
59 10678995 m -= uint32_t(1) << (BUCKET_SIZE - 1 - __builtin_clz(m));
60 }
61 16797351 m |= uint32_t(1) << (i & (BUCKET_SIZE - 1));
62 16797351 range_mask[i] = m;
63 } else {
64 541885 range_mask[i] = 1;
65 }
66 }
67
6/8
wala::RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 134 → 107 taken 897 times.
✓ Branch 134 → 135 taken 11 times.
wala::RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 134 → 107 taken 897 times.
✓ Branch 134 → 135 taken 11 times.
wala::RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 27 → 23 taken 17337442 times.
✓ Branch 27 → 28 taken 52 times.
✗ Branch 56 → 49 not taken.
✗ Branch 56 → 57 not taken.
 17339310 for (int i = 0; i < n; i++) {
68
2/2
✓ Branch 23 → 24 taken 16795629 times.
✓ Branch 23 → 26 taken 541813 times.
 17339236 pref_data[i] = data[i];
69
6/8
wala::RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 118 → 119 taken 861 times.
✓ Branch 118 → 131 taken 36 times.
wala::RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 118 → 119 taken 861 times.
✓ Branch 118 → 131 taken 36 times.
wala::RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 23 → 24 taken 16795629 times.
✓ Branch 23 → 26 taken 541813 times.
✗ Branch 51 → 52 not taken.
✗ Branch 51 → 55 not taken.
 17339236 if (i & (BUCKET_SIZE-1)) {
70
2/2
✓ Branch 24 → 25 taken 15051158 times.
✓ Branch 24 → 26 taken 1744471 times.
 32390322 setmin(pref_data[i], pref_data[i-1]);
71 }
72 }
73
6/8
wala::RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 166 → 138 taken 897 times.
✓ Branch 166 → 194 taken 11 times.
wala::RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 166 → 138 taken 897 times.
✓ Branch 166 → 194 taken 11 times.
wala::RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 34 → 29 taken 17337442 times.
✓ Branch 34 → 41 taken 52 times.
✗ Branch 66 → 58 not taken.
✗ Branch 66 → 67 not taken.
 17339310 for (int i = n-1; i >= 0; i--) {
74
2/2
✓ Branch 29 → 30 taken 17337390 times.
✓ Branch 29 → 33 taken 52 times.
 17339236 suff_data[i] = data[i];
75
12/16
wala::RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 151 → 152 taken 886 times.
✓ Branch 151 → 165 taken 11 times.
✓ Branch 152 → 153 taken 861 times.
✓ Branch 152 → 165 taken 25 times.
wala::RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 151 → 152 taken 886 times.
✓ Branch 151 → 165 taken 11 times.
✓ Branch 152 → 153 taken 861 times.
✓ Branch 152 → 165 taken 25 times.
wala::RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 29 → 30 taken 17337390 times.
✓ Branch 29 → 33 taken 52 times.
✓ Branch 30 → 31 taken 16795629 times.
✓ Branch 30 → 33 taken 541761 times.
✗ Branch 60 → 61 not taken.
✗ Branch 60 → 65 not taken.
✗ Branch 61 → 62 not taken.
✗ Branch 61 → 65 not taken.
 17339236 if (i+1 < n && ((i+1) & (BUCKET_SIZE-1))) {
76
2/2
✓ Branch 31 → 32 taken 10633161 times.
✓ Branch 31 → 33 taken 6162468 times.
 27972325 setmin(suff_data[i], suff_data[i+1]);
77 }
78 }
79
6/8
wala::RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 197 → 167 taken 26 times.
✓ Branch 197 → 239 taken 11 times.
wala::RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 197 → 167 taken 26 times.
✓ Branch 197 → 239 taken 11 times.
wala::RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 41 → 35 taken 541786 times.
✓ Branch 41 → 46 taken 52 times.
✗ Branch 78 → 68 not taken.
✗ Branch 78 → 79 not taken.
 541986 for (int i = 0; i < num_buckets(); i++) {
80 541838 sparse_table[i] = data[i * BUCKET_SIZE];
81
6/8
wala::RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 192 → 179 taken 806 times.
✓ Branch 192 → 193 taken 26 times.
wala::RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 192 → 179 taken 806 times.
✓ Branch 192 → 193 taken 26 times.
wala::RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 39 → 36 taken 16795366 times.
✓ Branch 39 → 40 taken 541786 times.
✗ Branch 75 → 71 not taken.
✗ Branch 75 → 76 not taken.
 17338816 for (int v = 1; v < BUCKET_SIZE; v++) {
82
2/2
✓ Branch 36 → 37 taken 1700391 times.
✓ Branch 36 → 38 taken 15094975 times.
 18497369 setmin(sparse_table[i], data[i * BUCKET_SIZE + v]);
83 }
84 }
85
8/10
wala::RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 241 → 233 taken 7 times.
✓ Branch 241 → 242 taken 11 times.
wala::RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 241 → 233 taken 7 times.
✓ Branch 241 → 242 taken 11 times.
wala::RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 46 → 47 taken 551 times.
✓ Branch 46 → 48 taken 12 times.
✓ Branch 48 → 45 taken 511 times.
✓ Branch 48 → 49 taken 52 times.
✗ Branch 93 → 80 not taken.
✗ Branch 93 → 94 not taken.
 1150 for (int l = 0; l+1 < num_levels(); l++) {
86
8/12
wala::RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✗ Branch 233 → 234 not taken.
✓ Branch 233 → 235 taken 53 times.
✓ Branch 238 → 198 taken 46 times.
✓ Branch 238 → 239 taken 7 times.
wala::RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✗ Branch 233 → 234 not taken.
✓ Branch 233 → 235 taken 53 times.
✓ Branch 238 → 198 taken 46 times.
✓ Branch 238 → 239 taken 7 times.
wala::RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 45 → 42 taken 6416463 times.
✓ Branch 45 → 46 taken 511 times.
✗ Branch 90 → 81 not taken.
✗ Branch 90 → 91 not taken.
 6417186 for (int i = 0; i + (1 << (l+1)) <= num_buckets(); i++) {
87
4/6
wala::RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✗ Branch 202 → 203 not taken.
✓ Branch 202 → 204 taken 46 times.
wala::RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✗ Branch 202 → 203 not taken.
✓ Branch 202 → 204 taken 46 times.
wala::RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 42 → 43 taken 2757611 times.
✓ Branch 42 → 44 taken 3658852 times.
 9174534 sparse_table[(l+1) * num_buckets() + i] = min(sparse_table[l * num_buckets() + i], sparse_table[l * num_buckets() + i + (1 << l)]);
88 }
89 }
90 74 }
91
92 16806956 T query(int l, int r) const {
93 16806956 assert(l <= r);
94 16806956 int bucket_l = (l >> BUCKET_SIZE_LOG);
95 16806956 int bucket_r = (r >> BUCKET_SIZE_LOG);
96
6/8
wala::RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::query(int, int) const:
✓ Branch 4 → 5 taken 14171 times.
✗ Branch 4 → 8 not taken.
✓ Branch 4 → 25 taken 137600 times.
wala::RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::query(int, int) const:
✓ Branch 4 → 5 taken 14171 times.
✓ Branch 4 → 25 taken 137600 times.
wala::RangeMinQuery<int, std::less<int> >::query(int, int) const:
✓ Branch 4 → 5 taken 386649 times.
✓ Branch 4 → 6 taken 16116765 times.
✗ Branch 4 → 8 not taken.
 16806956 if (bucket_l == bucket_r) {
97 414991 uint32_t msk = range_mask[r] & ~((uint32_t(1) << (l & (BUCKET_SIZE-1))) - 1);
98
2/4
wala::RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::query(int, int) const:
✗ Branch 13 → 14 not taken.
✓ Branch 13 → 15 taken 14171 times.
wala::RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::query(int, int) const:
✗ Branch 13 → 14 not taken.
✓ Branch 13 → 15 taken 14171 times.
 414991 int ind = (l & ~(BUCKET_SIZE-1)) + __builtin_ctz(msk);
99 414991 return data[ind];
100 } else {
101
2/3
wala::RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::query(int, int) const:
✗ Branch 10 → 11 not taken.
wala::RangeMinQuery<int, std::less<int> >::query(int, int) const:
✓ Branch 6 → 7 taken 7636595 times.
✓ Branch 6 → 8 taken 8480170 times.
 16667165 T ans = min(suff_data[l], pref_data[r]);
102 16391965 bucket_l++;
103
6/10
wala::RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::query(int, int) const:
✗ Branch 11 → 12 not taken.
✗ Branch 11 → 18 not taken.
✓ Branch 49 → 50 taken 115328 times.
✓ Branch 49 → 78 taken 22272 times.
wala::RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::query(int, int) const:
✓ Branch 49 → 50 taken 115328 times.
✓ Branch 49 → 78 taken 22272 times.
wala::RangeMinQuery<int, std::less<int> >::query(int, int) const:
✓ Branch 8 → 9 taken 15387945 times.
✓ Branch 8 → 10 taken 728820 times.
✗ Branch 11 → 12 not taken.
✗ Branch 11 → 18 not taken.
 16391965 if (bucket_l < bucket_r) {
104
2/4
wala::RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::query(int, int) const:
✗ Branch 50 → 51 not taken.
✓ Branch 50 → 52 taken 115328 times.
wala::RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::query(int, int) const:
✗ Branch 50 → 51 not taken.
✓ Branch 50 → 52 taken 115328 times.
 15618601 int level = (32 - __builtin_clz(bucket_r - bucket_l)) - 1;
105
0/1
✗ Branch 14 → 15 not taken.
 15849257 setmin(ans, sparse_table[level * num_buckets() + bucket_l]);
106
2/5
wala::RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::query(int, int) const:
✗ Branch 17 → 18 not taken.
✗ Branch 70 → 71 not taken.
✓ Branch 70 → 72 taken 115328 times.
wala::RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::query(int, int) const:
✗ Branch 70 → 71 not taken.
✓ Branch 70 → 72 taken 115328 times.
 16578077 setmin(ans, sparse_table[level * num_buckets() + bucket_r - (1 << level)]);
107 }
108 275200 return ans;
109 }
110 }
111 };
112
113 template <typename T> using RangeMaxQuery = RangeMinQuery<T, std::greater<T>>;
114
115 } // namespace wala
116