5 releases
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 |
#595 in Data structures
221 downloads per month
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
~25K SLoC