MimIR 0.1
MimIR is my Intermediate Representation
Loading...
Searching...
No Matches
sets.h
Go to the documentation of this file.
1#pragma once
2
3#include <fstream>
4
6#include "mim/util/util.h"
7#include "mim/util/vector.h"
8
9#include "fe/arena.h"
10
11namespace mim {
12
13template<class D, size_t N = 16> class Sets {
14private:
15 /// Trie Node.
16 class Node : public lct::Node<Node, D*> {
17 private:
18 using LCT = lct::Node<Node, D*>;
19
20 public:
21 constexpr Node(u32 id) noexcept
22 : parent(nullptr)
23 , def(nullptr)
24 , size(0)
25 , min(size_t(-1))
26 , id(id) {}
27
28 constexpr Node(Node* parent, D* def, u32 id) noexcept
29 : parent(parent)
30 , def(def)
31 , size(parent->size + 1)
32 , min(parent->def ? parent->min : def->tid())
33 , id(id) {
34 parent->link(this);
35 }
36
37 constexpr bool lt(D* d) const noexcept { return this->is_root() || this->def->tid() < d->tid(); }
38 constexpr bool eq(D* d) const noexcept { return this->def == d; }
39
40 void dot(std::ostream& os) {
41 using namespace std::string_literals;
42
43 auto node2str = [](const Node* n) {
44 return "n_"s + (n->def ? std::to_string(n->def->tid()) : "root"s) + "_"s + std::to_string(n->id);
45 };
46
47 println(os, "{} [tooltip=\"gid: {}, min: {}\"];", node2str(this), def ? def->gid() : 0, min);
48
49 for (const auto& [def, child] : children) println(os, "{} -> {}", node2str(this), node2str(child.get()));
50 for (const auto& [_, child] : children) child->dot(os);
51
52#if 0
53 // clang-format off
54 if (auto par = LCT::path_parent()) println(os, "{} -> {} [constraint=false,color=\"#0000ff\",style=dashed];", node2str(this), node2str(par));
55 if (auto top = aux.top ) println(os, "{} -> {} [constraint=false,color=\"#ff0000\"];", node2str(this), node2str(top));
56 if (auto bot = aux.bot ) println(os, "{} -> {} [constraint=false,color=\"#00ff00\"];", node2str(this), node2str(bot));
57 // clang-format on
58#endif
59 }
60
61 ///@name Getters
62 ///@{
63 constexpr bool is_root() const noexcept { return def == 0; }
64
65 [[nodiscard]] bool contains(D* d) noexcept {
66 auto tid = d->tid();
67 // clang-format off
68 if (tid == this->min || tid == this->def->tid()) return true;
69 if (tid < this->min || tid > this->def->tid()) return false;
70 // clang-format on
71
72 return LCT::contains(d);
73 }
74
75 using LCT::find;
76 ///@}
77
78 Node* const parent;
79 D* const def;
80 const size_t size;
81 const size_t min;
82 u32 const id;
84 };
85
86 struct Data {
87 constexpr Data() noexcept = default;
88 constexpr Data(size_t size) noexcept
89 : size(size) {}
90
91 size_t size = 0;
92 D* elems[];
93
94 struct Equal {
95 constexpr bool operator()(const Data* d1, const Data* d2) const noexcept {
96 bool res = d1->size == d2->size;
97 for (size_t i = 0, e = d1->size; res && i != e; ++i) res &= d1->elems[i] == d2->elems[i];
98 return res;
99 }
100 };
101
102 /// @name Iterators
103 ///@{
104 constexpr D** begin() noexcept { return elems; }
105 constexpr D** end() noexcept { return elems + size; }
106 constexpr D* const* begin() const noexcept { return elems; }
107 constexpr D* const* end() const noexcept { return elems + size; }
108 ///@}
109
110 template<class H> friend constexpr H AbslHashValue(H h, const Data* d) noexcept {
111 if (!d) return H::combine(std::move(h), 0);
112 return H::combine_contiguous(std::move(h), d->elems, d->size);
113 }
114 };
115
116public:
117 class Set {
118 private:
119 enum class Tag : uintptr_t { Null, Uniq, Data, Node };
120
121 constexpr Set(const Data* data) noexcept
122 : ptr_(uintptr_t(data) | uintptr_t(Tag::Data)) {} ///< Data Set.
123 constexpr Set(Node* node) noexcept
124 : ptr_(uintptr_t(node) | uintptr_t(Tag::Node)) {} ///< Node set.
125
126 public:
127 class iterator {
128 private:
129 constexpr iterator(D* d) noexcept
130 : tag_(Tag::Uniq)
131 , ptr_(std::bit_cast<uintptr_t>(d)) {}
132 constexpr iterator(D* const* elems) noexcept
133 : tag_(Tag::Data)
134 , ptr_(std::bit_cast<uintptr_t>(elems)) {}
135 constexpr iterator(Node* node) noexcept
136 : tag_(Tag::Node)
137 , ptr_(std::bit_cast<uintptr_t>(node)) {}
138
139 public:
140 /// @name Iterator Properties
141 ///@{
142 using iterator_category = std::forward_iterator_tag;
143 using difference_type = std::ptrdiff_t;
144 using value_type = D*;
145 using pointer = D* const*;
146 using reference = D* const&;
147 ///@}
148
149 /// @name Construction
150 ///@{
151 constexpr iterator() noexcept = default;
152 ///@}
153
154 /// @name Increment
155 /// @note These operations only change the *view* of this Set; the Set itself is **not** modified.
156 ///@{
157 constexpr iterator& operator++() noexcept {
158 // clang-format off
159 switch (tag_) {
160 case Tag::Uniq: return clear();
161 case Tag::Data: return ptr_ = std::bit_cast<uintptr_t>(std::bit_cast<D* const*>(ptr_) + 1), *this;
162 case Tag::Node: {
163 auto node = std::bit_cast<Node*>(ptr_);
164 node = node->parent;
165 if (node->is_root())
166 clear();
167 else
168 ptr_ = std::bit_cast<uintptr_t>(node);
169 return *this;
170 }
171 default: fe::unreachable();
172 }
173 // clang-format on
174 }
175
176 constexpr iterator operator++(int) noexcept {
177 auto res = *this;
178 this->operator++();
179 return res;
180 }
181 ///@}
182
183 /// @name Comparisons
184 ///@{
185 // clang-format off
186 constexpr bool operator==(iterator other) const noexcept { return this->tag_ == other.tag_ && this->ptr_ == other.ptr_; }
187 constexpr bool operator!=(iterator other) const noexcept { return this->tag_ != other.tag_ || this->ptr_ != other.ptr_; }
188 // clang-format on
189 ///@}
190
191 /// @name Dereference
192 ///@{
193 constexpr reference operator*() const noexcept {
194 switch (tag_) {
195 case Tag::Uniq: return *std::bit_cast<D* const*>(&ptr_);
196 case Tag::Data: return *std::bit_cast<D* const*>(ptr_);
197 case Tag::Node: return std::bit_cast<Node*>(ptr_)->def;
198 default: fe::unreachable();
199 }
200 }
201
202 constexpr pointer operator->() const noexcept { return this->operator*(); }
203 ///@}
204
205 iterator& clear() { return tag_ = Tag::Null, ptr_ = 0, *this; }
206
207 private:
208 Tag tag_;
209 uintptr_t ptr_;
210
211 friend class Set;
212 };
213
214 /// @name Construction
215 ///@{
216 constexpr Set(const Set&) noexcept = default;
217 constexpr Set(Set&&) noexcept = default;
218 constexpr Set() noexcept = default; ///< Null set
219 constexpr Set(D* d) noexcept
220 : ptr_(uintptr_t(d) | uintptr_t(Tag::Uniq)) {} ///< Uniq set.
221
222 constexpr Set& operator=(const Set&) noexcept = default;
223 ///@}
224
225 /// @name Getters
226 ///@{
227 constexpr size_t size() const noexcept {
228 if (isa_uniq()) return 1;
229 if (auto d = isa_data()) return d->size;
230 if (auto n = isa_node()) return n->size;
231 return 0; // empty
232 }
233
234 /// Is empty?
235 constexpr bool empty() const noexcept {
236 assert(tag() != Tag::Node || !ptr<Node>()->is_root());
237 return ptr_ == 0;
238 }
239
240 constexpr explicit operator bool() const noexcept { return ptr_ != 0; } ///< Not empty?
241 ///@}
242
243 /// @name Check Membership
244 ///@{
245
246 /// Is @f$d \in this@f$?.
247 bool contains(D* d) const noexcept {
248 if (auto u = isa_uniq()) return d == u;
249
250 if (auto data = isa_data()) {
251 for (auto e : *data)
252 if (d == e) return true;
253 return false;
254 }
255
256 if (auto n = isa_node()) return n->contains(d);
257
258 return false;
259 }
260
261 /// Is @f$this \cap other \neq \emptyset@f$?.
262 [[nodiscard]] bool has_intersection(Set other) const noexcept {
263 if (*this == other) return true;
264 if (this->empty() || other.empty()) return false;
265
266 auto u1 = this->isa_uniq();
267 auto u2 = other.isa_uniq();
268 if (u1) return other.contains(u1);
269 if (u2) return this->contains(u2);
270
271 auto d1 = this->isa_data();
272 auto d2 = other.isa_data();
273 if (d1 && d2) {
274 for (auto ai = d1->begin(), ae = d1->end(), bi = d2->begin(), be = d2->end(); ai != ae && bi != be;) {
275 if (*ai == *bi) return true;
276
277 if ((*ai)->gid() < (*bi)->gid())
278 ++ai;
279 else
280 ++bi;
281 }
282
283 return false;
284 }
285
286 auto n1 = this->isa_node();
287 auto n2 = other.isa_node();
288 if (n1 && n2) {
289 if (n1->min > n2->def->tid() || n1->def->tid() < n2->min) return false;
290 if (n1->def == n2->def) return true;
291 if (!n1->lca(n2)->is_root()) return true;
292
293 while (!n1->is_root() && !n2->is_root()) {
294 if (n1->def->tid() > n2->def->tid()) {
295 if (n1 = n1->find(n2->def); n2->def == n1->def) return true;
296 n1 = n1->parent;
297 } else {
298 if (n2 = n2->find(n1->def); n1->def == n2->def) return true;
299 n2 = n2->parent;
300 }
301 }
302
303 return false;
304 }
305
306 auto n = n1 ? n1 : n2;
307 for (auto e : *(d1 ? d1 : d2))
308 if (n->contains(e)) return true;
309
310 return false;
311 }
312 ///@}
313
314 /// @name Iterators
315 ///@{
316 constexpr iterator begin() const noexcept {
317 if (auto u = isa_uniq()) return {u};
318 if (auto d = isa_data()) return {d->begin()};
319 if (auto n = isa_node(); n && !n->is_root()) return {n};
320 return {};
321 }
322
323 constexpr iterator end() const noexcept {
324 if (auto data = isa_data()) return iterator(data->end());
325 return {};
326 }
327 ///@}
328
329 /// @name Comparisons
330 ///@{
331 constexpr bool operator==(Set other) const noexcept { return this->ptr_ == other.ptr_; }
332 constexpr bool operator!=(Set other) const noexcept { return this->ptr_ != other.ptr_; }
333 ///@}
334
335 /// @name Output
336 ///@{
337 std::ostream& stream(std::ostream& os) const {
338 os << '{';
339 auto sep = "";
340 for (auto d : *this) {
341 os << sep << d->gid() << '/' << d->tid();
342 sep = ", ";
343 }
344 return os << '}';
345 }
346
347 void dump() const { stream(std::cout) << std::endl; }
348 ///@}
349
350 private:
351 constexpr Tag tag() const noexcept { return Tag(ptr_ & uintptr_t(0b11)); }
352 template<class T> constexpr T* ptr() const noexcept {
353 return std::bit_cast<T*>(ptr_ & (uintptr_t(-2) << uintptr_t(2)));
354 }
355 // clang-format off
356 constexpr D* isa_uniq() const noexcept { return tag() == Tag::Uniq ? ptr<D >() : nullptr; }
357 constexpr Data* isa_data() const noexcept { return tag() == Tag::Data ? ptr<Data>() : nullptr; }
358 constexpr Node* isa_node() const noexcept { return tag() == Tag::Node ? ptr<Node>() : nullptr; }
359 // clang-format on
360
361 uintptr_t ptr_ = 0;
362
363 friend class Sets;
364 friend std::ostream& operator<<(std::ostream& os, Set set) { return set.stream(os); }
365 };
366
367 static_assert(std::forward_iterator<typename Set::iterator>);
368 static_assert(std::ranges::range<Set>);
369
370 /// @name Construction
371 ///@{
372 Sets& operator=(const Sets&) = delete;
373
374 constexpr Sets() noexcept
375 : root_(make_node()) {}
376 constexpr Sets(const Sets&) noexcept = delete;
377 constexpr Sets(Sets&& other) noexcept
378 : Sets() {
379 swap(*this, other);
380 }
381 ///@}
382
383 /// @name Set Operations
384 /// @note These operations do **not** modify the input set(s); they create a **new** Set.
385 ///@{
386
387 /// Create a Set wih all elements in @p v.
388 [[nodiscard]] Set create(Vector<D*> v) {
389 auto vb = v.begin();
390 auto ve = v.end();
391 std::sort(vb, ve, [](D* d1, D* d2) { return d1->gid() < d2->gid(); });
392 auto vu = std::unique(vb, ve);
393 auto size = std::distance(vb, vu);
394
395 if (size == 0) return {};
396 if (size == 1) return {*vb};
397
398 if (size_t(size) <= N) {
399 auto [data, state] = allocate(size);
400 std::copy(vb, vu, data->begin());
401 return unify(data, state);
402 }
403
404 // sort in ascending tids but 0 goes last
405 std::sort(vb, vu, [](D* d1, D* d2) { return d1->tid() != 0 && (d2->tid() == 0 || d1->tid() < d2->tid()); });
406
407 auto res = root();
408 for (auto i = vb; i != vu; ++i) res = insert(res, *i);
409 return res;
410 }
411
412 /// Yields @f$s \cup \{d\}@f$.
413 [[nodiscard]] Set insert(Set s, D* d) {
414 if (auto u = s.isa_uniq()) {
415 if (d == u) return {d};
416
417 auto [data, state] = allocate(2);
418 if (d->gid() < u->gid())
419 data->elems[0] = d, data->elems[1] = u;
420 else
421 data->elems[0] = u, data->elems[1] = d;
422 return unify(data, state);
423 }
424
425 if (auto src = s.isa_data()) {
426 auto size = src->size;
427 if (size + 1 <= N) {
428 auto [dst, state] = allocate(size + 1);
429
430 // copy over and insert new element d
431 bool ins = false;
432 for (auto si = src->begin(), di = dst->begin(), se = src->end(); si != se || !ins; ++di) {
433 if (si != se && d == *si) { // already here
434 data_arena_.deallocate(state);
435 return s;
436 }
437
438 if (!ins && (si == se || d->gid() < (*si)->gid()))
439 *di = d, ins = true;
440 else
441 *di = *si++;
442 }
443
444 return unify(dst, state);
445 } else { // we need to switch from Data to Node
446 auto [dst, state] = allocate(size + 1);
447
448 // copy over
449 auto di = dst->begin();
450 for (auto si = src->begin(), se = src->end(); si != se; ++si, ++di) {
451 if (d == *si) { // already here
452 data_arena_.deallocate(state);
453 return s;
454 }
455
456 *di = *si;
457 }
458 *di = d; // put new element at last into dst->elems
459
460 // sort in ascending tids but 0 goes last
461 std::sort(dst->begin(), di,
462 [](D* d1, D* d2) { return d1->tid() != 0 && (d2->tid() == 0 || d1->tid() < d2->tid()); });
463
464 auto res = root();
465 for (auto i = dst->begin(), e = dst->end(); i != e; ++i) res = insert(res, *i);
466 return res;
467 }
468 }
469
470 if (auto n = s.isa_node()) {
471 if (n->contains(d)) return n;
472 return insert(n, d);
473 }
474
475 return {d};
476 }
477
478 /// Yields @f$s_1 \cup s_2@f$.
479 [[nodiscard]] Set merge(Set s1, Set s2) {
480 if (s1.empty() || s1 == s2) return s2;
481 if (s2.empty()) return s1;
482
483 if (auto u = s1.isa_uniq()) return insert(s2, u);
484 if (auto u = s2.isa_uniq()) return insert(s1, u);
485
486 auto d1 = s1.isa_data();
487 auto d2 = s2.isa_data();
488 if (d1 && d2) {
489 auto v = Vector<D*>();
490 v.reserve(d1->size + d2->size);
491
492 for (auto d : *d1) v.emplace_back(d);
493 for (auto d : *d2) v.emplace_back(d);
494
495 return create(std::move(v));
496 }
497
498 auto n1 = s1.isa_node();
499 auto n2 = s2.isa_node();
500 if (n1 && n2) {
501 if (n1->is_descendant_of(n2)) return n1;
502 if (n2->is_descendant_of(n1)) return n2;
503 return merge(n1, n2);
504 }
505
506 auto n = n1 ? n1 : n2;
507 for (auto d : *(d1 ? d1 : d2))
508 if (!n->contains(d)) n = insert(n, d);
509 return n;
510 }
511
512 /// Yields @f$s \setminus \{d\}@f$.
513 [[nodiscard]] Set erase(Set s, D* d) {
514 if (auto u = s.isa_uniq()) return d == u ? Set() : s;
515
516 if (auto data = s.isa_data()) {
517 size_t i = 0, size = data->size;
518 for (; i != size; ++i)
519 if (data->elems[i] == d) break;
520
521 if (i == size--) return s;
522 if (size == 0) return {};
523 if (size == 1) return {i == 0 ? data->elems[1] : data->elems[0]};
524
525 assert(size <= N);
526 auto [new_data, state] = allocate(size);
527 auto db = data->begin();
528 std::copy(db + i + 1, data->end(), std::copy(db, db + i, new_data->elems)); // copy over, skip i
529
530 return unify(new_data, state);
531 }
532
533 if (auto n = s.isa_node()) {
534 if (d->tid() == 0 || d->tid() < n->min) return n;
535 if (!n->contains(d)) return n;
536
537 auto res = erase(n, d);
538 if (res->size > N) return res;
539
540 auto v = Vector<D*>();
541 v.reserve(res->size);
542 for (auto i = res; !i->is_root(); i = i->parent) v.emplace_back(i->def);
543 return create(std::move(v));
544 }
545
546 return {};
547 }
548 ///@}
549
550 /// @name DOT output
551 void dot() {
552 auto of = std::ofstream("trie.dot");
553 dot(of);
554 }
555
556 void dot(std::ostream& os) const {
557 os << "digraph {{" << std::endl;
558 os << "ordering=out;" << std::endl;
559 os << "node [shape=box,style=filled];" << std::endl;
560 root()->dot(os);
561 os << "}}" << std::endl;
562 }
563
564 friend void swap(Sets& s1, Sets& s2) noexcept {
565 using std::swap;
566 // clang-format off
567 swap(s1.data_arena_, s2.data_arena_);
568 swap(s1.node_arena_, s2.node_arena_);
569 swap(s1.pool_, s2.pool_);
570 swap(s1.root_, s2.root_);
571 swap(s1.tid_counter_, s2.tid_counter_);
572 swap(s1.id_counter_ , s2.id_counter_ );
573 // clang-format on
574 }
575
576private:
577 D* set_tid(D* def) noexcept {
578 assert(def->tid() == 0);
579 def->tid_ = tid_counter_++;
580 return def;
581 }
582
583 // get rid of clang warnings
584 template<class T>
585 inline static constexpr size_t SizeOf = sizeof(std::conditional_t<std::is_pointer_v<T>, uintptr_t, T>);
586
587 // array helpers
588 std::pair<Data*, fe::Arena::State> allocate(size_t size) {
589 auto bytes = sizeof(Data) + size * SizeOf<D>;
590 auto state = data_arena_.state();
591 auto buff = data_arena_.allocate(bytes, alignof(Data));
592 auto data = new (buff) Data(size);
593 return {data, state};
594 }
595
596 Set unify(Data* data, fe::Arena::State state, size_t excess = 0) {
597 assert(data->size != 0);
598 auto [i, ins] = pool_.emplace(data);
599 if (ins) {
600 data_arena_.deallocate(excess * SizeOf<D>); // release excess memory
601 return Set(data);
602 }
603
604 data_arena_.deallocate(state);
605 return Set(*i);
606 }
607
608 // Trie helpers
609 constexpr Node* root() const noexcept { return root_.get(); }
610 fe::Arena::Ptr<Node> make_node() { return node_arena_.mk<Node>(id_counter_++); }
611 fe::Arena::Ptr<Node> make_node(Node* parent, D* def) { return node_arena_.mk<Node>(parent, def, id_counter_++); }
612
613 [[nodiscard]] Node* mount(Node* parent, D* def) {
614 assert(def->tid() != 0);
615 auto [i, ins] = parent->children.emplace(def, nullptr);
616 if (ins) i->second = make_node(parent, def);
617 return i->second.get();
618 }
619
620 [[nodiscard]] constexpr Node* insert(Node* n, D* d) noexcept {
621 if (d->tid() == 0) return mount(n, set_tid(d));
622 if (n->def == d) return n;
623 if (n->is_root() || n->def->tid() < d->tid()) return mount(n, d);
624 return mount(insert(n->parent, d), n->def);
625 }
626
627 [[nodiscard]] constexpr Node* merge(Node* n, Node* m) {
628 if (n == m || m->is_root()) return n;
629 if (n->is_root()) return m;
630 auto nn = n->def->tid() < m->def->tid() ? n : n->parent;
631 auto mm = n->def->tid() > m->def->tid() ? m : m->parent;
632 return mount(merge(nn, mm), n->def->tid() < m->def->tid() ? m->def : n->def);
633 }
634
635 [[nodiscard]] Node* erase(Node* n, D* d) {
636 if (d->tid() > n->def->tid()) return n;
637 if (n->def == d) return n->parent;
638 return mount(erase(n->parent, d), n->def);
639 }
640
641 fe::Arena node_arena_;
642 fe::Arena data_arena_;
643 absl::flat_hash_set<const Data*, absl::Hash<const Data*>, typename Data::Equal> pool_;
644 fe::Arena::Ptr<Node> root_;
645 u32 tid_counter_ = 1;
646 u32 id_counter_ = 0;
647};
648
649} // namespace mim
constexpr iterator & operator++() noexcept
Definition sets.h:157
constexpr iterator() noexcept=default
D *const * pointer
Definition sets.h:145
constexpr pointer operator->() const noexcept
Definition sets.h:202
constexpr bool operator!=(iterator other) const noexcept
Definition sets.h:187
friend class Set
Definition sets.h:211
D *const & reference
Definition sets.h:146
constexpr reference operator*() const noexcept
Definition sets.h:193
std::forward_iterator_tag iterator_category
Definition sets.h:142
std::ptrdiff_t difference_type
Definition sets.h:143
iterator & clear()
Definition sets.h:205
constexpr iterator operator++(int) noexcept
Definition sets.h:176
constexpr bool operator==(iterator other) const noexcept
Definition sets.h:186
bool has_intersection(Set other) const noexcept
Is ?.
Definition sets.h:262
constexpr bool empty() const noexcept
Is empty?
Definition sets.h:235
constexpr bool operator==(Set other) const noexcept
Definition sets.h:331
constexpr Set() noexcept=default
Null set.
constexpr Set(const Set &) noexcept=default
friend class Sets
Definition sets.h:363
constexpr iterator begin() const noexcept
Definition sets.h:316
void dump() const
Definition sets.h:347
constexpr size_t size() const noexcept
Definition sets.h:227
friend std::ostream & operator<<(std::ostream &os, Set set)
Definition sets.h:364
std::ostream & stream(std::ostream &os) const
Definition sets.h:337
bool contains(D *d) const noexcept
Is ?.
Definition sets.h:247
constexpr Set & operator=(const Set &) noexcept=default
constexpr Set(Set &&) noexcept=default
constexpr bool operator!=(Set other) const noexcept
Definition sets.h:332
constexpr iterator end() const noexcept
Definition sets.h:323
friend void swap(Sets &s1, Sets &s2) noexcept
Definition sets.h:564
void dot()
Definition sets.h:551
void dot(std::ostream &os) const
Definition sets.h:556
Set merge(Set s1, Set s2)
Yields .
Definition sets.h:479
constexpr Sets(const Sets &) noexcept=delete
Sets & operator=(const Sets &)=delete
constexpr Sets() noexcept
Definition sets.h:374
constexpr Sets(Sets &&other) noexcept
Definition sets.h:377
Set erase(Set s, D *d)
Yields .
Definition sets.h:513
Set insert(Set s, D *d)
Yields .
Definition sets.h:413
Set create(Vector< D * > v)
Create a Set wih all elements in v.
Definition sets.h:388
This is a thin wrapper for absl::InlinedVector<T, N, A> which is a drop-in replacement for std::vecto...
Definition vector.h:17
This is an intrusive Link-Cut-Tree.
constexpr void link(Node *child) noexcept
Registers the edge this -> child in the aux tree.
bool contains(const D *&k) noexcept
constexpr Node * path_parent() noexcept
constexpr Node * find(const D *&k) noexcept
constexpr Node() noexcept=default
Definition ast.h:14
absl::flat_hash_map< K, V, GIDHash< K > > GIDMap
Definition util.h:176
bool u1
Definition types.h:38
uint32_t u32
Definition types.h:34
std::ostream & println(std::ostream &os, const char *fmt, Args &&... args)
As above but end with std::endl.
Definition print.h:151
Vector(I, I, A=A()) -> Vector< typename std::iterator_traits< I >::value_type, Default_Inlined_Size< typename std::iterator_traits< I >::value_type >, A >
constexpr bool operator()(const Data *d1, const Data *d2) const noexcept
Definition sets.h:95