/* Copyright (c) 2009, Markus Peloquin <markus@cs.wisc.edu>
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */

#ifndef FIBONACCI_HEAP_HPP
#define FIBONACCI_HEAP_HPP

/* The algorithm is from _Introduction to Algorithms, 2nd ed._ by Cormen et
 * al. (exactly seven functions, though they left much up to the reader to
 * implement.  The STLifying was done by me.  The interface has everything
 * offered by std::priority_queue, as well as cast-to-bool,
 * decrease(pointer, key), and pop(pointer).  There is also no merge
 * operation. */

#include <functional>
#include <queue>
#include <stdexcept>
#include <tr1/cstdint>
#include <valarray>

template <typename T, class Cmp=std::less<T> >
class fib_heap {
public:
	// types

	typedef T	value_type;
	typedef size_t	size_type;

private:
	struct node {
		node(const value_type &val) : val(val) {}
		node		*p;
		node		*child; // list
		node		*l;
		node		*r;
		size_type	degree;
		value_type	val;
		bool		mark;
	};

public:
	typedef node	*pointer;

	// O(1)
	explicit fib_heap(const Cmp &lt=Cmp()) : _lt(lt), _min(0), _sz(0) {}

	// O(n)
	template <class In>
	fib_heap(In first, In last, const Cmp &lt=Cmp()) :
		_lt(lt), _min(0), _sz(0)
	{	while (first != last) push(*first++); }

	// O(n)
	fib_heap(const fib_heap &heap);

	// O(n)
	~fib_heap()
	{
		clear();
	}

	// O(n)
	fib_heap &operator=(const fib_heap &heap)
	{
		fib_heap copy = heap;
		swap(copy);
		return *this;
	}

	// O(1)
	void swap(fib_heap &heap)
	{
		std::swap(_lt, heap._lt);
		std::swap(_min, heap._min);
		std::swap(_sz, heap._sz);
	}

	// O(1)
	operator bool() const
	{	return _sz; }
	// O(1)
	bool empty() const
	{	return !_sz; }
	// O(1)
	size_type size() const
	{	return _sz; }

	// O(1)
	const value_type &top() const
	{	return _min->val; }

	// O(1)
	pointer push(const value_type &val)
	{
		node *n = new node(val);
		insert (n);
		return n;
	}

	// O(lg n) amortized
	void pop()
	{
		node *n = extract_min();
		if (n) delete n;
	}

	// O(lg n) amortized
	void pop(pointer p)
	{
		node	*n;

		decrease_key_neginf(p);
		n = extract_min();
		if (n) delete n;
	}

	// O(1)
	void decrease(pointer p, value_type k) throw (std::invalid_argument)
	{	decrease_key(p, k); }

private:
	// O(1)
	void insert(node *x)
	{
		x->degree = 0;
		x->p = 0;
		x->child = 0;
		x->mark = false;
		if (_min) {
			x->l = _min;
			x->r = _min->r;
			x->l->r = x;
			x->r->l = x;
			if (_lt(x->val, _min->val))
				_min = x;
		} else {
			x->l = x;
			x->r = x;
			_min = x;
		}
		_sz++;
	}

	// O(lg n)
	node *extract_min()
	{
		node *z = _min;
		if (!z) return 0;

		node *r_last = z->l;
		node *r_first = z->r;
		if (r_last == z)
			// z has no siblings
			r_first = r_last = 0;
		// child list iterators
		node *c = z->child;
		node *c_first = c;
		// c_last point to last node, not after it
		node *c_last = 0;
		if (c) {
			c_last = c;
			for (;;) {
				c->p = 0;
				c = c->r;
				if (c == c_first) break;
				c_last = c;
			}
		}
		if (r_first) {
			if (c_first) {
				// patch child list into root list
				c_first->l = r_last;
				c_last->r = r_first;
				r_first->l = c_last;
				r_last->r = c_first;
			} else {
				// simply discard z from root list
				r_first->l = r_last;
				r_last->r = r_first;
			}
			_min = r_first;
		} else {
			// make child list (if it exists) the root list
			_min = c_first;
		}
		if (_min) consolidate();
		_sz--;
		return z;
	}

	// O(lg n)
	void consolidate()
	{
		node		*first;
		node		*last;
		node		*w;
		node		*w_next;
		uint8_t		max_degree; // [0,32)

		// need floor(lg(_sz)): minimum number of bits to represent
		// in base 2, minus 1
		max_degree = 0;
		for (size_type sz = _sz; sz; sz >>= 1)
			max_degree++;
		std::valarray<node *> A(max_degree);

		last = _min->l;
		for (w = _min;; w = w_next) {
			node		*x = w;
			size_type	d = x->degree;

			w_next = w->r;

			while (A[d]) {
				// another node with the same degree as x
				node *y = A[d];
				if (_lt(y->val, x->val))
					std::swap(x, y);
				link(y, x);
				A[d++] = 0;
			}
			A[d] = x;

			if (w == last) break;
		}

		_min = 0;
		first = 0;
		last = 0;
		for (uint8_t i = 0; i < A.size(); i++) {
			if (!A[i]) continue;

			if (last) {
				last->r = A[i];
				A[i]->l = last;
			} else
				first = A[i];
			last = A[i];

			if (!_min || _lt(last->val, _min->val))
				_min = last;
			last->p = 0;
		}
		if (last) {
			last->r = first;
			first->l = last;
		}
	}

	// O(1)
	void link(node *y, node *x)
	{
		// remove y from the root list
		y->l->r = y->r;
		y->r->l = y->l;

		// make y a child of x, incrementing x->degree
		if (x->child) {
			y->l = x->child;
			y->r = x->child->r;
			y->l->r = y;
			y->r->l = y;
		} else {
			x->child = y;
			y->r = y->l = y;
		}
		y->p = x;
		x->degree++;
		y->mark = false;
	}

	// O(1) amortized
	void decrease_key(node *x, value_type k) throw (std::invalid_argument)
	{
		if (_lt(x->val, k))
			throw std::invalid_argument(
			    "new key is greater than current key");
		x->val = k;
		node *y = x->p;
		if (y && _lt(x->val, y->val)) {
			cut(x, y);
			cascading_cut(y);
		}
		if (_lt(x->val, _min->val))
			_min = x;
	}

	// O(1) amortized
	void decrease_key_neginf(node *x)
	{
		node *y = x->p;
		if (y) {
			cut(x, y);
			cascading_cut(y);
		}
		_min = x;
	}

	// O(1)
	void cut(node *x, node *y)
	{
		if (x->l != x->r) {
			x->l->r = x->r;
			x->r->l = x->l;
			y->child = x->r;
		} else
			y->child = 0;
		y->degree--;
		x->l = _min;
		x->r = _min->r;
		_min->r->l = x;
		_min->r = x;
		x->p = 0;
		x->mark = false;
	}

	// O(1) amortized
	void cascading_cut(node *y)
	{
		node *z = y->p;
		if (!z);
		else if (!y->mark)
			y->mark = true;
		else {
			cut(y, z);
			cascading_cut(z);
		}
	}

	// O(n)
	void clear();

	Cmp		_lt;
	node		*_min; // list
	size_type	_sz;
};

template <typename T, class Cmp>
fib_heap<T, Cmp>::fib_heap(const fib_heap &heap) :
	_lt(heap.lt), _min(0), _sz(0)
{
	std::queue<const node *> q;

	if (_min) {
		q.push(_min);
		// add siblings to queue
		for (const node *s = _min->r; s != _min; s = s->r)
			q.push(s);
	}

	while (!q.empty()) {
		const node *n = q.front();
		q.pop();

		// add children to queue
		if (n->child) {
			q.push(n->child);
			for (const node *c = n->child->r;
			    c != n->child; c = c->r)
				q.push(c);
		}

		push(n->val);
	}
}

template <typename T, class Cmp>
void
fib_heap<T, Cmp>::clear()
{
	std::queue<node *> q;

	if (_min) {
		q.push(_min);
		// add siblings to queue
		for (node *s = _min->r; s != _min; s = s->r)
			q.push(s);
	}

	while (!q.empty()) {
		node *n = q.front();
		q.pop();

		push(n->val);

		// add children to queue
		if (n->child) {
			q.push(n->child);
			for (node *c = n->child->r;
			    c != n->child; c = c->r)
				q.push(c);
		}

		delete n;
	}
	_sz = 0;
}

#endif