splay-safe-rs

Description

Splay implemented with safe rust.

LICENSE

This software is licensed under Mozilla Public License Version 2.0.

lib.rs:

Splay implemented with safe rust.

Examples

SplayWithKey

use splay_safe_rs::{BasicOpsWithKey, KeyValue, SplayWithKey};
use std::ops::Bound;

struct SplayValue {
    num: usize,
    total: usize,
}
impl BasicOpsWithKey<u32> for SplayValue {
    fn push_up(
        &mut self,
        key: &u32,
        lc: Option<&KeyValue<u32, Self>>,
        rc: Option<&KeyValue<u32, Self>>,
    ) {
        self.total = self.num;
        if let Some(d) = lc {
            self.total += d.value.total;
        }
        if let Some(d) = rc {
            self.total += d.value.total;
        }
    }
}

let mut keys = SplayWithKey::<u32, SplayValue>::new();
keys.insert(1, SplayValue { num: 1, total: 1 });
keys.insert(2, SplayValue { num: 2, total: 2 });
keys.insert(3, SplayValue { num: 3, total: 3 });
keys.insert(4, SplayValue { num: 4, total: 4 });
assert_eq!(keys.range(2..4).root_data().unwrap().value.total, 5);

RankTreeWithKey

use splay_safe_rs::RankTreeWithKey;

let mut tree = RankTreeWithKey::<u32>::from(vec![1, 2, 3, 4, 5, 6, 7]);
assert_eq!(*tree.query_kth_key(4).unwrap(), 4);
tree.range(4..6).delete_all();
assert_eq!(
    tree.collect_data().iter().map(|d| d.key).collect::<Vec<_>>(),
    vec![1, 2, 3, 6, 7],
);
assert_eq!(*tree.query_kth_key(4).unwrap(), 6);