SplayTree.h

Go to the documentation of this file.

#ifndef   dsa_SplayTree_h__
#define   dsa_SplayTree_h__

#include <cstdlib>
#include <utility>

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

namespace meow {

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_;

  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;
  }

  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:
  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_;
    }

    Element& copyFrom(Element const& e) {
      reset(e.node_);
      return *this;
    }

    bool same(Element const& e2) const {
      return (node_ == e2.node_);
    }

    Element& operator=(Element const& e2) {
      return copyFrom(e2);
    }

    Entry* operator->() {
      return entry_;
    }

    Entry& operator*() {
      return *entry_;
    }

    bool operator==(Element const& e2) const{
      return same(e2);
    }

    bool operator!=(Element const& e2) const{
      return !same(e2);
    }
  };

  SplayTree(): root_(NULL) {
  }

  SplayTree(SplayTree const& tree2):
  root_(dup((Node*)(tree2.root_))) {
  }

  ~SplayTree(){
    clear(root_);
  }

  SplayTree& copyFrom(SplayTree const& tree2) {
    clear(root_);
    root_ = dup((Node*)(tree2.root_));
    return *this;
  }

  void moveTo(SplayTree* tree2) {
    tree2->clear();
    tree2->root_ = root_;
    root_ = NULL;
  }

  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_);
  }

  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_);
  }

  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_);
  }

  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_);
  }

  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);
  }

  Element order(size_t order) const {
    if (root_ == NULL || order >= root_->size_) return Element(NULL);
    splay(findOrder(root_, order + 1));
    return Element(root_);
  }

  Element first() const {
    splay(findMinMax(root_, true));
    return Element(root_);
  }

  Element last() const {
    splay(findMinMax(root_, false));
    return Element(root_);
  }

  Element end() const {
    return Element(NULL);
  }

  size_t size() const {
    return (root_ == NULL ? 0 : root_->size_);
  }

  bool empty() const{
    return (size() == 0);
  }

  void clear() {
    clear(root_);
    root_ = NULL;
  }

  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;
  }

  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;
  }

  void keyOffset(Key const& delta) {
    if (root_ != NULL) {
      root_->keyOffset(delta);
    }
  }

  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;
    }
  }

  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;
  }

  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;
  }

  Value& operator[](Key const& key) {
    if (find(key) == end()) insert(key, Value());
    return root_->value_;
  }

  SplayTree& operator=(SplayTree const& tree2) {
    return copyFrom(tree2);
  }
};

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_;

  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;
  }

  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:
  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_;
    }

    Element& copyFrom(Element const& e) {
      reset(e.node_);
      return *this;
    }

    bool same(Element const& e2) const {
      return (node_ == e2.node_);
    }

    Element& operator=(Element const& e2) {
      return copyFrom(e2);
    }

    Entry* operator->() {
      return entry_;
    }

    Entry& operator*() {
      return *entry_;
    }

    bool operator==(Element const& e2) const{
      return same(e2);
    }

    bool operator!=(Element const& e2) const{
      return !same(e2);
    }
  };

  SplayTree_Range(): root_(NULL) {
  }

  SplayTree_Range(SplayTree_Range const& tree2):
  root_(dup((Node*)(tree2.root_))) {
  }

  ~SplayTree_Range() {
    clear(root_);
  }

  SplayTree_Range& copyFrom(SplayTree_Range const& tree2) {
    clear(root_);
    root_ = dup((Node*)(tree2.root_));
    return *this;
  }

  void moveTo(SplayTree_Range* tree2) {
    tree2->clear();
    tree2->root_ = root_;
    root_ = NULL;
  }

  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_);
  }

  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_);
  }

  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_);
  }

  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_);
  }

  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);
  }

  Element order(size_t order) const {
    if (root_ == NULL || order >= root_->size_) return Element(NULL);
    splay(findOrder(root_, order + 1));
    return Element(root_);
  }

  Element first() const {
    splay(findMinMax(root_, true));
    return Element(root_);
  }

  Element last() const {
    splay(findMinMax(root_, false));
    return Element(root_);
  }

  Element end() const {
    return Element(NULL);
  }

  size_t size() const {
    return (root_ == NULL ? 0 : root_->size_);
  }

  bool empty() const{
    return (size() == 0);
  }

  Value query() const {
    if (root_ == NULL) return Value(0);
    return root_->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;
  }

  void clear() {
    clear(root_);
    root_ = NULL;
  }

  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;
  }

  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;
  }

  void keyOffset(Key const& delta) {
    if (root_ != NULL) {
      root_->keyOffset(delta);
    }
  }

  void valueOffset(Value const& delta){
    if (root_ != NULL) {
      root_->valueUpdate(delta, false);
    }
  }

  void valueOverride(Value const& value){
    if(root_ != NULL){
      root_->valueUpdate(value, true);
    }
  }

  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;
    }
  }

  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;
  }

  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;
  }

  Value& operator[](Key const& key) {
    if (find(key) == end()) insert(key, Value());
    return root_->value_;
  }

  SplayTree_Range& operator=(SplayTree_Range const& tree2){
    return copyFrom(tree2);
  }
};

}

#endif // dsa_SplayTree_h__