blob: 6e49a1c284425d71ca798a4a109929eb54efbd3f (
plain) (
tree)
|
|
#include <cstdlib>
namespace meow{
//////////////////////////////////////////////////////////
// **# MergeableHeap--Node-- constructor #** //
//////////////////////////////////////////////////////////
template<class Element>
inline
MergeableHeap<Element>::Node::Node(Element const& _value): // Node
value(_value), l_child(NULL), r_child(NULL), weight(1){ }
//////////////////////////////////////////////////////////
// **# MergeableHeap -- clear, duplicate #** //
//////////////////////////////////////////////////////////
template<class Element>
inline void
MergeableHeap<Element>::clear(Node* _node){ //clear
if(_node != NULL){
clear(_node->l_child);
clear(_node->r_child);
delete _node;
}
}
template<class Element>
inline typename MergeableHeap<Element>::Node*
MergeableHeap<Element>::dup(Node* _node2){ // dup
if(_node2 == NULL) return NULL;
Node* ret = new Node(_node2->value);
ret->l_child = dup(_node2->l_child);
ret->r_child = dup(_node2->r_child);
ret->weight = 1;
ret->weight += (ret->l_child == NULL ? 0 : ret->l_child->weight);
ret->weight += (ret->r_child == NULL ? 0 : ret->r_child->weight);
return ret;
}
//////////////////////////////////////////////////////////
// **# MergeableHeap -- merge #** //
//////////////////////////////////////////////////////////
template<class Element>
inline typename MergeableHeap<Element>::Node*
MergeableHeap<Element>::merge(Node* _left, Node* _right){ //merge
if(_left == NULL) return _right;
if(_right == NULL) return _left;
if(_left->value < _right->value){
std::swap(_left, _right);
}
_left->r_child = merge(_left->r_child, _right);
size_t lw = (_left->l_child == NULL ? 0 : _left->l_child->weight);
size_t rw = (_left->r_child == NULL ? 0 : _left->r_child->weight);
if(lw < rw){
std::swap(_left->l_child, _left->r_child);
}
_left->weight = 1 + lw + rw;
return _left;
}
//////////////////////////////////////////////////////////
// **# MergeableHeap -- constrctors/destructors #** //
//////////////////////////////////////////////////////////
template<class Element>
inline
MergeableHeap<Element>::MergeableHeap(): //MergeableHeap
root(NULL){ }
template<class Element>
inline
MergeableHeap<Element>::MergeableHeap(MergeableHeap const& _heap2):
root(NULL){
root = dup(_heap2.root);
}
template<class Element>
inline
MergeableHeap<Element>::~MergeableHeap(){ //~MergeableHeap
clear(root);
}
//////////////////////////////////////////////////////////
//**# MergeableHeap -- copy operation/data transform #**//
//////////////////////////////////////////////////////////
template<class Element>
inline MergeableHeap<Element>&
MergeableHeap<Element>::operator=(MergeableHeap const& _heap2){ // =
root = dup(_heap2.root);
return *this;
}
template<class Element>
inline void
MergeableHeap<Element>::moveTo(MergeableHeap* _heap2){ // moveTo
_heap2->clear();
_heap2->root = root;
root = NULL;
}
//////////////////////////////////////////////////////////
// **# MergeableHeap -- access: top, size, emtpy #** //
//////////////////////////////////////////////////////////
template<class Element>
inline Element const&
MergeableHeap<Element>::top() const{ // top
return root->value;
}
template<class Element>
inline size_t
MergeableHeap<Element>::size() const{ // size
return (root == NULL ? 0 : root->weight);
}
template<class Element>
inline size_t
MergeableHeap<Element>::empty() const{ // empty
return (size() == 0);
}
//////////////////////////////////////////////////////////
// **# MergeableHeap -- update: push, pop, merge #** //
//////////////////////////////////////////////////////////
template<class Element>
inline void
MergeableHeap<Element>::push(Element const& _value){ // push
Node* new_node = new Node(_value);
root = merge(root, new_node);
}
template<class Element>
inline void
MergeableHeap<Element>::pop(){ // pop
Node* l = root->l_child;
Node* r = root->r_child;
delete root;
root = merge(l, r);
}
template<class Element>
inline void
MergeableHeap<Element>::merge(MergeableHeap* _heap2){ // merge
root = merge(root, _heap2->root);
_heap2->root = NULL;
}
//////////////////////////////////////////////////////////
// **# MergeableHeap -- refresh: clear #** //
//////////////////////////////////////////////////////////
template<class Element>
inline void
MergeableHeap<Element>::clear(){ // clear
clear(root);
root = NULL;
}
}
|