#safe #splay #implemented

no-std splay-safe-rs

Splay implemented with safe rust

5 releases

new 0.8.1 Nov 1, 2024
0.8.0 Nov 1, 2024
0.7.12 Jun 26, 2024
0.7.11 Apr 29, 2024
0.7.10 Apr 29, 2024

#550 in Data structures

Download history 26/week @ 2024-07-27 6/week @ 2024-09-14 7/week @ 2024-09-21 64/week @ 2024-09-28 1/week @ 2024-10-05

65 downloads per month

MPL-2.0 license

77KB
2.5K SLoC

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);

Dependencies

~0.5–1.1MB
~24K SLoC