tree/top_tree.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include <utility> | ||
| 4 | #include <cassert> | ||
| 5 | #include <array> | ||
| 6 | |||
| 7 | namespace wala { | ||
| 8 | |||
| 9 | /** | ||
| 10 | * Top tree! | ||
| 11 | * | ||
| 12 | * Usage: | ||
| 13 | * Make a `struct T : public top_tree_node_base<T>` (CRTP), which implements | ||
| 14 | * void update() | ||
| 15 | * void downdate() | ||
| 16 | * void do_flip_path() | ||
| 17 | * void do_other_operation() ... | ||
| 18 | * When update() is called, you can assume downdate() has already been called. | ||
| 19 | * | ||
| 20 | * In general, do_op() should eagerly apply the operation but not touch the | ||
| 21 | * children. In downdate(), you can push down to the children with ch->do_op(). | ||
| 22 | * WARNING: if different operations do not trivially commute, you *must* | ||
| 23 | * implement a way to swap/alter them to compose in a consistent order, and you | ||
| 24 | * must use that order when implementing downdate(). This can be nontrivial! | ||
| 25 | * | ||
| 26 | * Creating vertices: | ||
| 27 | * n->is_path = n->is_vert = true; | ||
| 28 | * n->update(); | ||
| 29 | * | ||
| 30 | * Creating edges: no setup/update() needed, just call | ||
| 31 | * link(e, va, vb); | ||
| 32 | * | ||
| 33 | * Updates: | ||
| 34 | * auto cur = get_path(va, vb); // or get_subtree(va, vb) | ||
| 35 | * cur->do_stuff(); | ||
| 36 | * cur->update_parents(); or cur->downdate(), cur->update_all(); | ||
| 37 | * | ||
| 38 | * IMPORTANT: Call downdate() before any manual update() | ||
| 39 | * | ||
| 40 | * Node types: | ||
| 41 | * path edges: compress(c[0], self, c[1]) | ||
| 42 | * assert(is_path && !is_vert); | ||
| 43 | * assert(c[0] && c[1]); | ||
| 44 | * assert(c[0]->is_path && c[1]->is_path); | ||
| 45 | * assert(!c[2]); | ||
| 46 | * (path) vertices: self + rake(c[0], c[1]) | ||
| 47 | * assert(is_path && is_vert); | ||
| 48 | * assert(!c[2]); | ||
| 49 | * if (c[0]) assert(!c[0]->is_path); | ||
| 50 | * if (c[1]) assert(!c[1]->is_path); | ||
| 51 | * non-path edges: rake(c[0], self + c[2], c[1]) | ||
| 52 | * assert(!is_path && !is_vert); | ||
| 53 | * assert(c[2]) | ||
| 54 | * assert(c[2]->is_path); | ||
| 55 | * if (c[0]) assert(!c[0]->is_path); | ||
| 56 | * if (c[1]) assert(!c[1]->is_path); | ||
| 57 | */ | ||
| 58 | |||
| 59 | 15492022 | template <typename top_tree_node> struct top_tree_node_base { | |
| 60 | private: | ||
| 61 | ✗ | top_tree_node* derived_this() { | |
| 62 | ✗ | return static_cast<top_tree_node*>(this); | |
| 63 | } | ||
| 64 | ✗ | const top_tree_node* derived_this() const { | |
| 65 | ✗ | return static_cast<const top_tree_node*>(this); | |
| 66 | } | ||
| 67 | |||
| 68 | public: | ||
| 69 | mutable top_tree_node* p = nullptr; | ||
| 70 | std::array<top_tree_node*, 3> c{nullptr, nullptr, nullptr}; | ||
| 71 | |||
| 72 | 3294227471 | int d() const { | |
| 73 | 3294227471 | assert(p); | |
| 74 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::d() const:
✓ Branch 4 → 5 taken 1455460768 times.
✓ Branch 4 → 8 taken 725824111 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::d() const:
✓ Branch 4 → 5 taken 377365556 times.
✓ Branch 4 → 8 taken 224651684 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::d() const:
✓ Branch 4 → 5 taken 320871801 times.
✓ Branch 4 → 8 taken 190053551 times.
|
3294227471 | if (this == p->c[0]) { |
| 75 | return 0; | ||
| 76 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::d() const:
✓ Branch 5 → 6 taken 71583654 times.
✓ Branch 5 → 8 taken 1383877114 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::d() const:
✓ Branch 5 → 6 taken 29159670 times.
✓ Branch 5 → 8 taken 348205886 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::d() const:
✓ Branch 5 → 6 taken 19371311 times.
✓ Branch 5 → 8 taken 301500490 times.
|
2153698125 | } else if (this == p->c[1]) { |
| 77 | return 1; | ||
| 78 |
3/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::d() const:
✗ Branch 6 → 7 not taken.
✓ Branch 6 → 8 taken 71583654 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::d() const:
✗ Branch 6 → 7 not taken.
✓ Branch 6 → 8 taken 29159670 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::d() const:
✗ Branch 6 → 7 not taken.
✓ Branch 6 → 8 taken 19371311 times.
|
120114635 | } else if (this == p->c[2]) { |
| 79 | return 2; | ||
| 80 | − | } else assert(false); | |
| 81 | } | ||
| 82 | 769547211 | top_tree_node*& p_c() const { return p->c[d()]; } // p->c which points to you | |
| 83 | |||
| 84 | // 3 types of verts: path edges, path verts, non-path edges | ||
| 85 | bool is_path; | ||
| 86 | bool is_vert; | ||
| 87 | |||
| 88 |
27/36✓ Branch 3 → 4 taken 119662352 times.
✓ Branch 3 → 7 taken 7607681 times.
✓ Branch 4 → 5 taken 954266089 times.
✗ Branch 4 → 7 not taken.
✗ Branch 4 → 8 not taken.
✓ Branch 4 → 10 taken 16253968 times.
✓ Branch 4 → 29 taken 51590383 times.
✓ Branch 5 → 6 taken 1024623233 times.
✗ Branch 5 → 7 not taken.
✗ Branch 5 → 8 not taken.
✗ Branch 5 → 10 not taken.
✓ Branch 5 → 29 taken 7183093 times.
✓ Branch 6 → 7 taken 82541567 times.
✗ Branch 6 → 10 not taken.
✓ Branch 7 → 8 taken 158874089 times.
✓ Branch 7 → 11 taken 7183093 times.
✓ Branch 8 → 9 taken 114474697 times.
✓ Branch 8 → 14 taken 29734730 times.
✓ Branch 9 → 10 taken 319358722 times.
✓ Branch 9 → 12 taken 22749373 times.
✓ Branch 9 → 29 taken 22749373 times.
✓ Branch 12 → 13 taken 55318764 times.
✓ Branch 12 → 14 taken 122044618 times.
✓ Branch 12 → 18 taken 7183093 times.
✓ Branch 16 → 17 taken 153570647 times.
✓ Branch 16 → 18 taken 66759131 times.
✓ Branch 19 → 20 taken 77457274 times.
✓ Branch 19 → 25 taken 23571895 times.
✓ Branch 20 → 21 taken 82541567 times.
✓ Branch 20 → 26 taken 16388802 times.
✗ Branch 23 → 24 not taken.
✓ Branch 23 → 25 taken 66759131 times.
✗ Branch 24 → 25 not taken.
✓ Branch 24 → 26 taken 60398560 times.
✗ Branch 27 → 28 not taken.
✓ Branch 27 → 29 taken 60398560 times.
|
2699438159 | bool r() const { return !p || p->is_path != is_path; } |
| 89 | |||
| 90 | private: | ||
| 91 | // Convenience wrappers for the derived functions. | ||
| 92 | ✗ | void do_flip_path() { | |
| 93 | ✗ | derived_this()->do_flip_path(); | |
| 94 | } | ||
| 95 | 871740121 | void downdate() { | |
| 96 | 871740121 | derived_this()->downdate(); | |
| 97 | } | ||
| 98 | ✗ | void update() { | |
| 99 | ✗ | derived_this()->update(); | |
| 100 | } | ||
| 101 | |||
| 102 | public: | ||
| 103 | 871740121 | void downdate_all() { | |
| 104 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::downdate_all():
✓ Branch 2 → 3 taken 506508257 times.
✓ Branch 2 → 4 taken 58631397 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::downdate_all():
✓ Branch 2 → 3 taken 151294784 times.
✓ Branch 2 → 4 taken 12900816 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::downdate_all():
✓ Branch 2 → 3 taken 128233384 times.
✓ Branch 2 → 4 taken 14171483 times.
|
871740121 | if (p) p->downdate_all(); |
| 105 | 871740121 | downdate(); | |
| 106 | 871740121 | } | |
| 107 | |||
| 108 | // Returns the root | ||
| 109 | 116997116 | top_tree_node* update_all() { | |
| 110 | 116997116 | derived_this()->update(); | |
| 111 | 116997116 | return update_parents(); | |
| 112 | } | ||
| 113 | |||
| 114 | 117645394 | top_tree_node* update_parents() { | |
| 115 | 117645394 | top_tree_node* cur = derived_this(); | |
| 116 |
4/4✓ Branch 4 → 3 taken 59526744 times.
✓ Branch 4 → 5 taken 116997116 times.
✓ Branch 37 → 36 taken 648278 times.
✓ Branch 37 → 38 taken 648278 times.
|
177820416 | while (cur->p) { |
| 117 | 60175022 | cur = cur->p; | |
| 118 | 60175022 | cur->update(); | |
| 119 | } | ||
| 120 | return cur; | ||
| 121 | } | ||
| 122 | |||
| 123 | private: | ||
| 124 | 571627380 | void rot() { | |
| 125 | 571627380 | assert(!is_vert); | |
| 126 | ✗ | assert(!r()); | |
| 127 | 571627380 | top_tree_node* pa = p; | |
| 128 | 571627380 | int x = d(); assert(x == 0 || x == 1); | |
| 129 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::rot():
✓ Branch 10 → 11 taken 303741202 times.
✓ Branch 10 → 13 taken 64229697 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::rot():
✓ Branch 10 → 11 taken 98151461 times.
✓ Branch 10 → 13 taken 12999858 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::rot():
✓ Branch 10 → 11 taken 78870957 times.
✓ Branch 10 → 13 taken 13634205 times.
|
571627380 | top_tree_node* ch = c[!x]; |
| 130 | |||
| 131 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::rot():
✓ Branch 10 → 11 taken 303741202 times.
✓ Branch 10 → 13 taken 64229697 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::rot():
✓ Branch 10 → 11 taken 98151461 times.
✓ Branch 10 → 13 taken 12999858 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::rot():
✓ Branch 10 → 11 taken 78870957 times.
✓ Branch 10 → 13 taken 13634205 times.
|
571627380 | if (pa->p) pa->p_c() = derived_this(); |
| 132 | 571627380 | this->p = pa->p; | |
| 133 | |||
| 134 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::rot():
✓ Branch 13 → 14 taken 321704292 times.
✓ Branch 13 → 15 taken 46266607 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::rot():
✓ Branch 13 → 14 taken 95039672 times.
✓ Branch 13 → 15 taken 16111647 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::rot():
✓ Branch 13 → 14 taken 83585917 times.
✓ Branch 13 → 15 taken 8919245 times.
|
571627380 | pa->c[x] = ch; |
| 135 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::rot():
✓ Branch 13 → 14 taken 321704292 times.
✓ Branch 13 → 15 taken 46266607 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::rot():
✓ Branch 13 → 14 taken 95039672 times.
✓ Branch 13 → 15 taken 16111647 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::rot():
✓ Branch 13 → 14 taken 83585917 times.
✓ Branch 13 → 15 taken 8919245 times.
|
571627380 | if (ch) ch->p = pa; |
| 136 | |||
| 137 | 571627380 | this->c[!x] = pa; | |
| 138 | 571627380 | pa->p = derived_this(); | |
| 139 | |||
| 140 | 571627380 | pa->update(); | |
| 141 | 571627380 | } | |
| 142 | |||
| 143 | 191849884 | void rot_2(int c_d) { | |
| 144 | 191849884 | assert(!is_vert); | |
| 145 | ✗ | assert(!r()); | |
| 146 | 191849884 | assert(c[c_d]); | |
| 147 | 191849884 | assert(!c[c_d]->is_vert); | |
| 148 | |||
| 149 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::rot_2(int):
✓ Branch 12 → 13 taken 61238991 times.
✓ Branch 12 → 15 taken 66382283 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::rot_2(int):
✓ Branch 12 → 13 taken 18260876 times.
✓ Branch 12 → 15 taken 16242584 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::rot_2(int):
✓ Branch 12 → 13 taken 15965886 times.
✓ Branch 12 → 15 taken 13759264 times.
|
191849884 | if (d() == c_d) { |
| 150 | 95465753 | rot(); | |
| 151 | 95465753 | return; | |
| 152 | } | ||
| 153 | |||
| 154 | 96384131 | top_tree_node* pa = p; | |
| 155 | 96384131 | int x = d(); assert(x == 0 || x == 1); | |
| 156 | 96384131 | assert(c_d == !x); | |
| 157 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::rot_2(int):
✓ Branch 19 → 20 taken 61126696 times.
✓ Branch 19 → 22 taken 5255587 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::rot_2(int):
✓ Branch 19 → 20 taken 14496910 times.
✓ Branch 19 → 22 taken 1745674 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::rot_2(int):
✓ Branch 19 → 20 taken 13200447 times.
✓ Branch 19 → 22 taken 558817 times.
|
96384131 | top_tree_node* ch = c[c_d]->c[!x]; |
| 158 | |||
| 159 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::rot_2(int):
✓ Branch 19 → 20 taken 61126696 times.
✓ Branch 19 → 22 taken 5255587 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::rot_2(int):
✓ Branch 19 → 20 taken 14496910 times.
✓ Branch 19 → 22 taken 1745674 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::rot_2(int):
✓ Branch 19 → 20 taken 13200447 times.
✓ Branch 19 → 22 taken 558817 times.
|
96384131 | if (pa->p) pa->p_c() = derived_this(); |
| 160 | 96384131 | this->p = pa->p; | |
| 161 | |||
| 162 |
3/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::rot_2(int):
✓ Branch 22 → 23 taken 66382283 times.
✗ Branch 22 → 24 not taken.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::rot_2(int):
✓ Branch 22 → 23 taken 16242584 times.
✗ Branch 22 → 24 not taken.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::rot_2(int):
✓ Branch 22 → 23 taken 13759264 times.
✗ Branch 22 → 24 not taken.
|
96384131 | pa->c[x] = ch; |
| 163 |
3/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::rot_2(int):
✓ Branch 22 → 23 taken 66382283 times.
✗ Branch 22 → 24 not taken.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::rot_2(int):
✓ Branch 22 → 23 taken 16242584 times.
✗ Branch 22 → 24 not taken.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::rot_2(int):
✓ Branch 22 → 23 taken 13759264 times.
✗ Branch 22 → 24 not taken.
|
96384131 | if (ch) ch->p = pa; |
| 164 | |||
| 165 | 96384131 | this->c[c_d]->c[!x] = pa; | |
| 166 | 96384131 | pa->p = this->c[c_d]; | |
| 167 | |||
| 168 | 96384131 | pa->update(); | |
| 169 | } | ||
| 170 | |||
| 171 | 178604402 | void splay_dir(int x) { | |
| 172 |
12/12wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::splay_dir(int):
✓ Branch 8 → 9 taken 171106075 times.
✓ Branch 8 → 12 taken 52530025 times.
✓ Branch 11 → 12 taken 57174742 times.
✓ Branch 11 → 13 taken 102723397 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::splay_dir(int):
✓ Branch 8 → 9 taken 47628223 times.
✓ Branch 8 → 12 taken 8587933 times.
✓ Branch 11 → 12 taken 13879166 times.
✓ Branch 11 → 13 taken 26595181 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::splay_dir(int):
✓ Branch 8 → 9 taken 40832230 times.
✓ Branch 8 → 12 taken 12195504 times.
✓ Branch 11 → 12 taken 11487659 times.
✓ Branch 11 → 13 taken 24957010 times.
|
569697145 | while (!r() && d() == x) { |
| 173 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::splay_dir(int):
✓ Branch 5 → 6 taken 62151040 times.
✓ Branch 5 → 7 taken 17429194 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::splay_dir(int):
✓ Branch 5 → 6 taken 16789923 times.
✓ Branch 5 → 7 taken 3958113 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::splay_dir(int):
✓ Branch 5 → 6 taken 15788234 times.
✓ Branch 5 → 7 taken 3545848 times.
|
119662352 | if (!p->r() && p->d() == x) { |
| 174 | 94729197 | p->rot(); | |
| 175 | } | ||
| 176 | 154275588 | rot(); | |
| 177 | } | ||
| 178 | 178604402 | } | |
| 179 | |||
| 180 | 82541567 | void splay_2(int c_d) { | |
| 181 | 82541567 | assert(!is_vert && is_path); | |
| 182 | 82541567 | assert(c[c_d] && !c[c_d]->is_vert); | |
| 183 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::splay_2(int):
✓ Branch 15 → 16 taken 146303309 times.
✓ Branch 15 → 18 taken 13214843 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::splay_2(int):
✓ Branch 15 → 16 taken 36751804 times.
✓ Branch 15 → 18 taken 4929000 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::splay_2(int):
✓ Branch 15 → 16 taken 30914094 times.
✓ Branch 15 → 18 taken 3999164 times.
|
236112214 | while (!r()) { |
| 184 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::splay_2(int):
✓ Branch 17 → 8 taken 96130537 times.
✓ Branch 17 → 14 taken 6212873 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::splay_2(int):
✓ Branch 17 → 8 taken 25901665 times.
✓ Branch 17 → 14 taken 1899973 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::splay_2(int):
✓ Branch 17 → 8 taken 22177225 times.
✓ Branch 17 → 14 taken 1248374 times.
|
153570647 | if (!p->r()) { |
| 185 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::splay_2(int):
✓ Branch 11 → 12 taken 49094495 times.
✓ Branch 11 → 13 taken 25277864 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::splay_2(int):
✓ Branch 11 → 12 taken 14782112 times.
✓ Branch 11 → 13 taken 6701822 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::splay_2(int):
✓ Branch 11 → 12 taken 12318853 times.
✓ Branch 11 → 13 taken 6299551 times.
|
114474697 | if (p->d() == d()) { |
| 186 | 76195460 | p->rot(); | |
| 187 | } else { | ||
| 188 | 38279237 | rot_2(c_d); | |
| 189 | } | ||
| 190 | } | ||
| 191 | 153570647 | rot_2(c_d); | |
| 192 | } | ||
| 193 | 82541567 | } | |
| 194 | |||
| 195 | 82541567 | void splay_2() { | |
| 196 | 82541567 | assert(!is_vert && is_path); | |
| 197 | 82541567 | assert(!r()); | |
| 198 | 82541567 | p->splay_2(d()); | |
| 199 | 82541567 | } | |
| 200 | |||
| 201 | 237377878 | void splay_vert() { | |
| 202 | 237377878 | assert(is_vert); | |
| 203 | 415982280 | if (r()) { | |
| 204 | return; | ||
| 205 | } | ||
| 206 | 178604402 | p->splay_dir(d()); | |
| 207 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::splay_vert():
✓ Branch 8 → 9 taken 68382678 times.
✓ Branch 8 → 29 taken 52530025 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::splay_vert():
✓ Branch 8 → 9 taken 21033042 times.
✓ Branch 8 → 29 taken 8587933 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::splay_vert():
✓ Branch 8 → 9 taken 15875220 times.
✓ Branch 8 → 29 taken 12195504 times.
|
178604402 | if (p->r()) { |
| 208 | return; | ||
| 209 | } | ||
| 210 | |||
| 211 | 82541567 | assert(p->d() != d()); | |
| 212 | // we have a preference to be the left child | ||
| 213 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::splay_vert():
✓ Branch 14 → 15 taken 26767592 times.
✓ Branch 14 → 16 taken 30407150 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::splay_vert():
✓ Branch 14 → 15 taken 5853255 times.
✓ Branch 14 → 16 taken 8025911 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::splay_vert():
✓ Branch 14 → 15 taken 4528893 times.
✓ Branch 14 → 16 taken 6958766 times.
|
82541567 | if (d() == 1) { |
| 214 | 37149740 | p->rot(); | |
| 215 | } | ||
| 216 | 82541567 | assert(d() == 0); | |
| 217 | |||
| 218 | 82541567 | p->splay_2(); | |
| 219 | 82541567 | assert(d() == 0); | |
| 220 | 82541567 | assert(p->d() == 1); | |
| 221 | 82541567 | assert(p->p->r()); | |
| 222 | } | ||
| 223 | |||
| 224 | 122044618 | void splay() { | |
| 225 | 122044618 | assert(!is_vert); | |
| 226 |
3/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::splay():
✓ Branch 11 → 12 taken 88730700 times.
✗ Branch 11 → 14 not taken.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::splay():
✓ Branch 11 → 12 taken 30758009 times.
✗ Branch 11 → 14 not taken.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::splay():
✓ Branch 11 → 12 taken 23811207 times.
✗ Branch 11 → 14 not taken.
|
143299916 | while (!r()) { |
| 227 |
3/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::splay():
✓ Branch 13 → 4 taken 7886779 times.
✗ Branch 13 → 10 not taken.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::splay():
✓ Branch 13 → 4 taken 8095591 times.
✗ Branch 13 → 10 not taken.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::splay():
✓ Branch 13 → 4 taken 5272928 times.
✗ Branch 13 → 10 not taken.
|
21255298 | if (!p->r()) { |
| 228 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::splay():
✓ Branch 7 → 8 taken 530408 times.
✓ Branch 7 → 9 taken 433512 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::splay():
✓ Branch 7 → 8 taken 1372643 times.
✓ Branch 7 → 9 taken 1166538 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::splay():
✓ Branch 7 → 8 taken 815122 times.
✓ Branch 7 → 9 taken 683107 times.
|
5001330 | if (p->d() == d()) { |
| 229 | 2718173 | p->rot(); | |
| 230 | } else { | ||
| 231 | 2283157 | rot(); | |
| 232 | } | ||
| 233 | } | ||
| 234 | 21255298 | rot(); | |
| 235 | } | ||
| 236 | 122044618 | } | |
| 237 | |||
| 238 | 206733139 | top_tree_node* cut_right() { | |
| 239 | 206733139 | assert(is_vert && is_path); | |
| 240 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::cut_right():
✓ Branch 6 → 7 taken 111487712 times.
✓ Branch 6 → 11 taken 27436753 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::cut_right():
✓ Branch 6 → 7 taken 28616299 times.
✓ Branch 6 → 11 taken 6678936 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::cut_right():
✓ Branch 6 → 7 taken 25953171 times.
✓ Branch 6 → 11 taken 6560268 times.
|
206733139 | splay_vert(); |
| 241 | |||
| 242 |
12/12wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::cut_right():
✓ Branch 9 → 10 taken 82142646 times.
✓ Branch 9 → 11 taken 23848958 times.
✓ Branch 11 → 12 taken 29345066 times.
✓ Branch 11 → 18 taken 27436753 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::cut_right():
✓ Branch 9 → 10 taken 23395895 times.
✓ Branch 9 → 11 taken 4519197 times.
✓ Branch 11 → 12 taken 5220404 times.
✓ Branch 11 → 18 taken 6678936 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::cut_right():
✓ Branch 9 → 10 taken 19272082 times.
✓ Branch 9 → 11 taken 5695311 times.
✓ Branch 11 → 12 taken 6681089 times.
✓ Branch 11 → 18 taken 6560268 times.
|
206733139 | if (r() || d() == 1) { |
| 243 | 34063466 | assert(r() || (d() == 1 && p->r())); | |
| 244 | 81922516 | assert(c[0] == nullptr); | |
| 245 | return nullptr; | ||
| 246 | } | ||
| 247 | |||
| 248 | 124810623 | top_tree_node* pa = p; | |
| 249 | 207352190 | assert(pa->r() || (pa->d() == 1 && pa->p->r())); | |
| 250 | 124810623 | assert(!pa->is_vert); | |
| 251 | 124810623 | assert(pa->is_path); | |
| 252 | 124810623 | assert(pa->c[0] == this); | |
| 253 | 124810623 | assert(pa->c[2] == nullptr); | |
| 254 | |||
| 255 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::cut_right():
✓ Branch 34 → 35 taken 63728106 times.
✓ Branch 34 → 37 taken 18414540 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::cut_right():
✓ Branch 34 → 35 taken 20270759 times.
✓ Branch 34 → 37 taken 3125136 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::cut_right():
✓ Branch 34 → 35 taken 14931504 times.
✓ Branch 34 → 37 taken 4340578 times.
|
124810623 | if (pa->p) pa->p_c() = derived_this(); |
| 256 | 124810623 | this->p = pa->p; | |
| 257 | |||
| 258 | 124810623 | pa->is_path = false; | |
| 259 | 124810623 | pa->c[2] = pa->c[1]; // don't need to change the parent | |
| 260 | |||
| 261 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::cut_right():
✓ Branch 37 → 38 taken 46390136 times.
✓ Branch 37 → 39 taken 35752510 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::cut_right():
✓ Branch 37 → 38 taken 17856900 times.
✓ Branch 37 → 39 taken 5538995 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::cut_right():
✓ Branch 37 → 38 taken 12512407 times.
✓ Branch 37 → 39 taken 6759675 times.
|
124810623 | pa->c[0] = c[0]; if (c[0]) c[0]->p = pa; |
| 262 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::cut_right():
✓ Branch 39 → 40 taken 40640981 times.
✓ Branch 39 → 41 taken 41501665 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::cut_right():
✓ Branch 39 → 40 taken 14169991 times.
✓ Branch 39 → 41 taken 9225904 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::cut_right():
✓ Branch 39 → 40 taken 10980858 times.
✓ Branch 39 → 41 taken 8291224 times.
|
124810623 | pa->c[1] = c[1]; if (c[1]) c[1]->p = pa; |
| 263 | |||
| 264 | 124810623 | c[0] = nullptr; | |
| 265 | 124810623 | c[1] = pa; pa->p = derived_this(); | |
| 266 | 124810623 | assert(c[2] == nullptr); | |
| 267 | |||
| 268 | 124810623 | assert(c[0] == nullptr); | |
| 269 | |||
| 270 | 124810623 | pa->update(); | |
| 271 | 124810623 | return pa; | |
| 272 | } | ||
| 273 | |||
| 274 | 121029443 | top_tree_node* splice_non_path() { | |
| 275 | 121029443 | assert(!is_path); | |
| 276 | 121029443 | assert(!is_vert); | |
| 277 | |||
| 278 | 121029443 | splay(); | |
| 279 | 121029443 | assert(p && p->is_vert && p->is_path); | |
| 280 | 121029443 | p->cut_right(); | |
| 281 | |||
| 282 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::splice_non_path():
✓ Branch 12 → 13 taken 57144685 times.
✓ Branch 12 → 14 taken 23148383 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::splice_non_path():
✓ Branch 12 → 13 taken 18235200 times.
✓ Branch 12 → 14 taken 4159219 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::splice_non_path():
✓ Branch 12 → 13 taken 12175129 times.
✓ Branch 12 → 14 taken 6166827 times.
|
121029443 | if (!p->is_path) rot(); |
| 283 | 121029443 | assert(p && p->is_vert && p->is_path); | |
| 284 | 198486717 | assert(p->r() || (p->d() == 1 && p->p->r())); | |
| 285 | 121029443 | assert(p->c[d()] == this && p->c[!d()] == nullptr); | |
| 286 | |||
| 287 | 121029443 | top_tree_node* pa = p; | |
| 288 | |||
| 289 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::splice_non_path():
✓ Branch 29 → 30 taken 67291569 times.
✓ Branch 29 → 32 taken 13001499 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::splice_non_path():
✓ Branch 29 → 30 taken 18978895 times.
✓ Branch 29 → 32 taken 3415524 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::splice_non_path():
✓ Branch 29 → 30 taken 14758705 times.
✓ Branch 29 → 32 taken 3583251 times.
|
121029443 | if (pa->p) pa->p_c() = derived_this(); |
| 290 | 121029443 | this->p = pa->p; | |
| 291 | |||
| 292 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::splice_non_path():
✓ Branch 32 → 33 taken 47180581 times.
✓ Branch 32 → 34 taken 33112487 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::splice_non_path():
✓ Branch 32 → 33 taken 18091201 times.
✓ Branch 32 → 34 taken 4303218 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::splice_non_path():
✓ Branch 32 → 33 taken 12495938 times.
✓ Branch 32 → 34 taken 5846018 times.
|
121029443 | pa->c[0] = c[0]; if (c[0]) c[0]->p = pa; |
| 293 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::splice_non_path():
✓ Branch 34 → 35 taken 39931424 times.
✓ Branch 34 → 36 taken 40361644 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::splice_non_path():
✓ Branch 34 → 35 taken 13814507 times.
✓ Branch 34 → 36 taken 8579912 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::splice_non_path():
✓ Branch 34 → 35 taken 10902972 times.
✓ Branch 34 → 36 taken 7438984 times.
|
121029443 | pa->c[1] = c[1]; if (c[1]) c[1]->p = pa; |
| 294 | |||
| 295 | 121029443 | assert(c[2] && c[2]->is_path); | |
| 296 | 121029443 | c[1] = c[2]; // don't need to change parent | |
| 297 | 121029443 | c[0] = pa; pa->p = derived_this(); | |
| 298 | 121029443 | c[2] = nullptr; | |
| 299 | |||
| 300 | 121029443 | is_path = true; | |
| 301 | |||
| 302 | 121029443 | pa->update(); | |
| 303 | 121029443 | return pa; | |
| 304 | } | ||
| 305 | |||
| 306 | // Return the topmost vertex which was spliced into, self if none | ||
| 307 | 85703696 | top_tree_node* splice_all() { | |
| 308 | 85703696 | top_tree_node* res = derived_this(); | |
| 309 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::splice_all():
✓ Branch 8 → 3 taken 274595506 times.
✓ Branch 8 → 9 taken 58631397 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::splice_all():
✓ Branch 8 → 3 taken 77128947 times.
✓ Branch 8 → 9 taken 12900816 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::splice_all():
✓ Branch 8 → 3 taken 80582019 times.
✓ Branch 8 → 9 taken 14171483 times.
|
518010168 | for (top_tree_node* cur = derived_this(); cur; cur = cur->p) { |
| 310 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::splice_all():
✓ Branch 3 → 4 taken 80293068 times.
✓ Branch 3 → 5 taken 194302438 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::splice_all():
✓ Branch 3 → 4 taken 22394419 times.
✓ Branch 3 → 5 taken 54734528 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::splice_all():
✓ Branch 3 → 4 taken 18341956 times.
✓ Branch 3 → 5 taken 62240063 times.
|
432306472 | if (!cur->is_path) { |
| 311 | 121029443 | res = cur->splice_non_path(); | |
| 312 | } | ||
| 313 | 432306472 | assert(cur->is_path); | |
| 314 | } | ||
| 315 | 85703696 | return res; | |
| 316 | } | ||
| 317 | |||
| 318 | public: | ||
| 319 | // Return the topmost vertex which was spliced into, self if none | ||
| 320 | 82264095 | top_tree_node* expose() { | |
| 321 | 82264095 | assert(is_vert); | |
| 322 | 82264095 | downdate_all(); | |
| 323 | |||
| 324 | 82264095 | top_tree_node* res = splice_all(); | |
| 325 | |||
| 326 | 82264095 | cut_right(); | |
| 327 | |||
| 328 | 82264095 | update_all(); | |
| 329 | |||
| 330 | 82264095 | return res; | |
| 331 | } | ||
| 332 | |||
| 333 | // Return the topmost vertex which was spliced into, self (an edge) if none. | ||
| 334 | 3439601 | top_tree_node* expose_edge() { | |
| 335 | 3439601 | assert(!is_vert); | |
| 336 | 3439601 | downdate_all(); | |
| 337 | |||
| 338 |
3/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::expose_edge():
✓ Branch 5 → 6 taken 2141718 times.
✗ Branch 5 → 7 not taken.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::expose_edge():
✓ Branch 5 → 6 taken 650106 times.
✗ Branch 5 → 7 not taken.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::expose_edge():
✓ Branch 5 → 6 taken 647777 times.
✗ Branch 5 → 7 not taken.
|
3439601 | top_tree_node* v = is_path ? c[1] : c[2]; |
| 339 | 3439601 | v->downdate(); | |
| 340 | |||
| 341 |
4/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::expose_edge():
✓ Branch 11 → 10 taken 2974925 times.
✓ Branch 11 → 12 taken 2141718 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::expose_edge():
✗ Branch 11 → 10 not taken.
✓ Branch 11 → 12 taken 650106 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::expose_edge():
✗ Branch 11 → 10 not taken.
✓ Branch 11 → 12 taken 647777 times.
|
6414526 | while (!v->is_vert) { |
| 342 | 2974925 | v = v->c[0]; | |
| 343 | 2974925 | v->downdate(); | |
| 344 | } | ||
| 345 | |||
| 346 | 3439601 | top_tree_node* res = v->splice_all(); | |
| 347 | 3439601 | v->cut_right(); | |
| 348 | 3439601 | v->update_all(); | |
| 349 | |||
| 350 | 3439601 | assert(!p); | |
| 351 | 3439601 | assert(v == c[1]); | |
| 352 | |||
| 353 |
3/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::expose_edge():
✗ Branch 19 → 20 not taken.
✓ Branch 19 → 21 taken 2141718 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::expose_edge():
✗ Branch 19 → 20 not taken.
✓ Branch 19 → 21 taken 650106 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::expose_edge():
✗ Branch 19 → 20 not taken.
✓ Branch 19 → 21 taken 647777 times.
|
3439601 | return res == v ? derived_this() : res; |
| 354 | } | ||
| 355 | |||
| 356 | // Return the new root | ||
| 357 | 30644739 | top_tree_node* meld_path_end() { | |
| 358 | 30644739 | assert(!p); | |
| 359 | top_tree_node* rt = derived_this(); | ||
| 360 | 55285758 | while (true) { | |
| 361 | 85930497 | rt->downdate(); | |
| 362 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::meld_path_end():
✓ Branch 6 → 7 taken 41888523 times.
✓ Branch 6 → 8 taken 20971611 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::meld_path_end():
✓ Branch 6 → 7 taken 5225344 times.
✓ Branch 6 → 8 taken 4517449 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::meld_path_end():
✓ Branch 6 → 7 taken 8171891 times.
✓ Branch 6 → 8 taken 5155679 times.
|
85930497 | if (rt->is_vert) break; |
| 363 | 55285758 | rt = rt->c[1]; | |
| 364 | } | ||
| 365 | assert(rt->is_vert); | ||
| 366 | 30644739 | rt->splay_vert(); | |
| 367 |
12/12wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::meld_path_end():
✓ Branch 9 → 10 taken 5194700 times.
✓ Branch 9 → 11 taken 15776911 times.
✓ Branch 10 → 11 taken 4643847 times.
✓ Branch 10 → 12 taken 550853 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::meld_path_end():
✓ Branch 9 → 10 taken 767844 times.
✓ Branch 9 → 11 taken 3749605 times.
✓ Branch 10 → 11 taken 499845 times.
✓ Branch 10 → 12 taken 267999 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::meld_path_end():
✓ Branch 9 → 10 taken 1146370 times.
✓ Branch 9 → 11 taken 4009309 times.
✓ Branch 10 → 11 taken 950047 times.
✓ Branch 10 → 12 taken 196323 times.
|
30644739 | if (rt->c[0] && rt->c[1]) { |
| 368 | top_tree_node* ch = rt->c[1]; | ||
| 369 | while (true) { | ||
| 370 | 1303361 | ch->downdate(); | |
| 371 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::meld_path_end():
✓ Branch 14 → 15 taken 65898 times.
✓ Branch 14 → 16 taken 550853 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::meld_path_end():
✓ Branch 14 → 15 taken 143679 times.
✓ Branch 14 → 16 taken 267999 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::meld_path_end():
✓ Branch 14 → 15 taken 78609 times.
✓ Branch 14 → 16 taken 196323 times.
|
1303361 | if (!ch->c[0]) break; |
| 372 | ch = ch->c[0]; | ||
| 373 | } | ||
| 374 | 1015175 | ch->splay(); | |
| 375 | 1015175 | assert(ch->c[0] == nullptr); | |
| 376 | |||
| 377 | 1015175 | ch->c[0] = rt->c[0]; | |
| 378 | 1015175 | ch->c[0]->p = ch; | |
| 379 | |||
| 380 | 1015175 | rt->c[0] = nullptr; | |
| 381 | |||
| 382 | 1015175 | ch->update(); | |
| 383 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::meld_path_end():
✓ Branch 11 → 20 taken 4643847 times.
✓ Branch 11 → 21 taken 15776911 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::meld_path_end():
✓ Branch 11 → 20 taken 499845 times.
✓ Branch 11 → 21 taken 3749605 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::meld_path_end():
✓ Branch 11 → 20 taken 950047 times.
✓ Branch 11 → 21 taken 4009309 times.
|
29629564 | } else if (rt->c[0]) { |
| 384 | 6093739 | rt->c[1] = rt->c[0]; | |
| 385 | 6093739 | rt->c[0] = nullptr; | |
| 386 | } | ||
| 387 | 30644739 | assert(rt->c[0] == nullptr); | |
| 388 | 30644739 | return rt->update_all(); | |
| 389 | } | ||
| 390 | |||
| 391 | 27205138 | void make_root() { | |
| 392 | 27205138 | expose(); | |
| 393 | |||
| 394 | 27205138 | top_tree_node* rt = derived_this(); | |
| 395 |
6/6wala::top_tree_node_base<(anonymous namespace)::mst_top_tree_node>::make_root():
✓ Branch 7 → 3 taken 13142578 times.
✓ Branch 7 → 8 taken 18829893 times.
wala::top_tree_node_base<(anonymous namespace)::vertex_add_subtree_sum_top_tree_node>::make_root():
✓ Branch 7 → 3 taken 1705883 times.
✓ Branch 7 → 8 taken 3867343 times.
wala::top_tree_node_base<(anonymous namespace)::subtree_add_subtree_sum_top_tree_node>::make_root():
✓ Branch 7 → 3 taken 3103331 times.
✓ Branch 7 → 8 taken 4507902 times.
|
45156930 | while (rt->p) { |
| 396 | 17951792 | assert(rt->d() == 1); | |
| 397 | rt = rt->p; | ||
| 398 | } | ||
| 399 | 27205138 | rt->do_flip_path(); | |
| 400 | 27205138 | rt->meld_path_end(); | |
| 401 | |||
| 402 | 27205138 | expose(); | |
| 403 | |||
| 404 | 27205138 | assert(!p); | |
| 405 | 27205138 | } | |
| 406 | |||
| 407 | // Link v2 as a child of v1 with edge e | ||
| 408 | 10983127 | friend void link(top_tree_node* e, top_tree_node* v1, top_tree_node* v2) { | |
| 409 | 10983127 | assert(e && v1 && v2); | |
| 410 | 10983127 | assert(!e->c[0] && !e->c[1] && !e->c[2]); | |
| 411 |
5/6wala::link((anonymous namespace)::mst_top_tree_node*, (anonymous namespace)::mst_top_tree_node*, (anonymous namespace)::mst_top_tree_node*):
✗ Branch 10 → 11 not taken.
✓ Branch 10 → 12 taken 5851283 times.
wala::link((anonymous namespace)::vertex_add_subtree_sum_top_tree_node*, (anonymous namespace)::vertex_add_subtree_sum_top_tree_node*, (anonymous namespace)::vertex_add_subtree_sum_top_tree_node*):
✓ Branch 10 → 11 taken 2208889 times.
✓ Branch 10 → 12 taken 2568625 times.
wala::link((anonymous namespace)::subtree_add_subtree_sum_top_tree_node*, (anonymous namespace)::subtree_add_subtree_sum_top_tree_node*, (anonymous namespace)::subtree_add_subtree_sum_top_tree_node*):
✓ Branch 10 → 11 taken 1158097 times.
✓ Branch 10 → 12 taken 2563219 times.
|
14350113 | v1->expose(); while (v1->p) v1 = v1->p; |
| 412 | 10983127 | v2->make_root(); | |
| 413 | |||
| 414 | 10983127 | assert(!v1->p); | |
| 415 | 10983127 | assert(!v2->p); | |
| 416 | |||
| 417 | 10983127 | e->is_path = true, e->is_vert = false; | |
| 418 | 10983127 | e->c[0] = v1; | |
| 419 | 10983127 | v1->p = e; | |
| 420 | 10983127 | e->c[1] = v2; | |
| 421 | 10983127 | v2->p = e; | |
| 422 | 10983127 | e->update(); | |
| 423 | 10983127 | } | |
| 424 | |||
| 425 | // Link v2's root as a child of v1 with edge e | ||
| 426 | // Returns false if they're already in the same subtree | ||
| 427 | ✗ | friend bool link_root(top_tree_node* e, top_tree_node* v1, top_tree_node* v2) { | |
| 428 | ✗ | assert(e && v1 && v2); | |
| 429 | ✗ | assert(!e->c[0] && !e->c[1] && !e->c[2]); | |
| 430 | ✗ | v1->expose(); | |
| 431 | ✗ | v2->expose(); | |
| 432 | |||
| 433 | ✗ | while (v1->p) v1 = v1->p; | |
| 434 | ✗ | while (v2->p) v2 = v2->p; | |
| 435 | ✗ | if (v1 == v2) return false; | |
| 436 | |||
| 437 | ✗ | assert(!v1->p); | |
| 438 | ✗ | assert(!v2->p); | |
| 439 | |||
| 440 | ✗ | e->is_path = true, e->is_vert = false; | |
| 441 | ✗ | e->c[0] = v1; | |
| 442 | ✗ | v1->p = e; | |
| 443 | ✗ | e->c[1] = v2; | |
| 444 | ✗ | v2->p = e; | |
| 445 | ✗ | e->update(); | |
| 446 | |||
| 447 | ✗ | return true; | |
| 448 | } | ||
| 449 | |||
| 450 | // Link v2 as a child of v1 with edge e, v2 must be the root | ||
| 451 | ✗ | friend void link_direct(top_tree_node* e, top_tree_node* v1, top_tree_node* v2) { | |
| 452 | ✗ | assert(e && v1 && v2); | |
| 453 | ✗ | assert(!e->c[0] && !e->c[1] && !e->c[2]); | |
| 454 | ✗ | v1->expose(); | |
| 455 | ✗ | v2->expose(); | |
| 456 | |||
| 457 | ✗ | while (v1->p) v1 = v1->p; | |
| 458 | ✗ | assert(!v2->p); | |
| 459 | |||
| 460 | ✗ | assert(v1 != v2); | |
| 461 | |||
| 462 | ✗ | assert(!v1->p); | |
| 463 | ✗ | assert(!v2->p); | |
| 464 | |||
| 465 | ✗ | e->is_path = true, e->is_vert = false; | |
| 466 | ✗ | e->c[0] = v1; | |
| 467 | ✗ | v1->p = e; | |
| 468 | ✗ | e->c[1] = v2; | |
| 469 | ✗ | v2->p = e; | |
| 470 | ✗ | e->update(); | |
| 471 | } | ||
| 472 | |||
| 473 | // Cuts the edge e | ||
| 474 | // Returns the top-tree-root of the two halves; they are not necessarily the split vertices. | ||
| 475 | 3439601 | friend std::pair<top_tree_node*, top_tree_node*> cut(top_tree_node* e) { | |
| 476 | 3439601 | assert(!e->is_vert); | |
| 477 | 3439601 | e->expose_edge(); | |
| 478 | |||
| 479 | 3439601 | assert(!e->p); | |
| 480 | 3439601 | assert(e->is_path); | |
| 481 | |||
| 482 | 3439601 | top_tree_node* l = e->c[0]; | |
| 483 | 3439601 | top_tree_node* r = e->c[1]; | |
| 484 | 3439601 | assert(l && r); | |
| 485 | |||
| 486 | 3439601 | e->c[0] = e->c[1] = nullptr; | |
| 487 | 3439601 | l->p = r->p = nullptr; | |
| 488 | |||
| 489 | 3439601 | assert(e->c[2] == nullptr); | |
| 490 | |||
| 491 | 3439601 | l = l->meld_path_end(); | |
| 492 | |||
| 493 | 3439601 | return {l, r}; | |
| 494 | } | ||
| 495 | |||
| 496 | 1297883 | friend top_tree_node* get_path(top_tree_node* a, top_tree_node* b) { | |
| 497 | 1297883 | assert(a->is_vert && b->is_vert); | |
| 498 | 1297883 | a->make_root(); | |
| 499 | 1297883 | b->expose(); | |
| 500 |
2/4wala::get_path((anonymous namespace)::vertex_add_subtree_sum_top_tree_node*, (anonymous namespace)::vertex_add_subtree_sum_top_tree_node*):
✗ Branch 7 → 8 not taken.
✓ Branch 7 → 10 taken 650106 times.
wala::get_path((anonymous namespace)::subtree_add_subtree_sum_top_tree_node*, (anonymous namespace)::subtree_add_subtree_sum_top_tree_node*):
✗ Branch 7 → 8 not taken.
✓ Branch 7 → 10 taken 647777 times.
|
1297883 | if (a == b) { |
| 501 | ✗ | assert(!b->p); | |
| 502 | return b; | ||
| 503 | } | ||
| 504 | 1297883 | assert(!b->p->p); | |
| 505 | return b->p; | ||
| 506 | } | ||
| 507 | |||
| 508 | 1945518 | friend top_tree_node* get_subtree(top_tree_node* rt, top_tree_node* n) { | |
| 509 | 1945518 | rt->make_root(); | |
| 510 | 1945518 | n->expose(); | |
| 511 | return n; | ||
| 512 | } | ||
| 513 | |||
| 514 | ✗ | friend top_tree_node* get_path_to_root(top_tree_node* b) { | |
| 515 | ✗ | assert(b->is_vert); | |
| 516 | ✗ | b->expose(); | |
| 517 | ✗ | if (!b->p) return b; | |
| 518 | ✗ | assert(!b->p->p); | |
| 519 | ✗ | return b->p; | |
| 520 | } | ||
| 521 | |||
| 522 | 648681 | friend top_tree_node* get_subtree_from_root(top_tree_node* n) { | |
| 523 | 648681 | n->expose(); | |
| 524 | return n; | ||
| 525 | } | ||
| 526 | |||
| 527 | // Assumes a and b are in the same connected component | ||
| 528 | ✗ | friend top_tree_node* lca_same_cc(top_tree_node *a, top_tree_node *b) { | |
| 529 | ✗ | a->expose(); | |
| 530 | ✗ | return b->expose(); | |
| 531 | } | ||
| 532 | |||
| 533 | // Returns nullptr if a and b are in different ccs | ||
| 534 | ✗ | friend top_tree_node* maybe_lca(top_tree_node *a, top_tree_node *b) { | |
| 535 | ✗ | a->expose(); | |
| 536 | ✗ | auto ap = a->p; | |
| 537 | ✗ | assert(!ap || !ap->p); | |
| 538 | ✗ | auto res = b->expose(); | |
| 539 | ✗ | assert(!b->p || !b->p->p); | |
| 540 | // If a didn't move in the tree when exposing b, then a and b are in different trees | ||
| 541 | ✗ | if (a != b && ap == a->p && (!ap || !ap->p)) return nullptr; | |
| 542 | ✗ | return res; | |
| 543 | } | ||
| 544 | }; | ||
| 545 | |||
| 546 | struct sample_top_tree_node : public top_tree_node_base<sample_top_tree_node> { | ||
| 547 | bool lazy_flip_path = false; | ||
| 548 | |||
| 549 | ✗ | void do_flip_path() { | |
| 550 | ✗ | assert(is_path); | |
| 551 | ✗ | std::swap(c[0], c[1]); | |
| 552 | ✗ | lazy_flip_path ^= 1; | |
| 553 | } | ||
| 554 | |||
| 555 | ✗ | void downdate() { | |
| 556 | ✗ | if (lazy_flip_path) { | |
| 557 | ✗ | assert(is_path); | |
| 558 | ✗ | if (!is_vert) { | |
| 559 | ✗ | c[0]->do_flip_path(); | |
| 560 | ✗ | c[1]->do_flip_path(); | |
| 561 | } | ||
| 562 | ✗ | lazy_flip_path = false; | |
| 563 | } | ||
| 564 | } | ||
| 565 | |||
| 566 | // NOTE: You may assume downdate() has been called on the current node, but | ||
| 567 | // it may not have been called on the children! In particular, be careful | ||
| 568 | // when accessing grandchildren information. | ||
| 569 | ✗ | void update() { | |
| 570 | ✗ | if (is_vert) { | |
| 571 | ✗ | } else if (is_path) { | |
| 572 | } else { | ||
| 573 | } | ||
| 574 | } | ||
| 575 | }; | ||
| 576 | |||
| 577 | } // namespace wala | ||
| 578 |