seq/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 | namespace wala { | ||
| 9 | |||
| 10 | 53 | class CartesianTree { | |
| 11 | public: | ||
| 12 | struct Node { | ||
| 13 | int l, m, r; // inclusive ranges | ||
| 14 | std::array<int, 2> c; | ||
| 15 | int p; | ||
| 16 | }; | ||
| 17 | std::vector<Node> nodes; | ||
| 18 | int root = -1; | ||
| 19 | |||
| 20 | ✗ | CartesianTree() {} | |
| 21 | |||
| 22 |
2/2✓ Branch 11 → 12 taken 9123447 times.
✓ Branch 11 → 15 taken 25 times.
|
9125228 | Node& operator [] (int idx) { return nodes[idx]; } |
| 23 | ✗ | const Node& operator [] (int idx) const { return nodes[idx]; } | |
| 24 | |||
| 25 |
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()); } |
| 26 | |||
| 27 | private: | ||
| 28 | 39 | CartesianTree(std::vector<Node>&& nodes_, int root_) : nodes(std::move(nodes_)), root(root_) {} | |
| 29 | |||
| 30 | public: | ||
| 31 | // min-cartesian-tree, with earlier cells tiebroken earlier | ||
| 32 | template <typename T, typename Comp = std::less<T>> | ||
| 33 |
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()) { |
| 34 |
2/2wala::CartesianTree wala::CartesianTree::build_min_tree<int, wala::reverse_comparator_t<std::less<int> > >(std::__debug::vector<int, std::allocator<int> > const&, wala::reverse_comparator_t<std::less<int> >):
✓ Branch 10 → 11 taken 7 times.
wala::CartesianTree wala::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); |
| 35 |
4/5wala::CartesianTree wala::CartesianTree::build_min_tree<int, wala::reverse_comparator_t<std::less<int> > >(std::__debug::vector<int, std::allocator<int> > const&, wala::reverse_comparator_t<std::less<int> >):
✓ Branch 19 → 129 taken 7 times.
wala::CartesianTree wala::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.
wala::CartesianTree wala::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()); |
| 36 | 9123575 | int root = -1; | |
| 37 |
4/8wala::CartesianTree wala::CartesianTree::build_min_tree<int, wala::reverse_comparator_t<std::less<int> > >(std::__debug::vector<int, std::allocator<int> > const&, wala::reverse_comparator_t<std::less<int> >):
✓ Branch 135 → 20 taken 39 times.
✗ Branch 135 → 136 not taken.
wala::CartesianTree wala::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.
wala::CartesianTree wala::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++) { |
| 38 | 9123575 | int cur = 2*i; | |
| 39 | 9123575 | nodes[cur].l = i; | |
| 40 | 9123575 | nodes[cur].r = i-1; | |
| 41 | 9123575 | nodes[cur].m = i-1; | |
| 42 | 9123575 | nodes[cur].c = {-1, -1}; | |
| 43 |
18/18wala::CartesianTree wala::CartesianTree::build_min_tree<int, wala::reverse_comparator_t<std::less<int> > >(std::__debug::vector<int, std::allocator<int> > const&, wala::reverse_comparator_t<std::less<int> >):
✓ Branch 41 → 42 taken 54 times.
✓ Branch 41 → 93 taken 17 times.
✓ Branch 48 → 49 taken 40 times.
✓ Branch 48 → 66 taken 14 times.
✓ Branch 65 → 66 taken 18 times.
✓ Branch 65 → 93 taken 22 times.
wala::CartesianTree wala::CartesianTree::build_min_tree<int, std::less<int> >(std::__debug::vector<int, std::allocator<int> > const&, std::less<int>):
✓ Branch 41 → 42 taken 48 times.
✓ Branch 41 → 91 taken 23 times.
✓ Branch 48 → 49 taken 38 times.
✓ Branch 48 → 64 taken 10 times.
✓ Branch 63 → 64 taken 22 times.
✓ Branch 63 → 91 taken 16 times.
wala::CartesianTree wala::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.
|
33570897 | while (!stk.empty() && (i == int(v.size()) || comp(v[i], v[nodes[stk.back()].m]))) { |
| 44 | 9123536 | int nxt = stk.back(); stk.pop_back(); | |
| 45 | 9123536 | nodes[cur].p = nxt; | |
| 46 | 9123600 | nodes[nxt].c[1] = cur; | |
| 47 | 9123536 | nodes[nxt].r = nodes[cur].r; | |
| 48 | 9123536 | cur = nxt; | |
| 49 | } | ||
| 50 |
6/6wala::CartesianTree wala::CartesianTree::build_min_tree<int, wala::reverse_comparator_t<std::less<int> > >(std::__debug::vector<int, std::allocator<int> > const&, wala::reverse_comparator_t<std::less<int> >):
✓ Branch 99 → 100 taken 32 times.
✓ Branch 99 → 136 taken 7 times.
wala::CartesianTree wala::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.
wala::CartesianTree wala::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())) { |
| 51 | root = cur; | ||
| 52 | break; | ||
| 53 | } | ||
| 54 |
1/1✓ Branch 18 → 19 taken 9123472 times.
|
9123536 | nodes[2*i+1].l = nodes[cur].l; |
| 55 | 9123536 | nodes[2*i+1].m = i; | |
| 56 | 9123536 | nodes[cur].p = 2*i+1; | |
| 57 | 9123600 | nodes[2*i+1].c[0] = cur; | |
| 58 |
1/1✓ Branch 18 → 19 taken 9123472 times.
|
9123600 | stk.push_back(2*i+1); |
| 59 | } | ||
| 60 | 39 | nodes[root].p = -1; | |
| 61 | 53 | return {std::move(nodes), root}; | |
| 62 | 53 | } | |
| 63 | |||
| 64 | // max-cartesian-tree, with earlier cells tiebroken earlier | ||
| 65 | template <typename T, typename Comp = std::less<T>> | ||
| 66 | 7 | static CartesianTree build_max_tree(const std::vector<T>& v, Comp comp = Comp()) { | |
| 67 | 7 | return build_min_tree(v, reverse_comparator(comp)); | |
| 68 | } | ||
| 69 | }; | ||
| 70 | |||
| 71 | } // namespace wala | ||
| 72 |