// @class name  : MergeableHeap
// @implement   : Leftist 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;
  }
}