I've been playing around with implementing red-black trees from CLRS in Rust. The code (as it currently stands) is as follows:
use std::cmp::PartialOrd;
use std::fmt::Display;
struct RedBlackNode<'a, T> {
elem: T,
colour: bool,
left: Option<&'a mut RedBlackNode<'a, T>>,
right: Option<&'a mut RedBlackNode<'a, T>>,
parent: Option<&'a mut RedBlackNode<'a, T>>,
}
impl<'a, T> RedBlackNode<'a, T> {
fn new(elem: T) -> Self {
RedBlackNode::<T> {
elem: elem,
colour: false,
left: None,
right: None,
parent: None,
}
}
}
impl<T: PartialEq> PartialEq for RedBlackNode<'_, T> {
fn eq(&self, other: &Self) -> bool {
self.elem == other.elem
}
}
pub struct RedBlackTree<'a, T> {
root: Option<RedBlackNode<'a, T>>,
}
impl<'a, T: PartialOrd> RedBlackTree<'a, T> {
pub fn new() -> Self {
RedBlackTree::<T> { root: None }
}
pub fn add(&mut self, elem: T) {
let z: RedBlackNode<'a, T> = RedBlackNode::new(elem);
let mut y: Option<&'a mut RedBlackNode<'a, T>> = None;
let mut x: Option<&'a mut RedBlackNode<'a, T>> = self.root.as_mut();
while !x.is_none() {
y = x;
if z.elem < x.unwrap().elem {
x = x.unwrap().left;
} else {
x = x.unwrap().right;
}
}
z.parent = y;
if y.is_none() {
self.root = Some(z);
} else if z.elem < y.unwrap().elem {
y.unwrap().left = Some(&mut z);
} else {
y.unwrap().right = Some(&mut z);
}
z.left = None;
z.right = None;
z.colour = true;
self.insert_fixup(&mut z);
}
fn left_rotate(&mut self, z: &mut RedBlackNode<'a, T>) {
unimplemented!();
}
fn right_rotate(&mut self, z: &mut RedBlackNode<'a, T>) {
unimplemented!();
}
fn insert_fixup(&mut self, z: &mut RedBlackNode<'a, T>) {
if z.parent.is_none() {
return;
}
while z.parent.unwrap().colour {
if z.parent.unwrap().parent.is_some()
&& *z.parent.unwrap()
== *z.parent.unwrap().parent.unwrap().left.unwrap()
{
let y = z.parent.unwrap().parent.unwrap().right.unwrap();
if y.colour {
z.parent.unwrap().colour = false;
y.colour = false;
z.parent.unwrap().parent.unwrap().colour = true;
z = z.parent.unwrap().parent.unwrap();
} else {
if z.parent.unwrap().right.is_some()
&& *z == *z.parent.unwrap().right.unwrap()
{
z = z.parent.unwrap();
self.left_rotate(z);
}
z.parent.unwrap().colour = false;
z.parent.unwrap().parent.unwrap().colour = true;
self.right_rotate(z.parent.unwrap().parent.unwrap());
}
} else {
if z.parent.unwrap().parent.is_some()
&& *z.parent.unwrap()
== *z.parent.unwrap().parent.unwrap().right.unwrap()
{
let y = z.parent.unwrap().parent.unwrap().left.unwrap();
if y.colour {
z.parent.unwrap().colour = false;
y.colour = false;
z.parent.unwrap().parent.unwrap().colour = true;
z = z.parent.unwrap().parent.unwrap();
} else {
if z.parent.unwrap().left.is_some()
&& *z == *z.parent.unwrap().left.unwrap()
{
z = z.parent.unwrap();
self.right_rotate(z);
}
z.parent.unwrap().colour = false;
z.parent.unwrap().parent.unwrap().colour = true;
self.left_rotate(z.parent.unwrap().parent.unwrap());
}
}
}
}
self.root.unwrap().colour = false;
}
}
fn print_node<T>(node: &RedBlackNode<T>)
where
T: Display,
{
match &node.left {
Some(l) => print_node(l),
None => {}
};
println!("{}", node.elem);
match &node.right {
Some(r) => print_node(r),
None => {}
};
}
pub fn print_tree<T>(tree: &RedBlackTree<T>)
where
T: Display,
{
match &tree.root {
Some(root) => print_node(&root),
None => {}
};
}
fn main() {
let my_tree: RedBlackTree<u64> = RedBlackTree::new();
print_tree(&my_tree);
}
However, the compiler complains due to the conflicting lifetime on line 43, with:
error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
--> src/main.rs:43:68
|
43 | let mut x: Option<&'a mut RedBlackNode<'a, T>> = self.root.as_mut();
| ^^^^^^
|
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 39:5...
--> src/main.rs:39:5
|
39 | / pub fn add(&mut self, elem: T) {
40 | | let z: RedBlackNode<'a, T> = RedBlackNode::new(elem);
41 | |
42 | | let mut y: Option<&'a mut RedBlackNode<'a, T>> = None;
... |
69 | | self.insert_fixup(&mut z);
70 | | }
| |_____^
note: ...so that reference does not outlive borrowed content
--> src/main.rs:43:58
|
43 | let mut x: Option<&'a mut RedBlackNode<'a, T>> = self.root.as_mut();
| ^^^^^^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 34:6...
--> src/main.rs:34:6
|
34 | impl<'a, T: PartialOrd> RedBlackTree<'a, T> {
| ^^
note: ...so that the expression is assignable
--> src/main.rs:43:58
|
43 | let mut x: Option<&'a mut RedBlackNode<'a, T>> = self.root.as_mut();
| ^^^^^^^^^^^^^^^^^^
= note: expected `std::option::Option<&'a mut RedBlackNode<'a, T>>`
found `std::option::Option<&mut RedBlackNode<'a, T>>`
I'm assuming this is due to the definition of RedBlackTree<'a, T> taking ownership of the root node inside the Option type (i.e., on line 31).
How can this be fixed without breaking the interface to RedBlackTree?
