21 #ifndef INCLUDE_ELM_DATA_BINOMIALQUEUE_H_
22 #define INCLUDE_ELM_DATA_BINOMIALQUEUE_H_
24 #include <elm/assert.h>
25 #include <elm/compare.h>
26 #include <elm/data/custom.h>
30 template <
class T,
class C = Comparator<T>,
class A = DefaultAlloc>
37 : next(
nullptr), child(
nullptr),
38 degree(NOT_IN_HEAP), x(xx) { }
46 : C(c), A(a), _head(nullptr), _min(nullptr) { }
48 inline bool isEmpty()
const {
return _head ==
nullptr && _min ==
nullptr; }
52 Node *node = min(prev);
63 join(reverse(n->child));
69 void put(
const T& x) {
70 auto n =
new(A::allocate(
sizeof(Node))) Node(x);
72 if(_min !=
nullptr && higher(n->x, _min->x)) {
85 # ifdef TEST_BINOMIAL_QUEUE
91 inline bool higher(
const T& x,
const T& y)
const {
return C::doCompare(x, y) <= 0; }
93 inline void link(Node *root, Node *child) {
94 child->next = root->child;
99 Node *min(Node*& prev) {
100 ASSERTP(_head !=
nullptr,
"no head in empty queue");
102 Node *n = _head, *
p = _head, *c = _head->next;
103 while(c !=
nullptr) {
104 if(higher(c->x, n->x)) {
114 Node *merge(Node *a, Node *b) {
115 Node *h =
nullptr, **
p = &h;
116 while(a !=
nullptr && b !=
nullptr) {
117 if(a->degree < b->degree) {
134 void join(Node *h2) {
137 if(_head ==
nullptr) {
141 Node *h1 = merge(_head, h2);
142 Node *
p =
nullptr, *x = h1, *n = x->next;
143 while(n !=
nullptr) {
144 if(x->degree != n->degree || (n->next !=
nullptr && n->next->degree == x->degree)) {
148 else if(higher(x->x, n->x)) {
165 Node *reverse(Node *h) {
169 while(h->next !=
nullptr) {