GCC Code Coverage Report

Directory: src/
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 94.3% 82 / 0 / 87
Functions: 50.0% 5 / 0 / 10
Branches: 87.8% 43 / 0 / 49
cartesian_tree.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include <vector>
4 #include <array>
5
6 #include "reverse_comparator.hpp"
7
8 53 class CartesianTree {
9 public:
10 struct Node {
11 int l, m, r; // inclusive ranges
12 std::array<int, 2> c;
13 int p;
14 };
15 std::vector<Node> nodes;
16 int root = -1;
17
18 ✗ CartesianTree() {}
19
20
2/2
✓ Branch 11 → 12 taken 9123447 times.
✓ Branch 11 → 15 taken 25 times.
 9125228 Node& operator [] (int idx) { return nodes[idx]; }
21 ✗ const Node& operator [] (int idx) const { return nodes[idx]; }
22
23
4/4
✓ Branch 539 → 69 taken 32 times.
✓ Branch 539 → 540 taken 7 times.
✓ Branch 1031 → 561 taken 32 times.
✓ Branch 1031 → 1032 taken 7 times.
 78 int size() const { return int(nodes.size()); }
24
25 private:
26 39 CartesianTree(std::vector<Node>&& nodes_, int root_) : nodes(std::move(nodes_)), root(root_) {}
27
28 public:
29
30 // min-cartesian-tree, with earlier cells tiebroken earlier
31 template <typename T, typename Comp = std::less<T>>
32
1/2
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 25 times.
 39 static CartesianTree build_min_tree(const std::vector<T>& v, Comp comp = Comp()) {
33
2/2
CartesianTree CartesianTree::build_min_tree<int, reverse_comparator_t<std::less<int> > >(std::__debug::vector<int, std::allocator<int> > const&, reverse_comparator_t<std::less<int> >):
✓ Branch 10 → 11 taken 7 times.
CartesianTree CartesianTree::build_min_tree<int, std::less<int> >(std::__debug::vector<int, std::allocator<int> > const&, std::less<int>):
✓ Branch 10 → 11 taken 7 times.
 39 std::vector<Node> nodes(v.size()*2+1);
34
4/5
CartesianTree CartesianTree::build_min_tree<int, reverse_comparator_t<std::less<int> > >(std::__debug::vector<int, std::allocator<int> > const&, reverse_comparator_t<std::less<int> >):
✓ Branch 19 → 129 taken 7 times.
CartesianTree CartesianTree::build_min_tree<int, std::less<int> >(std::__debug::vector<int, std::allocator<int> > const&, std::less<int>):
✓ Branch 19 → 127 taken 7 times.
CartesianTree CartesianTree::build_min_tree<int, std::less<int> >(std::vector<int, std::allocator<int> > const&, std::less<int>):
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 25 times.
✓ Branch 7 → 20 taken 25 times.
 39 std::vector<int> stk; stk.reserve(v.size());
35 9123575 int root = -1;
36
4/8
CartesianTree CartesianTree::build_min_tree<int, reverse_comparator_t<std::less<int> > >(std::__debug::vector<int, std::allocator<int> > const&, reverse_comparator_t<std::less<int> >):
✓ Branch 135 → 20 taken 39 times.
✗ Branch 135 → 136 not taken.
CartesianTree CartesianTree::build_min_tree<int, std::less<int> >(std::__debug::vector<int, std::allocator<int> > const&, std::less<int>):
✓ Branch 133 → 20 taken 39 times.
✗ Branch 133 → 134 not taken.
CartesianTree CartesianTree::build_min_tree<int, std::less<int> >(std::vector<int, std::allocator<int> > const&, std::less<int>):
✗ Branch 20 → 21 not taken.
✓ Branch 20 → 22 taken 9123497 times.
✓ Branch 22 → 8 taken 9123497 times.
✗ Branch 22 → 23 not taken.
 9123575 for (int i = 0; i <= int(v.size()); i++) {
37 9123575 int cur = 2*i;
38 9123575 nodes[cur].l = i;
39 9123575 nodes[cur].r = i-1;
40 9123575 nodes[cur].m = i-1;
41 9123575 nodes[cur].c = {-1, -1};
42
18/18
CartesianTree CartesianTree::build_min_tree<int, reverse_comparator_t<std::less<int> > >(std::__debug::vector<int, std::allocator<int> > const&, reverse_comparator_t<std::less<int> >):
✓ Branch 41 → 42 taken 56 times.
✓ Branch 41 → 93 taken 15 times.
✓ Branch 48 → 49 taken 42 times.
✓ Branch 48 → 66 taken 14 times.
✓ Branch 65 → 66 taken 18 times.
✓ Branch 65 → 93 taken 24 times.
CartesianTree CartesianTree::build_min_tree<int, std::less<int> >(std::__debug::vector<int, std::allocator<int> > const&, std::less<int>):
✓ Branch 41 → 42 taken 52 times.
✓ Branch 41 → 91 taken 19 times.
✓ Branch 48 → 49 taken 37 times.
✓ Branch 48 → 64 taken 15 times.
✓ Branch 63 → 64 taken 17 times.
✓ Branch 63 → 91 taken 20 times.
CartesianTree CartesianTree::build_min_tree<int, std::less<int> >(std::vector<int, std::allocator<int> > const&, std::less<int>):
✓ Branch 9 → 10 taken 15323746 times.
✓ Branch 9 → 15 taken 2923223 times.
✓ Branch 12 → 13 taken 12400521 times.
✓ Branch 12 → 14 taken 2923225 times.
✓ Branch 13 → 14 taken 6200247 times.
✓ Branch 13 → 15 taken 6200274 times.
 33570899 while (!stk.empty() && (i == int(v.size()) || comp(v[i], v[nodes[stk.back()].m]))) {
43 9123536 int nxt = stk.back(); stk.pop_back();
44 9123536 nodes[cur].p = nxt;
45 9123600 nodes[nxt].c[1] = cur;
46 9123536 nodes[nxt].r = nodes[cur].r;
47 9123536 cur = nxt;
48 }
49
6/6
CartesianTree CartesianTree::build_min_tree<int, reverse_comparator_t<std::less<int> > >(std::__debug::vector<int, std::allocator<int> > const&, reverse_comparator_t<std::less<int> >):
✓ Branch 99 → 100 taken 32 times.
✓ Branch 99 → 136 taken 7 times.
CartesianTree CartesianTree::build_min_tree<int, std::less<int> >(std::__debug::vector<int, std::allocator<int> > const&, std::less<int>):
✓ Branch 97 → 98 taken 32 times.
✓ Branch 97 → 134 taken 7 times.
CartesianTree CartesianTree::build_min_tree<int, std::less<int> >(std::vector<int, std::allocator<int> > const&, std::less<int>):
✓ Branch 17 → 18 taken 9123472 times.
✓ Branch 17 → 23 taken 25 times.
 9123575 if (i == int(v.size())) {
50 root = cur;
51 break;
52 }
53
1/1
✓ Branch 18 → 19 taken 9123472 times.
 9123536 nodes[2*i+1].l = nodes[cur].l;
54 9123536 nodes[2*i+1].m = i;
55 9123536 nodes[cur].p = 2*i+1;
56 9123600 nodes[2*i+1].c[0] = cur;
57
1/1
✓ Branch 18 → 19 taken 9123472 times.
 9123600 stk.push_back(2*i+1);
58 }
59 39 nodes[root].p = -1;
60 53 return {std::move(nodes), root};
61 53 }
62
63 // max-cartesian-tree, with earlier cells tiebroken earlier
64 template <typename T, typename Comp = std::less<T>>
65 7 static CartesianTree build_max_tree(const std::vector<T>& v, Comp comp = Comp()) {
66 7 return build_min_tree(v, reverse_comparator(comp));
67 }
68 };
69