use super::*;
#[must_use]
unsafe fn rotate_left<K, V>(raw_h: Link<K, V>) -> Link<K, V> {
debug_assert!(raw_h.is_some());
debug_assert!(Node::is_red(unsafe { raw_h.unwrap().as_ref().right }));
let h = unsafe { raw_h.unwrap().as_mut() };
let raw_x = h.right;
let x = unsafe { raw_x.unwrap().as_mut() };
h.right = x.left;
x.left = raw_h;
x.color = h.color;
h.color = Color::Red;
x.size = h.size;
h.size = 1 + Node::size(h.left) + Node::size(h.right);
raw_x
}
#[must_use]
unsafe fn rotate_right<K, V>(raw_h: Link<K, V>) -> Link<K, V> {
debug_assert!(raw_h.is_some());
debug_assert!(Node::is_red(unsafe { raw_h?.as_ref().left }));
let h = unsafe { raw_h?.as_mut() };
let raw_x = h.left;
let x = unsafe { raw_x?.as_mut() };
h.left = x.right;
x.right = raw_h;
x.color = h.color;
h.color = Color::Red;
x.size = h.size;
h.size = 1 + Node::size(h.left) + Node::size(h.right);
raw_x
}
unsafe fn flip_colors<K, V>(raw_h: Link<K, V>) {
unsafe {
let h = raw_h.unwrap().as_mut();
let left = h.left.unwrap().as_mut();
let right = h.right.unwrap().as_mut();
debug_assert!(if h.color == Color::Red {
left.color == Color::Black && right.color == Color::Black
} else {
left.color == Color::Red && right.color == Color::Red
});
h.color.switch();
right.color.switch();
left.color.switch();
}
}
#[must_use]
unsafe fn move_red_left<K, V>(mut raw_h: Link<K, V>) -> Link<K, V> {
unsafe {
flip_colors(raw_h);
let h = raw_h.unwrap().as_mut();
let right_left_is_red = if let Some(r) = h.right {
Node::is_red(r.as_ref().left)
} else {
false
};
if right_left_is_red {
h.right = rotate_right(h.right);
raw_h = rotate_left(raw_h);
flip_colors(raw_h);
}
}
raw_h
}
#[must_use]
unsafe fn move_red_right<K, V>(mut raw_h: Link<K, V>) -> Link<K, V> {
unsafe {
flip_colors(raw_h);
let h = raw_h.unwrap().as_mut();
let left_left_is_red = if let Some(l) = h.left {
Node::is_red(l.as_ref().left)
} else {
false
};
if left_left_is_red {
raw_h = rotate_right(raw_h);
flip_colors(raw_h);
}
}
raw_h
}
#[must_use]
unsafe fn balance<K, V>(mut raw_h: Link<K, V>) -> Link<K, V> {
unsafe {
let node = raw_h?.as_ref();
if Node::is_red(node.right) && !Node::is_red(node.left) {
raw_h = rotate_left(raw_h);
}
let node = raw_h?.as_ref();
if Node::is_red(node.left)
&& Node::is_red(node.left.unwrap().as_ref().left)
{
raw_h = rotate_right(raw_h);
}
let node = raw_h?.as_ref();
if Node::is_red(node.left) && Node::is_red(node.right) {
flip_colors(raw_h);
}
let node = raw_h?.as_mut();
node.size = Node::size(node.left) + Node::size(node.right) + 1;
raw_h
}
}
#[must_use]
pub unsafe fn put<K: Ord, V>(
raw_h: Link<K, V>,
key: K,
value: V,
) -> Link<K, V> {
if let Some(mut n) = raw_h {
unsafe {
let node = n.as_mut();
match key.cmp(&node.key) {
Ordering::Less => node.left = put(node.left, key, value),
Ordering::Greater => node.right = put(node.right, key, value),
Ordering::Equal => node.value = value,
}
balance(raw_h)
}
} else {
unsafe {
Some(NonNull::new_unchecked(Box::into_raw(Box::new(Node::new(
key, value,
)))))
}
}
}
#[must_use]
pub unsafe fn delete_min<K: Ord, V>(mut raw_h: Link<K, V>) -> Link<K, V> {
unsafe {
let node = raw_h?.as_ref();
if node.left.is_none() {
let _ = Box::from_raw(raw_h.unwrap().as_ptr());
return None;
}
if !Node::is_red(node.left)
&& !Node::is_red(node.left.unwrap().as_ref().left)
{
raw_h = move_red_left(raw_h);
}
let node = raw_h?.as_mut();
node.left = delete_min(node.left);
balance(raw_h)
}
}
#[must_use]
pub unsafe fn delete_max<K: Ord, V>(mut raw_h: Link<K, V>) -> Link<K, V> {
unsafe {
let node = raw_h?.as_ref();
if Node::is_red(node.left) {
raw_h = rotate_right(raw_h);
}
let node = raw_h?.as_ref();
if node.right.is_none() {
let _ = Box::from_raw(raw_h.unwrap().as_ptr());
return None;
}
if !Node::is_red(node.right)
&& !Node::is_red(node.right.unwrap().as_ref().left)
{
raw_h = move_red_right(raw_h);
}
let node = raw_h?.as_mut();
node.right = delete_max(node.right);
balance(raw_h)
}
}
#[must_use]
pub unsafe fn delete<K: Clone + Ord, V: Clone>(
mut raw_h: Link<K, V>,
key: &K,
) -> Link<K, V> {
unsafe {
let node = raw_h?.as_ref();
match key.cmp(&node.key) {
Ordering::Less => {
if !Node::is_red(node.left)
&& !Node::is_red(node.left.unwrap().as_ref().left)
{
raw_h = move_red_left(raw_h);
}
let node = raw_h?.as_mut();
node.left = delete(node.left, key);
}
_ => {
if Node::is_red(node.left) {
raw_h = rotate_right(raw_h);
}
let node = raw_h?.as_ref();
if key.cmp(&node.key).is_eq() && node.right.is_none() {
let _ = Box::from_raw(raw_h.unwrap().as_ptr());
return None;
}
if !Node::is_red(node.right)
&& !Node::is_red(node.right.unwrap().as_ref().left)
{
raw_h = move_red_right(raw_h);
}
let node = raw_h?.as_mut();
if key.cmp(&node.key).is_eq() {
let min_ptr = min(node.right).unwrap().as_ptr();
let min = &*min_ptr;
node.key = min.key.clone();
node.value = min.value.clone();
node.right = delete_min(node.right);
} else {
node.right = delete(node.right, key);
}
}
}
balance(raw_h)
}
}
pub fn min<K: Ord, V>(mut current: Link<K, V>) -> Link<K, V> {
while current.is_some() {
let node = unsafe { current.unwrap().as_ref() };
if node.left.is_none() {
return current;
} else {
current = node.left;
}
}
None
}
#[must_use]
pub fn floor<K: Ord, V>(x: Link<K, V>, key: &K) -> Link<K, V> {
let node = unsafe { x?.as_ref() };
match key.cmp(&node.key) {
Ordering::Equal => x,
Ordering::Less => floor(node.left, key),
Ordering::Greater => floor(node.right, key).or(x),
}
}
#[must_use]
pub fn ceiling<K: Ord, V>(x: Link<K, V>, key: &K) -> Link<K, V> {
let node = unsafe { x?.as_ref() };
match key.cmp(&node.key) {
Ordering::Equal => x,
Ordering::Greater => ceiling(node.right, key),
Ordering::Less => ceiling(node.left, key).or(x),
}
}
#[must_use]
pub fn rank<K: Ord, V>(x: Link<K, V>, key: &K) -> usize {
if let Some(n) = x {
let node = unsafe { n.as_ref() };
match key.cmp(&node.key) {
Ordering::Less => rank(node.left, key),
Ordering::Greater => {
1 + Node::size(node.left) + rank(node.right, key)
}
Ordering::Equal => Node::size(node.left),
}
} else {
0
}
}