/*
++ 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 |