seq/perm_tree.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include <vector> | ||
| 4 | #include <array> | ||
| 5 | #include <cassert> | ||
| 6 | |||
| 7 | namespace wala { | ||
| 8 | |||
| 9 | 11856 | class PermTree { | |
| 10 | // The tree is "left-associative": INCR/DECR nodes are structured as (1 INCR 2) INCR 3... | ||
| 11 | public: | ||
| 12 | enum class NodeType { | ||
| 13 | LEAF, | ||
| 14 | INCR, | ||
| 15 | DECR, | ||
| 16 | FULL, | ||
| 17 | PARTIAL, | ||
| 18 | }; | ||
| 19 | |||
| 20 | struct Node { | ||
| 21 | std::array<int, 2> c; | ||
| 22 | NodeType type; | ||
| 23 | int l, r, lo, hi; | ||
| 24 | }; | ||
| 25 | |||
| 26 | std::vector<Node> nodes; | ||
| 27 | int root = -1; | ||
| 28 | |||
| 29 | ✗ | PermTree() {} | |
| 30 |
8/8✓ Branch 2 → 3 taken 14452513 times.
✓ Branch 2 → 4 taken 3609497 times.
✓ Branch 3 → 4 taken 3672730 times.
✓ Branch 3 → 7 taken 10779783 times.
✓ Branch 8 → 9 taken 1748763 times.
✓ Branch 8 → 13 taken 9031020 times.
✓ Branch 9 → 10 taken 1527012 times.
✓ Branch 9 → 11 taken 221751 times.
|
18520645 | Node& operator [] (int idx) { return nodes[idx]; } |
| 31 | ✗ | const Node& operator [] (int idx) const { return nodes[idx]; } | |
| 32 | |||
| 33 |
2/2✓ Branch 982 → 51 taken 74725 times.
✓ Branch 982 → 983 taken 5913 times.
|
80638 | int size() const { return int(nodes.size()); } |
| 34 | |||
| 35 |
3/8wala::PermTree::PermTree(std::__debug::vector<int, std::allocator<int> > const&):
✓ Branch 12 → 13 taken 5913 times.
✗ Branch 12 → 20 not taken.
✓ Branch 20 → 21 taken 5913 times.
wala::PermTree::PermTree(std::vector<int, std::allocator<int> > const&):
✓ Branch 2 → 3 taken 30 times.
✗ Branch 2 → 6 not taken.
✗ Branch 5 → 6 not taken.
✗ Branch 5 → 7 not taken.
✗ Branch 9 → 10 not taken.
|
5973 | PermTree(const std::vector<int>& A) : nodes(A.empty() ? 0 : int(A.size())*2-1) { |
| 36 |
2/6wala::PermTree::PermTree(std::__debug::vector<int, std::allocator<int> > const&):
✗ Branch 31 → 32 not taken.
✓ Branch 31 → 38 taken 5913 times.
wala::PermTree::PermTree(std::vector<int, std::allocator<int> > const&):
✗ Branch 7 → 8 not taken.
✓ Branch 7 → 9 taken 30 times.
✗ Branch 12 → 13 not taken.
✗ Branch 12 → 14 not taken.
|
5943 | if (A.empty()) { root = -1; return; } |
| 37 |
1/2✗ Branch 9 → 10 not taken.
✓ Branch 9 → 11 taken 30 times.
|
5943 | int N = int(A.size()); |
| 38 |
2/3wala::PermTree::PermTree(std::__debug::vector<int, std::allocator<int> > const&):
✓ Branch 46 → 47 taken 5913 times.
wala::PermTree::PermTree(std::vector<int, std::allocator<int> > const&):
✓ Branch 11 → 12 taken 30 times.
✗ Branch 17 → 18 not taken.
|
5943 | std::vector<int> nxt_earlier(N); |
| 39 |
2/3wala::PermTree::PermTree(std::__debug::vector<int, std::allocator<int> > const&):
✓ Branch 50 → 51 taken 5913 times.
wala::PermTree::PermTree(std::vector<int, std::allocator<int> > const&):
✓ Branch 12 → 13 taken 30 times.
✗ Branch 21 → 22 not taken.
|
5943 | std::vector<int> prv_earlier(N); |
| 40 |
4/6wala::PermTree::PermTree(std::__debug::vector<int, std::allocator<int> > const&):
✓ Branch 60 → 53 taken 40319 times.
✓ Branch 60 → 61 taken 5913 times.
wala::PermTree::PermTree(std::vector<int, std::allocator<int> > const&):
✓ Branch 15 → 14 taken 9031020 times.
✓ Branch 15 → 16 taken 30 times.
✗ Branch 27 → 24 not taken.
✗ Branch 27 → 28 not taken.
|
9077282 | for (int i = 0; i < N; i++) { |
| 41 | 9071339 | nxt_earlier[i] = i+1; | |
| 42 | 9071339 | prv_earlier[i] = i-1; | |
| 43 | } | ||
| 44 |
4/6wala::PermTree::PermTree(std::__debug::vector<int, std::allocator<int> > const&):
✓ Branch 83 → 62 taken 40319 times.
✓ Branch 83 → 84 taken 5913 times.
wala::PermTree::PermTree(std::vector<int, std::allocator<int> > const&):
✓ Branch 22 → 17 taken 9031020 times.
✓ Branch 22 → 23 taken 30 times.
✗ Branch 39 → 29 not taken.
✗ Branch 39 → 40 not taken.
|
9077282 | for (int i = N-1; i >= 0; i--) { |
| 45 |
2/2✓ Branch 17 → 18 taken 8124136 times.
✓ Branch 17 → 19 taken 906884 times.
|
9071339 | int a = A[i]; |
| 46 |
2/2✓ Branch 17 → 18 taken 8124136 times.
✓ Branch 17 → 19 taken 906884 times.
|
9071339 | int p = prv_earlier[a]; |
| 47 | 9071339 | int n = nxt_earlier[a]; | |
| 48 |
4/6wala::PermTree::PermTree(std::__debug::vector<int, std::allocator<int> > const&):
✓ Branch 72 → 73 taken 25148 times.
✓ Branch 72 → 77 taken 15171 times.
wala::PermTree::PermTree(std::vector<int, std::allocator<int> > const&):
✓ Branch 17 → 18 taken 8124136 times.
✓ Branch 17 → 19 taken 906884 times.
✗ Branch 32 → 33 not taken.
✗ Branch 32 → 35 not taken.
|
9071339 | if (p != -1) nxt_earlier[p] = n; |
| 49 |
4/6wala::PermTree::PermTree(std::__debug::vector<int, std::allocator<int> > const&):
✓ Branch 77 → 78 taken 25148 times.
✓ Branch 77 → 82 taken 15171 times.
wala::PermTree::PermTree(std::vector<int, std::allocator<int> > const&):
✓ Branch 19 → 20 taken 7674358 times.
✓ Branch 19 → 21 taken 1356662 times.
✗ Branch 35 → 36 not taken.
✗ Branch 35 → 38 not taken.
|
9071339 | if (n != N) prv_earlier[n] = p; |
| 50 | } | ||
| 51 | |||
| 52 | 5943 | struct cnd_t { | |
| 53 | int left; | ||
| 54 | int lo; | ||
| 55 | int lo_gap; | ||
| 56 | int hi; | ||
| 57 | int hi_gap; | ||
| 58 | int node; | ||
| 59 | }; | ||
| 60 | |||
| 61 |
2/3wala::PermTree::PermTree(std::__debug::vector<int, std::allocator<int> > const&):
✓ Branch 85 → 754 taken 5913 times.
wala::PermTree::PermTree(std::vector<int, std::allocator<int> > const&):
✓ Branch 23 → 64 taken 30 times.
✗ Branch 40 → 41 not taken.
|
5943 | std::vector<cnd_t> stk; stk.reserve(N); |
| 62 | |||
| 63 |
4/6wala::PermTree::PermTree(std::__debug::vector<int, std::allocator<int> > const&):
✓ Branch 754 → 86 taken 40319 times.
✓ Branch 754 → 755 taken 5913 times.
wala::PermTree::PermTree(std::vector<int, std::allocator<int> > const&):
✓ Branch 64 → 24 taken 9031020 times.
✓ Branch 64 → 65 taken 30 times.
✗ Branch 189 → 42 not taken.
✗ Branch 189 → 190 not taken.
|
9077282 | for (int i = 0; i < N; i++) { |
| 64 | 9071339 | int a = A[i]; | |
| 65 | 16311637 | while (true) { | |
| 66 |
12/20wala::PermTree::PermTree(std::__debug::vector<int, std::allocator<int> > const&):
✓ Branch 92 → 93 taken 45058 times.
✓ Branch 92 → 105 taken 5913 times.
✓ Branch 97 → 98 taken 39732 times.
✓ Branch 97 → 103 taken 5326 times.
✓ Branch 102 → 103 taken 5326 times.
✓ Branch 102 → 105 taken 34406 times.
wala::PermTree::PermTree(std::vector<int, std::allocator<int> > const&):
✓ Branch 25 → 26 taken 12640487 times.
✓ Branch 25 → 29 taken 30 times.
✓ Branch 26 → 27 taken 10835184 times.
✓ Branch 26 → 28 taken 1805303 times.
✓ Branch 27 → 28 taken 1804194 times.
✓ Branch 27 → 29 taken 9030990 times.
✗ Branch 45 → 46 not taken.
✗ Branch 45 → 51 not taken.
✗ Branch 47 → 48 not taken.
✗ Branch 47 → 50 not taken.
✗ Branch 49 → 50 not taken.
✗ Branch 49 → 51 not taken.
✗ Branch 52 → 53 not taken.
✗ Branch 52 → 97 not taken.
|
12691488 | if (!stk.empty() && (a < stk.back().lo_gap || a > stk.back().hi_gap)) { |
| 67 | 3620149 | assert(stk.size() >= 2); | |
| 68 |
4/4✓ Branch 33 → 34 taken 3382346 times.
✓ Branch 33 → 35 taken 227151 times.
✓ Branch 36 → 37 taken 3382342 times.
✓ Branch 36 → 38 taken 227155 times.
|
3641453 | stk.end()[-2].lo = std::min(stk.end()[-2].lo, stk.back().lo); |
| 69 |
2/2✓ Branch 36 → 37 taken 3382342 times.
✓ Branch 36 → 38 taken 227155 times.
|
3641453 | stk.end()[-2].hi = std::max(stk.end()[-2].hi, stk.back().hi); |
| 70 | |||
| 71 | 3620149 | int n = 2 * stk.back().left - 1; | |
| 72 | 3641453 | nodes[n].c = {stk.end()[-2].node, stk.end()[-1].node}; | |
| 73 | 3620149 | nodes[n].type = NodeType::PARTIAL; | |
| 74 | 3630801 | nodes[n].l = stk.end()[-2].left; | |
| 75 | 3620149 | nodes[n].r = i-1; | |
| 76 | 3630801 | nodes[n].lo = stk.end()[-2].lo; | |
| 77 | 3630801 | nodes[n].hi = stk.end()[-2].hi; | |
| 78 | |||
| 79 | 3620149 | stk.pop_back(); | |
| 80 | |||
| 81 | 3620149 | stk.back().node = n; | |
| 82 | } else { | ||
| 83 | ✗ | break; | |
| 84 | } | ||
| 85 | 3620149 | } | |
| 86 | |||
| 87 |
1/2✓ Branch 29 → 40 taken 9031020 times.
✗ Branch 101 → 102 not taken.
|
9111658 | stk.push_back({i, a, prv_earlier[a]+1, a, nxt_earlier[a]-1, 2*i}); |
| 88 | 9071339 | nodes[2*i].type = NodeType::LEAF; | |
| 89 | 9071339 | nodes[2*i].c = {-1, -1}; | |
| 90 | 9071339 | nodes[2*i].l = nodes[2*i].r = i; | |
| 91 | 9071339 | nodes[2*i].lo = nodes[2*i].hi = a; | |
| 92 | |||
| 93 |
25/32wala::PermTree::PermTree(std::__debug::vector<int, std::allocator<int> > const&):
✓ Branch 677 → 678 taken 46424 times.
✓ Branch 677 → 724 taken 17649 times.
✓ Branch 712 → 713 taken 23754 times.
✓ Branch 712 → 714 taken 22670 times.
✓ Branch 724 → 725 taken 46424 times.
✓ Branch 724 → 726 taken 17649 times.
✓ Branch 726 → 727 taken 46424 times.
✓ Branch 726 → 737 taken 17649 times.
✓ Branch 737 → 738 taken 46424 times.
✓ Branch 737 → 739 taken 17649 times.
✓ Branch 739 → 740 taken 46424 times.
✓ Branch 739 → 750 taken 17649 times.
✓ Branch 750 → 751 taken 46424 times.
✓ Branch 750 → 752 taken 17649 times.
✓ Branch 752 → 377 taken 23754 times.
✓ Branch 752 → 753 taken 40319 times.
wala::PermTree::PermTree(std::vector<int, std::allocator<int> > const&):
✗ Branch 51 → 52 not taken.
✓ Branch 51 → 53 taken 14452513 times.
✓ Branch 53 → 54 taken 12215708 times.
✓ Branch 53 → 61 taken 2236805 times.
✓ Branch 54 → 55 taken 4875561 times.
✓ Branch 54 → 56 taken 7340147 times.
✓ Branch 57 → 58 taken 3055661 times.
✓ Branch 57 → 59 taken 9160047 times.
✓ Branch 60 → 61 taken 6794215 times.
✓ Branch 60 → 62 taken 5421493 times.
✗ Branch 170 → 171 not taken.
✗ Branch 170 → 186 not taken.
✗ Branch 184 → 185 not taken.
✗ Branch 184 → 186 not taken.
✗ Branch 187 → 109 not taken.
✗ Branch 187 → 188 not taken.
|
14655858 | while (stk.size() >= 2 && std::max(stk.back().hi, stk.end()[-2].hi) - std::min(stk.back().lo, stk.end()[-2].lo) == i - stk.end()[-2].left) { |
| 94 | // merge these two nodes into one | ||
| 95 |
4/4✓ Branch 42 → 43 taken 2063479 times.
✓ Branch 42 → 44 taken 3358014 times.
✓ Branch 62 → 41 taken 1841728 times.
✓ Branch 62 → 63 taken 3579765 times.
|
5492755 | stk.end()[-2].lo = std::min(stk.end()[-2].lo, stk.back().lo); |
| 96 |
4/4✓ Branch 42 → 43 taken 2063479 times.
✓ Branch 42 → 44 taken 3358014 times.
✓ Branch 45 → 46 taken 1841728 times.
✓ Branch 45 → 47 taken 3579765 times.
|
5492755 | stk.end()[-2].hi = std::max(stk.end()[-2].hi, stk.back().hi); |
| 97 | |||
| 98 |
2/2✓ Branch 45 → 46 taken 1841728 times.
✓ Branch 45 → 47 taken 3579765 times.
|
5445247 | int n = 2 * stk.back().left - 1; |
| 99 |
2/2✓ Branch 45 → 46 taken 1841728 times.
✓ Branch 45 → 47 taken 3579765 times.
|
5492755 | nodes[n].c = {stk.end()[-2].node, stk.end()[-1].node}; |
| 100 |
4/6wala::PermTree::PermTree(std::__debug::vector<int, std::allocator<int> > const&):
✓ Branch 539 → 540 taken 10073 times.
✓ Branch 539 → 547 taken 13681 times.
wala::PermTree::PermTree(std::vector<int, std::allocator<int> > const&):
✓ Branch 45 → 46 taken 1841728 times.
✓ Branch 45 → 47 taken 3579765 times.
✗ Branch 139 → 140 not taken.
✗ Branch 139 → 142 not taken.
|
5492755 | if (stk.end()[-2].lo == stk.end()[-1].lo) { |
| 101 | 1851801 | nodes[n].type = NodeType::DECR; | |
| 102 |
4/6wala::PermTree::PermTree(std::__debug::vector<int, std::allocator<int> > const&):
✓ Branch 581 → 582 taken 10073 times.
✓ Branch 581 → 589 taken 3608 times.
wala::PermTree::PermTree(std::vector<int, std::allocator<int> > const&):
✓ Branch 47 → 48 taken 3358014 times.
✓ Branch 47 → 49 taken 221751 times.
✗ Branch 148 → 149 not taken.
✗ Branch 148 → 151 not taken.
|
3620808 | } else if (stk.end()[-2].hi == stk.end()[-1].hi) { |
| 103 | 3368087 | nodes[n].type = NodeType::INCR; | |
| 104 | } else { | ||
| 105 | 225359 | nodes[n].type = NodeType::FULL; | |
| 106 | } | ||
| 107 | 5469001 | nodes[n].l = stk.end()[-2].left; | |
| 108 | 5445247 | nodes[n].r = i; | |
| 109 | 5469001 | nodes[n].lo = stk.end()[-2].lo; | |
| 110 | 5469001 | nodes[n].hi = stk.end()[-2].hi; | |
| 111 | |||
| 112 | 5445247 | stk.pop_back(); | |
| 113 | 5445247 | stk.back().node = n; | |
| 114 | } | ||
| 115 | } | ||
| 116 | |||
| 117 | 5943 | assert(stk.size() == 1); | |
| 118 | 5943 | root = stk.back().node; | |
| 119 | 17769 | } | |
| 120 | }; | ||
| 121 | |||
| 122 | } // namespace wala | ||
| 123 |