path: root/meowpp/dsa/SplayTree_Range.hpp

#include "SplayTree_Range.h"


#include <cstdlib>

#include <utility>

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

namespace meow{
  ///////////////////////////// **# Node #** /////////////////////////
  //////////////////// **# Node -- Constructure #** //////////////////
  template<class Key, class Value>
  inline
  SplayTree_Range<Key, Value>::Node::Node(Key const& __key,
                                          Value const& __value):
  _key(__key), _keyOffset(0), _value(__value), _valueOffset(0), _range(__value){
    _same     = false;
    _size     = 1;
    _parent   = NULL;
    _child[0] = NULL;
    _child[1] = NULL;
  }
  ///////////////// **# Node -- Offset / Override #** ////////////////
  template<class Key, class Value>
  inline void
  SplayTree_Range<Key, Value>::Node::keyOffset(Key const& __delta){
    _key       = _key       + __delta;
    _keyOffset = _keyOffset + __delta;
  }
  template<class Key, class Value>
  inline void
  SplayTree_Range<Key, Value>::Node::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;
    }
  }
  //////////////////////// **# Node -- sync #** //////////////////////
  template<class Key, class Value>
  inline void
  SplayTree_Range<Key, Value>::Node::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;
  }
  template<class Key, class Value>
  inline void
  SplayTree_Range<Key, Value>::Node::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]);
  }
  ////////////////////////// **# SplayTree_Range #** ///////////////////////
  ///////////////////// **# connection, splay #** ////////////////////
  template<class Key, class Value>
  inline void
  SplayTree_Range<Key, Value>::connect(Node const* __parent,
                                       size_t __left_right,
                                       Node const* __child) const{
    Node* parent = (Node*)__parent;
    Node* child  = (Node*)__child;
    if(parent != NULL) parent->_child[__left_right] = child;
    if(child  != NULL) child ->_parent              = parent;
  }
  template<class Key, class Value>
  inline typename SplayTree_Range<Key, Value>::Node const*
  SplayTree_Range<Key, Value>::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);
  }
  ///////////////////////// **# clear, dup #** ///////////////////////
  template<class Key, class Value>
  inline void
  SplayTree_Range<Key, Value>::clear(Node* __node){
    if(__node == NULL) return ;
    clear(__node->_child[0]);
    clear(__node->_child[1]);
    delete __node;
  }
  template<class Key, class Value>
  inline typename SplayTree_Range<Key, Value>::Node*
  SplayTree_Range<Key, Value>::dup(Node* __node){
    if(__node == NULL) return NULL;
    __node->syncDown();
    Node* node = new Node(__node->_key, __node->_value);
    connect(node, 0, dup(__node->_child[0]));
    connect(node, 1, dup(__node->_child[1]));
    node->syncUp();
    return node;
  }
  /////////////////////////// **# find #** ///////////////////////////
  template<class Key, class Value>
  inline typename SplayTree_Range<Key, Value>::Node const*
  SplayTree_Range<Key, Value>::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;
  }
  template<class Key, class Value>
  inline typename SplayTree_Range<Key, Value>::Node const*
  SplayTree_Range<Key, Value>::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;
  }
  template<class Key, class Value>
  inline typename SplayTree_Range<Key, Value>::Node const*
  SplayTree_Range<Key, Value>::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;
  }
  /////////////////////// **# split, merge #** ///////////////////////
  template<class Key, class Value>
  inline void
  SplayTree_Range<Key, Value>::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();
    }
  }
  template<class Key, class Value>
  inline typename SplayTree_Range<Key, Value>::Node*
  SplayTree_Range<Key, Value>::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;
  }
  ///////////////////////// **# Element ##* //////////////////////////
  template<class Key, class Value>
  inline void SplayTree_Range<Key, Value>::Element::reset(Node* __node){
    _node = __node;
    delete _entry;
    if(__node == NULL) _entry = NULL;
    else               _entry = new Entry(__node->_key, __node->_value);
  }
  //
  template<class Key, class Value>
  inline
  SplayTree_Range<Key, Value>::Element::Element():
  _entry(NULL), _node(NULL){
  }
  template<class Key, class Value>
  inline
  SplayTree_Range<Key, Value>::Element::Element(Node* __node):
  _entry(NULL), _node(NULL){
    reset(__node);
  }
  template<class Key, class Value>
  inline
  SplayTree_Range<Key, Value>::Element::Element(Element const& __element2):
  _entry(NULL), _node(NULL){
    reset(__element2._node);
  }
  template<class Key, class Value>
  inline
  SplayTree_Range<Key, Value>::Element::~Element(){
    delete _entry;
  }
  template<class Key, class Value>
  inline typename SplayTree_Range<Key, Value>::Element&
  SplayTree_Range<Key, Value>::Element::operator=(Element const& __e2){
    reset(__e2._node);
    return *this;
  }
  //////////////////// **# Element operations #** ////////////////////
  template<class Key, class Value>
  inline typename SplayTree_Range<Key, Value>::Element::Entry*
  SplayTree_Range<Key, Value>::Element::operator->(){ return  _entry; }
  template<class Key, class Value>
  inline typename SplayTree_Range<Key, Value>::Element::Entry&
  SplayTree_Range<Key, Value>::Element::operator*(){ return *_entry; }
  //
  template<class Key, class Value>
  inline bool
  SplayTree_Range<Key, Value>::Element::operator==(Element const& __e2) const{
    return (_node == __e2._node);
  }
  template<class Key, class Value>
  inline bool
  SplayTree_Range<Key, Value>::Element::operator!=(Element const& __e2) const{
    return (_node != __e2._node);
  }
  /////// **# Splay tree constructure/destructure/copy oper #** //////
  template<class Key, class Value>
  inline
  SplayTree_Range<Key, Value>::SplayTree_Range(): _root(NULL){
  }
  template<class Key, class Value>
  inline
  SplayTree_Range<Key, Value>::SplayTree_Range(SplayTree_Range const& __tree2):
  _root(NULL){
    _root = dup((Node*)(__tree2._root));
  }
  template<class Key, class Value>
  inline
  SplayTree_Range<Key, Value>::~SplayTree_Range(){
    clear(_root);
  }
  template<class Key, class Value>
  inline SplayTree_Range<Key, Value>&
  SplayTree_Range<Key, Value>::operator=(SplayTree_Range const& __tree2){
    clear(_root);
    _root = dup((Node*)(__tree2._root));
    return *this;
  }
  template<class Key, class Value>
  inline void
  SplayTree_Range<Key, Value>::moveTo(SplayTree_Range* __tree2){
    __tree2->clear();
    __tree2->_root = _root;
    _root = NULL;
  }
  //////////////////////// **# Bounding #** //////////////////////////
  template<class Key, class Value>
  inline typename SplayTree_Range<Key, Value>::Element
  SplayTree_Range<Key, Value>::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);
  }
  template<class Key, class Value>
  inline typename SplayTree_Range<Key, Value>::Element
  SplayTree_Range<Key, Value>::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);
  }
  template<class Key, class Value>
  inline typename SplayTree_Range<Key, Value>::Element
  SplayTree_Range<Key, Value>::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);
  }
  template<class Key, class Value>
  inline typename SplayTree_Range<Key, Value>::Element
  SplayTree_Range<Key, Value>::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);
  }
  ////////////// **# find / order / first / last / end #** ////////////
  template<class Key, class Value>
  inline typename SplayTree_Range<Key, Value>::Element
  SplayTree_Range<Key, Value>::find(Key const& __key) const{
    splay(findKey(_root, __key));
    if(_root != NULL && !(__key < _root->_key) && !(_root->_key < __key)){
      return Element(_root);
    }
    return Element(NULL);
  }
  template<class Key, class Value>
  inline typename SplayTree_Range<Key, Value>::Element
  SplayTree_Range<Key, Value>::order(size_t __order) const{
    if(_root == NULL || __order >= _root->_size) return Element(NULL);
    splay(findOrder(_root, __order + 1));
    return Element(_root);
  }
  template<class Key, class Value>
  inline typename SplayTree_Range<Key, Value>::Element
  SplayTree_Range<Key, Value>::first() const{
    splay(findMinMax(_root, true));
    return Element(_root);
  }
  template<class Key, class Value>
  inline typename SplayTree_Range<Key, Value>::Element
  SplayTree_Range<Key, Value>::last() const{
    splay(findMinMax(_root, false));
    return Element(_root);
  }
  template<class Key, class Value>
  inline typename SplayTree_Range<Key, Value>::Element
  SplayTree_Range<Key, Value>::end() const{ return Element(NULL); }
  //////////////////// **# query, range query #** ////////////////////
  template<class Key, class Value>
  inline Value
  SplayTree_Range<Key, Value>::query() const{
    if(_root == NULL) return Value(0);
    return _root->_range;
  }
  template<class Key, class Value>
  inline Value
  SplayTree_Range<Key, 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;
  }
  //////////////////// **# size, empty, clear #** ////////////////////
  template<class Key, class Value>
  inline size_t SplayTree_Range<Key, Value>::size() const{
    return (_root == NULL ? 0 : _root->_size);
  }
  template<class Key, class Value>
  inline bool SplayTree_Range<Key, Value>::empty() const{
    return (size() == 0);
  }
  //
  template<class Key, class Value>
  inline void SplayTree_Range<Key, Value>::clear(){
    clear(_root);
    _root = NULL;
  }
  ////////////// **# insert, erase, keyOffset, oper[] #** ////////////
  template<class Key, class Value>
  inline bool SplayTree_Range<Key, Value>::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;
  }
  template<class Key, class Value>
  inline bool SplayTree_Range<Key, Value>::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;
  }
  template<class Key, class Value>
  inline void SplayTree_Range<Key, Value>::keyOffset(Key const& __delta){
    if(_root != NULL){
      _root->keyOffset(__delta);
    }
  }
  template<class Key, class Value>
  inline void SplayTree_Range<Key, Value>::valueOffset(Value const& __delta){
    if(_root != NULL){
      _root->valueUpdate(__delta, false);
    }
  }
  template<class Key, class Value>
  inline void SplayTree_Range<Key, Value>::valueOverride(Value const& __value){
    if(_root != NULL){
      _root->valueUpdate(__value, true);
    }
  }
  template<class Key, class Value>
  inline Value&
  SplayTree_Range<Key, Value>::operator[](Key const& __key){
    if(find(__key) == end()) insert(__key, Value());
    return _root->_value;
  }
  /////////////////////// **# split, merge #** ///////////////////////
  template<class Key, class Value>
  inline void
  SplayTree_Range<Key, Value>::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;
    }
  }
  template<class Key, class Value>
  inline bool
  SplayTree_Range<Key, Value>::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;
  }
  template<class Key, class Value>
  inline bool
  SplayTree_Range<Key, Value>::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;
  }
}