tree/lct.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include <cassert> | ||
| 4 | #include <utility> | ||
| 5 | |||
| 6 | namespace wala::lct { | ||
| 7 | |||
| 8 | struct node { | ||
| 9 | node* p; | ||
| 10 | node* c[2]; | ||
| 11 | |||
| 12 | int s; | ||
| 13 | |||
| 14 | bool flip; | ||
| 15 | |||
| 16 | // isroot | ||
| 17 | ✗ | inline bool r() { return p == nullptr || !(this == p->c[0] || this == p->c[1]); } | |
| 18 | // direction | ||
| 19 | ✗ | inline bool d() { assert(!r()); return this == p->c[1]; } | |
| 20 | |||
| 21 | ✗ | inline void update() { s = 1 + (c[0] ? c[0]->s : 0) + (c[1] ? c[1]->s : 0); } | |
| 22 | ✗ | void propogate() { | |
| 23 | ✗ | if (flip) { | |
| 24 | ✗ | std::swap(c[0], c[1]); | |
| 25 | ✗ | if (c[0]) c[0]->flip = !c[0]->flip; | |
| 26 | ✗ | if (c[1]) c[1]->flip = !c[1]->flip; | |
| 27 | ✗ | flip = false; | |
| 28 | } | ||
| 29 | } | ||
| 30 | |||
| 31 | // precondition: parent and current are propogated | ||
| 32 | ✗ | void rot() { | |
| 33 | ✗ | assert(!r()); | |
| 34 | |||
| 35 | ✗ | int x = d(); | |
| 36 | ✗ | node* pa = p; | |
| 37 | ✗ | node* ch = c[!x]; | |
| 38 | |||
| 39 | ✗ | assert(!pa->flip); | |
| 40 | ✗ | assert(!flip); | |
| 41 | |||
| 42 | ✗ | assert((!ch) || ch->p == this); | |
| 43 | |||
| 44 | ✗ | if (!pa->r()) pa->p->c[pa->d()] = this; | |
| 45 | ✗ | this->p = pa->p; | |
| 46 | |||
| 47 | ✗ | pa->c[x] = ch; | |
| 48 | ✗ | if (ch) ch->p = pa; | |
| 49 | |||
| 50 | ✗ | this->c[!x] = pa; | |
| 51 | ✗ | pa->p = this; | |
| 52 | |||
| 53 | ✗ | pa->update(); | |
| 54 | ✗ | update(); | |
| 55 | } | ||
| 56 | |||
| 57 | // postcondition: always propogated | ||
| 58 | ✗ | void splay() { | |
| 59 | ✗ | if (r()) { | |
| 60 | ✗ | update(); | |
| 61 | ✗ | propogate(); | |
| 62 | ✗ | return; | |
| 63 | } | ||
| 64 | |||
| 65 | ✗ | while (!r()) { | |
| 66 | ✗ | if (!p->r()) { | |
| 67 | ✗ | node* gp = p->p; | |
| 68 | ✗ | node* pa = p; | |
| 69 | ✗ | gp->propogate(); | |
| 70 | ✗ | pa->propogate(); | |
| 71 | ✗ | propogate(); | |
| 72 | ✗ | if (d() == p->d()) { | |
| 73 | ✗ | pa->rot(); | |
| 74 | ✗ | assert(p == pa); | |
| 75 | } else { | ||
| 76 | ✗ | rot(); | |
| 77 | ✗ | assert(p == gp); | |
| 78 | } | ||
| 79 | ✗ | rot(); | |
| 80 | } else { | ||
| 81 | ✗ | p->propogate(); | |
| 82 | ✗ | propogate(); | |
| 83 | ✗ | rot(); | |
| 84 | ✗ | assert(r()); | |
| 85 | } | ||
| 86 | } | ||
| 87 | ✗ | update(); | |
| 88 | } | ||
| 89 | |||
| 90 | // attach on right side | ||
| 91 | // precondition: propogated | ||
| 92 | ✗ | void make_child(node* n) { | |
| 93 | ✗ | assert(!flip); | |
| 94 | ✗ | assert(r()); | |
| 95 | |||
| 96 | ✗ | if (c[1]) { | |
| 97 | ✗ | node* v = c[1]; | |
| 98 | ✗ | c[1] = nullptr; | |
| 99 | ✗ | assert(v->r()); | |
| 100 | |||
| 101 | ✗ | update(); | |
| 102 | } | ||
| 103 | |||
| 104 | ✗ | assert(!flip); | |
| 105 | ✗ | assert(!c[1]); | |
| 106 | |||
| 107 | ✗ | if (n) { | |
| 108 | ✗ | assert(n->r()); | |
| 109 | ✗ | assert(n->p == this); | |
| 110 | |||
| 111 | ✗ | c[1] = n; | |
| 112 | ✗ | assert(c[1]->p == this); | |
| 113 | |||
| 114 | ✗ | update(); | |
| 115 | } | ||
| 116 | } | ||
| 117 | |||
| 118 | // postcondition: propogated | ||
| 119 | ✗ | void expose() { | |
| 120 | ✗ | splay(); | |
| 121 | ✗ | assert(!flip); | |
| 122 | ✗ | make_child(nullptr); | |
| 123 | ✗ | while (p) { | |
| 124 | ✗ | assert(r()); | |
| 125 | ✗ | p->splay(); | |
| 126 | ✗ | p->make_child(this); | |
| 127 | ✗ | assert(!p->flip); | |
| 128 | ✗ | assert(!flip); | |
| 129 | ✗ | rot(); | |
| 130 | ✗ | update(); | |
| 131 | ✗ | assert(r()); | |
| 132 | } | ||
| 133 | ✗ | assert(!p); | |
| 134 | ✗ | assert(!c[1]); | |
| 135 | } | ||
| 136 | |||
| 137 | // does not propogate | ||
| 138 | ✗ | void make_root() { | |
| 139 | ✗ | expose(); | |
| 140 | ✗ | assert(p == nullptr); | |
| 141 | ✗ | assert(r()); | |
| 142 | ✗ | flip = !flip; | |
| 143 | } | ||
| 144 | }; | ||
| 145 | |||
| 146 | } // namespace wala::lct | ||
| 147 |