GCC Code Coverage Report

Directory: src/
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 0.0% 0 / 0 / 320
Functions: 0.0% 0 / 0 / 3
Branches: 0.0% 0 / 4 / 10
top_tree.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include <utility>
4 #include <cassert>
5 #include <array>
6
7 /**
8 * Top tree!
9 *
10 * Usage:
11 * Make a `struct T : public top_tree_node_base<T>` (CRTP), which implements
12 * void update()
13 * void downdate()
14 * void do_flip_path()
15 * void do_other_operation() ...
16 * When update() is called, you can assume downdate() has already been called.
17 *
18 * In general, do_op() should eagerly apply the operation but not touch the
19 * children. In downdate(), you can push down to the children with ch->do_op().
20 * WARNING: if different operations do not trivially commute, you *must*
21 * implement a way to swap/alter them to compose in a consistent order, and you
22 * must use that order when implementing downdate(). This can be nontrivial!
23 *
24 * Creating vertices:
25 * n->is_path = n->is_vert = true;
26 * n->update();
27 *
28 * Creating edges: no setup/update() needed, just call
29 * link(e, va, vb);
30 *
31 * Updates:
32 * auto cur = get_path(va, vb); // or get_subtree(va, vb)
33 * cur->do_stuff();
34 * cur->downdate();
35 * cur->update_all();
36 *
37 * Node types:
38 * path edges: compress(c[0], self, c[1])
39 * assert(is_path && !is_vert);
40 * assert(c[0] && c[1]);
41 * assert(c[0]->is_path && c[1]->is_path);
42 * assert(!c[2]);
43 * (path) vertices: self + rake(c[0], c[1])
44 * assert(is_path && is_vert);
45 * assert(!c[2]);
46 * if (c[0]) assert(!c[0]->is_path);
47 * if (c[1]) assert(!c[1]->is_path);
48 * non-path edges: rake(c[0], self + c[2], c[1])
49 * assert(!is_path && !is_vert);
50 * assert(c[2])
51 * assert(c[2]->is_path);
52 * if (c[0]) assert(!c[0]->is_path);
53 * if (c[1]) assert(!c[1]->is_path);
54 */
55
56 template <typename top_tree_node> struct top_tree_node_base {
57 private:
58 ✗ top_tree_node* derived_this() {
59 ✗ return static_cast<top_tree_node*>(this);
60 }
61 ✗ const top_tree_node* derived_this() const {
62 ✗ return static_cast<const top_tree_node*>(this);
63 }
64 public:
65 mutable top_tree_node* p = nullptr;
66 std::array<top_tree_node*, 3> c{nullptr, nullptr, nullptr};
67
68 ✗ int d() const {
69 ✗ assert(p);
70 ✗ if (this == p->c[0]) {
71 ✗ return 0;
72 ✗ } else if (this == p->c[1]) {
73 ✗ return 1;
74 ✗ } else if (this == p->c[2]) {
75 ✗ return 2;
76 } else assert(false);
77 }
78 ✗ top_tree_node*& p_c() const { return p->c[d()]; } // p->c which points to you
79
80 // 3 types of verts: path edges, path verts, non-path edges
81 bool is_path;
82 bool is_vert;
83
84 ✗ bool r() const { return !p || p->is_path != is_path; }
85
86 private:
87 // Convenience wrappers for the derived functions.
88 ✗ void do_flip_path() {
89 ✗ derived_this()->do_flip_path();
90 }
91 ✗ void downdate() {
92 ✗ derived_this()->downdate();
93 }
94 ✗ void update() {
95 ✗ derived_this()->update();
96 }
97
98 public:
99 ✗ void downdate_all() {
100 ✗ if (p) p->downdate_all();
101 ✗ downdate();
102 }
103
104 // Returns the root
105 ✗ top_tree_node* update_all() {
106 ✗ top_tree_node* cur = derived_this();
107 ✗ cur->update();
108 ✗ while (cur->p) {
109 ✗ cur = cur->p;
110 ✗ cur->update();
111 }
112 ✗ return cur;
113 }
114
115 private:
116
117 ✗ void rot() {
118 ✗ assert(!is_vert);
119 ✗ assert(!r());
120 ✗ top_tree_node* pa = p;
121 ✗ int x = d(); assert(x == 0 || x == 1);
122 ✗ top_tree_node* ch = c[!x];
123
124 ✗ if (pa->p) pa->p_c() = derived_this();
125 ✗ this->p = pa->p;
126
127 ✗ pa->c[x] = ch;
128 ✗ if (ch) ch->p = pa;
129
130 ✗ this->c[!x] = pa;
131 ✗ pa->p = derived_this();
132
133 ✗ pa->update();
134 }
135
136 ✗ void rot_2(int c_d) {
137 ✗ assert(!is_vert);
138 ✗ assert(!r());
139 ✗ assert(c[c_d]);
140 ✗ assert(!c[c_d]->is_vert);
141
142 ✗ if (d() == c_d) {
143 ✗ rot();
144 ✗ return;
145 }
146
147 ✗ top_tree_node* pa = p;
148 ✗ int x = d(); assert(x == 0 || x == 1);
149 ✗ assert(c_d == !x);
150 ✗ top_tree_node* ch = c[c_d]->c[!x];
151
152 ✗ if (pa->p) pa->p_c() = derived_this();
153 ✗ this->p = pa->p;
154
155 ✗ pa->c[x] = ch;
156 ✗ if (ch) ch->p = pa;
157
158 ✗ this->c[c_d]->c[!x] = pa;
159 ✗ pa->p = this->c[c_d];
160
161 ✗ pa->update();
162 }
163
164 ✗ void splay_dir(int x) {
165 ✗ while (!r() && d() == x) {
166 ✗ if (!p->r() && p->d() == x) {
167 ✗ p->rot();
168 }
169 ✗ rot();
170 }
171 }
172
173 ✗ void splay_2(int c_d) {
174 ✗ assert(!is_vert && is_path);
175 ✗ assert(c[c_d] && !c[c_d]->is_vert);
176 ✗ while (!r()) {
177 ✗ if (!p->r()) {
178 ✗ if (p->d() == d()) {
179 ✗ p->rot();
180 } else {
181 ✗ rot_2(c_d);
182 }
183 }
184 ✗ rot_2(c_d);
185 }
186 }
187
188 ✗ void splay_2() {
189 ✗ assert(!is_vert && is_path);
190 ✗ assert(!r());
191 ✗ p->splay_2(d());
192 }
193
194 ✗ void splay_vert() {
195 ✗ assert(is_vert);
196 ✗ if (r()) {
197 ✗ return;
198 }
199 ✗ p->splay_dir(d());
200 ✗ if (p->r()) {
201 ✗ return;
202 }
203
204 ✗ assert(p->d() != d());
205 // we have a preference to be the left child
206 ✗ if (d() == 1) {
207 ✗ p->rot();
208 }
209 ✗ assert(d() == 0);
210
211 ✗ p->splay_2();
212 ✗ assert(d() == 0);
213 ✗ assert(p->d() == 1);
214 ✗ assert(p->p->r());
215 }
216
217 ✗ void splay() {
218 ✗ assert(!is_vert);
219 ✗ while (!r()) {
220 ✗ if (!p->r()) {
221 ✗ if (p->d() == d()) {
222 ✗ p->rot();
223 } else {
224 ✗ rot();
225 }
226 }
227 ✗ rot();
228 }
229 }
230
231 ✗ top_tree_node* cut_right() {
232 ✗ assert(is_vert && is_path);
233 ✗ splay_vert();
234
235 ✗ if (r() || d() == 1) {
236 ✗ assert(r() || (d() == 1 && p->r()));
237 ✗ assert(c[0] == nullptr);
238 ✗ return nullptr;
239 }
240
241 ✗ top_tree_node* pa = p;
242 ✗ assert(pa->r() || (pa->d() == 1 && pa->p->r()));
243 ✗ assert(!pa->is_vert);
244 ✗ assert(pa->is_path);
245 ✗ assert(pa->c[0] == this);
246 ✗ assert(pa->c[2] == nullptr);
247
248 ✗ if (pa->p) pa->p_c() = derived_this();
249 ✗ this->p = pa->p;
250
251 ✗ pa->is_path = false;
252 ✗ pa->c[2] = pa->c[1]; // don't need to change the parent
253
254 ✗ pa->c[0] = c[0]; if (c[0]) c[0]->p = pa;
255 ✗ pa->c[1] = c[1]; if (c[1]) c[1]->p = pa;
256
257 ✗ c[0] = nullptr;
258 ✗ c[1] = pa; pa->p = derived_this();
259 ✗ assert(c[2] == nullptr);
260
261 ✗ assert(c[0] == nullptr);
262
263 ✗ pa->update();
264 ✗ return pa;
265 }
266
267 ✗ top_tree_node* splice_non_path() {
268 ✗ assert(!is_path);
269 ✗ assert(!is_vert);
270
271 ✗ splay();
272 ✗ assert(p && p->is_vert && p->is_path);
273 ✗ p->cut_right();
274
275 ✗ if (!p->is_path) rot();
276 ✗ assert(p && p->is_vert && p->is_path);
277 ✗ assert(p->r() || (p->d() == 1 && p->p->r()));
278 ✗ assert(p->c[d()] == this && p->c[!d()] == nullptr);
279
280 ✗ top_tree_node* pa = p;
281
282 ✗ if (pa->p) pa->p_c() = derived_this();
283 ✗ this->p = pa->p;
284
285 ✗ pa->c[0] = c[0]; if (c[0]) c[0]->p = pa;
286 ✗ pa->c[1] = c[1]; if (c[1]) c[1]->p = pa;
287
288 ✗ assert(c[2] && c[2]->is_path);
289 ✗ c[1] = c[2]; // don't need to change parent
290 ✗ c[0] = pa; pa->p = derived_this();
291 ✗ c[2] = nullptr;
292
293 ✗ is_path = true;
294
295 ✗ pa->update();
296 ✗ return pa;
297 }
298
299 // Return the topmost vertex which was spliced into, self if none
300 ✗ top_tree_node* splice_all() {
301 ✗ top_tree_node* res = derived_this();
302 ✗ for (top_tree_node* cur = derived_this(); cur; cur = cur->p) {
303 ✗ if (!cur->is_path) {
304 ✗ res = cur->splice_non_path();
305 }
306 ✗ assert(cur->is_path);
307 }
308 ✗ return res;
309 }
310
311 public:
312 // Return the topmost vertex which was spliced into, self if none
313 ✗ top_tree_node* expose() {
314 ✗ assert(is_vert);
315 ✗ downdate_all();
316
317 ✗ top_tree_node* res = splice_all();
318
319 ✗ cut_right();
320
321 ✗ update_all();
322
323 ✗ return res;
324 }
325
326 // Return the topmost vertex which was spliced into, self (an edge) if none.
327 ✗ top_tree_node* expose_edge() {
328 ✗ assert(!is_vert);
329 ✗ downdate_all();
330
331 ✗ top_tree_node* v = is_path ? c[1] : c[2];
332 ✗ v->downdate();
333
334 ✗ while (!v->is_vert) {
335 ✗ v = v->c[0];
336 ✗ v->downdate();
337 }
338
339 ✗ top_tree_node* res = v->splice_all();
340 ✗ v->cut_right();
341 ✗ v->update_all();
342
343 ✗ assert(!p);
344 ✗ assert(v == c[1]);
345
346 ✗ return res == v ? derived_this() : res;
347 }
348
349 // Return the new root
350 ✗ top_tree_node* meld_path_end() {
351 ✗ assert(!p);
352 ✗ top_tree_node* rt = derived_this();
353 ✗ while (true) {
354 ✗ rt->downdate();
355 ✗ if (rt->is_vert) break;
356 ✗ rt = rt->c[1];
357 }
358 ✗ assert(rt->is_vert);
359 ✗ rt->splay_vert();
360 ✗ if (rt->c[0] && rt->c[1]) {
361 ✗ top_tree_node* ch = rt->c[1];
362 ✗ while (true) {
363 ✗ ch->downdate();
364 ✗ if (!ch->c[0]) break;
365 ✗ ch = ch->c[0];
366 }
367 ✗ ch->splay();
368 ✗ assert(ch->c[0] == nullptr);
369
370 ✗ ch->c[0] = rt->c[0];
371 ✗ ch->c[0]->p = ch;
372
373 ✗ rt->c[0] = nullptr;
374
375 ✗ ch->update();
376 ✗ } else if (rt->c[0]) {
377 ✗ rt->c[1] = rt->c[0];
378 ✗ rt->c[0] = nullptr;
379 }
380 ✗ assert(rt->c[0] == nullptr);
381 ✗ return rt->update_all();
382 }
383
384 ✗ void make_root() {
385 ✗ expose();
386
387 ✗ top_tree_node* rt = derived_this();
388 ✗ while (rt->p) {
389 ✗ assert(rt->d() == 1);
390 ✗ rt = rt->p;
391 }
392 ✗ rt->do_flip_path();
393 ✗ rt->meld_path_end();
394
395 ✗ expose();
396
397 ✗ assert(!p);
398 }
399
400 // Link v2 as a child of v1 with edge e
401 ✗ friend void link(top_tree_node* e, top_tree_node* v1, top_tree_node* v2) {
402 ✗ assert(e && v1 && v2);
403 ✗ assert(!e->c[0] && !e->c[1] && !e->c[2]);
404 ✗ v1->expose(); while (v1->p) v1 = v1->p;
405 ✗ v2->make_root();
406
407 ✗ assert(!v1->p);
408 ✗ assert(!v2->p);
409
410 ✗ e->is_path = true, e->is_vert = false;
411 ✗ e->c[0] = v1;
412 ✗ v1->p = e;
413 ✗ e->c[1] = v2;
414 ✗ v2->p = e;
415 ✗ e->update();
416 }
417
418 // Link v2's root as a child of v1 with edge e
419 // Returns false if they're already in the same subtree
420 ✗ friend bool link_root(top_tree_node* e, top_tree_node* v1, top_tree_node* v2) {
421 ✗ assert(e && v1 && v2);
422 ✗ assert(!e->c[0] && !e->c[1] && !e->c[2]);
423 ✗ v1->expose();
424 ✗ v2->expose();
425
426 ✗ while (v1->p) v1 = v1->p;
427 ✗ while (v2->p) v2 = v2->p;
428 ✗ if (v1 == v2) return false;
429
430 ✗ assert(!v1->p);
431 ✗ assert(!v2->p);
432
433 ✗ e->is_path = true, e->is_vert = false;
434 ✗ e->c[0] = v1;
435 ✗ v1->p = e;
436 ✗ e->c[1] = v2;
437 ✗ v2->p = e;
438 ✗ e->update();
439
440 ✗ return true;
441 }
442
443 // Link v2 as a child of v1 with edge e, v2 must be the root
444 ✗ friend void link_direct(top_tree_node* e, top_tree_node* v1, top_tree_node* v2) {
445 ✗ assert(e && v1 && v2);
446 ✗ assert(!e->c[0] && !e->c[1] && !e->c[2]);
447 ✗ v1->expose();
448 ✗ v2->expose();
449
450 ✗ while (v1->p) v1 = v1->p;
451 ✗ assert(!v2->p);
452
453 ✗ assert(v1 != v2);
454
455 ✗ assert(!v1->p);
456 ✗ assert(!v2->p);
457
458 ✗ e->is_path = true, e->is_vert = false;
459 ✗ e->c[0] = v1;
460 ✗ v1->p = e;
461 ✗ e->c[1] = v2;
462 ✗ v2->p = e;
463 ✗ e->update();
464 }
465
466 // Cuts the edge e
467 // Returns the top-tree-root of the two halves; they are not necessarily the split vertices.
468 ✗ friend std::pair<top_tree_node*, top_tree_node*> cut(top_tree_node* e) {
469 ✗ assert(!e->is_vert);
470 ✗ e->expose_edge();
471
472 ✗ assert(!e->p);
473 ✗ assert(e->is_path);
474
475 ✗ top_tree_node* l = e->c[0];
476 ✗ top_tree_node* r = e->c[1];
477 ✗ assert(l && r);
478
479 ✗ e->c[0] = e->c[1] = nullptr;
480 ✗ l->p = r->p = nullptr;
481
482 ✗ assert(e->c[2] == nullptr);
483
484 ✗ l = l->meld_path_end();
485
486 ✗ return {l, r};
487 }
488
489 ✗ friend top_tree_node* get_path(top_tree_node* a, top_tree_node* b) {
490 ✗ assert(a->is_vert && b->is_vert);
491 ✗ a->make_root();
492 ✗ b->expose();
493 ✗ if (a == b) {
494 ✗ assert(!b->p);
495 ✗ return b;
496 }
497 ✗ assert(!b->p->p);
498 ✗ return b->p;
499 }
500
501 ✗ friend top_tree_node* get_subtree(top_tree_node* rt, top_tree_node* n) {
502 ✗ rt->make_root();
503 ✗ n->expose();
504 ✗ return n;
505 }
506
507 ✗ friend top_tree_node* get_path_to_root(top_tree_node* b) {
508 ✗ assert(b->is_vert);
509 ✗ b->expose();
510 ✗ if (!b->p) return b;
511 ✗ assert(!b->p->p);
512 ✗ return b->p;
513 }
514
515 ✗ friend top_tree_node* get_subtree_from_root(top_tree_node* n) {
516 ✗ n->expose();
517 ✗ return n;
518 }
519
520 // Assumes a and b are in the same connected component
521 ✗ friend top_tree_node* lca_same_cc(top_tree_node *a, top_tree_node *b) {
522 ✗ a->expose();
523 ✗ return b->expose();
524 }
525
526 // Returns nullptr if a and b are in different ccs
527 ✗ friend top_tree_node* maybe_lca(top_tree_node *a, top_tree_node *b) {
528 ✗ a->expose();
529 ✗ auto ap = a->p;
530 ✗ assert(!ap || !ap->p);
531 ✗ auto res = b->expose();
532 ✗ assert(!b->p || !b->p->p);
533 // If a didn't move in the tree when exposing b, then a and b are in different trees
534 ✗ if (a != b && ap == a->p && (!ap || !ap->p)) return nullptr;
535 ✗ return res;
536 }
537 };
538
539 struct sample_top_tree_node : public top_tree_node_base<sample_top_tree_node> {
540 bool lazy_flip_path = false;
541
542 ✗ void do_flip_path() {
543 ✗ assert(is_path);
544 ✗ std::swap(c[0], c[1]);
545 ✗ lazy_flip_path ^= 1;
546 }
547
548 ✗ void downdate() {
549 ✗ if (lazy_flip_path) {
550 ✗ assert(is_path);
551 ✗ if (!is_vert) {
552 ✗ c[0]->do_flip_path();
553 ✗ c[1]->do_flip_path();
554 }
555 ✗ lazy_flip_path = false;
556 }
557 }
558
559 // NOTE: You may assume downdate() has been called on the current node, but
560 // it may not have been called on the children! In particular, be careful
561 // when accessing grandchildren information.
562 ✗ void update() {
563 ✗ if (is_vert) {
564 ✗ } else if (is_path) {
565 } else {
566 }
567 }
568 };
569