use smallvec::SmallVec;
use std::cmp::Ordering;
#[derive(Clone, PartialEq)]
pub enum AVLTag {
Free,
None,
Left,
Right,
}
#[derive(Clone)]
pub struct AVLNode<T> {
pub tag: AVLTag,
pub left: u32,
pub right: u32,
pub item: T,
}
impl<T> AVLNode<T> {
fn new(tag: AVLTag, left: u32, right: u32, item: T) -> Self {
Self {
tag,
left,
right,
item,
}
}
}
pub const AVL_NULL: u32 = 0xFFFF_FFFF;
pub struct AVLTree<T> {
pub pool: Vec<AVLNode<T>>,
default: T,
freelist: u32,
pub root: u32,
}
impl<T: Clone> AVLTree<T> {
pub fn new(default: T) -> Self {
let pool = Vec::with_capacity(16);
let freelist = AVL_NULL;
let root = AVL_NULL;
Self {
pool,
default,
freelist,
root,
}
}
fn free(&mut self, index: u32) {
assert!(index != AVL_NULL);
assert!(self.pool[index as usize].tag != AVLTag::Free);
self.pool[index as usize] =
AVLNode::new(AVLTag::Free, self.freelist, AVL_NULL, self.default.clone());
self.freelist = index;
}
fn alloc(&mut self) -> u32 {
if self.freelist == AVL_NULL {
let start = self.pool.len();
let fill_item = AVLNode::new(AVLTag::Free, AVL_NULL, AVL_NULL, self.default.clone());
if start >= 0x7000_0000 {
panic!("AVLTree<T>::alloc: too many items");
}
self.pool.resize(2 * start + 2, fill_item);
let end_plus_1 = self.pool.len();
debug_assert!(end_plus_1 >= 2);
self.pool[end_plus_1 - 1].left = self.freelist;
let mut i = end_plus_1 - 2;
while i >= start {
self.pool[i].left = i as u32 + 1;
if i == 0 {
break;
}
i -= 1;
}
self.freelist = start as u32;
debug_assert!(self.freelist != AVL_NULL);
}
let new = self.freelist;
assert!(self.pool[new as usize].tag == AVLTag::Free);
self.pool[new as usize].tag = AVLTag::None;
self.freelist = self.pool[new as usize].left;
new
}
}
#[derive(Clone, Copy, PartialEq)]
enum AVLRes {
Error,
OK,
Balance,
}
impl<T: Clone + PartialOrd> AVLTree<T> {
fn rotleft(&mut self, old_root: u32) -> u32 {
let new_root = self.pool[old_root as usize].right;
self.pool[old_root as usize].right = self.pool[new_root as usize].left;
self.pool[new_root as usize].left = old_root;
new_root
}
fn rotright(&mut self, old_root: u32) -> u32 {
let new_root = self.pool[old_root as usize].left;
self.pool[old_root as usize].left = self.pool[new_root as usize].right;
self.pool[new_root as usize].right = old_root;
new_root
}
#[inline(never)]
fn leftgrown_left(&mut self, mut root: u32) -> (u32, AVLRes) {
if self.pool[self.pool[root as usize].left as usize].tag == AVLTag::Left {
self.pool[root as usize].tag = AVLTag::None;
let t = self.pool[root as usize].left;
self.pool[t as usize].tag = AVLTag::None;
root = self.rotright(root);
} else {
match self.pool[self.pool[self.pool[root as usize].left as usize].right as usize].tag {
AVLTag::Left => {
self.pool[root as usize].tag = AVLTag::Right;
let t = self.pool[root as usize].left;
self.pool[t as usize].tag = AVLTag::None;
}
AVLTag::Right => {
self.pool[root as usize].tag = AVLTag::None;
let t = self.pool[root as usize].left;
self.pool[t as usize].tag = AVLTag::Left;
}
AVLTag::None => {
self.pool[root as usize].tag = AVLTag::None;
let t = self.pool[root as usize].left;
self.pool[t as usize].tag = AVLTag::None;
}
AVLTag::Free => panic!("AVLTree::leftgrown_left: unallocated node in tree"),
}
let t = self.pool[self.pool[root as usize].left as usize].right;
self.pool[t as usize].tag = AVLTag::None;
self.pool[root as usize].left = self.rotleft(self.pool[root as usize].left);
root = self.rotright(root);
}
return (root, AVLRes::OK);
}
#[inline(always)]
fn leftgrown(&mut self, root: u32) -> (u32, AVLRes) {
let root_node = &mut self.pool[root as usize];
match root_node.tag {
AVLTag::Left => self.leftgrown_left(root),
AVLTag::Right => {
root_node.tag = AVLTag::None;
return (root, AVLRes::OK);
}
AVLTag::None => {
root_node.tag = AVLTag::Left;
return (root, AVLRes::Balance);
}
AVLTag::Free => panic!("AVLTree::leftgrown: unallocated node in tree"),
}
}
#[inline(never)]
fn rightgrown_right(&mut self, mut root: u32) -> (u32, AVLRes) {
if self.pool[self.pool[root as usize].right as usize].tag == AVLTag::Right {
self.pool[root as usize].tag = AVLTag::None;
let t = self.pool[root as usize].right as usize;
self.pool[t].tag = AVLTag::None;
root = self.rotleft(root);
} else {
match self.pool[self.pool[self.pool[root as usize].right as usize].left as usize].tag {
AVLTag::Right => {
self.pool[root as usize].tag = AVLTag::Left;
let t = self.pool[root as usize].right;
self.pool[t as usize].tag = AVLTag::None;
}
AVLTag::Left => {
self.pool[root as usize].tag = AVLTag::None;
let t = self.pool[root as usize].right;
self.pool[t as usize].tag = AVLTag::Right;
}
AVLTag::None => {
self.pool[root as usize].tag = AVLTag::None;
let t = self.pool[root as usize].right;
self.pool[t as usize].tag = AVLTag::None;
}
AVLTag::Free => panic!("AVLTree::rightgrown_right: unallocated node in tree"),
}
let t = self.pool[self.pool[root as usize].right as usize].left;
self.pool[t as usize].tag = AVLTag::None;
self.pool[root as usize].right = self.rotright(self.pool[root as usize].right);
root = self.rotleft(root);
}
return (root, AVLRes::OK);
}
#[inline(always)]
fn rightgrown(&mut self, root: u32) -> (u32, AVLRes) {
match self.pool[root as usize].tag {
AVLTag::Left => {
self.pool[root as usize].tag = AVLTag::None;
return (root, AVLRes::OK);
}
AVLTag::Right => self.rightgrown_right(root),
AVLTag::None => {
self.pool[root as usize].tag = AVLTag::Right;
return (root, AVLRes::Balance);
}
AVLTag::Free => panic!("AVLTree::rightgrown: unallocated node in tree"),
}
}
fn insert_wrk<F>(&mut self, mut root: u32, item: T, mb_cmp: Option<&F>) -> u32
where
F: Fn(T, T) -> Option<Ordering>,
{
#[inline(always)]
fn stack_entry_set_is_left(node: u32) -> u32 {
node | 0x8000_0000
}
#[inline(always)]
fn stack_entry_get_is_left(ent: u32) -> u32 {
ent & 0x8000_0000
}
#[inline(always)]
fn stack_entry_get_node(ent: u32) -> u32 {
ent & 0x7FFF_FFFF
}
let mut stack = SmallVec::<[u32; 64]>::new();
match mb_cmp {
None => {
while root != AVL_NULL {
let cmp_loc_right = &self.pool[root as usize];
let cmp_arg_right: T = cmp_loc_right.item.clone();
let cmp_arg_left: T = item.clone();
debug_assert!(stack_entry_get_is_left(root) == 0);
match cmp_arg_left.partial_cmp(&cmp_arg_right) {
None => panic!("AVLTree::insert_wrk: unordered elements(1)"),
Some(Ordering::Less) => {
stack.push(stack_entry_set_is_left(root));
root = cmp_loc_right.left;
}
Some(Ordering::Greater) => {
stack.push(root);
root = cmp_loc_right.right;
}
Some(Ordering::Equal) => {
return AVL_NULL;
}
}
}
}
Some(cmp) => {
while root != AVL_NULL {
let cmp_loc_right = &self.pool[root as usize];
let cmp_arg_right: T = cmp_loc_right.item.clone();
let cmp_arg_left: T = item.clone();
debug_assert!(stack_entry_get_is_left(root) == 0);
match cmp(cmp_arg_left, cmp_arg_right) {
None => panic!("AVLTree::insert_wrk: unordered elements(2)"),
Some(Ordering::Less) => {
stack.push(stack_entry_set_is_left(root));
root = cmp_loc_right.left;
}
Some(Ordering::Greater) => {
stack.push(root);
root = cmp_loc_right.right;
}
Some(Ordering::Equal) => {
return AVL_NULL;
}
}
}
}
}
debug_assert!(root == AVL_NULL);
let new_node = self.alloc();
self.pool[new_node as usize] = AVLNode::new(AVLTag::None, AVL_NULL, AVL_NULL, item.clone());
let mut curr_node = new_node;
let mut curr_node_action = AVLRes::Balance;
while let Some(parent_node_tagged) = stack.pop() {
let parent_node = stack_entry_get_node(parent_node_tagged);
if stack_entry_get_is_left(parent_node_tagged) != 0 {
self.pool[parent_node as usize].left = curr_node;
if curr_node_action == AVLRes::Balance {
let pair = self.leftgrown(parent_node);
curr_node = pair.0;
curr_node_action = pair.1;
} else {
curr_node = parent_node;
break;
}
} else {
self.pool[parent_node as usize].right = curr_node;
if curr_node_action == AVLRes::Balance {
let pair = self.rightgrown(parent_node);
curr_node = pair.0;
curr_node_action = pair.1;
} else {
curr_node = parent_node;
break;
}
}
}
if !stack.is_empty() {
curr_node = stack_entry_get_node(stack[0]);
}
debug_assert!(curr_node != AVL_NULL);
return curr_node;
}
fn leftshrunk(&mut self, mut n: u32) -> (u32, AVLRes) {
match self.pool[n as usize].tag {
AVLTag::Left => {
self.pool[n as usize].tag = AVLTag::None;
return (n, AVLRes::Balance);
}
AVLTag::Right => {
if self.pool[self.pool[n as usize].right as usize].tag == AVLTag::Right {
self.pool[n as usize].tag = AVLTag::None;
let t = self.pool[n as usize].right;
self.pool[t as usize].tag = AVLTag::None;
n = self.rotleft(n);
return (n, AVLRes::Balance);
} else if self.pool[self.pool[n as usize].right as usize].tag == AVLTag::None {
self.pool[n as usize].tag = AVLTag::Right;
let t = self.pool[n as usize].right;
self.pool[t as usize].tag = AVLTag::Left;
n = self.rotleft(n);
return (n, AVLRes::OK);
} else {
match self.pool[self.pool[self.pool[n as usize].right as usize].left as usize]
.tag
{
AVLTag::Left => {
self.pool[n as usize].tag = AVLTag::None;
let t = self.pool[n as usize].right;
self.pool[t as usize].tag = AVLTag::Right;
}
AVLTag::Right => {
self.pool[n as usize].tag = AVLTag::Left;
let t = self.pool[n as usize].right;
self.pool[t as usize].tag = AVLTag::None;
}
AVLTag::None => {
self.pool[n as usize].tag = AVLTag::None;
let t = self.pool[n as usize].right;
self.pool[t as usize].tag = AVLTag::None;
}
AVLTag::Free => {
panic!("AVLTree::leftshrunk(1): unallocated node in tree");
}
}
{
let t = self.pool[self.pool[n as usize].right as usize].left;
self.pool[t as usize].tag = AVLTag::None;
}
{
let t = self.rotright(self.pool[n as usize].right);
self.pool[n as usize].right = t;
}
n = self.rotleft(n);
return (n, AVLRes::Balance);
}
}
AVLTag::None => {
self.pool[n as usize].tag = AVLTag::Right;
return (n, AVLRes::OK);
}
AVLTag::Free => {
panic!("AVLTree::leftshrunk(2): unallocated node in tree");
}
}
}
fn rightshrunk(&mut self, mut n: u32) -> (u32, AVLRes) {
match self.pool[n as usize].tag {
AVLTag::Right => {
self.pool[n as usize].tag = AVLTag::None;
return (n, AVLRes::Balance);
}
AVLTag::Left => {
if self.pool[self.pool[n as usize].left as usize].tag == AVLTag::Left {
self.pool[n as usize].tag = AVLTag::None;
let t = self.pool[n as usize].left;
self.pool[t as usize].tag = AVLTag::None;
n = self.rotright(n);
return (n, AVLRes::Balance);
} else if self.pool[self.pool[n as usize].left as usize].tag == AVLTag::None {
self.pool[n as usize].tag = AVLTag::Left;
let t = self.pool[n as usize].left;
self.pool[t as usize].tag = AVLTag::Right;
n = self.rotright(n);
return (n, AVLRes::OK);
} else {
match self.pool[self.pool[self.pool[n as usize].left as usize].right as usize]
.tag
{
AVLTag::Left => {
self.pool[n as usize].tag = AVLTag::Right;
let t = self.pool[n as usize].left;
self.pool[t as usize].tag = AVLTag::None;
}
AVLTag::Right => {
self.pool[n as usize].tag = AVLTag::None;
let t = self.pool[n as usize].left;
self.pool[t as usize].tag = AVLTag::Left;
}
AVLTag::None => {
self.pool[n as usize].tag = AVLTag::None;
let t = self.pool[n as usize].left;
self.pool[t as usize].tag = AVLTag::None;
}
AVLTag::Free => {
panic!("AVLTree::rightshrunk(1): unallocated node in tree");
}
}
{
let t = self.pool[self.pool[n as usize].left as usize].right;
self.pool[t as usize].tag = AVLTag::None;
}
{
let t = self.rotleft(self.pool[n as usize].left);
self.pool[n as usize].left = t;
}
n = self.rotright(n);
return (n, AVLRes::Balance);
}
}
AVLTag::None => {
self.pool[n as usize].tag = AVLTag::Left;
return (n, AVLRes::OK);
}
AVLTag::Free => {
panic!("AVLTree::rightshrunk(2): unallocated node in tree");
}
}
}
fn findhighest(&mut self, target: u32, mut n: u32) -> Option<(u32, AVLRes)> {
if n == AVL_NULL {
return None;
}
let mut res = AVLRes::Balance;
if self.pool[n as usize].right != AVL_NULL {
let rec = self.findhighest(target, self.pool[n as usize].right);
if let Some((new_n_right, new_res)) = rec {
self.pool[n as usize].right = new_n_right;
res = new_res;
if res == AVLRes::Balance {
let (new_n, new_res) = self.rightshrunk(n);
n = new_n;
res = new_res;
}
return Some((n, res));
} else {
return None;
}
}
self.pool[target as usize].item = self.pool[n as usize].item.clone();
let tmp = n;
n = self.pool[n as usize].left;
self.free(tmp);
Some((n, res))
}
fn findlowest(&mut self, target: u32, mut n: u32) -> Option<(u32, AVLRes)> {
if n == AVL_NULL {
return None;
}
let mut res = AVLRes::Balance;
if self.pool[n as usize].left != AVL_NULL {
let rec = self.findlowest(target, self.pool[n as usize].left);
if let Some((new_n_left, new_res)) = rec {
self.pool[n as usize].left = new_n_left;
res = new_res;
if res == AVLRes::Balance {
let (new_n, new_res) = self.leftshrunk(n);
n = new_n;
res = new_res;
}
return Some((n, res));
} else {
return None;
}
}
self.pool[target as usize].item = self.pool[n as usize].item.clone();
let tmp = n;
n = self.pool[n as usize].right;
self.free(tmp);
Some((n, res))
}
fn delete_wrk<F>(&mut self, mut root: u32, item: T, mb_cmp: Option<&F>) -> (u32, AVLRes)
where
F: Fn(T, T) -> Option<Ordering>,
{
let mut tmp = AVLRes::Balance;
if root == AVL_NULL {
return (root, AVLRes::Error);
}
let cmp_arg_left: T = item.clone();
let cmp_arg_right: T = self.pool[root as usize].item.clone();
let cmp_res = match mb_cmp {
None => cmp_arg_left.partial_cmp(&cmp_arg_right),
Some(cmp) => cmp(cmp_arg_left, cmp_arg_right),
};
match cmp_res {
None => panic!("AVLTree::delete_wrk: unordered elements"),
Some(Ordering::Less) => {
let root_left = self.pool[root as usize].left;
let (new_root_left, new_tmp) = self.delete_wrk(root_left, item, mb_cmp);
self.pool[root as usize].left = new_root_left;
tmp = new_tmp;
if tmp == AVLRes::Balance {
let (new_root, new_res) = self.leftshrunk(root);
root = new_root;
tmp = new_res;
}
return (root, tmp);
}
Some(Ordering::Greater) => {
let root_right = self.pool[root as usize].right;
let (new_root_right, new_tmp) = self.delete_wrk(root_right, item, mb_cmp);
self.pool[root as usize].right = new_root_right;
tmp = new_tmp;
if tmp == AVLRes::Balance {
let (new_root, new_res) = self.rightshrunk(root);
root = new_root;
tmp = new_res;
}
return (root, tmp);
}
Some(Ordering::Equal) => {
if self.pool[root as usize].left != AVL_NULL {
let root_left = self.pool[root as usize].left;
if let Some((new_root_left, new_tmp)) = self.findhighest(root, root_left) {
self.pool[root as usize].left = new_root_left;
tmp = new_tmp;
if new_tmp == AVLRes::Balance {
let (new_root, new_res) = self.leftshrunk(root);
root = new_root;
tmp = new_res;
}
}
return (root, tmp);
}
if self.pool[root as usize].right != AVL_NULL {
let root_right = self.pool[root as usize].right;
if let Some((new_root_right, new_tmp)) = self.findlowest(root, root_right) {
self.pool[root as usize].right = new_root_right;
tmp = new_tmp;
if new_tmp == AVLRes::Balance {
let (new_root, new_res) = self.rightshrunk(root);
root = new_root;
tmp = new_res;
}
}
return (root, tmp);
}
self.free(root);
root = AVL_NULL;
return (root, AVLRes::Balance);
}
}
}
#[cfg(test)]
fn count_wrk(&self, n: u32) -> usize {
if n == AVL_NULL {
return 0;
}
1 + self.count_wrk(self.pool[n as usize].left) + self.count_wrk(self.pool[n as usize].right)
}
#[cfg(test)]
fn depth_wrk(&self, n: u32) -> usize {
if n == AVL_NULL {
return 0;
}
let d_left = self.depth_wrk(self.pool[n as usize].left);
let d_right = self.depth_wrk(self.pool[n as usize].right);
1 + if d_left > d_right { d_left } else { d_right }
}
}
pub struct AVLTreeIter<'t, 's, T> {
tree: &'t AVLTree<T>,
stack: &'s mut Vec<u32>,
}
impl<'t, 's, T> AVLTreeIter<'t, 's, T> {
#[allow(dead_code)]
fn new(tree: &'t AVLTree<T>, stack: &'s mut Vec<u32>) -> Self {
let mut iter = AVLTreeIter { tree, stack };
if tree.root != AVL_NULL {
iter.stack.push(tree.root);
iter.visit_left_children(tree.root);
}
iter
}
fn visit_left_children(&mut self, root: u32) {
let mut cur = root;
loop {
let left = self.tree.pool[cur as usize].left;
if left == AVL_NULL {
break;
}
self.stack.push(left);
cur = left;
}
}
}
impl<'s, 't, T: Copy> Iterator for AVLTreeIter<'s, 't, T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
let ret = match self.stack.pop() {
Some(ret) => ret,
None => return None,
};
let right = self.tree.pool[ret as usize].right;
if right != AVL_NULL {
self.stack.push(right);
self.visit_left_children(right);
}
Some(self.tree.pool[ret as usize].item)
}
}
impl<T: Clone + PartialOrd> AVLTree<T> {
pub fn insert<F>(&mut self, item: T, mb_cmp: Option<&F>) -> bool
where
F: Fn(T, T) -> Option<Ordering>,
{
let new_root = self.insert_wrk(self.root, item, mb_cmp);
if new_root == AVL_NULL {
return false;
} else {
self.root = new_root;
return true;
}
}
pub fn delete<F>(&mut self, item: T, mb_cmp: Option<&F>) -> bool
where
F: Fn(T, T) -> Option<Ordering>,
{
let (new_root, res) = self.delete_wrk(self.root, item, mb_cmp);
if res == AVLRes::Error {
return false;
} else {
self.root = new_root;
return true;
}
}
pub fn find_and_replace<F>(&mut self, item: T, replacement: T, cmp: &F) -> bool
where
F: Fn(T, T) -> Option<Ordering>,
{
let mut n = self.root;
loop {
if n == AVL_NULL {
return false;
}
let cmp_arg_left: T = item.clone();
let cmp_arg_right: T = self.pool[n as usize].item.clone();
match cmp(cmp_arg_left, cmp_arg_right) {
Some(Ordering::Less) => {
n = self.pool[n as usize].left;
}
Some(Ordering::Greater) => {
n = self.pool[n as usize].right;
}
Some(Ordering::Equal) => {
assert!(cmp(item, replacement.clone()) == Some(Ordering::Equal));
self.pool[n as usize].item = replacement.clone();
return true;
}
None => {
panic!("AVLTree::find_and_replace: unordered elements in search!");
}
}
}
}
#[cfg(test)]
pub fn contains<F>(&self, item: T, mb_cmp: Option<&F>) -> bool
where
F: Fn(T, T) -> Option<Ordering>,
{
let mut n = self.root;
match mb_cmp {
None => {
loop {
if n == AVL_NULL {
return false;
}
let cmp_arg_left: T = item.clone();
let cmp_arg_right: T = self.pool[n as usize].item.clone();
match cmp_arg_left.partial_cmp(&cmp_arg_right) {
Some(Ordering::Less) => {
n = self.pool[n as usize].left;
}
Some(Ordering::Greater) => {
n = self.pool[n as usize].right;
}
Some(Ordering::Equal) => {
return true;
}
None => {
panic!("AVLTree::contains(1): unordered elements in search!");
}
}
}
}
Some(cmp) => {
loop {
if n == AVL_NULL {
return false;
}
let cmp_arg_left: T = item.clone();
let cmp_arg_right: T = self.pool[n as usize].item.clone();
match cmp(cmp_arg_left, cmp_arg_right) {
Some(Ordering::Less) => {
n = self.pool[n as usize].left;
}
Some(Ordering::Greater) => {
n = self.pool[n as usize].right;
}
Some(Ordering::Equal) => {
return true;
}
None => {
panic!("AVLTree::contains(2): unordered elements in search!");
}
}
}
}
}
}
#[cfg(test)]
fn count(&self) -> usize {
self.count_wrk(self.root)
}
#[cfg(test)]
fn depth(&self) -> usize {
self.depth_wrk(self.root)
}
pub fn to_vec(&self) -> Vec<T> {
fn walk<U: Clone>(res: &mut Vec<U>, root: u32, pool: &Vec<AVLNode<U>>) {
let root_left = pool[root as usize].left;
if root_left != AVL_NULL {
walk(res, root_left, pool);
}
res.push(pool[root as usize].item.clone());
let root_right = pool[root as usize].right;
if root_right != AVL_NULL {
walk(res, root_right, pool);
}
}
let mut res = Vec::<T>::new();
if self.root != AVL_NULL {
walk(&mut res, self.root, &self.pool);
}
res
}
#[allow(dead_code)]
pub fn iter<'t, 's>(&'t self, storage: &'s mut Vec<u32>) -> AVLTreeIter<'t, 's, T> {
storage.clear();
AVLTreeIter::new(self, storage)
}
}
#[cfg(test)]
mod avl_tree_test_utils {
use crate::data_structures::Set;
use std::cmp::Ordering;
pub fn check_tree(
tree: &super::AVLTree<u32>,
should_be_in_tree: &Set<u32>,
univ_min: u32,
univ_max: u32,
) {
let n_in_set = should_be_in_tree.card();
let n_in_tree = tree.count();
assert!(n_in_set == n_in_tree);
let tree_depth = tree.depth();
let mut log2_size = 0;
{
let mut n: usize = n_in_tree;
while n > 0 {
n = n >> 1;
log2_size += 1;
}
}
assert!(tree_depth <= log2_size + 1);
for i in univ_min..univ_max {
let should_be_in = should_be_in_tree.contains(i);
let is_in = tree.contains::<fn(u32, u32) -> Option<Ordering>>(i, None);
assert!(is_in == should_be_in);
let is_in_w_cmp = tree.contains(
i,
Some(&(|x_left: u32, x_right: u32| x_left.partial_cmp(&x_right))),
);
assert!(is_in_w_cmp == is_in);
let forty_two: u32 = 52;
let is_in_w_cmp_closure = tree.contains(
i,
Some(
&(|x_left: u32, x_right: u32| {
(x_left + forty_two).partial_cmp(&(x_right + forty_two))
}),
),
);
assert!(is_in_w_cmp_closure == is_in);
}
}
}
#[test]
fn test_avl_tree1() {
use crate::data_structures::Set;
const UNIV_MIN: u32 = 5000;
const UNIV_MAX: u32 = 5999;
const UNIV_SIZE: u32 = UNIV_MAX - UNIV_MIN + 1;
let mut tree = AVLTree::<u32>::new(0);
let mut should_be_in_tree = Set::<u32>::empty();
for i in UNIV_MIN..UNIV_MAX {
if i % 3 != 0 {
continue;
}
let was_added = tree.insert::<fn(u32, u32) -> Option<Ordering>>(i, None);
should_be_in_tree.insert(i);
assert!(was_added == true);
avl_tree_test_utils::check_tree(&tree, &should_be_in_tree, UNIV_MIN, UNIV_MAX);
}
for i in UNIV_MIN + UNIV_SIZE / 4..UNIV_MIN + 3 * (UNIV_SIZE / 4) {
let was_removed = tree.delete::<fn(u32, u32) -> Option<Ordering>>(i, None);
let should_have_been_removed = should_be_in_tree.contains(i);
assert!(was_removed == should_have_been_removed);
should_be_in_tree.delete(i);
avl_tree_test_utils::check_tree(&tree, &should_be_in_tree, UNIV_MIN, UNIV_MAX);
}
for i in UNIV_MIN..UNIV_MIN + UNIV_SIZE / 4 {
if i % 3 != 0 {
continue;
}
let was_added = tree.insert::<fn(u32, u32) -> Option<Ordering>>(i, None);
let should_have_been_added = !should_be_in_tree.contains(i);
assert!(was_added == should_have_been_added);
should_be_in_tree.insert(i);
avl_tree_test_utils::check_tree(&tree, &should_be_in_tree, UNIV_MIN, UNIV_MAX);
}
for ir in UNIV_MIN..UNIV_MAX {
let i = UNIV_MIN + (UNIV_MAX - ir);
let was_removed = tree.delete::<fn(u32, u32) -> Option<Ordering>>(i, None);
let should_have_been_removed = should_be_in_tree.contains(i);
assert!(was_removed == should_have_been_removed);
should_be_in_tree.delete(i);
avl_tree_test_utils::check_tree(&tree, &should_be_in_tree, UNIV_MIN, UNIV_MAX);
}
assert!(should_be_in_tree.is_empty());
assert!(tree.count() == 0);
for i in UNIV_MIN + 10..UNIV_MIN + 100 {
assert!(should_be_in_tree.is_empty());
assert!(tree.count() == 0);
tree.delete::<fn(u32, u32) -> Option<Ordering>>(i, None);
avl_tree_test_utils::check_tree(&tree, &should_be_in_tree, UNIV_MIN, UNIV_MAX);
}
assert!(tree.root == AVL_NULL);
assert!(tree.freelist != AVL_NULL);
for e in &tree.pool {
assert!(e.tag == AVLTag::Free);
assert!(e.left == AVL_NULL || (e.left as usize) < tree.pool.len());
assert!(e.right == AVL_NULL);
assert!(e.item == 0);
}
let mut n_in_freelist = 0;
let mut cursor: u32 = tree.freelist;
while cursor != AVL_NULL {
assert!((cursor as usize) < tree.pool.len());
n_in_freelist += 1;
assert!(n_in_freelist < 100000 );
cursor = tree.pool[cursor as usize].left;
}
assert!(n_in_freelist == tree.pool.len());
}
#[test]
fn test_avl_tree2() {
use std::cmp::Ordering;
let mut tree = AVLTree::<u32>::new(0);
let nums = [31, 41, 59, 27, 14, 35, 62, 25, 18, 28, 45, 90, 61];
fn reverse_cmp(x: u32, y: u32) -> Option<Ordering> {
y.partial_cmp(&x)
}
for n in &nums {
let insert_happened = tree.insert(*n, Some(&reverse_cmp));
assert!(insert_happened == true);
}
for n in 0..100 {
let is_in = tree.contains(n, Some(&reverse_cmp));
let should_be_in = nums.iter().any(|m| n == *m);
assert!(is_in == should_be_in);
}
for n in 0..100 {
let remove_happened = tree.delete(n, Some(&reverse_cmp));
let remove_should_have_happened = nums.iter().any(|m| n == *m);
assert!(remove_happened == remove_should_have_happened);
}
assert!(tree.root == AVL_NULL);
assert!(tree.count() == 0);
}
#[test]
fn test_avl_tree_iter() {
let mut storage = Vec::new();
let tree = AVLTree::<u32>::new(0);
assert!(tree.iter(&mut storage).next().is_none());
const FROM: u32 = 0;
const TO: u32 = 10000;
let mut tree = AVLTree::<u32>::new(0);
for i in FROM..TO {
tree.insert(i, Some(&|a: u32, b: u32| a.partial_cmp(&b)));
}
let as_vec = tree.to_vec();
for (i, val) in tree.iter(&mut storage).enumerate() {
assert_eq!(as_vec[i], val, "not equal for i={}", i);
}
}