GCC Code Coverage Report

Directory: src/
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 77.9% 187 / 0 / 240
Functions: 58.9% 33 / 0 / 56
Branches: 75.1% 169 / 115 / 340
seg_tree.hpp
Line Branch Exec Source
1 #include <cassert>
2 #include <array>
3 #include <ostream>
4
5 namespace seg_tree {
6
7 // Floor of log_2(a); index of highest 1-bit
8 29589329 inline int floor_log_2(int a) {
9
0/2
✗ Branch 2 → 3 not taken.
✗ Branch 2 → 4 not taken.
 14127356 return a ? (8 * sizeof(a)) - 1 - __builtin_clz(a) : -1;
10 }
11
12 698895 inline int ceil_log_2(int a) {
13
0/2
✗ Branch 2 → 3 not taken.
✗ Branch 2 → 4 not taken.
 1397715 return a ? floor_log_2(2*a-1) : -1;
14 }
15
16 698895 inline int next_pow_2(int a) {
17
1/2
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 698820 times.
 698895 return 1 << ceil_log_2(a);
18 }
19
20 struct point {
21 int a;
22 ✗ point() : a(0) {}
23 1029888892 explicit point(int a_) : a(a_) { assert(a >= -1); }
24
25 ✗ explicit operator bool () { return bool(a); }
26
27 // This is useful so you can directly do array indices
28
18/19
✓ Branch 2 → 3 taken 122253662 times.
✓ Branch 2 → 4 taken 77753786 times.
✓ Branch 4 → 5 taken 23436729 times.
✓ Branch 4 → 6 taken 23438267 times.
✓ Branch 9 → 10 taken 46874996 times.
✗ Branch 9 → 11 not taken.
✓ Branch 18 → 14 taken 4112495 times.
✓ Branch 18 → 15 taken 4112460 times.
✓ Branch 18 → 19 taken 37 times.
✓ Branch 20 → 18 taken 2407127 times.
✓ Branch 20 → 21 taken 19 times.
✓ Branch 21 → 18 taken 2407127 times.
✓ Branch 21 → 22 taken 19 times.
✓ Branch 24 → 25 taken 1916669 times.
✓ Branch 38 → 39 taken 1359180 times.
✓ Branch 241 → 91 taken 625 times.
✓ Branch 241 → 242 taken 16 times.
✓ Branch 287 → 103 taken 625 times.
✓ Branch 287 → 288 taken 16 times.
 542879481 /* implicit */ operator int() const { return a; }
29
30 591881882 point c(bool z) const {
31 591881882 return point((a<<1)|z);
32 }
33
34 ✗ point operator [] (bool z) const {
35 ✗ return c(z);
36 }
37
38 ✗ point p() const {
39 ✗ return point(a>>1);
40 }
41
42 ✗ friend std::ostream& operator << (std::ostream& o, const point& p) { return o << int(p); }
43
44 ✗ template <typename F> void for_each(F f) const {
45 ✗ for (int v = a; v > 0; v >>= 1) {
46 ✗ f(point(v));
47 }
48 }
49
50 ✗ template <typename F> void for_each_down(F f) const {
51 // strictly greater than 0
52 ✗ for (int L = floor_log_2(a); L >= 0; L--) {
53 ✗ f(point(a >> L));
54 }
55 }
56
57 1919775 template <typename F> void for_each_up(F f) const {
58
2/2
✓ Branch 5 → 3 taken 37487358 times.
✓ Branch 5 → 6 taken 1919775 times.
 39407133 for (int v = a; v > 0; v >>= 1) {
59 37487358 f(point(v));
60 }
61 1919775 }
62
63 1359180 template <typename F> void for_parents_down(F f) const {
64 // strictly greater than 0
65
3/4
✓ Branch 2 → 3 taken 1359180 times.
✗ Branch 2 → 4 not taken.
✓ Branch 8 → 5 taken 24974044 times.
✓ Branch 8 → 9 taken 1359180 times.
 27692404 for (int L = floor_log_2(a); L > 0; L--) {
66 24974044 f(point(a >> L));
67 }
68 1359180 }
69
70 1916669 template <typename F> void for_parents_up(F f) const {
71
2/2
✓ Branch 6 → 3 taken 35548899 times.
✓ Branch 6 → 7 taken 1916669 times.
 37465568 for (int v = a >> 1; v > 0; v >>= 1) {
72 35548899 f(point(v));
73 }
74 1916669 }
75
76 ✗ point& operator ++ () { ++a; return *this; }
77 ✗ point operator ++ (int) { return point(a++); }
78 ✗ point& operator -- () { --a; return *this; }
79 13040459 point operator -- (int) { return point(a--); }
80 };
81
82 struct range {
83 int a, b;
84 2 range() : a(1), b(1) {}
85 7990879 range(int a_, int b_) : a(a_), b(b_) {
86 7990879 assert(1 <= a && a <= b && b <= 2 * a);
87 7990879 }
88 ✗ explicit range(std::array<int, 2> r) : range(r[0], r[1]) {}
89
90 ✗ explicit operator std::array<int, 2>() const {
91 ✗ return {a,b};
92 }
93
94 ✗ const int& operator[] (bool z) const {
95 ✗ return z ? b : a;
96 }
97
98 ✗ friend std::ostream& operator << (std::ostream& o, const range& r) { return o << "[" << r.a << ".." << r.b << ")"; }
99
100 // Iterate over the range from outside-in.
101 // Calls f(point a)
102 6071412 template <typename F> void for_each(F f) const {
103
12/12
void seg_tree::range::for_each<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#1}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#1}) const:
✓ Branch 19 → 8 taken 167839 times.
✓ Branch 19 → 20 taken 35846 times.
void seg_tree::range::for_each<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#1}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#1}) const:
✓ Branch 19 → 8 taken 177528 times.
✓ Branch 19 → 20 taken 35846 times.
void seg_tree::range::for_each<main::{lambda(seg_tree::point)#2}>(main::{lambda(seg_tree::point)#2}) const:
✓ Branch 10 → 3 taken 31272019 times.
✓ Branch 10 → 11 taken 1921363 times.
✓ Branch 12 → 3 taken 21909777 times.
✓ Branch 12 → 13 taken 1359591 times.
void seg_tree::range::for_each<main::{lambda(seg_tree::point)#3}>(main::{lambda(seg_tree::point)#3}) const:
✓ Branch 12 → 3 taken 21901281 times.
✓ Branch 12 → 13 taken 1359136 times.
void seg_tree::range::for_each<main::{lambda(seg_tree::point)#4}>(main::{lambda(seg_tree::point)#4}) const:
✓ Branch 12 → 3 taken 21914179 times.
✓ Branch 12 → 13 taken 1359630 times.
 103414035 for (int x = a, y = b; x < y; x >>= 1, y >>= 1) {
104
11/11
void seg_tree::range::for_each<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#1}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#1}) const:
✓ Branch 8 → 9 taken 86386 times.
✓ Branch 8 → 13 taken 81453 times.
void seg_tree::range::for_each<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#1}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#1}) const:
✓ Branch 8 → 9 taken 89134 times.
✓ Branch 8 → 13 taken 88394 times.
void seg_tree::range::for_each<main::{lambda(seg_tree::point)#2}>(main::{lambda(seg_tree::point)#2}) const:
✓ Branch 3 → 4 taken 27138756 times.
✓ Branch 3 → 6 taken 15319831 times.
✓ Branch 3 → 7 taken 10723209 times.
void seg_tree::range::for_each<main::{lambda(seg_tree::point)#3}>(main::{lambda(seg_tree::point)#3}) const:
✓ Branch 3 → 4 taken 11177623 times.
✓ Branch 3 → 7 taken 10723658 times.
void seg_tree::range::for_each<main::{lambda(seg_tree::point)#4}>(main::{lambda(seg_tree::point)#4}) const:
✓ Branch 3 → 4 taken 11185703 times.
✓ Branch 3 → 7 taken 10728476 times.
 97342623 if (x & 1) f(point(x++));
105
12/12
void seg_tree::range::for_each<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#1}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#1}) const:
✓ Branch 13 → 14 taken 86589 times.
✓ Branch 13 → 18 taken 81250 times.
void seg_tree::range::for_each<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#1}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#1}) const:
✓ Branch 13 → 14 taken 85139 times.
✓ Branch 13 → 18 taken 92389 times.
void seg_tree::range::for_each<main::{lambda(seg_tree::point)#2}>(main::{lambda(seg_tree::point)#2}) const:
✓ Branch 6 → 7 taken 15602185 times.
✓ Branch 6 → 9 taken 15669834 times.
✓ Branch 7 → 8 taken 10920828 times.
✓ Branch 7 → 11 taken 10988949 times.
void seg_tree::range::for_each<main::{lambda(seg_tree::point)#3}>(main::{lambda(seg_tree::point)#3}) const:
✓ Branch 7 → 8 taken 10918209 times.
✓ Branch 7 → 11 taken 10983072 times.
void seg_tree::range::for_each<main::{lambda(seg_tree::point)#4}>(main::{lambda(seg_tree::point)#4}) const:
✓ Branch 7 → 8 taken 10921722 times.
✓ Branch 7 → 11 taken 10992457 times.
 97342623 if (y & 1) f(point(--y));
106 }
107 6071412 }
108
109 // Iterate over the range from outside-in.
110 // Calls f(point a, bool is_right)
111 71692 template <typename F> void for_each_with_side(F f) const {
112
4/4
void seg_tree::range::for_each_with_side<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1, bool)#1}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1, bool)#1}) const:
✓ Branch 19 → 8 taken 167839 times.
✓ Branch 19 → 20 taken 35846 times.
void seg_tree::range::for_each_with_side<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1, bool)#1}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1, bool)#1}) const:
✓ Branch 19 → 8 taken 177528 times.
✓ Branch 19 → 20 taken 35846 times.
 417059 for (int x = a, y = b; x < y; x >>= 1, y >>= 1) {
113
6/6
void seg_tree::range::for_each_with_side<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1, bool)#1}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1, bool)#1}) const:
✓ Branch 8 → 9 taken 86386 times.
✓ Branch 8 → 13 taken 81453 times.
✓ Branch 11 → 12 taken 86386 times.
void seg_tree::range::for_each_with_side<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1, bool)#1}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1, bool)#1}) const:
✓ Branch 8 → 9 taken 89134 times.
✓ Branch 8 → 13 taken 88394 times.
✓ Branch 11 → 12 taken 89134 times.
 345367 if (x & 1) f(point(x++), false);
114
6/6
void seg_tree::range::for_each_with_side<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1, bool)#1}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1, bool)#1}) const:
✓ Branch 13 → 14 taken 86589 times.
✓ Branch 13 → 18 taken 81250 times.
✓ Branch 16 → 17 taken 86589 times.
void seg_tree::range::for_each_with_side<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1, bool)#1}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1, bool)#1}) const:
✓ Branch 13 → 14 taken 85139 times.
✓ Branch 13 → 18 taken 92389 times.
✓ Branch 16 → 17 taken 85139 times.
 345367 if (y & 1) f(point(--y), true);
115 }
116 71692 }
117
118 // Iterate over the range from left to right.
119 // Calls f(point)
120 1991161 template <typename F> void for_each_l_to_r(F f) const {
121
3/6
void seg_tree::range::for_each_l_to_r<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#2}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#2}) const:
✗ Branch 7 → 8 not taken.
✓ Branch 7 → 9 taken 35846 times.
void seg_tree::range::for_each_l_to_r<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#2}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#2}) const:
✗ Branch 7 → 8 not taken.
✓ Branch 7 → 9 taken 35846 times.
void seg_tree::range::for_each_l_to_r<main::{lambda(seg_tree::point)#2}>(main::{lambda(seg_tree::point)#2}) const:
✓ Branch 2 → 3 taken 1919469 times.
✗ Branch 2 → 4 not taken.
 1991161 int anc_depth = floor_log_2((a-1) ^ b);
122 1919469 int anc_msk = (1 << anc_depth) - 1;
123
6/6
void seg_tree::range::for_each_l_to_r<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#2}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#2}) const:
✓ Branch 19 → 12 taken 86386 times.
✓ Branch 19 → 20 taken 35846 times.
void seg_tree::range::for_each_l_to_r<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#2}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#2}) const:
✓ Branch 19 → 12 taken 89134 times.
✓ Branch 19 → 20 taken 35846 times.
void seg_tree::range::for_each_l_to_r<main::{lambda(seg_tree::point)#2}>(main::{lambda(seg_tree::point)#2}) const:
✓ Branch 8 → 5 taken 15953464 times.
✓ Branch 8 → 9 taken 1919469 times.
 18120145 for (int v = (-a) & anc_msk; v; v &= v-1) {
124 16128984 int i = __builtin_ctz(v);
125
2/2
void seg_tree::range::for_each_l_to_r<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#2}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#2}) const:
✓ Branch 16 → 17 taken 86386 times.
void seg_tree::range::for_each_l_to_r<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#2}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#2}) const:
✓ Branch 16 → 17 taken 89134 times.
 16128984 f(point(((a-1) >> i) + 1));
126 }
127
6/6
void seg_tree::range::for_each_l_to_r<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#2}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#2}) const:
✓ Branch 34 → 24 taken 86589 times.
✓ Branch 34 → 35 taken 35846 times.
void seg_tree::range::for_each_l_to_r<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#2}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#2}) const:
✓ Branch 34 → 24 taken 85139 times.
✓ Branch 34 → 35 taken 35846 times.
void seg_tree::range::for_each_l_to_r<main::{lambda(seg_tree::point)#2}>(main::{lambda(seg_tree::point)#2}) const:
✓ Branch 13 → 10 taken 15605303 times.
✓ Branch 13 → 14 taken 1919469 times.
 17768192 for (int v = b & anc_msk; v; ) {
128 15777031 int i = floor_log_2(v);
129
2/2
void seg_tree::range::for_each_l_to_r<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#2}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#2}) const:
✓ Branch 29 → 30 taken 86589 times.
void seg_tree::range::for_each_l_to_r<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#2}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#2}) const:
✓ Branch 29 → 30 taken 85139 times.
 15777031 f(point((b >> i) - 1));
130
2/4
void seg_tree::range::for_each_l_to_r<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#2}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#2}) const:
✗ Branch 31 → 32 not taken.
✓ Branch 31 → 33 taken 86589 times.
void seg_tree::range::for_each_l_to_r<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#2}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#2}) const:
✗ Branch 31 → 32 not taken.
✓ Branch 31 → 33 taken 85139 times.
 15777031 v ^= (1 << i);
131 }
132 1991161 }
133
134 // Iterate over the range from right to left.
135 // Calls f(point)
136 71692 template <typename F> void for_each_r_to_l(F f) const {
137
2/4
void seg_tree::range::for_each_r_to_l<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#3}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#3}) const:
✗ Branch 7 → 8 not taken.
✓ Branch 7 → 9 taken 35846 times.
void seg_tree::range::for_each_r_to_l<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#3}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#3}) const:
✗ Branch 7 → 8 not taken.
✓ Branch 7 → 9 taken 35846 times.
 71692 int anc_depth = floor_log_2((a-1) ^ b);
138 ✗ int anc_msk = (1 << anc_depth) - 1;
139
4/4
void seg_tree::range::for_each_r_to_l<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#3}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#3}) const:
✓ Branch 21 → 13 taken 86589 times.
✓ Branch 21 → 22 taken 35846 times.
void seg_tree::range::for_each_r_to_l<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#3}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#3}) const:
✓ Branch 21 → 13 taken 85139 times.
✓ Branch 21 → 22 taken 35846 times.
 243420 for (int v = b & anc_msk; v; v &= v-1) {
140 171728 int i = __builtin_ctz(v);
141
2/2
void seg_tree::range::for_each_r_to_l<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#3}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#3}) const:
✓ Branch 18 → 19 taken 86589 times.
void seg_tree::range::for_each_r_to_l<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#3}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#3}) const:
✓ Branch 18 → 19 taken 85139 times.
 171728 f(point((b >> i) - 1));
142 }
143
4/4
void seg_tree::range::for_each_r_to_l<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#3}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#3}) const:
✓ Branch 34 → 25 taken 86386 times.
✓ Branch 34 → 35 taken 35846 times.
void seg_tree::range::for_each_r_to_l<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#3}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#3}) const:
✓ Branch 34 → 25 taken 89134 times.
✓ Branch 34 → 35 taken 35846 times.
 247212 for (int v = (-a) & anc_msk; v; ) {
144 175520 int i = floor_log_2(v);
145
2/2
void seg_tree::range::for_each_r_to_l<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#3}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#3}) const:
✓ Branch 29 → 30 taken 86386 times.
void seg_tree::range::for_each_r_to_l<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#3}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#3}) const:
✓ Branch 29 → 30 taken 89134 times.
 175520 f(point(((a-1) >> i) + 1));
146
2/4
void seg_tree::range::for_each_r_to_l<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#3}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::circular_layout>()::{lambda(auto:1)#3}) const:
✗ Branch 31 → 32 not taken.
✓ Branch 31 → 33 taken 86386 times.
void seg_tree::range::for_each_r_to_l<CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#3}>(CATCH2_INTERNAL_TEMPLATE_TEST_0<seg_tree::in_order_layout>()::{lambda(auto:1)#3}) const:
✗ Branch 31 → 32 not taken.
✓ Branch 31 → 33 taken 89134 times.
 175520 v ^= (1 << i);
147 }
148 71692 }
149
150 4078357 template <typename F> void for_parents_down(F f) const {
151 4078357 int x = a, y = b;
152
2/2
✓ Branch 2 → 3 taken 6051 times.
✓ Branch 2 → 4 taken 4072306 times.
 4078357 if ((x ^ y) > x) { x <<= 1, std::swap(x, y); }
153 4078357 int dx = __builtin_ctz(x);
154 4078357 int dy = __builtin_ctz(y);
155
1/2
✓ Branch 4 → 5 taken 4078357 times.
✗ Branch 4 → 6 not taken.
 4078357 int anc_depth = floor_log_2((x-1) ^ y);
156
3/4
✓ Branch 6 → 7 taken 4078357 times.
✗ Branch 6 → 8 not taken.
✓ Branch 12 → 9 taken 71268955 times.
✓ Branch 12 → 16 taken 4078357 times.
 79425669 for (int i = floor_log_2(x); i > dx; i--) {
157 71268955 f(point(x >> i));
158 }
159
2/2
✓ Branch 16 → 13 taken 62170346 times.
✓ Branch 16 → 17 taken 4078357 times.
 66248703 for (int i = anc_depth; i > dy; i--) {
160 62170346 f(point(y >> i));
161 }
162 4078357 }
163
164 1359136 template <typename F> void for_parents_up(F f) const {
165 1359136 int x = a, y = b;
166
2/2
✓ Branch 2 → 3 taken 2057 times.
✓ Branch 2 → 4 taken 1357079 times.
 1359136 if ((x ^ y) > x) { x <<= 1, std::swap(x, y); }
167 1359136 int dx = __builtin_ctz(x);
168 1359136 int dy = __builtin_ctz(y);
169
1/2
✓ Branch 4 → 5 taken 1359136 times.
✗ Branch 4 → 6 not taken.
 1359136 int anc_depth = floor_log_2((x-1) ^ y);
170
2/2
✓ Branch 10 → 7 taken 20988901 times.
✓ Branch 10 → 11 taken 1359136 times.
 22348037 for (int i = dx+1; i <= anc_depth; i++) {
171 20988901 f(point(x >> i));
172 }
173
2/2
✓ Branch 15 → 12 taken 23478968 times.
✓ Branch 15 → 16 taken 1359136 times.
 24838104 for (int v = y >> (dy+1); v; v >>= 1) {
174 23478968 f(point(v));
175 }
176 1359136 }
177 };
178
179 struct in_order_layout {
180 // Alias them in for convenience
181 using point = seg_tree::point;
182 using range = seg_tree::range;
183
184 int N, S;
185 ✗ in_order_layout() : N(0), S(0) {}
186
5/9
None:
✓ Branch 5 → 6 taken 37 times.
✗ Branch 5 → 7 not taken.
✓ Branch 10 → 11 taken 38 times.
✗ Branch 10 → 12 not taken.
✓ Branch 12 → 13 taken 38 times.
seg_tree::in_order_layout::in_order_layout(int):
✗ Branch 2 → 3 not taken.
✗ Branch 2 → 4 not taken.
✓ Branch 6 → 7 taken 15 times.
✓ Branch 6 → 10 taken 1 time.
 91 in_order_layout(int N_) : N(N_), S(N ? next_pow_2(N) : 0) {}
187
188 18235548 point get_point(int a) const {
189 18235548 assert(0 <= a && a < N);
190 18235548 a += S;
191
4/6
✓ Branch 5 → 6 taken 2587692 times.
✓ Branch 5 → 7 taken 15647216 times.
✗ Branch 6 → 7 not taken.
✗ Branch 6 → 8 not taken.
✓ Branch 13 → 14 taken 203 times.
✓ Branch 13 → 17 taken 437 times.
 18235548 return point(a >= 2 * N ? a - N : a);
192 }
193
194 7955035 range get_range(int a, int b) const {
195 7955035 assert(0 <= a && a <= b && b <= N);
196
3/6
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 7919189 times.
✗ Branch 7 → 8 not taken.
✗ Branch 7 → 11 not taken.
✓ Branch 9 → 10 taken 1 time.
✓ Branch 9 → 13 taken 35845 times.
 7955035 if (N == 0) return range();
197 7955034 a += S, b += S;
198
8/12
✓ Branch 7 → 8 taken 1806609 times.
✓ Branch 7 → 9 taken 6112580 times.
✓ Branch 9 → 10 taken 286477 times.
✓ Branch 9 → 11 taken 7632712 times.
✗ Branch 11 → 12 not taken.
✗ Branch 11 → 13 not taken.
✗ Branch 14 → 15 not taken.
✗ Branch 14 → 16 not taken.
✓ Branch 22 → 23 taken 14082 times.
✓ Branch 22 → 26 taken 21763 times.
✓ Branch 28 → 29 taken 9191 times.
✓ Branch 28 → 32 taken 26654 times.
 7955034 return range((a >= 2 * N ? 2*(a-N) : a), (b >= 2 * N ? 2*(b-N) : b));
199 }
200
201 ✗ range get_range(std::array<int, 2> p) const {
202 ✗ return get_range(p[0], p[1]);
203 }
204
205 640 int get_leaf_index(point pt) const {
206 640 int a = int(pt);
207 640 assert(N <= a && a < 2 * N);
208
2/4
✗ Branch 7 → 8 not taken.
✗ Branch 7 → 9 not taken.
✓ Branch 13 → 14 taken 203 times.
✓ Branch 13 → 17 taken 437 times.
 640 return (a < S ? a + N : a) - S;
209 }
210
211 703997 std::array<int, 2> get_node_bounds(point pt) const {
212 703997 int a = int(pt);
213 703997 assert(1 <= a && a < 2 * N);
214
2/4
✗ Branch 8 → 9 not taken.
✓ Branch 8 → 10 taken 703997 times.
✗ Branch 12 → 13 not taken.
✓ Branch 12 → 14 taken 703997 times.
 703997 int l = __builtin_clz(a) - __builtin_clz(2*N-1);
215
1/2
✗ Branch 14 → 15 not taken.
✓ Branch 14 → 16 taken 703997 times.
 703997 int x = a << l, y = (a+1) << l;
216 703997 assert(S <= x && x < y && y <= 2*S);
217
4/8
✗ Branch 12 → 13 not taken.
✗ Branch 12 → 14 not taken.
✗ Branch 15 → 16 not taken.
✗ Branch 15 → 17 not taken.
✓ Branch 28 → 29 taken 212979 times.
✓ Branch 28 → 32 taken 491018 times.
✓ Branch 37 → 38 taken 232939 times.
✓ Branch 37 → 41 taken 471058 times.
 703997 return {(x >= 2 * N ? (x>>1) + N : x) - S, (y >= 2 * N ? (y>>1) + N : y) - S};
218 }
219
220 ✗ int get_node_split(point pt) const {
221 ✗ int a = int(pt);
222 ✗ assert(1 <= a && a < N);
223 ✗ int l = __builtin_clz(2*a+1) - __builtin_clz(2*N-1);
224 ✗ int x = (2*a+1) << l;
225 ✗ assert(S <= x && x < 2*S);
226 ✗ return (x >= 2 * N ? (x>>1) + N : x) - S;
227 }
228
229 2515 int get_node_size(point pt) const {
230 2515 auto bounds = get_node_bounds(pt);
231 7545 return bounds[1] - bounds[0];
232 }
233 };
234
235 struct circular_layout {
236 // Alias them in for convenience
237 using point = seg_tree::point;
238 using range = seg_tree::range;
239
240 int N;
241 ✗ circular_layout() : N(0) {}
242 16 circular_layout(int N_) : N(N_) {}
243
244 640 point get_point(int a) const {
245 640 assert(0 <= a && a < N);
246 640 return point(N + a);
247 }
248
249 35846 range get_range(int a, int b) const {
250 35846 assert(0 <= a && a <= b && b <= N);
251
2/4
✗ Branch 7 → 8 not taken.
✗ Branch 7 → 11 not taken.
✓ Branch 9 → 10 taken 1 time.
✓ Branch 9 → 13 taken 35845 times.
 35846 if (N == 0) return range();
252 35845 return range(N + a, N + b);
253 }
254
255 ✗ range get_range(std::array<int, 2> p) const {
256 ✗ return get_range(p[0], p[1]);
257 }
258
259 640 int get_leaf_index(point pt) const {
260 640 int a = int(pt);
261 640 assert(N <= a && a < 2 * N);
262 640 return a - N;
263 }
264
265 // Returns {x,y} so that 0 <= x < N and 1 <= y <= N
266 // If the point is non-wrapping, then 0 <= x < y <= N
267 698805 std::array<int, 2> get_node_bounds(point pt) const {
268 698805 int a = int(pt);
269 698805 assert(1 <= a && a < 2 * N);
270
2/4
✗ Branch 8 → 9 not taken.
✓ Branch 8 → 10 taken 698805 times.
✗ Branch 12 → 13 not taken.
✓ Branch 12 → 14 taken 698805 times.
 698805 int l = __builtin_clz(a) - __builtin_clz(2*N-1);
271 698805 int S = next_pow_2(N);
272
1/2
✗ Branch 17 → 18 not taken.
✓ Branch 17 → 19 taken 698805 times.
 698805 int x = a << l, y = (a+1) << l;
273 698805 assert(S <= x && x < y && y <= 2*S);
274
4/8
✗ Branch 13 → 14 not taken.
✗ Branch 13 → 15 not taken.
✗ Branch 16 → 17 not taken.
✗ Branch 16 → 18 not taken.
✓ Branch 24 → 25 taken 220967 times.
✓ Branch 24 → 26 taken 477838 times.
✓ Branch 30 → 31 taken 221141 times.
✓ Branch 30 → 32 taken 477664 times.
 698805 return {(x >= 2 * N ? x >> 1 : x) - N, (y > 2 * N ? y >> 1 : y) - N};
275 }
276
277 // Returns the split point of the node, such that 1 <= s <= N.
278 ✗ int get_node_split(point pt) const {
279 ✗ int a = int(pt);
280 ✗ assert(1 <= a && a < N);
281 ✗ return get_node_bounds(pt.c(0))[1];
282 }
283
284 2515 int get_node_size(point pt) const {
285 2515 auto bounds = get_node_bounds(pt);
286 7545 int r = bounds[1] - bounds[0];
287
2/4
✗ Branch 5 → 6 not taken.
✗ Branch 5 → 7 not taken.
✓ Branch 14 → 15 taken 58 times.
✓ Branch 14 → 18 taken 2457 times.
 2515 return r > 0 ? r : r + N;
288 }
289 };
290
291 } // namespace seg_tree
292