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