#ifndef   dsa_MergeableHeap_H__
#define   dsa_MergeableHeap_H__

#include <cstdlib>
#include <algorithm>

namespace meow {

/*!
 * @brief 
 *
 * 一個用 \b 左偏樹 實作的 \c Maximum-Heap , 除了原本heap有的功能外,
 * 還支援 \c merge 功能
 *
 * Template Class Operators Request
 * --------------------------------
 *
 * |const?|Typename|Operator   | Parameters   |Return Type | Description       |
 * |-----:|:------:|----------:|:-------------|:----------:|:------------------|
 * |const |Element |operator<  |(Element \c b)|bool        | 大小比較          |
 *
 * @note:
 *   假設現在有兩個MergeableHeap \c A 和 \c B,  則:
 *   - 執行 \c A.merge(&B) 後 \c B 會變成空的
 *   - 執行 \c B.moveTo(&A) 後 \c B 會變成空的, \c A 原本擁有的資料也會覆蓋掉
 *
 * @author cat_leopard
 */
template<class Element>
class MergeableHeap { // maximum-heap
private:
  struct Node {
    Element  value_;
    Node*   lChild_;
    Node*   rChild_;
    size_t  weight_;
    Node(Element const& value):
    value_(value), lChild_(NULL), rChild_(NULL), weight_(1){
    }
  };

  Node* root_;

  void clear(Node* node) {
    if (node != NULL) {
      clear(node->lChild_);
      clear(node->rChild_);
      delete node;
    }
  }
  Node* dup(Node* node) {
    if (node == NULL) return NULL;
    Node* ret = new Node(node->value_);
    ret->lChild_ = dup(node->lChild_);
    ret->rChild_ = dup(node->rChild_);
    ret->weight_ = 1;
    ret->weight_ += (ret->lChild_ == NULL ? 0 : ret->lChild_->weight_);
    ret->weight_ += (ret->rChild_ == NULL ? 0 : ret->rChild_->weight_);
    return ret;
  }
  Node* merge(Node* left, Node* right) {
    if (left  == NULL) return right;
    if (right == NULL) return left;
    if (left->value_ < right->value_) {
      std::swap(left, right);
    }
    left->rChild_ = merge(left->rChild_, right);
    size_t lw = (left->lChild_ == NULL ? 0 : left->lChild_->weight_);
    size_t rw = (left->rChild_ == NULL ? 0 : left->rChild_->weight_);
    if (lw < rw) {
      std::swap(left->lChild_, left->rChild_);
    }
    left->weight_ = 1 + lw + rw;
    return left;
  }
public:
  //! @brief constructor
  MergeableHeap(): root_(NULL){
  }

  //! @brief constructor, 並且複製資料
  MergeableHeap(MergeableHeap const& heap2): root_(dup(heap2.root_)) {
  }

  //! @brief destructor
  ~MergeableHeap(){
    clear(root_);
  }

  //! @brief 複製資料
  MergeableHeap& copyFrom(MergeableHeap const& heap2) {
    delete root_;
    root_ = dup(heap2.root_);
    return *this;
  }

  /*!
   * @brief 將自己的資料丟給指定的heap, 從此自己一身空
   */
  void moveTo(MergeableHeap* heap2){
    heap2->clear();
    heap2->root_ = root_;
    root_ = NULL;
  }

  /*!
   * @brief 回傳最大的那個 Element
   */
  Element const& top() const {
    return root_->value_;
  }

  /*!
   * @brief 回傳資料個數
   */
  size_t size() const {
    return (root_ == NULL ? 0 : root_->weight_);
  }

  /*!
   * @brief 回傳是否為空
   */
  bool empty() const {
    return (size() == 0);
  }

  /*!
   * @brief 加入element
   */
  void push(Element const& value) {
    root_ = merge(root_, new Node(value));
  }

  /*!
   * @brief 將最大的element移除
   */
  void pop() {
    Node* l = root_->lChild_;
    Node* r = root_->rChild_;
    delete root_;
    root_ = merge(l, r);
  }

  /*!
   * 將資料清空
   */
  void clear() {
    clear(root_);
    root_ = NULL;
  }

  /*!
   * 將給定的MergeableHeap的資料統統加到自己身上並且清空該heap
   */
  void merge(MergeableHeap* heap2) {
    root_ = merge(root_, heap2->root_);
    heap2->root_ = NULL;
  }

  //! @brief same as \c copyFrom(heap2)
  MergeableHeap& operator=(MergeableHeap const& heap2) {
    return copyFrom(heap2);
  }
};

}

#endif // dsa_MergeableHeap_H__