extern crate num;
use std::collections::HashMap;
use std::isize;
use self::num::Bounded;
#[allow(dead_code)]
#[derive(Debug, Copy, Clone)]
enum Colour {
Red,
Black,
}
#[derive(Debug, Copy, Clone)]
struct Node<K, V>
where
K: Ord + Default + Bounded + Clone,
V: Default + Clone,
{
_key: K,
_colour: Colour,
_parent: isize,
_child_l: isize,
_child_r: isize,
_val: V,
_index: isize,
}
impl<K, V> Default for Node<K, V>
where
K: Ord + Default + Bounded + Clone,
V: Default + Clone,
{
fn default() -> Node<K, V> {
Node {
_key: Default::default(),
_colour: Colour::Red,
_parent: -1isize,
_child_l: -1isize,
_child_r: -1isize,
_val: Default::default(),
_index: -1isize,
}
}
}
#[derive(Clone)]
pub struct TreeRb<K, V>
where
K: Ord + Default + Bounded + Clone,
V: Default + Clone,
{
_root: isize,
_buf: Vec<Node<K, V>>,
_sentinil: Node<K, V>,
_freelist: Vec<isize>,
_leaf_remove_index: isize,
}
impl<K, V> TreeRb<K, V>
where
K: Ord + Default + Bounded + Clone,
V: Default + Clone,
{
pub fn new() -> TreeRb<K, V> {
TreeRb {
_root: -1isize,
_buf: vec![],
_sentinil: Node {
_colour: Colour::Black,
_parent: -1isize,
..Default::default()
},
_freelist: vec![],
_leaf_remove_index: -1isize,
}
}
pub fn len(&self) -> usize {
self._buf.len() - self._freelist.len()
}
pub fn len_freelist(&self) -> usize {
self._freelist.len()
}
pub fn is_empty(&self) -> bool {
self._buf.len() - self._freelist.len() == 0
}
pub fn insert(&mut self, key: K, val: V) -> Option<V> {
let mut x = self._root;
let mut prev = -1isize;
while x != -1 {
prev = x;
if key < self._buf[x as usize]._key {
x = self._buf[x as usize]._child_l;
} else if key > self._buf[x as usize]._key {
x = self._buf[x as usize]._child_r;
} else {
let val_prev = self._buf[prev as usize]._val.clone();
self._buf[prev as usize]._val = val;
return Some(val_prev);
}
}
let n_index = self._buf.len();
let n = Node {
_key: key.clone(),
_colour: Colour::Red,
_parent: prev,
_val: val,
_index: n_index as isize,
..Default::default()
};
if prev == -1 {
self._buf.push(n);
self._root = n_index as isize;
self.fixup_insert(n_index as isize);
None
} else if key < self._buf[prev as usize]._key {
self._buf.push(n);
self.connect_left(prev as isize, n_index as isize);
self.fixup_insert(n_index as isize);
None
} else {
self._buf.push(n);
self.connect_right(prev as isize, n_index as isize);
self.fixup_insert(n_index as isize);
None
}
}
pub fn remove(&mut self, key: &K) -> Option<V> {
if let Some(z) = self.get_index(key) {
let val = self.get_node(z)._val.clone();
#[allow(unused_assignments)]
let mut x = -1;
#[allow(unused_assignments)]
let mut x_p = -1;
let mut y = z;
let mut y_colour_orig = self.get_node(y)._colour;
self._leaf_remove_index = self._buf.len() as isize;
let mut leaf_dummy = Node {
_key: Bounded::max_value(),
_colour: Colour::Black,
_index: self._leaf_remove_index,
..Default::default()
};
self._buf.push(leaf_dummy);
if self.get_node(z)._child_l == -1 {
x = self.get_node(z)._child_r;
x_p = self.get_node(z)._parent;
if x == -1 {
let a = self._leaf_remove_index;
self.transplant(z, a);
} else {
self.transplant(z, x);
}
} else if self.get_node(z)._child_r == -1 {
x = self.get_node(z)._child_l;
x_p = self.get_node(z)._parent;
if x == -1 {
let a = self._leaf_remove_index;
self.transplant(z, a);
} else {
self.transplant(z, x);
}
} else {
let z_r = self.get_node(z)._child_r;
y = self.get_subtree_leftmost(z_r);
y_colour_orig = self.get_node(y)._colour;
x = self.get_node(y)._child_r;
x_p = y;
if x == -1 {
let a = self._leaf_remove_index;
self.connect_right(y, a);
}
if self.get_node(y)._parent == z {
self.get_node_mut(x)._parent = y;
} else {
if x == -1 {
let a = self._leaf_remove_index;
self.transplant(y, a);
} else {
self.transplant(y, x);
}
self.connect_right(y, z_r);
}
self.transplant(z, y);
let z_l = self.get_node(z)._child_l;
self.connect_left(y, z_l);
self.get_node_mut(y)._colour = self.get_node(z)._colour;
}
match y_colour_orig {
Colour::Black => {
if x == -1 {
x = self._leaf_remove_index;
} else {
self._leaf_remove_index = -1;
self._buf.pop();
}
self.fixup_remove(x);
if self._leaf_remove_index != -1 {
assert!(
self._buf.len() as isize == self._leaf_remove_index + 1,
"leaf dummy node not at back of buffer"
);
let leaf_p = self._buf[self._leaf_remove_index as usize]._parent;
let leaf_p_l = self.get_node(leaf_p)._child_l;
if leaf_p_l == self._leaf_remove_index {
self.get_node_mut(leaf_p)._child_l = -1;
}
let leaf_p_r = self.get_node(leaf_p)._child_r;
if leaf_p_r == self._leaf_remove_index {
self.get_node_mut(leaf_p)._child_r = -1;
}
let leaf_x_p_l = self.get_node(x_p)._child_l;
let leaf_x_p_r = self.get_node(x_p)._child_r;
if leaf_x_p_l == self._leaf_remove_index {
self.get_node_mut(leaf_p)._child_l = -1;
}
if leaf_x_p_r == self._leaf_remove_index {
self.get_node_mut(leaf_p)._child_r = -1;
}
let h = self._leaf_remove_index;
if self.get_node(h)._parent == -1 && self._root == h {
self._root = -1;
}
self._leaf_remove_index = -1;
self._buf.pop();
}
}
_ => {
if x == -1 {
let leaf_p = self._buf[self._leaf_remove_index as usize]._parent;
let leaf_p_l = self.get_node(leaf_p)._child_l;
if leaf_p_l == self._leaf_remove_index {
self.get_node_mut(leaf_p)._child_l = -1;
}
let leaf_p_r = self.get_node(leaf_p)._child_r;
if leaf_p_r == self._leaf_remove_index {
self.get_node_mut(leaf_p)._child_r = -1;
}
let leaf_x_p_l = self.get_node(x_p)._child_l;
let leaf_x_p_r = self.get_node(x_p)._child_r;
if leaf_x_p_l == self._leaf_remove_index {
self.get_node_mut(leaf_p)._child_l = -1;
}
if leaf_x_p_r == self._leaf_remove_index {
self.get_node_mut(leaf_p)._child_r = -1;
}
let h = self._leaf_remove_index;
if self.get_node(h)._parent == -1 && self._root == h {
self._root = -1;
}
}
self._leaf_remove_index = -1;
self._buf.pop();
}
}
self._freelist.push(z);
if self._freelist.len() > self._buf.len() * 7 / 8 {
self.compact();
}
Some(val.clone())
} else {
None
}
}
pub fn contains_key(&self, key: K) -> bool {
let mut x = self._root;
while x != -1 {
let k = &self._buf[x as usize]._key;
if &key == k {
return true;
} else if &key < k {
x = self._buf[x as usize]._child_l;
} else {
x = self._buf[x as usize]._child_r;
}
}
false
}
pub fn shrink_to_fit(&mut self) {
self._buf.shrink_to_fit();
self._freelist.shrink_to_fit();
}
pub fn with_capacity(capacity: usize) -> Self {
TreeRb {
_root: -1isize,
_buf: Vec::with_capacity(capacity),
_sentinil: Node {
_colour: Colour::Black,
_parent: -1isize,
..Default::default()
},
_freelist: vec![],
_leaf_remove_index: -1isize,
}
}
pub fn predecessor(&self, key: K) -> Option<&V> {
let mut x = self._root;
let mut curr_pred = None;
while x != -1 {
let k = &self._buf[x as usize]._key;
if &key == k {
return Some(&self._buf[x as usize]._val);
} else if &key < k {
x = self._buf[x as usize]._child_l;
} else {
curr_pred = Some(&self._buf[x as usize]._val);
x = self._buf[x as usize]._child_r;
}
}
curr_pred
}
pub fn successor(&self, key: K) -> Option<&V> {
let mut x = self._root;
let mut curr_pred = None;
while x != -1 {
let k = &self._buf[x as usize]._key;
if &key == k {
return Some(&self._buf[x as usize]._val);
} else if &key < k {
curr_pred = Some(&self._buf[x as usize]._val);
x = self._buf[x as usize]._child_l;
} else {
x = self._buf[x as usize]._child_r;
}
}
curr_pred
}
pub fn get(&self, key: K) -> Option<V> {
let mut x = self._root;
while x != -1 {
let k = &self._buf[x as usize]._key;
if &key == k {
return Some(self._buf[x as usize]._val.clone());
} else if &key < k {
x = self._buf[x as usize]._child_l;
} else {
x = self._buf[x as usize]._child_r;
}
}
None
}
fn get_index(&self, key: &K) -> Option<isize> {
let mut x = self._root;
while x != -1 {
let k = &self._buf[x as usize]._key;
if key == k {
return Some(x);
} else if key < k {
x = self._buf[x as usize]._child_l;
} else {
x = self._buf[x as usize]._child_r;
}
}
None
}
pub fn clear(&mut self) {
self._root = -1isize;
self._buf.clear();
}
fn fixup_insert(&mut self, node: isize) {
assert!(node >= 0 && node < self._buf.len() as isize);
let mut n = node;
loop {
if self.get_node(n)._parent == -1 {
break;
}
let mut n_p = self.get_node(n)._parent;
match self.get_node(n_p)._colour {
Colour::Black => {
break;
}
_ => (),
}
let mut n_p_p = self.get_node(n_p)._parent;
if n_p_p == -1 {
self.get_node_mut(n)._colour = Colour::Red;
break;
}
if n_p == self.get_node(n_p_p)._child_l {
let y = self.get_node(n_p_p)._child_r;
match self.get_node(y)._colour {
Colour::Red => {
self.get_node_mut(n_p)._colour = Colour::Black;
self.get_node_mut(y)._colour = Colour::Black;
self.get_node_mut(n_p_p)._colour = Colour::Red;
n = n_p_p;
}
_ => {
if n == self.get_node(n_p)._child_r {
n = n_p;
self.rotate_left(n);
}
n_p = self.get_node(n)._parent;
n_p_p = self.get_node(n_p)._parent;
self.get_node_mut(n_p)._colour = Colour::Black;
self.get_node_mut(n_p_p)._colour = Colour::Red;
self.rotate_right(n_p_p);
}
}
} else {
let y = self.get_node(n_p_p)._child_l;
match self.get_node(y)._colour {
Colour::Red => {
self.get_node_mut(n_p)._colour = Colour::Black;
self.get_node_mut(y)._colour = Colour::Black;
self.get_node_mut(n_p_p)._colour = Colour::Red;
n = n_p_p;
}
_ => {
if n == self.get_node(n_p)._child_l {
n = n_p;
self.rotate_right(n);
}
n_p = self.get_node(n)._parent;
n_p_p = self.get_node(n_p)._parent;
self.get_node_mut(n_p)._colour = Colour::Black;
self.get_node_mut(n_p_p)._colour = Colour::Red;
self.rotate_left(n_p_p);
}
}
}
}
let n_root = self._root;
self.get_node_mut(n_root)._colour = Colour::Black;
}
fn fixup_remove(&mut self, node: isize) {
let mut x = node;
loop {
if x == -1 {
break;
}
let mut x_p = self.get_node(x)._parent;
if x_p == -1 {
break;
}
match self.get_node(x)._colour {
Colour::Red => {
break;
}
_ => {}
}
if x == self.get_node(x_p)._child_l {
let mut w = self.get_node(x_p)._child_r;
let w_colour = self.get_node(w)._colour;
match w_colour {
Colour::Red => {
self.get_node_mut(w)._colour = Colour::Black;
self.get_node_mut(x_p)._colour = Colour::Red;
self.rotate_left(x_p);
w = self.get_node(x_p)._child_r;
}
_ => {}
}
let w_left = self.get_node(w)._child_l;
let w_left_colour = self.get_node(w_left)._colour;
let w_right_colour = {
let w_right = self.get_node(w)._child_r;
self.get_node(w_right)._colour
};
match (w_left_colour, w_right_colour) {
(Colour::Black, Colour::Black) => {
self.get_node_mut(w)._colour = Colour::Red;
x = self.get_node(x)._parent;
}
_ => {
match w_right_colour {
Colour::Black => {
self.get_node_mut(w_left)._colour = Colour::Black;
self.get_node_mut(w)._colour = Colour::Red;
self.rotate_right(w);
x_p = self.get_node(x)._parent;
w = self.get_node(x_p)._child_r;
}
_ => {}
}
x_p = self.get_node_mut(x)._parent;
self.get_node_mut(w)._colour = self.get_node(x_p)._colour;
self.get_node_mut(x_p)._colour = Colour::Black;
let w_right = self.get_node(w)._child_r;
self.get_node_mut(w_right)._colour = Colour::Black;
self.rotate_left(x_p);
x = self._root;
}
}
} else {
let mut w = self.get_node(x_p)._child_l;
let w_colour = self.get_node(w)._colour;
match w_colour {
Colour::Red => {
self.get_node_mut(w)._colour = Colour::Black;
self.get_node_mut(x_p)._colour = Colour::Red;
self.rotate_right(x_p);
w = self.get_node(x_p)._child_l;
}
_ => {}
}
let w_left_colour = {
let w_left = self.get_node(w)._child_l;
self.get_node(w_left)._colour
};
let w_right = self.get_node(w)._child_r;
let w_right_colour = self.get_node(w_right)._colour;
match (w_left_colour, w_right_colour) {
(Colour::Black, Colour::Black) => {
self.get_node_mut(w)._colour = Colour::Red;
x = self.get_node(x)._parent;
}
_ => {
match w_left_colour {
Colour::Black => {
self.get_node_mut(w_right)._colour = Colour::Black;
self.get_node_mut(w)._colour = Colour::Red;
self.rotate_left(w);
x_p = self.get_node(x)._parent;
w = self.get_node(x_p)._child_l;
}
_ => {}
}
x_p = self.get_node_mut(x)._parent;
self.get_node_mut(w)._colour = self.get_node(x_p)._colour;
self.get_node_mut(x_p)._colour = Colour::Black;
let w_left = self.get_node(w)._child_l;
self.get_node_mut(w_left)._colour = Colour::Black;
self.rotate_right(x_p);
x = self._root;
}
}
}
}
self.get_node_mut(x)._colour = Colour::Black;
}
fn get_node(&mut self, node: isize) -> &Node<K, V> {
assert!(node >= -1 && node < self._buf.len() as isize);
if node == -1 {
self._sentinil._parent = -1;
&self._sentinil
} else {
assert!(node >= 0 && node < self._buf.len() as isize);
&self._buf[node as usize]
}
}
fn get_node_mut(&mut self, node: isize) -> &mut Node<K, V> {
assert!(node >= -1 && node < self._buf.len() as isize);
if node == -1 {
&mut self._sentinil
} else {
assert!(node >= 0 && node < self._buf.len() as isize);
&mut self._buf[node as usize]
}
}
#[allow(dead_code)]
fn get_parent_left(&self, node: isize) -> isize {
assert!(node >= 0 && node < self._buf.len() as isize);
let mut n = node;
#[allow(unused_assignments)]
let mut prev = -1isize;
loop {
prev = n;
n = self._buf[n as usize]._parent;
if n == -1 {
break;
}
if prev == self._buf[n as usize]._child_r {
break;
}
}
if n == -1 {
node
} else {
prev
}
}
#[allow(dead_code)]
fn get_parent_right(&self, node: isize) -> isize {
assert!(node >= 0 && node < self._buf.len() as isize);
let mut n = node;
#[allow(unused_assignments)]
let mut prev = -1isize;
loop {
prev = n;
n = self._buf[n as usize]._parent;
if n == -1 {
break;
}
if prev == self._buf[n as usize]._child_l {
break;
}
}
if n == -1 {
node
} else {
prev
}
}
#[allow(dead_code)]
fn get_subtree_leftmost(&self, node: isize) -> isize {
assert!(node >= 0 && node < self._buf.len() as isize);
let mut n = node;
let mut prev = -1isize;
while n != -1 {
prev = n;
n = self._buf[n as usize]._child_l;
}
prev
}
#[allow(dead_code)]
fn get_subtree_rightmost(&self, node: isize) -> isize {
assert!(node >= 0 && node < self._buf.len() as isize);
let mut n = node;
let mut prev = -1isize;
while n != -1 {
prev = n;
n = self._buf[n as usize]._child_r;
}
prev
}
fn transplant(&mut self, node_dest: isize, node_src: isize) {
if self.get_node(node_dest)._parent == -1 {
self._root = node_src;
if node_src != -1 {
self.get_node_mut(node_src)._parent = -1;
}
} else {
let n_p = self.get_node(node_dest)._parent;
if node_dest == self.get_node(n_p)._child_l {
self.connect_left(n_p, node_src);
} else {
self.connect_right(n_p, node_src);
}
}
}
fn connect_left(&mut self, node_parent: isize, node_child: isize) {
if node_parent != -1 {
self._buf[node_parent as usize]._child_l = node_child;
} else {
self._root = node_child;
}
if node_child != -1 {
self._buf[node_child as usize]._parent = node_parent;
}
}
fn connect_right(&mut self, node_parent: isize, node_child: isize) {
if node_parent != -1 {
self._buf[node_parent as usize]._child_r = node_child;
} else {
self._root = node_child;
}
if node_child != -1 {
self._buf[node_child as usize]._parent = node_parent;
}
}
fn rotate_left(&mut self, node: isize) -> Option<isize> {
if node >= 0 && node < self._buf.len() as isize {
let n_p = self.get_node(node)._parent;
let y = self.get_node(node)._child_r;
let y_l = self.get_node(y)._child_l;
self.connect_right(node, y_l);
self.get_node_mut(y)._parent = n_p;
if n_p == -1 {
self._root = y;
} else if node == self.get_node(n_p)._child_l {
self.connect_left(n_p, y);
} else {
self.connect_right(n_p, y);
}
self.connect_left(y, node);
Some(y)
} else {
None
}
}
fn rotate_right(&mut self, node: isize) -> Option<isize> {
if node >= 0 && node < self._buf.len() as isize {
let n_p = self.get_node(node)._parent;
let y = self.get_node(node)._child_l;
let y_r = self.get_node(y)._child_r;
self.connect_left(node, y_r);
self.get_node_mut(y)._parent = n_p;
if n_p == -1 {
self._root = y;
} else if node == self.get_node(n_p)._child_l {
self.connect_left(n_p, y);
} else {
self.connect_right(n_p, y);
}
self.connect_right(y, node);
Some(y)
} else {
None
}
}
pub fn compact(&mut self) {
self._freelist.sort_unstable();
let mut f = 0;
let mut f_rev = self._freelist.len();
let mut n = self._buf.len();
loop {
if f >= f_rev || self._freelist[f] >= n as isize {
break;
}
if (n as isize - 1) == self._freelist[f_rev as usize - 1] {
f_rev -= 1;
n -= 1;
continue;
}
let n_p = self.get_node(n as isize - 1)._parent;
let n_l = self.get_node(n as isize - 1)._child_l;
let n_r = self.get_node(n as isize - 1)._child_r;
let f_index = self._freelist[f];
self._buf[f_index as usize] = self._buf[n - 1].clone();
self._buf[f_index as usize]._index = f_index;
self.connect_left(f_index, n_l);
self.connect_right(f_index, n_r);
if self.get_node(n_p)._child_l == n as isize - 1 {
self.connect_left(n_p, f_index);
} else if self.get_node(n_p)._child_r == n as isize - 1 {
self.connect_right(n_p, f_index);
}
if n_p == -1 {
self._root = f_index;
}
n -= 1;
f += 1;
}
self._buf.resize(n, Default::default());
self._freelist.clear();
}
pub fn print(&mut self) {
let x = self._root;
let mut v = vec![];
v.push(x);
println!("tree root: {}", x);
println!("tree print: ");
while v.len() > 0 {
let n = v.pop().unwrap();
if n != -1 {
v.push(self.get_node(n)._child_l);
v.push(self.get_node(n)._child_r);
}
}
}
pub fn check_nodes(&self) {
let mut hm = HashMap::new();
let mut leaves = vec![];
let x = self._root;
let mut v = vec![x];
while v.len() > 0 {
let &n = v.last().unwrap();
v.pop();
if n != -1 {
let nl = self._buf[n as usize]._child_l;
let nr = self._buf[n as usize]._child_r;
if (nl, nr) == (-1, -1) {
leaves.push(n);
} else {
v.push(nl);
v.push(nr);
}
}
}
for i in leaves {
let mut n = i;
let mut count = 0;
while n != -1 {
match hm.insert(n, count) {
Some(v) => {
assert!(v == count);
break;
}
_ => {}
}
let c = self._buf[n as usize]._colour;
match c {
Colour::Black => {
count += 1;
}
_ => {}
}
n = self._buf[n as usize]._parent;
}
}
if x != -1 {
match self._buf[x as usize]._colour {
Colour::Red => {
panic!("root colour incorrect");
}
_ => {}
}
}
}
}
#[cfg(test)]
extern crate chrono;
#[cfg(test)]
extern crate rand;
#[cfg(test)]
use self::chrono::prelude::*;
#[cfg(test)]
use rand::distributions::{Distribution, Uniform};
#[cfg(test)]
use self::rand::Rng;
#[cfg(test)]
use std::collections::BTreeMap;
#[test]
fn test_rb_insert() {
let mut t: TreeRb<isize, isize> = TreeRb::new();
for i in 0..10 {
t.insert(i, i);
}
t.check_nodes();
}
#[test]
fn test_rb_contains_key() {
{
let mut t: TreeRb<isize, isize> = TreeRb::new();
for i in 0..10 {
t.insert(i, i);
}
for i in 0..10 {
assert!(t.contains_key(i));
}
for i in 10..15 {
assert!(!t.contains_key(i));
}
}
{
let mut t: TreeRb<isize, isize> = TreeRb::new();
for i in (0..10).rev() {
t.insert(i, i);
}
for i in 0..10 {
assert!(t.contains_key(i));
}
for i in 10..15 {
assert!(!t.contains_key(i));
}
}
}
#[test]
fn test_rb_get() {
let mut t: TreeRb<isize, isize> = TreeRb::new();
for i in 0..10 {
t.insert(i, i);
}
for i in 0..10 {
let n = t.get(i).expect("get() unsuccessful");
assert!(n == i);
}
for i in 10..15 {
match t.get(i) {
Some(_) => {
panic!("get() unsuccessfil");
}
None => (),
}
}
}
#[test]
fn test_rb_len() {
let mut t: TreeRb<isize, isize> = TreeRb::new();
assert!(t.len() == 0);
assert!(t.is_empty());
for i in 0..10 {
t.insert(i, i);
}
assert!(t.len() == 10);
assert!(!t.is_empty());
}
#[test]
fn test_rb_clear() {
let mut t: TreeRb<isize, isize> = TreeRb::new();
for i in 0..10 {
t.insert(i, i);
}
assert!(t.len() == 10);
t.clear();
assert!(t.len() == 0);
}
#[test]
fn test_rb_remove_compact() {
let mut t: TreeRb<isize, isize> = TreeRb::new();
for i in 0..3 {
t.insert(i, i);
}
t.check_nodes();
let t_size = t.len();
for i in 0..3 {
let r = t.remove(&i).expect("remove unsuccessful");
assert!(r == i);
assert!(t.len() == t_size - i as usize - 1);
}
t.check_nodes();
}
#[test]
fn test_rb_remove_leaf_black() {
let mut t: TreeRb<isize, isize> = TreeRb::new();
for i in 0..10 {
t.insert(i, i);
}
t.check_nodes();
let t_size = t.len();
let mut count_remove = 0;
for i in 8..9 {
let r = t.remove(&i).expect("remove unsuccessful");
assert!(r == i);
count_remove += 1;
assert!(t.len() == t_size - count_remove);
}
t.check_nodes();
}
#[test]
fn test_rb_remove_leaf_red() {
let mut t: TreeRb<isize, isize> = TreeRb::new();
for i in 0..10 {
t.insert(i, i);
}
t.check_nodes();
let t_size = t.len();
let mut count_remove = 0;
for i in 4..5 {
let r = t.remove(&i).expect("remove unsuccessful");
assert!(r == i);
count_remove += 1;
assert!(t.len() == t_size - count_remove);
}
t.check_nodes();
}
#[test]
fn test_rb_remove_internal_red() {
let mut t: TreeRb<isize, isize> = TreeRb::new();
for i in 0..10 {
t.insert(i, i);
}
t.check_nodes();
let t_size = t.len();
let mut count_remove = 0;
for i in 7..8 {
let r = t.remove(&i).expect("remove unsuccessful");
assert!(r == i);
count_remove += 1;
assert!(t.len() == t_size - count_remove);
}
t.check_nodes();
}
#[test]
fn test_rb_remove_internal_black() {
let mut t: TreeRb<isize, isize> = TreeRb::new();
for i in 0..10 {
t.insert(i, i);
}
t.check_nodes();
let t_size = t.len();
let mut count_remove = 0;
for i in 1..2 {
let r = t.remove(&i).expect("remove unsuccessful");
assert!(r == i);
count_remove += 1;
assert!(t.len() == t_size - count_remove);
}
t.check_nodes();
}
#[test]
fn test_rb_remove_internal_black_2() {
let mut t: TreeRb<isize, isize> = TreeRb::new();
for i in 0..10 {
t.insert(i, i);
}
t.check_nodes();
let t_size = t.len();
let mut count_remove = 0;
for i in 5..6 {
let r = t.remove(&i).expect("remove unsuccessful");
assert!(r == i);
count_remove += 1;
assert!(t.len() == t_size - count_remove);
}
t.check_nodes();
}
#[test]
fn test_rb_insert_remove_rand() {
let mut t: TreeRb<isize, isize> = TreeRb::new();
let bounds = Uniform::from(-300..301);
let mut rng = rand::thread_rng();
let mut hm = HashMap::new();
for i in 0..10000 {
let r = bounds.sample(&mut rng);
t.insert(r, i);
hm.insert(r, i);
}
t.check_nodes();
assert!(t.len() == hm.len());
for _ in 0..30000 {
let r = bounds.sample(&mut rng);
match hm.remove(&r) {
Some(v_check) => {
let v = t.remove(&r).expect("remove unsuccessful");
assert!(v == v_check);
assert!(hm.len() == t.len());
t.check_nodes();
}
_ => match t.remove(&r) {
Some(_v) => {
panic!("remove unsuccessful");
}
_ => {}
},
}
}
}