path: root/meowpp/dsa/SplayTree.h

#ifndef   dsa_SplayTree_h__
#define   dsa_SplayTree_h__

#include <cstdlib>
#include <utility>

#include "../math/utility.h"

namespace meow {

/*!
 * @brief
 *
 * 是一種神乎其技的資料結構, 維護一堆 Key->Value . 並且支援
 * 一些 \c std::map 難以快速實踐的操作, 如 \c split , \c merge , \c keyOffset
 *
 * Template Class Operators Request
 * --------------------------------
 *
 * |const?|Typename|Operator   | Parameters   |Return Type | Description       |
 * |-----:|:------:|----------:|:-------------|:----------:|:------------------|
 * |const |Key     |operator+  |(Key    \c k) | Key        |相加               |
 * |const |Key     |operator<  |(Key    \c k) | bool       |大小比較           |
 * |      |Key     |operator=  |(Key    \c k) | Key        |copy oper          |
 * |      |Key     |Key        |(int    \c n) |            |構子,\c n 永遠是0  |
 * |      |Value   | Value     |(           ) |            |建構子             |
 *
 * @note:
 *   -假設現在有兩個SplayTree `A` 和 `B`,  則:
 *        -執行 `B.moveTo(&A)` 後 `B` 會變成空的, `A` 原本擁有的資料也會覆蓋掉
 *        -行 `A.merge(&B)` 或 `A.mergeAfter(&B)` 後
 *         如果檢查發現確實可以merge, 則之後 `B` 會變成空的
 *
 * @author cat_leopard
 */
template<class Key, class Value>
class SplayTree {
private:
  struct Node {
    Key            key_;
    Key      keyOffset_;
    Value        value_;
    size_t        size_;
    Node*       parent_;
    Node*        child_[2];
    
    Node(Key const& key, Value const& value):
    key_(key), keyOffset_(0), value_(value) {
      size_     = 1;
      parent_   = NULL;
      child_[0] = NULL;
      child_[1] = NULL;
    }
    //
    void keyOffset(Key const& delta) {
      key_       = key_       + delta;
      keyOffset_ = keyOffset_ + delta;
    }
    void syncDown() const {
      for (size_t i = 0; i < 2; i++) {
        if (child_[i] == NULL) continue;
        child_[i]->keyOffset(keyOffset_);
      }
      ((Node*)this)->keyOffset_ = Key(0);
    }
    void syncUp() const {
      ((Node*)this)->size_ = 1;
      for (size_t i = 0; i < 2; i++) {
        if (child_[i] == NULL) continue;
        ((Node*)this)->size_ += child_[i]->size_;
      }
    }
  };

  Node* root_;

  //! @brief 指定左子or右子, 連接parent<--->child
  void connect(Node const* parent, size_t left_right, Node const* child) const {
    Node* p = (Node*)parent;
    Node* c = (Node*)child;
    if (p != NULL) p->child_[left_right] = c;
    if (c != NULL) c->parent_            = p;
  }

  //! @brief 一路往上轉
  Node const* splay(Node const* node) const {
    if (node != NULL && node->parent_ != NULL) {
      for (const Node *g_grand, *grand, *parent, *child = node; ; ) {
        g_grand = (grand = parent = child->parent_)->parent_;
        size_t pc = (parent->child_[0] == child ? 0 : 1);
        connect(parent,  pc, child->child_[!pc]);
        connect(child , !pc, parent);
        if (g_grand != NULL) {
          g_grand = (grand = g_grand)->parent_;
          size_t gp = (grand->child_[0] == parent ? 0 : 1);
          Node const* who = (pc == gp ? parent : child);
          connect(grand,  gp, who->child_[!gp]);
          connect(who  , !gp, grand);
          grand->syncUp();
        }
        parent->syncUp();
        child ->syncUp();
        if (g_grand == NULL) {
          connect(NULL, 0, child);
          break;
        }
        connect(g_grand, (g_grand->child_[0] == grand ?  0 : 1), child);
      }
    }
    return (((SplayTree*)this)->root_ = (Node*)node);
  }

  void clear(Node* node) {
    if (node == NULL) return ;
    clear(node->child_[0]);
    clear(node->child_[1]);
    delete node;
  }

  Node* dup(Node* node2) {
    if (node2 == NULL) return NULL;
    node2->syncDown();
    Node* node = new Node(node2->key_, node2->value_);
    connect(node, 0, dup(node2->child_[0]));
    connect(node, 1, dup(node2->child_[1]));
    node->syncUp();
    return node;
  }

  Node const* findKey(Node const* node, Key const& key) const {
    Node const* ret = node;
    while (node != NULL) {
      node->syncDown();
      ret = node;
      if (!(key < node->key_)) {
        if (!(node->key_< key)) break;
        node = node->child_[1];
      }
      else {
        node = node->child_[0];
      }
    }
    return ret;
  }
  Node const* findMinMax(Node const* node, bool minimum) const {
    Node const* ret = node;
    for (int i = minimum ? 0 : 1; node != NULL; node = node->child_[i]) {
      node->syncDown();
      ret = node;
    }
    return ret;
  }
  Node const* findOrder(Node const* node, size_t order) const {
    Node const* ret = node;
    while (node != NULL) {
      node->syncDown();
      ret = node;
      size_t ord = 1 + (node->child_[0] == NULL ? 0 : node->child_[0]->size_);
      if     (ord == order) return ret;
      else if(ord <  order){ node = node->child_[1]; order -= ord; }
      else                 { node = node->child_[0];               }
    }
    return ret;
  }

  void split(Node* root, Node** left, Node** right) {
    if (root == NULL) { *left = NULL; *right = NULL; return ; }
    root->syncDown();
    *left  = root;
    *right = root->child_[1];
    if (*right != NULL) {
      (*left )->child_[1] = NULL;
      (*right)->parent_   = NULL;
      (*left )->syncUp();
    }
  }
  Node* merge(Node* left, Node* right) {
    if (left  == NULL) return right;
    if (right == NULL) return left ;
    left->syncDown();
    connect(left, 1, right);
    left->syncUp();
    return left;
  }
public:
  /*!
   * @brief 類似 \c stl 的 \c iterator ,不過這邊叫做\c Element
   *
   * 用來當作回傳資料的媒介
   */
  class Element{
  private:
    typedef std::pair<Key const&, Value&> Entry;
    Entry* entry_;
    Node *  node_;
    //
    void reset(Node* node) {
      node_ = node;
      delete entry_;
      entry_ = (node == NULL ? NULL : new Entry(node->key_, node->value_));
    }
  public:
    Element(): entry_(NULL), node_(NULL) {
    }
    Element(Node* node): entry_(NULL), node_(NULL) {
      reset(node);
    }
    Element(Element const& element2): entry_(NULL), node_(NULL) {
      reset(element2.node_);
    }
    ~Element(){
      delete entry_;
    }

    //! @brief 複製資料
    Element& copyFrom(Element const& e) {
      reset(e.node_);
      return *this;
    }

    //! @brief 比對兩者是否為指向同一個Entry
    bool same(Element const& e2) const {
      return (node_ == e2.node_);
    }

    //! @brief same as copyFrom
    Element& operator=(Element const& e2) {
      return copyFrom(e2);
    }

    //! @brief 重導至\c std::pair<Key \c const&,\c Value&>*
    Entry* operator->() {
      return entry_;
    }

    //! @brief 重導至\c std::pair<Key \c const&,\c Value&>&
    Entry& operator*() {
      return *entry_;
    }

    //! @brief same as \c same(e2)
    bool operator==(Element const& e2) const{
      return same(e2);
    }

    //! @brief same as \c !same(e2)
    bool operator!=(Element const& e2) const{
      return !same(e2);
    }
  };

  //! @brief constructor
  SplayTree(): root_(NULL) {
  }

  //! @brief constructor, 複製資料
  SplayTree(SplayTree const& tree2):
  root_(dup((Node*)(tree2.root_))) {
  }

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

  /*!
   * @brief 複製資料
   */
  SplayTree& copyFrom(SplayTree const& tree2) {
    clear(root_);
    root_ = dup((Node*)(tree2.root_));
    return *this;
  }

  /*!
   * @brief 將資料都丟到 \c tree2 身上, 並且清空自己
   */
  void moveTo(SplayTree* tree2) {
    tree2->clear();
    tree2->root_ = root_;
    root_ = NULL;
  }

  /*!
   * @brief 找出第一個(最小的) Element且 \c k <= 它的 Key, 並且回傳之.
   *
   * 找不到的話回傳 \c this->end()
   */
  Element lowerBound(Key const& key) const {
    splay(findKey(root_, key));
    if (root_ == NULL || !(root_->key_ < key)) return Element(root_);
    if (root_->child_[1] == NULL) return Element(NULL);
    splay(findMinMax(root_->child_[1], true));
    return Element(root_);
  }

  /*!
   * @brief 找出第一個(最小的) Element且 \c k < 它的 Key, 並且回傳之.
   *
   * 找不到的話回傳 \c this->end()
   */
  Element upperBound(Key const& key) const {
    splay(findKey(root_, key));
    if (root_ == NULL || key < root_->key_) return Element(root_);
    if (root_->child_[1] == NULL) return Element(NULL);
    splay(findMinMax(root_->child_[1], true));
    return Element(root_);
  }

  /*!
   * @brief 找出第一個(最小的) Element且 \c k >= 它的 Key, 並且回傳之.
   *
   * 找不到的話回傳 \c this->end()
   */
  Element rLowerBound(Key const& key) const {
    splay(findKey(root_, key));
    if (root_ == NULL || !(key < root_->key_)) return Element(root_);
    if (root_->child_[0] == NULL) return Element(NULL);
    splay(findMinMax(root_->child_[0], false));
    return Element(root_);
  }

  /*!
   * @brief 找出第一個(最小的) Element且 \c k > 它的 Key, 並且回傳之.
   *
   * 找不到的話回傳 \c this->end()
   */
  Element rUpperBound(Key const& key) const {
    splay(findKey(root_, key));
    if (root_ == NULL || root_->key_ < key) return Element(root_);
    if (root_->child_[0] == NULL) return Element(NULL);
    splay(findMinMax(root_->child_[0], false));
    return Element(root_);
  }

  /*!
   * @brief 找出 Key= \c k 的Elemenet 並回傳. 找不到的話回傳 \c this->end()
   */
  Element find(Key const& key) const {
    splay(findKey(root_, key));
    if (root_ != NULL && !(key < root_->key_) && !(root_->key_ < key)) {
      return Element(root_);
    }
    return Element(NULL);
  }

  /*!
   * @brief 將Elements依照Key由小到大排序, 回傳第 \c ord 個Element (由0算起).
   *
   * 其中如果 \c ord>N-1, 則會回傳 \c this->last()
   */
  Element order(size_t order) const {
    if (root_ == NULL || order >= root_->size_) return Element(NULL);
    splay(findOrder(root_, order + 1));
    return Element(root_);
  }

  /*!
   * @brief 回傳Key最小的Element, 如果SplayTree為空, 則回傳 \c this->end()
   */
  Element first() const {
    splay(findMinMax(root_, true));
    return Element(root_);
  }

  /*!
   * @brief 回傳Key最大的Element, 如果SplayTree為空, 則回傳 \c this->end()
   */
  Element last() const {
    splay(findMinMax(root_, false));
    return Element(root_);
  }

  /*!
   * @brief 回傳一個指向NULL的Element,
   * 
   * 以供 \c find ,\c order ,\c first ,\c last 等判斷是否有找到相對應的Element
   */
  Element end() const {
    return Element(NULL);
  }

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

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

  /*!
   * @brief 清空
   */
  void clear() {
    clear(root_);
    root_ = NULL;
  }

  /*!
   * @brief 插入一組\c (Key ---> \c Value)
   * 
   * 檢查是否已有Element的Key 為 \c key, 若有則回傳 \c false , 否則將
   * 一個 (Key -> Value) = (\c key -> \c value)的Element加入, 並回傳 \c true
   */
  bool insert(Key const& key, Value const& value) {
    if (root_ == NULL) {
      root_ = new Node(key, value);
    }
    else {
      Node* parent = (Node*)findKey(root_, key);
      if (!(parent->key_ < key) && !(key < parent->key_)) {
        splay(parent);
        return false;
      }
      Node* new_node = new Node(key, value);
      connect(parent, (parent->key_ < key ? 1 : 0), new_node);
      parent->syncUp();
      splay(new_node);
    }
    return true;
  }

  /*!
   * @brief 刪除一組資料
   *
   * 檢查是否已有Element的Key 為 \c key, 若有則刪除之, 並回傳 \c true,
   * 否則則回傳 \c false
   */
  bool erase(Key const& key) {
    if (root_ == NULL) return false;
    Node* body = (Node*)findKey(root_, key);
    if (body->key_ < key || key < body->key_) {
      splay(body);
      return false;
    }
    Node* ghost;
    if (body->child_[1] == NULL) {
      ghost = body->child_[0];
      if (ghost != NULL) ghost->syncDown();
    }
    else {
      ghost = (Node*)findMinMax(body->child_[1], true);
      connect(ghost, 0, body->child_[0]);
      if (ghost != body->child_[1]) {
        connect(ghost->parent_, 0, ghost->child_[1]);
        connect(ghost, 1, body->child_[1]);
        for (Node* a = ghost->parent_; a != ghost; a = a->parent_)
          a->syncUp();
      }
      ghost->syncUp();
    }
    Node* parent = body->parent_;
    connect(parent, parent != NULL && parent->child_[0] == body ? 0 : 1, ghost);
    delete body;
    splay(ghost != NULL ? ghost : parent);
    return true;
  }

  /*!
   * @brief 將所有Element的Key同加上 \c delta
   */
  void keyOffset(Key const& delta) {
    if (root_ != NULL) {
      root_->keyOffset(delta);
    }
  }

  /*!
   * @brief 將\c tree2 清空, 再將所有Key > \c upper_bound 的Element都丟過去
   */
  void splitOut(Key const& upper_bound, SplayTree* right) {
    right->clear();
    if (rLowerBound(upper_bound) != end()) {
      split(root_, &root_, &(right->root_));
    }
    else {
      right->root_ = root_;
      root_ = NULL;
    }
  }

  /*!
   * @brief 合併
   *
   * 檢查是否自己中的 Key 都小於 \c tree2 中的Key, 是的話把 \c tree2`
   * 中的 Element 都搬到自己這, 同時清空 \c tree2 , 否則回傳 \c false
   */
  bool mergeAfter(SplayTree* tree2) {
    if (root_ == NULL || tree2->root_ == NULL ||
        last()->first < tree2->first()->first) {
      root_ = merge(root_, tree2->root_);
      tree2->root_ = NULL;
      return true;
    }
    return false;
  }

  /*!
   * @brief 合併
   *
   * 檢查是否自己中的 Key 都小於 \c tree2 中的Key, 或是完全相反, 
   * 是的話把 \c tree2`中的 Element 都搬到自己這,
   * 同時清空 \c tree2 , 否則回傳 \c false
   */
  bool merge(SplayTree* tree2) {
    if (root_ == NULL || tree2->root_ == NULL ||
        last()->first < tree2->first()->first) {
      root_ = merge(root_, tree2->root_);
    }
    else if(tree2->last()->first < first()->first) {
      root_ = merge(tree2->root_, root_);
    }
    else {
      return false;
    }
    tree2->root_ = NULL;
    return true;
  }
  
  /*!
   * @brief 就像\c stl::map::operator[]
   *
   * 會先檢查是否已有Element的Key 為 \c key, 若有則回傳相對應的Value的Reference
   * 否則先執行 \c insert(key,Value()) 再回傳相對應的Reference
   */
  Value& operator[](Key const& key) {
    if (find(key) == end()) insert(key, Value());
    return root_->value_;
  }

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

/*!
 * @brief
 *
 * 基本上跟SplayTree一樣, 不過這邊結合線段樹, 多了區間操作
 * (線段樹相關operator定義請見 \c SegmentTree )
 *
 * Template Class Operators Request
 * --------------------------------
 *
 * |const?|Typename|Operator   | Parameters   |Return Type | Description       |
 * |-----:|:------:|----------:|:-------------|:----------:|:------------------|
 * |const |Key     |operator+  |(Key    \c k) | Key        |相加               |
 * |const |Key     |operator<  |(Key    \c k) | bool       |大小比較           |
 * |      |Key     |operator=  |(Key    \c k) | Key        |copy oper          |
 * |      |Key     |Key        |(int    \c n) |            |構子,\c n 永遠是0  |
 * |      |Value   | Value     |(           ) |            |建構子             |
 *
 * @note:
 *   -假設現在有兩個SplayTree `A` 和 `B`,  則:
 *        -執行 `B.moveTo(&A)` 後 `B` 會變成空的, `A` 原本擁有的資料也會覆蓋掉
 *        -行 `A.merge(&B)` 或 `A.mergeAfter(&B)` 後
 *         如果檢查發現確實可以merge, 則之後 `B` 會變成空的
 *
 * @author cat_leopard
 */
template<class Key, class Value>
class SplayTree_Range {
private:
  struct Node {
    Value  valueOffset_;
    Value        range_;
    Key            key_;
    Key      keyOffset_;
    Value        value_;
    bool          same_;
    size_t        size_;
    Node*       parent_;
    Node*        child_[2];
    
    Node(Key const& key, Value const& value):
    valueOffset_(0), range_(value),
    key_(key), keyOffset_(0), value_(value) {
      same_     = false;
      size_     = 1;
      parent_   = NULL;
      child_[0] = NULL;
      child_[1] = NULL;
    }
    //
    void keyOffset(Key const& delta) {
      key_       = key_       + delta;
      keyOffset_ = keyOffset_ + delta;
    }
    void valueUpdate(Value const& delta, bool over) {
      if(over) {
        value_       = delta * size_;
        valueOffset_ = delta;
        range_       = delta * size_;
        same_        = true;
      }
      else {
        value_       = value_       + delta * size_;
        valueOffset_ = valueOffset_ + delta;
        range_       = range_       + delta * size_;
      }
    }
    void syncDown() const {
      for (size_t i = 0; i < 2; i++) {
        if (child_[i] == NULL) continue;
        child_[i]->keyOffset(keyOffset_);
        child_[i]->valueUpdate(valueOffset_, same_);
      }
      ((Node*)this)->keyOffset_ = Key(0);
      ((Node*)this)->valueOffset_ = Value(0);
      ((Node*)this)->same_        = false;
    }
    void syncUp() const {
      ((Node*)this)->size_ = 1;
      Value* v[3] = {&(((Node*)this)->value_), NULL, NULL};
      size_t vct = 1;
      for (size_t i = 0; i < 2; i++) {
        if (child_[i] == NULL) continue;
        ((Node*)this)->size_ += child_[i]->size_;
        v[vct++] = &(child_[i]->range_);
      }
      if     (vct == 1) ((Node*)this)->range_ = (*v[0]);
      else if(vct == 2) ((Node*)this)->range_ = (*v[0]) | (*v[1]);
      else              ((Node*)this)->range_ = (*v[0]) | (*v[1]) | (*v[2]);
    }
  };

  Node* root_;

  //! @brief 指定左子or右子, 連接parent<--->child
  void connect(Node const* parent, size_t left_right, Node const* child) const {
    Node* p = (Node*)parent;
    Node* c = (Node*)child;
    if (p != NULL) p->child_[left_right] = c;
    if (c != NULL) c->parent_            = p;
  }

  //! @brief 一路往上轉
  Node const* splay(Node const* node) const {
    if (node != NULL && node->parent_ != NULL) {
      for (const Node *g_grand, *grand, *parent, *child = node; ; ) {
        g_grand = (grand = parent = child->parent_)->parent_;
        size_t pc = (parent->child_[0] == child ? 0 : 1);
        connect(parent,  pc, child->child_[!pc]);
        connect(child , !pc, parent);
        if (g_grand != NULL) {
          g_grand = (grand = g_grand)->parent_;
          size_t gp = (grand->child_[0] == parent ? 0 : 1);
          Node const* who = (pc == gp ? parent : child);
          connect(grand,  gp, who->child_[!gp]);
          connect(who  , !gp, grand);
          grand->syncUp();
        }
        parent->syncUp();
        child ->syncUp();
        if (g_grand == NULL) {
          connect(NULL, 0, child);
          break;
        }
        connect(g_grand, (g_grand->child_[0] == grand ?  0 : 1), child);
      }
    }
    return (((SplayTree_Range*)this)->root_ = (Node*)node);
  }

  void clear(Node* node) {
    if (node == NULL) return ;
    clear(node->child_[0]);
    clear(node->child_[1]);
    delete node;
  }

  Node* dup(Node* node2) {
    if (node2 == NULL) return NULL;
    node2->syncDown();
    Node* node = new Node(node2->key_, node2->value_);
    connect(node, 0, dup(node2->child_[0]));
    connect(node, 1, dup(node2->child_[1]));
    node->syncUp();
    return node;
  }

  Node const* findKey(Node const* node, Key const& key) const {
    Node const* ret = node;
    while (node != NULL) {
      node->syncDown();
      ret = node;
      if (!(key < node->key_)) {
        if (!(node->key_< key)) break;
        node = node->child_[1];
      }
      else {
        node = node->child_[0];
      }
    }
    return ret;
  }
  Node const* findMinMax(Node const* node, bool minimum) const {
    Node const* ret = node;
    for (int i = minimum ? 0 : 1; node != NULL; node = node->child_[i]) {
      node->syncDown();
      ret = node;
    }
    return ret;
  }
  Node const* findOrder(Node const* node, size_t order) const {
    Node const* ret = node;
    while (node != NULL) {
      node->syncDown();
      ret = node;
      size_t ord = 1 + (node->child_[0] == NULL ? 0 : node->child_[0]->size_);
      if     (ord == order) return ret;
      else if(ord <  order){ node = node->child_[1]; order -= ord; }
      else                 { node = node->child_[0];               }
    }
    return ret;
  }

  void split(Node* root, Node** left, Node** right) {
    if (root == NULL) { *left = NULL; *right = NULL; return ; }
    root->syncDown();
    *left  = root;
    *right = root->child_[1];
    if (*right != NULL) {
      (*left )->child_[1] = NULL;
      (*right)->parent_   = NULL;
      (*left )->syncUp();
    }
  }
  Node* merge(Node* left, Node* right) {
    if (left  == NULL) return right;
    if (right == NULL) return left ;
    left->syncDown();
    connect(left, 1, right);
    left->syncUp();
    return left;
  }
public:
  /*!
   * @brief 類似 \c stl 的 \c iterator ,不過這邊叫做\c Element
   *
   * 用來當作回傳資料的媒介
   */
  class Element{
  private:
    typedef std::pair<Key const&, Value&> Entry;
    Entry* entry_;
    Node *  node_;
    //
    void reset(Node* node) {
      node_ = node;
      delete entry_;
      entry_ = (node == NULL ? NULL : new Entry(node->key_, node->value_));
    }
  public:
    Element(): entry_(NULL), node_(NULL) {
    }
    Element(Node* node): entry_(NULL), node_(NULL) {
      reset(node);
    }
    Element(Element const& element2): entry_(NULL), node_(NULL) {
      reset(element2.node_);
    }
    ~Element(){
      delete entry_;
    }

    //! @brief 複製資料
    Element& copyFrom(Element const& e) {
      reset(e.node_);
      return *this;
    }

    //! @brief 比對兩者是否為指向同一個Entry
    bool same(Element const& e2) const {
      return (node_ == e2.node_);
    }

    //! @brief same as copyFrom
    Element& operator=(Element const& e2) {
      return copyFrom(e2);
    }

    //! @brief 重導至\c std::pair<Key \c const&,\c Value&>*
    Entry* operator->() {
      return entry_;
    }

    //! @brief 重導至\c std::pair<Key \c const&,\c Value&>&
    Entry& operator*() {
      return *entry_;
    }

    //! @brief same as \c same(e2)
    bool operator==(Element const& e2) const{
      return same(e2);
    }

    //! @brief same as \c !same(e2)
    bool operator!=(Element const& e2) const{
      return !same(e2);
    }
  };

  //! @brief constructor
  SplayTree_Range(): root_(NULL) {
  }

  //! @brief constructor, 複製資料
  SplayTree_Range(SplayTree_Range const& tree2):
  root_(dup((Node*)(tree2.root_))) {
  }

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

  /*!
   * @brief 複製資料
   */
  SplayTree_Range& copyFrom(SplayTree_Range const& tree2) {
    clear(root_);
    root_ = dup((Node*)(tree2.root_));
    return *this;
  }

  /*!
   * @brief 將資料都丟到 \c tree2 身上, 並且清空自己
   */
  void moveTo(SplayTree_Range* tree2) {
    tree2->clear();
    tree2->root_ = root_;
    root_ = NULL;
  }

  /*!
   * @brief 找出第一個(最小的) Element且 \c k <= 它的 Key, 並且回傳之.
   *
   * 找不到的話回傳 \c this->end()
   */
  Element lowerBound(Key const& key) const {
    splay(findKey(root_, key));
    if (root_ == NULL || !(root_->key_ < key)) return Element(root_);
    if (root_->child_[1] == NULL) return Element(NULL);
    splay(findMinMax(root_->child_[1], true));
    return Element(root_);
  }

  /*!
   * @brief 找出第一個(最小的) Element且 \c k < 它的 Key, 並且回傳之.
   *
   * 找不到的話回傳 \c this->end()
   */
  Element upperBound(Key const& key) const {
    splay(findKey(root_, key));
    if (root_ == NULL || key < root_->key_) return Element(root_);
    if (root_->child_[1] == NULL) return Element(NULL);
    splay(findMinMax(root_->child_[1], true));
    return Element(root_);
  }

  /*!
   * @brief 找出第一個(最小的) Element且 \c k >= 它的 Key, 並且回傳之.
   *
   * 找不到的話回傳 \c this->end()
   */
  Element rLowerBound(Key const& key) const {
    splay(findKey(root_, key));
    if (root_ == NULL || !(key < root_->key_)) return Element(root_);
    if (root_->child_[0] == NULL) return Element(NULL);
    splay(findMinMax(root_->child_[0], false));
    return Element(root_);
  }

  /*!
   * @brief 找出第一個(最小的) Element且 \c k > 它的 Key, 並且回傳之.
   *
   * 找不到的話回傳 \c this->end()
   */
  Element rUpperBound(Key const& key) const {
    splay(findKey(root_, key));
    if (root_ == NULL || root_->key_ < key) return Element(root_);
    if (root_->child_[0] == NULL) return Element(NULL);
    splay(findMinMax(root_->child_[0], false));
    return Element(root_);
  }

  /*!
   * @brief 找出 Key= \c k 的Elemenet 並回傳. 找不到的話回傳 \c this->end()
   */
  Element find(Key const& key) const {
    splay(findKey(root_, key));
    if (root_ != NULL && !(key < root_->key_) && !(root_->key_ < key)) {
      return Element(root_);
    }
    return Element(NULL);
  }

  /*!
   * @brief 將Elements依照Key由小到大排序, 回傳第 \c ord 個Element (由0算起).
   *
   * 其中如果 \c ord>N-1, 則會回傳 \c this->last()
   */
  Element order(size_t order) const {
    if (root_ == NULL || order >= root_->size_) return Element(NULL);
    splay(findOrder(root_, order + 1));
    return Element(root_);
  }

  /*!
   * @brief 回傳Key最小的Element, 如果SplayTree為空, 則回傳 \c this->end()
   */
  Element first() const {
    splay(findMinMax(root_, true));
    return Element(root_);
  }

  /*!
   * @brief 回傳Key最大的Element, 如果SplayTree為空, 則回傳 \c this->end()
   */
  Element last() const {
    splay(findMinMax(root_, false));
    return Element(root_);
  }

  /*!
   * @brief 回傳一個指向NULL的Element,
   * 
   * 以供 \c find ,\c order ,\c first ,\c last 等判斷是否有找到相對應的Element
   */
  Element end() const {
    return Element(NULL);
  }

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

  /*!
   * @brief 回傳是否為空
   */
  bool empty() const{
    return (size() == 0);
  }
  
  /*!
   * @brief 查找
   *
   * 詢問目前整個range的值
   */
  Value query() const {
    if (root_ == NULL) return Value(0);
    return root_->range_;
  }

  /*!
   * @brief 查找
   *
   * 詢問給定range的值
   */
  Value query(Key const& first, Key const& last) const {
    SplayTree_Range* self = (SplayTree_Range*)this;
    Node* tmp;
    rUpperBound(first);
    self->split(self->root_, &tmp, &(self->root_));
    upperBound(last);
    Value ret(0);
    if (root_ != NULL && root_->child_[0] != NULL) {
      ret = root_->child_[0]->range_;
    }
    self->root_ = self->merge(tmp, self->root_);
    return ret;
  }

  /*!
   * @brief 清空
   */
  void clear() {
    clear(root_);
    root_ = NULL;
  }

  /*!
   * @brief 插入一組\c (Key ---> \c Value)
   * 
   * 檢查是否已有Element的Key 為 \c key, 若有則回傳 \c false , 否則將
   * 一個 (Key -> Value) = (\c key -> \c value)的Element加入, 並回傳 \c true
   */
  bool insert(Key const& key, Value const& value) {
    if (root_ == NULL) {
      root_ = new Node(key, value);
    }
    else {
      Node* parent = (Node*)findKey(root_, key);
      if (!(parent->key_ < key) && !(key < parent->key_)) {
        splay(parent);
        return false;
      }
      Node* new_node = new Node(key, value);
      connect(parent, (parent->key_ < key ? 1 : 0), new_node);
      parent->syncUp();
      splay(new_node);
    }
    return true;
  }

  /*!
   * @brief 刪除一組資料
   *
   * 檢查是否已有Element的Key 為 \c key, 若有則刪除之, 並回傳 \c true,
   * 否則則回傳 \c false
   */
  bool erase(Key const& key) {
    if (root_ == NULL) return false;
    Node* body = (Node*)findKey(root_, key);
    if (body->key_ < key || key < body->key_) {
      splay(body);
      return false;
    }
    Node* ghost;
    if (body->child_[1] == NULL) {
      ghost = body->child_[0];
      if (ghost != NULL) ghost->syncDown();
    }
    else {
      ghost = (Node*)findMinMax(body->child_[1], true);
      connect(ghost, 0, body->child_[0]);
      if (ghost != body->child_[1]) {
        connect(ghost->parent_, 0, ghost->child_[1]);
        connect(ghost, 1, body->child_[1]);
        for (Node* a = ghost->parent_; a != ghost; a = a->parent_)
          a->syncUp();
      }
      ghost->syncUp();
    }
    Node* parent = body->parent_;
    connect(parent, parent != NULL && parent->child_[0] == body ? 0 : 1, ghost);
    delete body;
    splay(ghost != NULL ? ghost : parent);
    return true;
  }

  /*!
   * @brief 將所有Element的Key同加上 \c delta
   */
  void keyOffset(Key const& delta) {
    if (root_ != NULL) {
      root_->keyOffset(delta);
    }
  }

  /*!
   * @brief 將所有Element的Value同加上 \c delta
   */
  void valueOffset(Value const& delta){
    if (root_ != NULL) {
      root_->valueUpdate(delta, false);
    }
  }

  /*!
   * @brief 將所有Element的Value全部設定成\c value
   */
  void valueOverride(Value const& value){
    if(root_ != NULL){
      root_->valueUpdate(value, true);
    }
  }

  /*!
   * @brief 將\c tree2 清空, 再將所有Key > \c upper_bound 的Element都丟過去
   */
  void splitOut(Key const& upper_bound, SplayTree_Range* right) {
    right->clear();
    if (rLowerBound(upper_bound) != end()) {
      split(root_, &root_, &(right->root_));
    }
    else {
      right->root_ = root_;
      root_ = NULL;
    }
  }

  /*!
   * @brief 合併
   *
   * 檢查是否自己中的 Key 都小於 \c tree2 中的Key, 是的話把 \c tree2`
   * 中的 Element 都搬到自己這, 同時清空 \c tree2 , 否則回傳 \c false
   */
  bool mergeAfter(SplayTree_Range* tree2) {
    if (root_ == NULL || tree2->root_ == NULL ||
        last()->first < tree2->first()->first) {
      root_ = merge(root_, tree2->root_);
      tree2->root_ = NULL;
      return true;
    }
    return false;
  }

  /*!
   * @brief 合併
   *
   * 檢查是否自己中的 Key 都小於 \c tree2 中的Key, 或是完全相反, 
   * 是的話把 \c tree2`中的 Element 都搬到自己這,
   * 同時清空 \c tree2 , 否則回傳 \c false
   */
  bool merge(SplayTree_Range* tree2) {
    if (root_ == NULL || tree2->root_ == NULL ||
        last()->first < tree2->first()->first) {
      root_ = merge(root_, tree2->root_);
    }
    else if(tree2->last()->first < first()->first) {
      root_ = merge(tree2->root_, root_);
    }
    else {
      return false;
    }
    tree2->root_ = NULL;
    return true;
  }
  
  /*!
   * @brief 就像\c stl::map::operator[]
   *
   * 會先檢查是否已有Element的Key 為 \c key, 若有則回傳相對應的Value的Reference
   * 否則先執行 \c insert(key,Value()) 再回傳相對應的Reference
   */
  Value& operator[](Key const& key) {
    if (find(key) == end()) insert(key, Value());
    return root_->value_;
  }

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

}

#endif // dsa_SplayTree_h__