/*
++	File name: Heap.h
++	File comments: Use this code in any way if you so desire but
		include this copyright notice.
++	Copyright (c) 2003, Jesper Öqvist
*/

//created: 2003-02-25
//last updated: 2003-02-28

#ifndef _JSH_HEAP_H
#define _JSH_HEAP_H

namespace jsh{

struct greater
{
public:
	template <class _t>
	bool operator()(const _t& _a, const _t& _b) const {return (_a > _b);}
};

struct less
{
public:
	template <class _t>
	bool operator()(const _t& _a, const _t& _b) const {return (_a < _b);}
};

template <typename _t, typename _c = less>
class heap
{
	struct _node
	{
		_t _value;
		_node* _next;

		_node() {}
		_node(const _node& _a): _value(_a._value), _next(_a._next) {}
		_node& operator=(const _node& _a) {_value = _a._value;_next = _a._next;}
		~_node() {}
	};
	_node* _top;
	_node* _bottom;

	heap<_t, _c>(const heap<_t, _c>& _a): _top(NULL), _bottom(NULL) {}
	heap<_t, _c>& operator=(const heap<_t, _c>& _a) {return *this;}

public:
	heap<_t, _c>(): _top(NULL), _bottom(NULL) {}
	~heap<_t, _c>() {clear();}

	void push(const _t& _a);//push a new value onto the heap
	void pop();//remove the top value
	const _t& top() {return _top->_value;}//what's the top value?
	bool empty() {return (_top == NULL);}//is the heap empty?
	void clear() {while (!empty()) pop();}//removes all nodes of the heap
};

template <typename _t, typename _c>
void heap<_t, _c>::push(const _t& _a)
{
	if (_top != NULL)
	{
		//test last value to avoid comparing all values if possible
		if (_c()(_a, _bottom->_value)) goto _push_bottom;
		else
		{
			//test first value to avoid unnecessary comparisons
			if (!_c()(_a, _top->_value))
			{
				_node* _new = new _node;
				_new->_value = _a;
				_new->_next = _top;
				_top = _new;
				return;
			}
			else
			{
				_node* _current = _top;
				_node* _last = _current;
				//compare values untill comparison fails
				while (_c()(_a, _current->_value))
				{
					_last = _current;
					_current = _last->_next;
				}
				_node* _new = new _node;
				_new->_value = _a;
				_new->_next = _current;
				_last->_next = _new;
				return;
			}
		}
_push_bottom:
		_node* _new = new _node;
		_new->_value = _a;
		_new->_next = _bottom->_next;
		_bottom->_next = _new;
		_bottom = _new;
		return;
	}
	else
	{
		//if there is no top / the heap is empty:
		_top = new _node;
		_top->_value = _a;
		_top->_next = NULL;
		_bottom = _top;
	}
}

template <typename _t, typename _c>
void heap<_t, _c>::pop()
{
	if (_top == NULL) return;
	if (_top == _bottom)
	{
		delete _top;
		_top = _bottom = NULL;
	}
	else
	{
		_node* _tmp = _top->_next;
		delete _top;
		_top = _tmp;
	}
}

};

#endif _JSH_HEAP_H