How to mem::replace self with an Option if the type of self is not Option?

Question

I am attempting to implementing delete for a binary tree:

#[derive(Debug)]
struct Binary_Tree<T: PartialOrd + Clone> {
    left: Box<Option<Binary_Tree<T>>>,
    value: T,
    right: Box<Option<Binary_Tree<T>>>,
}

impl<T: PartialOrd + Clone> Binary_Tree<T> {
    fn new(value: T) -> Binary_Tree<T> {
        Binary_Tree {
            left: Box::new(None),
            value: value,
            right: Box::new(None),
        }
    }

    fn delete(&mut self, value_to_delete: T) -> bool {
        use std::mem;
        match self {
            &mut Binary_Tree {
                ref mut left,
                ref mut value,
                ref mut right,
            } => if value_to_delete < *value {
                if let None = **left {
                    return false;
                } else {
                    return (**left).as_mut().unwrap().delete(value_to_delete);
                }
            } else if value_to_delete > *value {
                if let None = **right {
                    return false;
                } else {
                    return (**right).as_mut().unwrap().delete(value_to_delete);
                }
            } else {
                if let Some(ref mut left_content) = **left {
                    *value = (*left_content).value.clone();
                    let temp = (*left_content).value.clone();
                    return (*left_content).delete(temp);
                } else if let Some(ref mut right_content) = **right {
                    *value = (*right_content).value.clone();
                    let temp = (*right_content).value.clone();
                    return (*right_content).delete(temp);
                } else {
                    mem::replace(self, None);
                    return true;
                }
            },
        }
    }
}

The place that is causing trouble is mem::replace(self, None); since self is of Binary_Tree type and not Option.

I implemented another solution but it ran into other issues as well:

fn delete(&mut self, value_to_delete: T) -> bool {
    match self {
        &mut Binary_Tree {
            ref mut left,
            ref mut value,
            ref mut right,
        } => {
            if value_to_delete < *value {
                if let None = **left {
                    return false;
                } else {
                    return (**left).as_mut().unwrap().delete(value_to_delete);
                }
            } else if value_to_delete > *value {
                if let None = **right {
                    return false;
                } else {
                    return (**right).as_mut().unwrap().delete(value_to_delete);
                }
            } else {
                if let Some(ref mut left_content) = **left {
                    *value = (*left_content).value.clone();
                    let temp = (*left_content).value.clone();

                    if let None = *left_content.left {
                        if let None = *left_content.right {
                            //**left = None;
                            return true;
                        } else {
                            return (*left_content).delete(temp);
                        }
                    } else {
                        return (*left_content).delete(temp);
                    }
                } else if let Some(ref mut right_content) = **right {
                    *value = (*right_content).value.clone();
                    let temp = (*right_content).value.clone();

                    if let None = *right_content.left {
                        if let None = *right_content.right {
                            //**right = None;
                            return true;
                        } else {
                            return (*right_content).delete(temp);
                        }
                    } else {
                        return (*right_content).delete(temp);
                    }
                } else {
                    // This should never go here
                    return true;
                }
            }
        }
    }
}

The problem with this solution is that both **right = None; and **left = None; are borrowed out to do checks.

I feel like I am missing something important since both solutions should work in other language.

Answer 1

You need to pass tree: &mut Option<Self> instead of &mut self; you cannot call it as a method anymore, but Self::delete(left, value_to_delete) should still work fine.

Your current Tree type should probably be called Node - a Tree can consist of no node, and your current Tree always is at least one node. You should then provide a pub struct Tree(Option<Node>); Option<Node> wouldn't be very user friendly.

I feel like I am missing something important since both solutions should work in other language.

Some languages pass objects always by a shared and nullable pointer. In Rust you need to be explicit about this.

Your comment // This should never go here in the second solution is simply a wrong assumption. You could match *left.take() instead of **left*, thenleft` isn't borrowed (but empty; so you need to restore it if it shouldn't be).

Given that borrow-checking is a rather unique feature it should be obvious that certain patterns don't work in Rust, even if they are safe and would work in other languages.