use core::fmt;
use std::borrow::BorrowMut;
use std::cmp::max;
use std::fmt::{Debug, Display};
use std::mem::{replace, swap};
use std::ops::Not;
use std::collections::HashSet;
use std::hash::Hash;
#[derive(Debug, PartialEq, Clone, Copy)]
#[repr(u8)]
pub enum Side {
Left = 0,
Right = 1,
}
impl Not for Side {
type Output = Self;
fn not(self) -> Self::Output {
match self {
Side::Left => Side::Right,
Side::Right => Side::Left
}
}
}
#[derive(Debug, Clone, PartialEq)]
struct Node<T: Clone + Ord + Eq + Debug + Display + Hash> {
children: [Tree<T>; 2],
value: T,
duplicates: HashSet<T>,
height: usize,
}
impl<T: Clone + Ord + Eq + Debug + Display + Hash> fmt::Pointer for Node<T> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let ptr = self as *const Self;
fmt::Pointer::fmt(&ptr, f)
}
}
impl<T: Clone + Ord + Eq + Debug + Display + Hash> fmt::Display for Node<T> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "{:?}", self)
}
}
type Tree<T> = Option<Box<Node<T>>>;
#[derive(Debug, PartialEq, Clone)]
pub struct AvlTree<T: Clone + Ord + Eq + Debug + Display + Hash> {
root: Tree<T>,
}
#[cfg(test)]
mod test_tree {
use super::*;
use std::cmp::Ordering;
#[derive(Clone, Eq, PartialEq, Debug, Hash)]
struct Position {
x: i32,
y: i32,
}
impl Ord for Position {
fn cmp(&self, other: &Self) -> Ordering {
self.x.cmp(&other.x)
}
}
impl PartialOrd for Position {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl fmt::Display for Position {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "\"{},{}\"", self.x, self.y)
}
}
const TEST_1: u64 = 42;
const TEST_2: u64 = 420;
const TEST_3: u64 = 66;
const TEST_4: u64 = 88;
const TEST_5: u64 = 99;
#[test]
fn test_create() {
let tree: AvlTree<u64> = AvlTree::new();
assert!(tree.root.is_none());
assert!(tree.is_empty())
}
#[test]
fn test_insert() {
let mut tree: AvlTree<u64> = AvlTree::new();
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&TEST_1);
assert!(res.is_ok());
assert!(!tree.is_empty());
assert!(tree.root.is_some());
assert_eq!(tree.root.unwrap().value, TEST_1);
}
#[test]
fn test_insert_twice() {
let mut tree: AvlTree<u64> = AvlTree::new();
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&TEST_1);
assert!(res.is_ok());
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&TEST_2);
assert!(res.is_ok());
assert!(!tree.is_empty());
assert!(tree.root.is_some());
assert_eq!(tree.root.as_ref().unwrap().value, TEST_1);
assert!(tree.root.as_ref().unwrap().children[Side::Right as usize].is_some());
assert!(tree.root.as_ref().unwrap().children[Side::Left as usize].is_none());
assert_eq!(tree.root.as_ref().unwrap().children[Side::Right as usize].as_ref().unwrap().value, TEST_2);
}
#[test]
fn test_insert_thrice() {
let mut tree: AvlTree<u64> = AvlTree::new();
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&TEST_1);
assert!(res.is_ok());
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&TEST_2);
assert!(res.is_ok());
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&TEST_3);
assert!(res.is_ok());
assert!(!tree.is_empty());
assert!(tree.root.is_some());
assert_eq!(tree.root.as_ref().unwrap().value, TEST_3);
assert!(tree.root.as_ref().unwrap().children[Side::Right as usize].is_some());
assert_eq!(tree.root.as_ref().unwrap().children[Side::Right as usize].as_ref().unwrap().value, TEST_2);
assert!(tree.root.as_ref().unwrap().children[Side::Left as usize].is_some());
assert_eq!(tree.root.as_ref().unwrap().children[Side::Left as usize].as_ref().unwrap().value, TEST_1);
}
#[test]
fn test_contains() {
let mut tree: AvlTree<u64> = AvlTree::new();
tree.insert(&TEST_1).expect("Insert failed")
.insert(&TEST_2).expect("Insert failed")
.insert(&TEST_3).expect("Insert failed")
.insert(&TEST_4).expect("Insert failed");
assert!(tree.contains(&TEST_1));
assert!(tree.contains(&TEST_2));
assert!(tree.contains(&TEST_3));
assert!(tree.contains(&TEST_4));
assert!(!tree.contains(&TEST_5));
tree.insert(&TEST_5).expect("Insert failed");
assert!(tree.contains(&TEST_5));
}
#[test]
fn test_insert_complex() {
let mut tree: AvlTree<u64> = AvlTree::new();
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&1);
assert!(res.is_ok());
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&2);
assert!(res.is_ok());
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&3);
assert!(res.is_ok());
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&4);
assert!(res.is_ok());
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&5);
assert!(res.is_ok());
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&6);
assert!(res.is_ok());
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&7);
assert!(res.is_ok());
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&8);
assert!(res.is_ok());
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&9);
assert!(res.is_ok());
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&10);
assert!(res.is_ok());
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&11);
assert!(res.is_ok());
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&12);
assert!(res.is_ok());
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&13);
assert!(res.is_ok());
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&14);
assert!(res.is_ok());
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&15);
assert!(res.is_ok());
assert!(!tree.is_empty());
assert_eq!(tree.root.unwrap().height, 4)
}
#[test]
fn test_insert_heap_var() {
let mut tree: AvlTree<u64> = AvlTree::new();
{
let value: u64 = 67;
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&value);
assert!(res.is_ok());
drop(value);
}
assert!(!tree.is_empty());
assert_eq!(tree.root.unwrap().value, 67)
}
#[test]
fn test_delete_heap() {
let mut tree: AvlTree<u64> = AvlTree::new();
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&TEST_1);
assert!(res.is_ok());
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&TEST_2);
assert!(res.is_ok());
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&TEST_3);
assert!(res.is_ok());
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&TEST_4);
assert!(res.is_ok());
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&TEST_5);
assert!(res.is_ok());
assert!(!tree.is_empty());
assert_eq!(tree.root.as_ref().unwrap().value, TEST_3);
tree.clear();
assert_eq!(tree.depth(), 0);
tree.delete();
}
#[test]
fn test_delete_complex() {
let mut tree: AvlTree<u64> = AvlTree::new();
{
let payload: u64 = 67;
let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&payload);
assert!(res.is_ok());
drop(payload);
}
assert!(!tree.is_empty());
assert_eq!(tree.root.as_ref().unwrap().value, 67);
tree.delete();
}
#[test]
fn test_height() {
let mut tree: AvlTree<u64> = AvlTree::new();
let _res = tree.insert(&TEST_1).expect("Failed insert")
.insert(&TEST_2).expect("Failed insert")
.insert(&TEST_3).expect("Failed insert")
.insert(&TEST_4).expect("Failed insert")
.insert(&TEST_5).expect("Failed insert");
assert_eq!(tree.height(), 3);
}
#[test]
fn test_balancing() {
let tree: AvlTree<u64> = AvlTree::new();
assert!(tree.is_balanced());
tree.delete();
let mut tree: AvlTree<u64> = AvlTree::new();
let _res = tree.insert(&TEST_1).expect("Failed insert")
.insert(&TEST_2).expect("Failed insert")
.insert(&TEST_3).expect("Failed insert")
.insert(&TEST_4).expect("Failed insert")
.insert(&TEST_5).expect("Failed insert");
assert!(tree.is_correct());
assert!(tree.is_balanced());
}
#[test]
fn test_remove() {
let mut tree: AvlTree<u64> = AvlTree::new();
let _res = tree.insert(&TEST_1).expect("Failed insert")
.insert(&TEST_2).expect("Failed insert")
.insert(&TEST_3).expect("Failed insert")
.insert(&TEST_4).expect("Failed insert")
.insert(&TEST_5).expect("Failed insert");
assert!(tree.is_correct());
assert!(tree.is_balanced());
assert_eq!(tree.height(), 3);
let res: Result<&mut AvlTree<u64>, &str> = tree.remove(&TEST_1);
assert!(res.is_ok());
assert_eq!(tree.height(), 3);
assert!(tree.is_balanced());
let res: Result<&mut AvlTree<u64>, &str> = tree.remove(&TEST_2);
assert!(res.is_ok());
assert_eq!(tree.height(), 2);
assert!(tree.is_balanced());
let res: Result<&mut AvlTree<u64>, &str> = tree.remove(&TEST_2);
assert!(res.is_err());
assert_eq!(tree.height(), 2);
assert!(tree.is_balanced());
let _res = tree.remove(&TEST_3).expect("Failed removed");
let _res = tree.remove(&TEST_4).expect("Failed removed");
let _res = tree.remove(&TEST_5).expect("Failed removed");
assert_eq!(tree.height(), 0);
}
#[test]
fn test_min_max() {
let mut tree: AvlTree<u64> = AvlTree::new();
let _res = tree.insert(&TEST_1).expect("Failed insert")
.insert(&TEST_2).expect("Failed insert")
.insert(&TEST_3).expect("Failed insert")
.insert(&TEST_4).expect("Failed insert")
.insert(&TEST_5).expect("Failed insert");
assert!(tree.min().is_some());
assert_eq!(tree.min().unwrap(), TEST_1);
assert!(tree.max().is_some());
assert_eq!(tree.max().unwrap(), TEST_2);
}
#[test]
fn test_width_count_depth() {
let mut tree: AvlTree<u64> = AvlTree::new();
let _res = tree.insert(&TEST_1).expect("Failed insert")
.insert(&TEST_2).expect("Failed insert")
.insert(&TEST_3).expect("Failed insert")
.insert(&TEST_4).expect("Failed insert")
.insert(&TEST_5).expect("Failed insert");
assert_eq!(tree.depth(), 3);
assert_eq!(tree.width(), 3);
assert_eq!(tree.count(), 5);
}
#[test]
fn test_get_set() {
let mut tree: AvlTree<Position> = AvlTree::new();
let _res = tree.insert(&Position { x: 1, y: 0 }).expect("Failed insert")
.insert(&Position { x: 2, y: 0 }).expect("Failed insert")
.insert(&Position { x: 3, y: 0 }).expect("Failed insert")
.insert(&Position { x: 4, y: 0 }).expect("Failed insert")
.insert(&Position { x: 5, y: 1 }).expect("Failed insert")
.insert(&Position { x: 5, y: 2 }).expect("Failed insert")
.insert(&Position { x: 5, y: 3 }).expect("Failed insert")
.insert(&Position { x: 5, y: 4 }).expect("Failed insert")
.insert(&Position { x: 5, y: 5 }).expect("Failed insert");
assert_eq!(tree.get_set(&Position { x: 5, y: -1 }).len(), 5);
}
#[test]
fn test_remove_duplicates() {
let mut tree: AvlTree<Position> = AvlTree::new();
let _res = tree.insert(&Position { x: 1, y: 0 }).expect("Failed insert")
.insert(&Position { x: 2, y: 0 }).expect("Failed insert")
.insert(&Position { x: 3, y: 0 }).expect("Failed insert")
.insert(&Position { x: 5, y: 1 }).expect("Failed insert")
.insert(&Position { x: 5, y: 2 }).expect("Failed insert")
.insert(&Position { x: 5, y: 3 }).expect("Failed insert")
.insert(&Position { x: 5, y: 4 }).expect("Failed insert")
.insert(&Position { x: 5, y: 5 }).expect("Failed insert");
assert_eq!(tree.depth(), 3);
let res=tree.remove(&Position { x: 5, y: -1 });
assert!(res.is_err());
assert_eq!(res.unwrap_err(), "The value was not found");
assert_eq!(tree.depth(), 3);
let res=tree.remove(&Position { x: 5, y: 1 });
assert!(res.is_ok());
assert_eq!(tree.depth(), 3);
assert!(tree.contains(&Position { x: 5, y: 1 }));
assert!(!tree.contains_exact(&Position { x: 5, y: 1 }));
let res=tree.remove(&Position { x: 5, y: 2 });
assert!(res.is_ok());
assert_eq!(tree.depth(), 3);
let res=tree.remove(&Position { x: 5, y: 3 });
assert!(res.is_ok());
assert_eq!(tree.depth(), 3);
let res=tree.remove(&Position { x: 5, y: 4 });
assert!(res.is_ok());
assert_eq!(tree.depth(), 3);
let res=tree.remove(&Position { x: 5, y: 5 });
assert!(res.is_ok());
assert_eq!(tree.depth(), 2);
}
}
impl<'a, T: 'a + Clone + Ord + Eq + Debug + Display + Hash> AvlTree<T> {
pub fn new() -> Self {
AvlTree {
root: None
}
}
pub fn with(value: &T) -> Self {
AvlTree {
root: Node::create_tree(value)
}
}
pub fn insert(&mut self, value: &T) -> Result<&mut Self, &str> {
if self.root.is_none() {
self.root = Node::create_tree(value)
} else {
if !self.root.as_mut().unwrap().insert(value.clone()) {
return Err("Can not insert same value twice");
}
}
Ok(&mut *self)
}
pub fn delete(mut self) -> () {
if !self.root.is_none() {
Node::delete(self.root.borrow_mut())
}
drop(self);
}
pub fn clear(&mut self) -> () {
if !self.root.is_none() {
Node::delete(self.root.borrow_mut())
}
}
pub fn remove(&mut self, value: &T) -> Result<&mut Self, &str> {
if self.root.is_none() {
Err("You don't have any node in the tree")
} else {
let res: Option<T> = Node::remove(&mut self.root, value);
if res.is_none() {
Err("The value was not found")
} else if &res.unwrap() != value {
Err("ERROR ! The value removed was not the correct one.")
} else {
Ok(&mut *self)
}
}
}
pub fn print(&self, prettify: bool) -> () {
if self.root.is_none() {
println!("You don't have any node in the tree");
} else {
println!("{}", self.root.as_ref().unwrap().dump(prettify));
}
}
pub fn dump(&self, prettify: bool) -> Result<String, &str> {
if self.root.is_none() {
Err("You don't have any node in the tree")
} else {
Ok(self.root.as_ref().unwrap().dump(prettify))
}
}
pub fn get(&self, value: &T) -> Option<T> {
let tree: &Tree<T> = Node::get(&self.root, value);
return tree.as_ref().map_or(None, |x| Some(x.value.clone()));
}
pub fn get_exact(&self, value: &T) -> Option<T> {
let set: HashSet<T> = self.get_set(value);
let value: Option<&T> = set.get(value);
return if value.is_none() { None } else { Some(value.unwrap().clone()) };
}
pub fn get_set(&self, value: &T) -> HashSet<T> {
let tree: &Tree<T> = Node::get(&self.root, value);
return if tree.is_none() {
HashSet::new()
} else {
let mut set: HashSet<T> = tree.as_ref().unwrap().duplicates.clone();
set.insert(tree.as_ref().unwrap().value.clone());
set
};
}
pub fn find(&self, value: &T) -> Result<Self, &str> {
let tree: &Tree<T> = Node::get(&self.root, value);
if tree.is_none() {
return Err("Not found");
}
return Ok(AvlTree {
root: tree.clone()
});
}
pub fn contains(&self, value: &T) -> bool {
Node::get(&self.root, value).is_some()
}
pub fn contains_exact(&self, value: &T) -> bool {
let res: HashSet<T> = self.get_set(value);
return res.contains(value);
}
pub fn is_empty(&self) -> bool {
self.root.is_none()
}
pub fn fail(&mut self) -> Result<&mut Self, &str> {
Err("Oups, I always fail")
}
pub fn works(&mut self) -> Result<&mut Self, &str> {
Ok(&mut *self)
}
pub fn height(&self) -> usize {
self.root.as_ref().map_or(0, |node: &Box<Node<T>>| node.height())
}
pub fn depth(&self) -> usize {
self.root.as_ref().map_or(0, |node: &Box<Node<T>>| node.depth())
}
pub fn width(&self) -> usize {
self.root.as_ref().map_or(0, |node: &Box<Node<T>>| node.width())
}
pub fn count(&self) -> usize {
self.root.as_ref().map_or(0, |node: &Box<Node<T>>| node.count())
}
pub fn min(&self) -> Option<T> {
self.root.as_ref().map_or(None, |node: &Box<Node<T>>| Some(node.min().clone()))
}
pub fn max(&self) -> Option<T> {
self.root.as_ref().map_or(None, |node: &Box<Node<T>>| Some(node.max().clone()))
}
pub fn is_balanced(&self) -> bool {
self.root.as_ref().map_or(true, |node: &Box<Node<T>>| node.is_balanced())
}
pub fn is_correct(&self) -> bool {
self.root.as_ref().map_or(true, |node: &Box<Node<T>>| node.sanity_check())
}
}
#[cfg(test)]
mod test_node {
use super::*;
const TEST_1: u64 = 42;
const TEST_2: u64 = 420;
const TEST_3: u64 = 66;
const TEST_4: u64 = 88;
const TEST_5: u64 = 99;
#[test]
fn test_side() {
assert_eq!(Side::Left as u8, 0);
assert_eq!(Side::Right as u8, 1);
assert_eq!(!Side::Left, Side::Right);
assert_eq!(!Side::Right, Side::Left);
assert_eq!(!!Side::Right, Side::Right);
}
#[test]
fn test_create() {
let tree: Option<Box<Node<u64>>> = Some(Box::new(Node {
children: [
Some(Box::new(Node {
children: [None, None],
value: TEST_2,
duplicates: HashSet::with_capacity(0),
height: 1,
})),
None
],
value: TEST_1,
duplicates: HashSet::with_capacity(0),
height: 2,
}));
let ref_tree: Option<&Box<Node<u64>>> = tree.as_ref();
assert!(ref_tree.is_some());
assert_eq!(ref_tree.unwrap().height, 2);
assert_eq!(ref_tree.unwrap().value, TEST_1);
assert_eq!(ref_tree.unwrap().children.len(), 2);
assert_eq!(ref_tree.unwrap().children[1], None);
assert!(ref_tree.unwrap().children[0].is_some());
assert_eq!(ref_tree.unwrap().children[0].as_ref().unwrap().value, TEST_2);
assert_eq!(ref_tree.unwrap().children[0].as_ref().unwrap().height, 1);
}
#[test]
fn test_sanity_check() {
let tree: Option<Box<Node<u64>>> = Some(Box::new(Node {
children: [
Some(Box::new(Node {
children: [None, None],
value: TEST_2,
duplicates: HashSet::with_capacity(0),
height: 1,
})),
Some(Box::new(Node {
children: [None, None],
value: TEST_3,
duplicates: HashSet::with_capacity(0),
height: 1,
})),
],
value: TEST_1,
duplicates: HashSet::with_capacity(0),
height: 2,
}));
let ref_tree: Option<&Box<Node<u64>>> = tree.as_ref();
assert!(ref_tree.is_some());
assert_eq!(ref_tree.unwrap().sanity_check(), true);
assert_eq!(ref_tree.unwrap().is_balanced(), true);
let tree: Option<Box<Node<u64>>> = Some(Box::new(Node {
children: [
Some(Box::new(Node {
children: [None, None],
value: TEST_2,
duplicates: HashSet::with_capacity(0),
height: 1,
})),
Some(Box::new(Node {
children: [None, None],
value: TEST_3,
duplicates: HashSet::with_capacity(0),
height: 2,
})),
],
value: TEST_1,
duplicates: HashSet::with_capacity(0),
height: 2,
}));
let ref_tree: Option<&Box<Node<u64>>> = tree.as_ref();
assert!(ref_tree.is_some());
assert_eq!(ref_tree.unwrap().sanity_check(), false);
assert_eq!(ref_tree.unwrap().is_balanced(), true);
let tree: Option<Box<Node<u64>>> = Some(Box::new(Node {
children: [
Some(Box::new(Node {
children: [Some(Box::new(Node {
children: [None, None],
value: TEST_3,
duplicates: HashSet::with_capacity(0),
height: 1,
})), None],
value: TEST_2,
duplicates: HashSet::with_capacity(0),
height: 2,
})),
None,
],
value: TEST_1,
duplicates: HashSet::with_capacity(0),
height: 3,
}));
let ref_tree: Option<&Box<Node<u64>>> = tree.as_ref();
assert!(ref_tree.is_some());
assert_eq!(ref_tree.unwrap().sanity_check(), true);
assert_eq!(ref_tree.unwrap().is_balanced(), false);
assert_eq!(ref_tree.unwrap().depth(), ref_tree.unwrap().height);
let tree: Option<Box<Node<u64>>> = Some(Box::new(Node {
children: [
Some(Box::new(Node {
children: [Some(Box::new(Node {
children: [None, None],
value: TEST_3,
duplicates: HashSet::with_capacity(0),
height: 1,
})), None],
value: TEST_2,
duplicates: HashSet::with_capacity(0),
height: 22121,
})),
None,
],
value: TEST_1,
duplicates: HashSet::with_capacity(0),
height: 3,
}));
let ref_tree: Option<&Box<Node<u64>>> = tree.as_ref();
assert!(ref_tree.is_some());
assert_eq!(ref_tree.unwrap().sanity_check(), false);
assert_eq!(ref_tree.unwrap().is_balanced(), false);
assert_eq!(ref_tree.unwrap().depth(), ref_tree.unwrap().height)
}
#[test]
fn test_rotate_right() {
let mut tree: Option<Box<Node<u64>>> = Some(Box::new(Node {
children: [
Some(Box::new(Node {
children: [Some(Box::new(Node {
children: [None, None],
value: TEST_4,
duplicates: HashSet::with_capacity(0),
height: 1,
})), Some(Box::new(Node {
children: [None, None],
value: TEST_5,
duplicates: HashSet::with_capacity(0),
height: 1,
}))],
value: TEST_2,
duplicates: HashSet::with_capacity(0),
height: 2,
})),
Some(Box::new(Node {
children: [None, None],
value: TEST_3,
duplicates: HashSet::with_capacity(0),
height: 1,
})),
],
value: TEST_1,
duplicates: HashSet::with_capacity(0),
height: 3,
}));
let ref_tree: &Box<Node<u64>> = tree.as_ref().unwrap();
assert_eq!(ref_tree.value, TEST_1);
assert_eq!(ref_tree.children[Side::Left as usize].as_ref().unwrap().value, TEST_2);
assert_eq!(ref_tree.children[Side::Left as usize].as_ref().unwrap().children[Side::Left as usize].as_ref().unwrap().value, TEST_4);
assert_eq!(ref_tree.children[Side::Left as usize].as_ref().unwrap().children[Side::Right as usize].as_ref().unwrap().value, TEST_5);
assert_eq!(ref_tree.children[Side::Right as usize].as_ref().unwrap().value, TEST_3);
let res: bool = tree.as_mut().unwrap().rotate(Side::Right);
assert!(res);
let ref_tree: &Box<Node<u64>> = tree.as_ref().unwrap();
assert_eq!(ref_tree.value, TEST_2);
assert_eq!(ref_tree.children[Side::Left as usize].as_ref().unwrap().value, TEST_4);
assert_eq!(ref_tree.children[Side::Right as usize].as_ref().unwrap().value, TEST_1);
assert_eq!(ref_tree.children[Side::Right as usize].as_ref().unwrap().children[Side::Left as usize].as_ref().unwrap().value, TEST_5);
assert_eq!(ref_tree.children[Side::Right as usize].as_ref().unwrap().children[Side::Right as usize].as_ref().unwrap().value, TEST_3);
}
#[test]
fn test_rotate_left() {
let mut tree: Option<Box<Node<u64>>> = Some(Box::new(Node {
children: [
Some(Box::new(Node {
children: [None, None],
value: TEST_2,
duplicates: HashSet::with_capacity(0),
height: 1,
})),
Some(Box::new(Node {
children: [Some(Box::new(Node {
children: [None, None],
value: TEST_4,
duplicates: HashSet::with_capacity(0),
height: 1,
})), Some(Box::new(Node {
children: [None, None],
value: TEST_5,
duplicates: HashSet::with_capacity(0),
height: 1,
}))],
value: TEST_3,
duplicates: HashSet::with_capacity(0),
height: 2,
})),
],
value: TEST_1,
duplicates: HashSet::with_capacity(0),
height: 3,
}));
let ref_tree: &Box<Node<u64>> = tree.as_ref().unwrap();
assert_eq!(ref_tree.value, TEST_1);
assert_eq!(ref_tree.children[Side::Left as usize].as_ref().unwrap().value, TEST_2);
assert_eq!(ref_tree.children[Side::Right as usize].as_ref().unwrap().value, TEST_3);
assert_eq!(ref_tree.children[Side::Right as usize].as_ref().unwrap().children[Side::Left as usize].as_ref().unwrap().value, TEST_4);
assert_eq!(ref_tree.children[Side::Right as usize].as_ref().unwrap().children[Side::Right as usize].as_ref().unwrap().value, TEST_5);
let res: bool = tree.as_mut().unwrap().rotate(Side::Left);
assert!(res);
let ref_tree: &Box<Node<u64>> = tree.as_ref().unwrap();
assert_eq!(ref_tree.value, TEST_3);
assert_eq!(ref_tree.children[Side::Left as usize].as_ref().unwrap().value, TEST_1);
assert_eq!(ref_tree.children[Side::Left as usize].as_ref().unwrap().children[Side::Left as usize].as_ref().unwrap().value, TEST_2);
assert_eq!(ref_tree.children[Side::Left as usize].as_ref().unwrap().children[Side::Right as usize].as_ref().unwrap().value, TEST_4);
assert_eq!(ref_tree.children[Side::Right as usize].as_ref().unwrap().value, TEST_5);
}
#[test]
fn test_rotate_left_right() {
let mut tree: Option<Box<Node<u64>>> = Some(Box::new(Node {
children: [
Some(Box::new(Node {
children: [None, None],
value: TEST_2,
duplicates: HashSet::with_capacity(0),
height: 1,
})),
Some(Box::new(Node {
children: [Some(Box::new(Node {
children: [None, None],
value: TEST_4,
duplicates: HashSet::with_capacity(0),
height: 1,
})), Some(Box::new(Node {
children: [None, None],
value: TEST_5,
duplicates: HashSet::with_capacity(0),
height: 1,
}))],
value: TEST_3,
duplicates: HashSet::with_capacity(0),
height: 2,
})),
],
value: TEST_1,
duplicates: HashSet::with_capacity(0),
height: 3,
}));
let res: bool = tree.as_mut().unwrap().rotate(Side::Left);
assert!(res);
let res: bool = tree.as_mut().unwrap().rotate(Side::Right);
assert!(res);
let ref_tree: &Box<Node<u64>> = tree.as_ref().unwrap();
assert_eq!(ref_tree.value, TEST_1);
assert_eq!(ref_tree.children[Side::Left as usize].as_ref().unwrap().value, TEST_2);
assert_eq!(ref_tree.children[Side::Right as usize].as_ref().unwrap().value, TEST_3);
assert_eq!(ref_tree.children[Side::Right as usize].as_ref().unwrap().children[Side::Left as usize].as_ref().unwrap().value, TEST_4);
assert_eq!(ref_tree.children[Side::Right as usize].as_ref().unwrap().children[Side::Right as usize].as_ref().unwrap().value, TEST_5);
}
#[test]
fn test_rotate_right_left() {
let mut tree: Option<Box<Node<u64>>> = Some(Box::new(Node {
children: [
Some(Box::new(Node {
children: [Some(Box::new(Node {
children: [None, None],
value: TEST_4,
duplicates: HashSet::with_capacity(0),
height: 1,
})), Some(Box::new(Node {
children: [None, None],
value: TEST_5,
duplicates: HashSet::with_capacity(0),
height: 1,
}))],
value: TEST_2,
duplicates: HashSet::with_capacity(0),
height: 2,
})),
Some(Box::new(Node {
children: [None, None],
value: TEST_3,
duplicates: HashSet::with_capacity(0),
height: 1,
})),
],
value: TEST_1,
duplicates: HashSet::with_capacity(0),
height: 3,
}));
let res: bool = tree.as_mut().unwrap().rotate(Side::Right);
assert!(res);
let res: bool = tree.as_mut().unwrap().rotate(Side::Left);
assert!(res);
let ref_tree: &Box<Node<u64>> = tree.as_ref().unwrap();
assert_eq!(ref_tree.value, TEST_1);
assert_eq!(ref_tree.children[Side::Left as usize].as_ref().unwrap().value, TEST_2);
assert_eq!(ref_tree.children[Side::Left as usize].as_ref().unwrap().children[Side::Left as usize].as_ref().unwrap().value, TEST_4);
assert_eq!(ref_tree.children[Side::Left as usize].as_ref().unwrap().children[Side::Right as usize].as_ref().unwrap().value, TEST_5);
assert_eq!(ref_tree.children[Side::Right as usize].as_ref().unwrap().value, TEST_3);
}
#[test]
fn test_rebalance() {
let mut tree: Option<Box<Node<u64>>> = Some(Box::new(Node {
children: [
Some(Box::new(Node {
children: [Some(Box::new(Node {
children: [None, None],
value: TEST_3,
duplicates: HashSet::with_capacity(0),
height: 1,
})), None],
value: TEST_2,
duplicates: HashSet::with_capacity(0),
height: 2,
})),
None,
],
value: TEST_1,
duplicates: HashSet::with_capacity(0),
height: 3,
}));
let ref_tree: Option<&Box<Node<u64>>> = tree.as_ref();
assert!(ref_tree.is_some());
assert_eq!(ref_tree.unwrap().sanity_check(), true);
assert_eq!(ref_tree.unwrap().is_balanced(), false);
assert_eq!(ref_tree.unwrap().depth(), ref_tree.unwrap().height);
let res: bool = tree.as_mut().unwrap().rebalance();
assert!(res);
let ref_tree: &Box<Node<u64>> = tree.as_ref().unwrap();
assert_eq!(ref_tree.sanity_check(), true);
assert_eq!(ref_tree.is_balanced(), true);
assert_eq!(ref_tree.depth(), ref_tree.height);
}
#[test]
fn test_rebalance_twice() {
let mut tree: Option<Box<Node<u64>>> = Some(Box::new(Node {
children: [
Some(Box::new(Node {
children: [Some(Box::new(Node {
children: [None, None],
value: TEST_3,
duplicates: HashSet::with_capacity(0),
height: 1,
})), None],
value: TEST_2,
duplicates: HashSet::with_capacity(0),
height: 2,
})),
None,
],
value: TEST_1,
duplicates: HashSet::with_capacity(0),
height: 3,
}));
let res: bool = tree.as_mut().unwrap().rebalance();
assert!(res);
let res: bool = tree.as_mut().unwrap().rebalance();
assert!(!res);
}
#[test]
fn test_create_tree() {
let tree: Tree<u64> = Node::create_tree(&TEST_1);
let ref_tree: Option<&Box<Node<u64>>> = tree.as_ref();
assert!(ref_tree.is_some());
assert_eq!(ref_tree.unwrap().value, TEST_1);
assert_eq!(ref_tree.unwrap().height, 1);
assert!(ref_tree.unwrap().children[Side::Left as usize].is_none());
assert!(ref_tree.unwrap().children[Side::Right as usize].is_none());
}
#[test]
fn test_create_node() {
let node: Node<u64> = Node::create_node(&TEST_1);
assert_eq!(node.value, TEST_1);
assert_eq!(node.height, 1);
assert!(node.children[Side::Left as usize].is_none());
assert!(node.children[Side::Right as usize].is_none());
}
#[test]
fn test_insert() {
let mut node: Node<u64> = Node::create_node(&1);
let res: bool = node.insert(2);
assert!(res);
let res: bool = node.insert(3);
assert!(res);
let res: bool = node.insert(4);
assert!(res);
let res: bool = node.insert(5);
assert!(res);
let res: bool = node.insert(6);
assert!(res);
let res: bool = node.insert(7);
assert!(res);
let res: bool = node.insert(8);
assert!(res);
assert_eq!(node.height, 4)
}
#[test]
fn test_width_depth_count() {
let mut node: Node<u64> = Node::create_node(&1);
assert_eq!(node.count(), 1);
assert_eq!(node.depth(), 1);
assert_eq!(node.width(), 1);
let res: bool = node.insert(2);
assert!(res);
assert_eq!(node.count(), 2);
assert_eq!(node.depth(), 2);
assert_eq!(node.width(), 2);
let res: bool = node.insert(3);
assert!(res);
assert_eq!(node.count(), 3);
assert_eq!(node.depth(), 2);
assert_eq!(node.width(), 2);
let res: bool = node.insert(4);
assert!(res);
assert_eq!(node.count(), 4);
assert_eq!(node.depth(), 3);
assert_eq!(node.width(), 3);
let res: bool = node.insert(5);
assert!(res);
assert_eq!(node.count(), 5);
assert_eq!(node.depth(), 3);
assert_eq!(node.width(), 3);
let res: bool = node.insert(6);
assert!(res);
assert_eq!(node.count(), 6);
assert_eq!(node.depth(), 3);
assert_eq!(node.width(), 4);
let res: bool = node.insert(7);
assert!(res);
assert_eq!(node.count(), 7);
assert_eq!(node.depth(), 3);
assert_eq!(node.width(), 4);
let res: bool = node.insert(8);
assert!(res);
assert_eq!(node.count(), 8);
assert_eq!(node.depth(), 4);
assert_eq!(node.width(), 5);
let res: bool = node.insert(9);
assert!(res);
assert_eq!(node.count(), 9);
assert_eq!(node.depth(), 4);
assert_eq!(node.width(), 5);
let res: bool = node.insert(10);
assert!(res);
assert_eq!(node.count(), 10);
assert_eq!(node.depth(), 4);
assert_eq!(node.width(), 6);
let res: bool = node.insert(11);
assert!(res);
assert_eq!(node.count(), 11);
assert_eq!(node.depth(), 4);
assert_eq!(node.width(), 6);
let res: bool = node.insert(12);
assert!(res);
assert_eq!(node.count(), 12);
assert_eq!(node.depth(), 4);
assert_eq!(node.width(), 7);
let res: bool = node.insert(13);
assert!(res);
assert_eq!(node.count(), 13);
assert_eq!(node.depth(), 4);
assert_eq!(node.width(), 7);
let res: bool = node.insert(14);
assert!(res);
assert_eq!(node.count(), 14);
assert_eq!(node.depth(), 4);
assert_eq!(node.width(), 8);
let res: bool = node.insert(15);
assert!(res);
assert_eq!(node.count(), 15);
assert_eq!(node.depth(), 4);
assert_eq!(node.width(), 8);
let res: bool = node.insert(16);
assert!(res);
assert_eq!(node.count(), 16);
assert_eq!(node.depth(), 5);
assert_eq!(node.width(), 9);
}
#[test]
fn test_delete() {
let mut tree: Tree<u64> = Node::create_tree(&1);
let node: &mut Box<Node<u64>> = tree.as_mut().unwrap();
let res: bool = node.insert(2);
assert!(res);
let res: bool = node.insert(3);
assert!(res);
let res: bool = node.insert(4);
assert!(res);
let res: bool = node.insert(5);
assert!(res);
let res: bool = node.insert(6);
assert!(res);
let res: bool = node.insert(7);
assert!(res);
let res: bool = node.insert(8);
assert!(res);
assert_eq!(node.height, 4);
Node::delete(&mut tree);
}
#[test]
fn test_min_max() {
let mut tree: Tree<u64> = Node::create_tree(&TEST_1);
let node: &mut Box<Node<u64>> = tree.as_mut().unwrap();
let res: bool = node.insert(TEST_2);
assert!(res);
let res: bool = node.insert(TEST_3);
assert!(res);
let res: bool = node.insert(TEST_4);
assert!(res);
let res: bool = node.insert(TEST_4);
assert!(res);
assert_eq!(node.max(), &TEST_2);
assert_eq!(node.min(), &TEST_1);
}
#[test]
fn test_dump() {
#[derive(Clone, Ord, PartialOrd, Eq, PartialEq, Debug, Hash)]
struct Position {
x: i32,
}
impl fmt::Display for Position {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "\"{}\"", self.x)
}
}
let mut tree: Tree<Position> = Node::create_tree(&Position {
x: 10
});
let node: &mut Box<Node<Position>> = tree.as_mut().unwrap();
assert_eq!(node.dump(false), "[\"10\",null,null]");
let res: bool = node.insert(Position {
x: 20
});
assert!(res);
let res: bool = node.insert(Position {
x: 30
});
assert!(res);
let res: bool = node.insert(Position {
x: 50
});
assert!(res);
let res: bool = node.insert(Position {
x: 40
});
assert!(res);
assert_eq!(node.dump(false), "[\"20\",[\"10\",null,null],[\"40\",[\"30\",null,null],[\"50\",null,null]]]");
assert_eq!(node.dump(true), r#"[
"20",
[
"10",
null,
null
],
[
"40",
[
"30",
null,
null
],
[
"50",
null,
null
]
]
]"#)
}
#[test]
fn test_remove_min() {
let mut tree: Tree<u64> = Node::create_tree(&TEST_1);
let node: &mut Box<Node<u64>> = tree.as_mut().unwrap();
let res: bool = node.insert(TEST_2);
assert!(res);
let res: bool = node.insert(TEST_3);
assert!(res);
let res: bool = node.insert(TEST_4);
assert!(res);
assert_eq!(tree.as_ref().unwrap().height, 3);
assert!(tree.as_ref().unwrap().is_balanced());
let res: u64 = Node::remove_min(&mut tree);
assert_eq!(res, TEST_1);
assert_eq!(tree.as_ref().unwrap().height, 2);
assert!(tree.as_ref().unwrap().is_balanced());
}
#[test]
fn test_remove() {
let mut tree: Tree<u64> = Node::create_tree(&TEST_1);
let node: &mut Box<Node<u64>> = tree.as_mut().unwrap();
let res: bool = node.insert(TEST_2);
assert!(res);
let res: bool = node.insert(TEST_3);
assert!(res);
let res: bool = node.insert(TEST_4);
assert!(res);
assert_eq!(tree.as_ref().unwrap().height, 3);
assert!(tree.as_ref().unwrap().is_balanced());
let res: Option<u64> = Node::remove(&mut tree, &TEST_4);
assert!(res.is_some());
assert_eq!(res.unwrap(), TEST_4);
assert_eq!(tree.as_ref().unwrap().height, 2);
assert!(tree.as_ref().unwrap().is_balanced());
}
#[test]
fn test_remove_complex() {
let mut tree: Tree<u64> = Node::create_tree(&TEST_1);
let node: &mut Box<Node<u64>> = tree.as_mut().unwrap();
let res: bool = node.insert(TEST_2);
assert!(res);
let res: bool = node.insert(TEST_3);
assert!(res);
let res: bool = node.insert(TEST_4);
assert!(res);
assert_eq!(tree.as_ref().unwrap().height, 3);
assert!(tree.as_ref().unwrap().is_balanced());
let res: Option<u64> = Node::remove(&mut tree, &TEST_4);
assert!(res.is_some());
assert_eq!(res.unwrap(), TEST_4);
assert_eq!(tree.as_ref().unwrap().height, 2);
assert!(tree.as_ref().unwrap().is_balanced());
let res: Option<u64> = Node::remove(&mut tree, &TEST_4);
assert!(res.is_none());
let res: Option<u64> = Node::remove(&mut tree, &TEST_2);
assert!(res.is_some());
assert_eq!(res.unwrap(), TEST_2);
let res: Option<u64> = Node::remove(&mut tree, &TEST_1);
assert!(res.is_some());
assert_eq!(res.unwrap(), TEST_1);
let res: Option<u64> = Node::remove(&mut tree, &TEST_3);
assert!(res.is_some());
assert_eq!(res.unwrap(), TEST_3);
assert!(tree.as_ref() == None)
}
#[test]
fn test_get() {
let mut tree: Tree<u64> = Node::create_tree(&TEST_1);
let node: &mut Box<Node<u64>> = tree.as_mut().unwrap();
let res: bool = node.insert(TEST_2);
assert!(res);
let res: bool = node.insert(TEST_3);
assert!(res);
let res: bool = node.insert(TEST_4);
assert!(res);
let tree: &Tree<u64> = Node::get(&tree, &TEST_2);
assert!(tree.is_some());
assert_eq!(tree.as_ref().unwrap().value, TEST_2);
assert_eq!(tree.as_ref().unwrap().height, 2);
}
#[test]
fn test_get_missing() {
let mut tree: Tree<u64> = Node::create_tree(&TEST_1);
let node: &mut Box<Node<u64>> = tree.as_mut().unwrap();
let res: bool = node.insert(TEST_2);
assert!(res);
let res: bool = node.insert(TEST_3);
assert!(res);
let res: bool = node.insert(TEST_4);
assert!(res);
let tree: &Tree<u64> = Node::get(&tree, &TEST_5);
assert!(tree.is_none());
}
#[test]
fn test_get_remove() {
let mut tree: Tree<u64> = Node::create_tree(&TEST_1);
let node: &mut Box<Node<u64>> = tree.as_mut().unwrap();
let res: bool = node.insert(TEST_2);
assert!(res);
let res: bool = node.insert(TEST_3);
assert!(res);
let tree2: &Tree<u64> = Node::get(&tree, &TEST_2);
assert!(tree2.is_some());
assert_eq!(tree2.as_ref().unwrap().value, TEST_2);
let old: u64 = tree2.as_ref().unwrap().value.clone();
let removed: Option<u64> = Node::remove(&mut tree, &TEST_2);
assert!(removed.is_some());
assert_eq!(removed.unwrap(), TEST_2);
assert_eq!(old, TEST_2);
let removed: Option<u64> = Node::remove(&mut tree, &TEST_2);
assert!(removed.is_none());
let tree2: &Tree<u64> = Node::get(&tree, &TEST_2);
assert!(tree2.is_none());
}
#[test]
fn test_get_not_modifying() {
let mut tree: Tree<u64> = Node::create_tree(&TEST_1);
let node: &mut Box<Node<u64>> = tree.as_mut().unwrap();
let res: bool = node.insert(TEST_2);
assert!(res);
let res: bool = node.insert(TEST_3);
assert!(res);
let tree_get: &Tree<u64> = Node::get(&tree, &TEST_3);
assert!(tree_get.is_some());
assert_eq!(tree_get.as_ref().unwrap().value, TEST_3);
let mut tree2: Tree<u64> = tree_get.clone();
let removed: Option<u64> = Node::remove(&mut tree, &TEST_2);
assert!(removed.is_some());
assert_eq!(removed.unwrap(), TEST_2);
let removed2: Option<u64> = Node::remove(&mut tree2, &TEST_2);
assert!(removed2.is_some());
assert_eq!(removed2.unwrap(), TEST_2);
assert_eq!(tree2, tree);
let l_ptr: String = format!("{:018p}", tree.unwrap());
let r_ptr: String = format!("{:018p}", tree2.unwrap());
assert_ne!(l_ptr, r_ptr);
}
}
impl<'a, T: 'a + Clone + Ord + Eq + Debug + Display + Hash> Node<T> {
fn insert(&mut self, new_value: T) -> bool {
if new_value <= self.value && self.value <= new_value {
if self.duplicates.contains(&new_value) {
return false;
}
self.duplicates.insert(new_value);
return true;
}
let mut res = true;
let target_node: &mut Tree<T> = if new_value <= self.value { &mut self.children[Side::Left as usize] } else { &mut self.children[Side::Right as usize] };
match target_node {
&mut Some(ref mut subnode) => {
res = subnode.insert(new_value);
}
&mut None => {
let new_node = Node { children: [None, None], value: new_value, duplicates: HashSet::with_capacity(0), height: 1 };
let boxed_node = Some(Box::new(new_node));
*target_node = boxed_node;
}
}
self.update_height();
self.rebalance();
res
}
fn create_tree(value: &T) -> Tree<T> {
Some(Box::new(Self::create_node(value)))
}
fn create_node(value: &T) -> Self {
Node {
children: [None, None],
value: value.clone(),
duplicates: HashSet::with_capacity(0),
height: 1,
}
}
fn delete(node: &mut Tree<T>) {
if node.is_some() {
Self::delete(node.as_mut().unwrap().children[Side::Left as usize].take().borrow_mut());
Self::delete(node.as_mut().unwrap().children[Side::Right as usize].take().borrow_mut());
node.as_mut().unwrap().duplicates.clear();
node.take();
}
}
fn remove_min(node: &mut Tree<T>) -> T {
if node.is_none() {
panic!("You should not pass a NULL in that function");
}
if node.as_ref().unwrap().children[Side::Left as usize].is_none() {
let right = node.as_mut().unwrap().children[Side::Right as usize].take();
return replace(node, right).unwrap().value;
}
let value: T = Self::remove_min(&mut node.as_mut().unwrap().children[Side::Left as usize]);
node.as_mut().unwrap().update_height();
node.as_mut().unwrap().rebalance();
return value;
}
fn remove(node: &mut Tree<T>, value: &T) -> Option<T> {
if node.is_some() {
return if &node.as_ref().unwrap().value <= value && value <= &node.as_ref().unwrap().value {
if &node.as_ref().unwrap().value == value && node.as_ref().unwrap().duplicates.is_empty() {
if node.as_ref().unwrap().children[Side::Right as usize].is_some() {
let value: T = Self::remove_min(&mut node.as_mut().unwrap().children[Side::Right as usize]);
let old: T = replace(&mut node.as_mut().unwrap().value, value);
node.as_mut().unwrap().rebalance();
Some(old)
} else {
let left: Tree<T> = node.as_mut().unwrap().children[Side::Left as usize].take();
let tree: Tree<T> = replace(node, left);
if node.is_some() {
node.as_mut().unwrap().rebalance();
}
tree.map_or(None, |node| Some(node.value))
}
} else {
if &node.as_ref().unwrap().value == value {
let new_value: Option<T> = node.as_ref().unwrap().duplicates.iter().next().cloned();
if new_value.is_none() {
return None;
}
let new_value: T = new_value.unwrap();
node.as_mut().unwrap().duplicates.remove(&new_value);
Some(replace(&mut node.as_mut().unwrap().value, new_value))
} else {
if node.as_mut().unwrap().duplicates.remove(&value){
Some(value.clone())
}else{
None
}
}
}
} else {
let target_node: &mut Tree<T> = if value <= &node.as_mut().unwrap().value { &mut node.as_mut().unwrap().children[Side::Left as usize] } else { &mut node.as_mut().unwrap().children[Side::Right as usize] };
let res: Option<T> = Self::remove(target_node, value);
node.as_mut().unwrap().rebalance();
res
};
}
return None;
}
fn get(tree: &'a Tree<T>, value: &T) -> &'a Tree<T> {
if tree.is_some() {
if &tree.as_ref().unwrap().value <= value && &tree.as_ref().unwrap().value >= value {
return tree;
}
return if value > &tree.as_ref().unwrap().value {
Node::get(&tree.as_ref().unwrap().children[Side::Right as usize], value)
} else {
Node::get(&tree.as_ref().unwrap().children[Side::Left as usize], value)
};
}
&None
}
fn left_height(&self) -> usize {
self.children[Side::Left as usize].as_ref().map_or(0, |left| left.height)
}
fn right_height(&self) -> usize {
self.children[Side::Right as usize].as_ref().map_or(0, |right| right.height)
}
fn update_height(&mut self) {
self.height = 1 + max(self.left_height(), self.right_height());
}
fn height(&self) -> usize {
self.height
}
fn dump(&self, prettify: bool) -> String {
self._dump(prettify,1)
}
fn _dump(&self, prettify: bool, height: usize)->String {
let mut pad = String::new();
if prettify {
pad = " ".repeat(height);
}
let mut string_node: String = format!("[{}{},{}", (if prettify { "\n".to_string() } else { String::new() }) + &*pad, self.value, (if prettify { "\n".to_string() } else { String::new() }) + &*pad);
if self.children[Side::Left as usize].is_some() {
string_node += &*self.children[Side::Left as usize].as_ref().unwrap()._dump(prettify, height+1);
} else {
string_node += "null";
}
if self.children[Side::Right as usize].is_some() {
string_node += &*(",".to_owned()+&( if prettify { "\n".to_string() + &*pad } else { String::new() }));
string_node += &*self.children[Side::Right as usize].as_ref().unwrap()._dump(prettify, height+1);
} else {
string_node+=",";
string_node += &*((if prettify { "\n".to_string() } else { String::new() }) + &*pad + "null");
}
return string_node + &*(if prettify { "\n".to_string() + &*( " ".repeat(max(height,1)-1)) } else { String::new() }) + "]";
}
fn sanity_check(&self) -> bool {
let mut is_correct: bool = self.height() == (1 + max(self.left_height(), self.right_height()));
if self.children[Side::Left as usize].is_some() {
is_correct &= self.children[Side::Left as usize].as_ref().unwrap().sanity_check();
}
if self.children[Side::Right as usize].is_some() {
is_correct &= self.children[Side::Right as usize].as_ref().unwrap().sanity_check();
}
return is_correct;
}
fn is_balanced(&self) -> bool {
let mut lh: usize = 0;
let mut lb: bool = true;
if self.children[Side::Left as usize].is_some() {
lh = self.children[Side::Left as usize].as_ref().unwrap().depth();
lb = self.children[Side::Left as usize].as_ref().unwrap().is_balanced();
}
let mut rh: usize = 0;
let mut rb: bool = true;
if self.children[Side::Right as usize].is_some() {
rh = self.children[Side::Right as usize].as_ref().unwrap().depth();
rb = self.children[Side::Right as usize].as_ref().unwrap().is_balanced();
}
let diff: usize;
if lh < rh {
diff = rh - lh;
} else {
diff = lh - rh;
}
if diff <= 1 && lb && rb {
return true;
}
return false;
}
fn depth(&self) -> usize {
let mut left: usize = 0;
if self.children[Side::Left as usize].is_some() {
left = self.children[Side::Left as usize].as_ref().unwrap().depth()
}
let mut right: usize = 0;
if self.children[Side::Right as usize].is_some() {
right = self.children[Side::Right as usize].as_ref().unwrap().depth()
}
return 1 + max(left, right);
}
fn balance_factor(&self) -> i8 {
let left_height = self.left_height();
let right_height = self.right_height();
if left_height >= right_height {
(left_height - right_height) as i8
} else {
-((right_height - left_height) as i8)
}
}
fn rotate(&mut self, side: Side) -> bool {
if self.children[!side as usize].is_none() {
return false;
}
let right_node: &mut Box<Node<T>> = self.children[!side as usize].as_mut().unwrap();
let right_left_tree = right_node.children[side as usize].take();
let right_right_tree = right_node.children[!side as usize].take();
let mut new_left_tree = replace(&mut self.children[!side as usize], right_right_tree);
swap(&mut self.value, &mut new_left_tree.as_mut().unwrap().value);
let left_tree = self.children[side as usize].take();
let new_left_node = new_left_tree.as_mut().unwrap();
new_left_node.children[!side as usize] = right_left_tree;
new_left_node.children[side as usize] = left_tree;
self.children[side as usize] = new_left_tree;
if let Some(node) = self.children[side as usize].as_mut() {
node.update_height();
}
self.update_height();
true
}
fn rebalance(&mut self) -> bool {
match self.balance_factor() {
-2 => {
let right_node = self.children[Side::Right as usize].as_mut().unwrap();
if right_node.balance_factor() == 1 {
right_node.rotate(Side::Right);
}
self.rotate(Side::Left);
true
}
2 => {
let left_node = self.children[Side::Left as usize].as_mut().unwrap();
if left_node.balance_factor() == -1 {
left_node.rotate(Side::Left);
}
self.rotate(Side::Right);
true
}
_ => {
self.update_height();
false
}
}
}
fn count(&self) -> usize {
let left: usize;
if self.children[Side::Left as usize].is_some() {
left = self.children[Side::Left as usize].as_ref().unwrap().count()
} else {
left = 0;
}
let right: usize;
if self.children[Side::Right as usize].is_some() {
right = self.children[Side::Right as usize].as_ref().unwrap().count()
} else {
right = 0;
}
return 1 + self.duplicates.len() + left + right;
}
fn max(&self) -> &T {
if self.children[Side::Right as usize].is_some() {
self.children[Side::Right as usize].as_ref().unwrap().max()
} else {
return &self.value;
}
}
fn min(&self) -> &T {
if self.children[Side::Left as usize].is_some() {
self.children[Side::Left as usize].as_ref().unwrap().min()
} else {
return &self.value;
}
}
fn width(&self) -> usize {
let left: usize;
if self.children[Side::Left as usize].is_some() {
left = self.children[Side::Left as usize].as_ref().unwrap().width()
} else {
left = 1;
}
let right: usize;
if self.children[Side::Right as usize].is_some() {
right = self.children[Side::Right as usize].as_ref().unwrap().width()
} else {
right = 1;
}
if self.children[Side::Left as usize].is_none() && self.children[Side::Right as usize].is_none() {
return 1;
}
return left + right;
}
}