splay max height every f(log n, log^2 n, sqrt(n)) splay poc

splay max height.cpp

#include <bits/stdc++.h>
using namespace std;

int rotate_count;

template<typename T>
struct node{
    node *l, *r, *p; int sz, h; T v;
    node() : node(T(0)) {}
    node(T v) : l(nullptr), r(nullptr), p(nullptr), sz(1), h(1), v(v) {}
    bool is_left() const { return this == p->l; }
    bool is_root() const { return p == nullptr; }
    void update(){
        sz = 1 + (l ? l->sz : 0) + (r ? r->sz : 0);
        h = max(l ? l->h : 0, r ? r->h : 0) + 1;
    }
    void push(){ /* use if lazy propagation */ }
    void rotate(){
        rotate_count++;
        p->push(); push();
        if(is_left()) r && (r->p = p), p->l = r, r = p;
        else l && (l->p = p), p->r = l, l = p;
        if(p->p) (p->is_left()? p->p->l : p->p->r) = this;
        auto *t = p; p = t->p; t->p = this;
        t->update(); update();
    }
};

template<typename T>
class base_splay_tree{
public:
    node<T> *root;
    base_splay_tree() : base_splay_tree(vector<T>()) {}
    base_splay_tree(vector<T> v){
        root = new node<T>();
        v.insert(v.begin(), T(0));
        v.push_back(T(0));
        root = build(v, 0, (int)v.size()-1);
    }
    node<T>* build(const vector<T> &v, int l, int r){
        if(l > r) return nullptr;
        int m = (l + r) / 2;
        auto x = new node<T>(v[m]);
        x->l = build(v, l, m-1); if(x->l) x->l->p = x;
        x->r = build(v, m+1, r); if(x->r) x->r->p = x;
        x->update();
        return x;
    }
    node<T>* internal_splay(node<T> *x, node<T> *g=nullptr){
        for(g || (root = x); x->p != g; x->rotate()){
            if(!x->p->is_root()) x->p->p->push();
            x->p->push(); x->push();
            if(x->p->p != g) (x->is_left() != x->p->is_left() ? x : x->p)->rotate();
        }
        x->push(); return x;
    }
    node<T>* splay(node<T> *x, node<T> *g=nullptr){
        if(g) internal_splay(g);
        return internal_splay(x, g);
    }
    node<T>* insert_prev_of_root(T v){
        auto x = new node<T>(v), l = root->l;
        x->l = l; l->p = x; x->update();
        root->l = x; x->p = root; root->update();
        return splay(x);
    }
    node<T>* insert_next_of_root(T v){
        auto x = new node<T>(v), r = root->r;
        x->r = r; r->p = x; x->update();
        root->r = x; x->p = root; root->update();
        return splay(x);
    }
    node<T>* insert_empty_tree(T v){
        if(root->l != nullptr) root = root->l;
        return insert_next_of_root(v);
    }
    node<T>* insert_before(node<T> *nxt, T v){
        if(root->sz == 2) return insert_empty_tree(v);
        splay(nxt); return insert_prev_of_root(v);
    }
    node<T>* insert_after(node<T> *prv, T v){
        if(root->sz == 2) return insert_empty_tree(v);
        splay(prv); return insert_next_of_root(v);
    }
    void erase(int v){
        if(kth(v) == nullptr) return;
        auto p = root;
        if(p->l && p->r){
            root = p->l; root->p = nullptr;
            auto x = root;
            while(x->r) x = x->r;
            x->r = p->r; p->r->p = x;
            x->update(); splay(x);
            delete p;
        }
        else if(p->l){
            root = p->l; root->p = nullptr;
            delete p;
        }
        else if(p->r){
            root = p->r; root->p = nullptr;
            delete p;
        }
        else assert(false);
    }
    int order_of_node(node<T> *x){
        splay(x); return x->l->sz;
    }
    node<T>* kth(int k){
        for(auto x=root; x; x=x->r){
            for(; x->push(), x->l && x->l->sz > k; x=x->l);
            if(x->l) k -= x->l->sz;
            if(!k--) return splay(x);
        }
        return nullptr;
    }
    node<T>* gather_range(int s, int e){
        auto t = kth(e+1);
        return splay(t, kth(s-1))->l;
    }
    void erase_range(int s, int e){
        auto x = gather_range(s, e), p = x->p;
        p->l = nullptr; p->update(); p->p->update();
        delete x;
    }
    void internal_dfs(node<T> *x, vector<T> &out){
        if(x->l) internal_dfs(x->l, out);
        if(x->v) out.push_back(x->v);
        if(x->r) internal_dfs(x->r, out);
    }
    vector<int> inorder(){
        vector<int> res;
        internal_dfs(root, res);
        return res;
    }
    int max_height(node<T> *x, int dep){
        int res = dep;
        if(x->l) res = max(res, max_height(x->l, dep+1));
        if(x->r) res = max(res, max_height(x->r, dep+1));
        return res;
    }
    int max_height(){ return max_height(root, 1); }
};

template<typename T, class F>
class splay_tree_test : public base_splay_tree<T> {
public:
    int total_splay, cnt, random_pick;
    F wait_func;
    splay_tree_test() : total_splay(0), cnt(0), random_pick(1) { }
    void splay_max() {
        node<T>* x = this->root;
        while(x->l || x->r) {
            if(x->l && x->l->h+1==x->h) x=x->l;
            else x=x->r;
        }
        this->internal_splay(x);
    }
    node<T>* splay(node<T> *x, node<T> *g=nullptr){
        if(++cnt == wait_func(++total_splay)){
            splay_max();
            cnt = 0;
            total_splay = this->root->sz;
        }
        if(g) this->internal_splay(g);
        return this->internal_splay(x, g);
    }
    node<T>* insert_before(node<T> *nxt, T v){
        if(this->root->sz == 2) return this->insert_empty_tree(v);
        splay(nxt); return this->insert_prev_of_root(v);
    }
    node<T>* insert_after(node<T> *prv, T v){
        if(this->root->sz == 2) return this->insert_empty_tree(v);
        splay(prv); return this->insert_next_of_root(v);
    }
    void erase(int v){
        if(this->kth(v) == nullptr) return;
        auto p = this->root;
        if(p->l && p->r){
            this->root = p->l; this->root->p = nullptr;
            auto x = this->root;
            while(x->r) x = x->r;
            x->r = p->r; p->r->p = x;
            x->update(); splay(x);
            delete p;
        }
        else if(p->l){
            this->root = p->l; this->root->p = nullptr;
            delete p;
        }
        else if(p->r){
            this->root = p->r; this->root->p = nullptr;
            delete p;
        }
        else assert(false);
    }
    int order_of_node(node<T> *x){
        splay(x); return x->l->sz;
    }
    void erase_range(int s, int e){
        auto x = this->gather_range(s, e), p = x->p;
        p->l = nullptr; p->update(); p->p->update();
        delete x;
    }
};

vector<pair<int,int>> Parse(){
    ifstream in("./editing-trace.json");
    vector<pair<int,int>> res;

    string s;
    while(getline(in, s)){
        int l = 0, r = (int)s.size() - 1;
        while(l <= r && isspace(s[l])) l++;
        while(l <= r && (isspace(s[r]) || s[r] == ',')) r--;
        s = s.substr(l, max(0, r-l+1));
        if(s.empty() || s[0] != '[' || s.back() != ']') continue;
        for(auto &i : s) if(!isdigit(i)) i = ' ';

        stringstream ss(s);
        int a, b; ss >> a >> b;
        res.emplace_back(a, b?2:0);
    }
    return res;
}

struct test_result{
    string test_name;
    int max_height;
    int max_rotate;
    int sum_rotate;
};

template<typename T, class F>
test_result Test(string test_name, splay_tree_test<T,F> &tree, const vector<pair<int,int>> &data) {
    rotate_count = 0;
    int mx_h = 0, mx_rot = 0;
    for(auto [pos, op] : data) {
        int prv = rotate_count;
        if(op == 0) {
            tree.insert_after(tree.kth(pos), 0);
        } else if(op == 1) {
            tree.order_of_node(tree.kth(pos));
        } else if(op == 2) {
            tree.erase(pos + 1);
        }

        mx_h = max(mx_h, tree.root->h);
        mx_rot = max(mx_rot, rotate_count - prv);
    }
    return {test_name, mx_h, mx_rot, rotate_count};
}

test_result EditTraceTest(const vector<pair<int,int>> &data){
    base_splay_tree<int> T;
    rotate_count = 0;
    int mx_h = 0, mx_rot = 0;

    for(auto [pos,val] : data){
        int prv = rotate_count;
        if(val == 0) T.insert_after(T.kth(pos), 0);
        else if(val == 1) T.order_of_node(T.kth(pos));
        else if(val == 2) T.erase(pos + 1);
        mx_h = max(mx_h, T.root->h);
        mx_rot = max(mx_rot, rotate_count - prv);
    }

    return {"default", mx_h, mx_rot, rotate_count};
}

// log n, log^2 n, n^(1/3), sqrt(n), n^(2/3)
struct P1 { int operator() (int x) {return __lg(x);} };
struct P2 { int operator() (int x) {return __lg(x)*__lg(x);} };
struct P3 { int operator() (int x) {return __lg(x)*__lg(x)*__lg(x);} };
struct P4 { int operator() (int x) {return pow(x, 1.0/3);} };
struct P5 { int operator() (int x) {return sqrt(x);} };
struct P6 { int operator() (int x) {return pow(x, 2.0/3);} };

ostream& operator<<(ostream &os, const test_result &res) {
    return cout << res.test_name << " : " << res.max_height << ' ' << res.max_rotate << ' ' << res.sum_rotate;
}

void TestAll(string data_name, const vector<pair<int,int>> &data) {
    cout << data_name << "\n";

    int ins = 0, del = 0, sz = 0, mx_sz = 0, se = 0;
    for(auto [pos,val] : data){
        if(val == 0) ins++, sz++;
        else if(val == 1) se++;
        else if(val == 2) del++, sz--;
        mx_sz = max(mx_sz, sz);
    }

    cout << "number of operations: " << data.size() << '\n' ;
    cout << "number of insert: " << ins << "\n";
    cout << "number of search: " << se << '\n';
    cout << "number of erase: " << del << '\n';
    cout << "maximum tree size: " << mx_sz << '\n';
    
    auto default_res = EditTraceTest(data);
    cout << fixed << setprecision(2) << default_res.test_name << "\t:\t" << default_res.max_height << '\t' << default_res.max_rotate << '\t' << default_res.sum_rotate << '\n';
    cout << '\n';

    vector<test_result> res;
    splay_tree_test<int, P1> a;
    auto res1 = Test<int, P1>("log n", a, data);
    res.push_back(res1);
    
    splay_tree_test<int, P2> b;
    auto res2 = Test<int, P2>("log^2 n", b, data);
    res.push_back(res2);
    
    splay_tree_test<int, P4> d;
    auto res4 = Test<int, P4>("n^(1/3)", d, data);
    res.push_back(res4);
    
    splay_tree_test<int, P5> e;
    auto res5 = Test<int, P5>("n^(1/2)", e, data);
    res.push_back(res5);

    for(auto i:res) {
        cout << fixed << setprecision(2) << i.test_name << "\t:\t" << 1.*i.max_height/default_res.max_height << '\t' << 1.*i.max_rotate/default_res.max_rotate << '\t' << 1.*i.sum_rotate/default_res.sum_rotate << '\n';
    }
    cout << "\n\n";
}

vector<pair<int,int>> GetData(int N) {
    auto data = Parse();
    if(N < data.size()) {
        while(data.size() < N) data.pop_back();
        return data;
    }

    int i=0;
    while(data.size() < N) data.push_back(data[i++]);
    return data;
}

int main(){
    auto data = Parse();
    TestAll("Edit Trace Data", data);

    for(int sz:{1e3, 1e4, 1e5, 1e6, 1e7}) {
        data = GetData(sz);
        TestAll("Edit Trace Data (" + to_string(sz) + ")", data);
    }
}

Edit Trace Data (default)
default : 6735 6653 641004

log n : 1.00 1.00 1.00
log^2 n : 0.08 0.08 1.10
n^(1/3) : 0.02 0.02 1.35
n^(1/2) : 0.09 0.09 1.10

Edit Trace Data (1000)
default : 6735 6653 641004

log n : 1.00 1.00 1.00
log^2 n : 0.08 0.08 1.10
n^(1/3) : 0.02 0.02 1.35
n^(1/2) : 0.09 0.09 1.10

Edit Trace Data (10000)
default : 6735 6653 641004

log n : 1.00 1.00 1.00
log^2 n : 0.08 0.08 1.10
n^(1/3) : 0.02 0.02 1.35
n^(1/2) : 0.09 0.09 1.10

Edit Trace Data (100000)
default : 6735 6653 641004

log n : 1.00 1.00 1.00
log^2 n : 0.08 0.08 1.10
n^(1/3) : 0.02 0.02 1.35
n^(1/2) : 0.09 0.09 1.10

Edit Trace Data (1000000)
default : 6735 6653 2465583

log n : 1.00 1.00 1.00
log^2 n : 0.10 0.10 1.09
n^(1/3) : 0.03 0.03 1.28
n^(1/2) : 0.18 0.19 1.08

Edit Trace Data (10000000)
default : 6735 6653 24672200

log n : 1.00 1.00 1.00
log^2 n : 0.13 0.15 1.07
n^(1/3) : 0.05 0.06 1.17
n^(1/2) : 0.47 0.48 1.04