splay-test.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();
    }
};

// int RANDOM_WAIT = 100, RANDOM_PICK = 10;
int RANDOM_WAIT = 1e9, RANDOM_PICK = 0;

template<typename T>
struct splay_tree{
    node<T> *root; int cnt;
    splay_tree() : splay_tree(vector<T>()) {}
    splay_tree(vector<T> v){
        root = new node<T>(); cnt = 0;
        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){
        static mt19937 rng(0x917917);
        if(++cnt == RANDOM_WAIT){
            uniform_int_distribution<int> gen(1, root->sz-2);
            for(int i=1; i<=RANDOM_PICK; i++) kth(gen(rng));
            cnt = 0;
        }
        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); }
};

int StressTest(int N, int Q){
    int mx = 0;
    mt19937 rng((unsigned)chrono::steady_clock::now().time_since_epoch().count());
    auto gen_value = [&](){ return uniform_int_distribution<int>(1, 101010)(rng); };

    vector<int> v(N);
    for(auto &i : v) i = gen_value();

    splay_tree<int> T(v);
    assert(T.inorder() == v);

    mx = max(mx, T.max_height());

    auto gen_index = [&](){ return uniform_int_distribution<int>(1, v.size())(rng); };
    auto gen_range = [&](){
        auto l = gen_index(), r = gen_index();
        if(l > r) swap(l, r);
        return make_pair(l, r);
    };

    auto insert_after = [&](int pos, int val){
        T.insert_after(T.kth(pos), val);
        if(!v.empty()) v.insert(v.begin()+pos, val);
        else v.push_back(val);
         return T.inorder() == v;
    };
    auto insert_before = [&](int pos, int val){
        T.insert_before(T.kth(pos), val);
        if(!v.empty()) v.insert(v.begin()+pos-1, val);
        else v.push_back(val);
        return T.inorder() == v;
    };
    auto order_of_node = [&](int pos){
        return T.order_of_node(T.kth(pos)) == pos;
    };
    auto erase = [&](int pos){
        T.erase(pos);
        v.erase(v.begin()+pos-1);
        return T.inorder() == v;
    };
    auto erase_range = [&](int s, int e){
        T.erase_range(s, e);
        v.erase(v.begin()+s-1, v.begin()+e);
        return T.inorder() == v;
    };

    for(int iter=1; iter<=Q; iter++){
        int op = rand() % 5;
        if(v.empty()) op = rand() % 2;
        if(op == 0){
            int idx = gen_index(), val = gen_value();
            bool flag0 = insert_after(idx, val);
            assert(flag0);
        }
        if(op == 1){
            int idx = gen_index(), val = gen_value();
            bool flag1 = insert_before(idx, val);
            assert(flag1);
        }
        if(op == 2 && !v.empty()){
            int idx = gen_index();
            bool flag2 = order_of_node(idx);
            assert(flag2);
        }
        if(op == 3 && !v.empty()){
            int idx = gen_index();
            bool flag3 = erase(idx);
            assert(flag3);
        }
        if(op == 4 && !v.empty()){
            auto [l,r] = gen_range();
            bool flag4 = erase_range(l, r);
            assert(flag4);
        }
        mx = max(mx, T.max_height());
        assert(T.max_height() == T.root->h);
    }
    return mx;
}

int HeightTest(int N){
    int mx = 0;
    splay_tree<int> T({1});
    assert(T.kth(1)->v == 1);
    mx = max(mx, T.max_height());
    for(int i=2; i<=N; i++){
        T.insert_next_of_root(i);
        mx = max(mx, T.max_height());
        assert(T.max_height() == T.root->h);
    }
    auto res = T.inorder();
    assert(res.size() == N);
    for(int i=0; i<N; i++) assert(res[i] == i + 1);
    return mx;
}

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

void Run(int sz){
    cout << sz << " : " << StressTest(sz, sz) << " " << HeightTest(sz) << endl;
}

struct test_result{
    int random_wait;
    int random_pick;
    int max_height;
    int max_rotate;
    int sum_rotate;
};

test_result EditTraceTest(int random_wait, int random_pick, const vector<pair<int,int>> &data){
    RANDOM_WAIT = random_wait;
    RANDOM_PICK = random_pick;

    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 T.erase(pos + 1);
        mx_h = max(mx_h, T.root->h);
        mx_rot = max(mx_rot, rotate_count - prv);
    }

    return {random_wait, random_pick, mx_h, mx_rot, rotate_count};
}

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

    printf("number of operations: %llu\n", data.size());
    printf("number of insert: %d\n", ins);
    printf("number of erase: %d\n", del);
    printf("maximum tree size: %d\n\n", mx_sz);

    auto default_res = EditTraceTest(1e9, 0, data);
    printf("default: %d %d %d\n\n", default_res.max_height, default_res.max_rotate, default_res.sum_rotate);

    printf(" wait pick:   mx.h mx.rot sum.rot\n");
    for(auto wait : {100, 500, 1000, 5000, 10000}){
        for(auto pick : {1, 5, 10, 50, 100}){
            auto res = EditTraceTest(wait, pick, data);
            // if(res.sum_rotate > default_res.sum_rotate * 2) continue;
            // if(res.max_rotate > default_res.max_rotate) continue;
            printf("%5d %4d: ", res.random_wait, res.random_pick);
            printf("%6.2lf %6.2lf %7.2lf\n",
                   1. * res.max_height / default_res.max_height,
                   1. * res.max_rotate / default_res.max_rotate,
                   1. * res.sum_rotate / default_res.sum_rotate);
        }
    }
}

int main(){
    GetMaxHeight();
    // for(auto i : {10, 50, 100, 500, 1000, 5000, 10000, 50000}) Run(i);
}

number of operations: 259778
number of insert: 182315
number of erase: 77463
maximum tree size: 106979

default: 6735 6653 641004

 wait pick:   mx.h mx.rot sum.rot
  100    1:   0.30   0.30    1.30
  100    5:   0.13   0.15    2.23
  100   10:   0.09   0.11    3.33
  100   50:   0.04   0.19   11.97
  100  100:   0.02   0.35   22.71
  500    1:   0.37   0.34    1.07
  500    5:   0.32   0.36    1.27
  500   10:   0.18   0.26    1.50
  500   50:   0.07   0.26    3.23
  500  100:   0.05   0.39    5.38
 1000    1:   0.69   0.67    1.04
 1000    5:   0.38   0.35    1.15
 1000   10:   0.30   0.32    1.26
 1000   50:   0.12   0.33    2.13
 1000  100:   0.10   0.43    3.20
 5000    1:   1.00   1.00    1.01
 5000    5:   0.93   0.96    1.03
 5000   10:   0.87   0.69    1.06
 5000   50:   0.33   0.62    1.23
 5000  100:   0.27   0.78    1.45
10000    1:   0.88   0.85    1.00
10000    5:   0.75   0.72    1.01
10000   10:   1.00   1.00    1.03
10000   50:   0.62   1.22    1.12
10000  100:   0.54   1.26    1.23