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) {
Definition: BinomialQueue.h:31
const T & head() const
Definition: BinomialQueue.h:50
void put(const T &x)
Definition: BinomialQueue.h:69
BinomialQueue(const C &c=single< C >(), const A &a=single< A >())
Definition: BinomialQueue.h:45
bool isEmpty() const
Definition: BinomialQueue.h:48
T get()
Definition: BinomialQueue.h:56
T t
Definition: compare.h:36
Definition: type_info.h:56
Printable< T, M > p(const T &data, const M &man)
Definition: Output.h:302
typename type_info< T >::out_t out
Definition: type_info.h:284