Splay tree

splay.rs

trait SplayOp {
    type T;

    fn pull(_t: &mut SplayTree<Self>, _u: usize) {}
    fn push(_t: &mut SplayTree<Self>, _u: usize) {}
}

struct SplayNode<T> {
    v: T,
    c: [u32; 2],
    p: u32,
}

struct SplayTree<Op: SplayOp + ?Sized> {
    v: Vec<SplayNode<Op::T>>,
}

impl<Op: SplayOp> SplayTree<Op> {
    fn new() -> Self {
        SplayTree { v: vec![] }
    }

    fn push(&mut self, v: Op::T) -> u32 {
        let i = self.v.len();
        self.v.push(SplayNode {
            v,
            c: [u32::MAX; 2],
            p: u32::MAX,
        });
        i as u32
    }

    fn side(&self, n: u32) -> usize {
        let p = self.v[n as usize].p as usize;
        if self.v[p].c[0] == n {
            0
        } else {
            1
        }
    }

    fn attach(&mut self, u: u32, v: u32, i: usize) {
        if v != u32::MAX {
            self.v[v as usize].p = u;
        }
        self.v[u as usize].c[i] = v;
    }

    fn rotate(&mut self, n: u32) {
        let p = self.v[n as usize].p;
        let i = self.side(n);
        if self.v[p as usize].p == u32::MAX {
            self.v[n as usize].p = u32::MAX;
        } else {
            self.attach(self.v[p as usize].p, n, self.side(p));
        }
        self.attach(p, self.v[n as usize].c[i ^ 1], i);
        self.attach(n, p, i ^ 1);
        Op::pull(self, p as usize);
        Op::pull(self, n as usize);
    }

    fn splay(&mut self, n: u32) {
        while self.v[n as usize].p != u32::MAX {
            let p = self.v[n as usize].p;
            if self.v[p as usize].p != u32::MAX {
                if self.side(p) == self.side(n) {
                    self.rotate(p);
                } else {
                    self.rotate(n);
                }
            }
            self.rotate(n);
        }
    }

    fn find<F>(&mut self, mut n: u32, mut f: F) -> u32
    where
        F: FnMut(&Self, usize) -> usize,
    {
        loop {
            Op::push(self, n as usize);
            let i = f(&self, n as usize);
            if i > 1 || self.v[n as usize].c[i] == u32::MAX {
                break n;
            } else {
                n = self.v[n as usize].c[i];
            }
        }
    }

    fn split(&mut self, n: u32, i: usize) -> u32 {
        Op::push(self, n as usize);
        let o = self.v[n as usize].c[i];
        if o != u32::MAX {
            self.v[o as usize].p = u32::MAX;
        }
        self.v[n as usize].c[i] = u32::MAX;
        Op::pull(self, n as usize);
        o
    }

    fn join(&mut self, u: u32, v: u32, i: usize) {
        Op::push(self, u as usize);
        self.attach(u, v, i);
        Op::pull(self, u as usize);
    }
}