Return a reference from the function

1

I've decided to implement a BinaryTree structure and one of the BinaryTree methods i want to create is get() which returns a mutable reference to the Node with given index, so that the user will be able to change the Node's value, for example, but I have a problem with it:
As the answ value is created inside a function, I can't return it. What should I change in my code to be able to return a mutable reference to the Node with the given index (not the copy, but the Node itself). Do I have to rewrite get() function completely, or can it be fixed in one move?

pub struct Node<T:Clone+Debug> {
     val: T,
    index:usize,
    parent:Option<Weak<RefCell<Node<T>>>>,
    left: Option<Box<Node<T>>>,
    right:Option<Box<Node<T>>>
}
impl<T:Eq+Clone+Debug> PartialEq for Node<T>{
    fn eq(&self,other:&Node<T>)->bool{
        if self.val==other.val{
            return true;
        }
        false
    }
}

#[derive(Debug,Clone)]
pub struct BinaryTree<T:Eq+Clone+Debug>{
    root:Box<Node<T>>
}```


mpl<T:Eq+Clone+Debug> BinaryTree<T>{
    pub fn root<'a>(&'a self)->&'a Node<T>{
        return &self.root
    }
    pub fn root_mut<'a>(&'a mut self)->&'a mut Node<T>{
        return &mut self.root;
    }
    fn get<'b>(&'b mut self,i:&'b usize)-> Option< &'b mut Node<T>>{
        let closure = move |x:&Node<T>|->bool{x.index==*i};
        let answ = DFS(&mut self.root_mut(),& closure);
        return answ
    }
}

fn DFS<'a,T:Clone+std::fmt::Debug>(tree:&'a mut Node<T>,feature:&dyn Fn(&Node<T>) -> bool)->Option<&'a mut Node<T>>{
    if feature(&tree.clone()){
        return Option::Some(tree);
    }
    if let Some(node) =  &mut tree.left{
         return DFS(node,feature);
    }
    if let Some( node) = &mut tree.right{
        return DFS( node,feature);
    }
        return  Option::None;
    }
2 
pub struct Node<T: Clone + Debug> {
    val: T,
    index: usize,
    parent: Option<Weak<RefCell<Node<T>>>>,
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
}

This design isn't going to work. In order to use Weak<RefCell<Node<T>>> for the parent pointers, you have to use Rc<RefCell<Node<T>>> for the left and right pointers. Otherwise there's nowhere for the RefCell to live and no strong pointer to keep the Weak alive.

5 Likes
3

Thank you, I have changed the Node structure, but I still have a problem with the get function: I want get() to return either a mutable reference to the Node with the requested index, or Option::None. But I can't do that, because &mut Option::None is created inside the get function and it is cleared as the call of the get() function ends. What shall I do to correct this?

pub struct Node<T:Clone+Debug> {
     val: T,
    index:usize,
    parent:Option<Weak<RefCell<Node<T>>>>,
    left: Option<Rc<RefCell<Node<T>>>>,
    right:Option<Rc<RefCell<Node<T>>>>,
}
impl<T:Eq+Clone+Debug> PartialEq for Node<T>{
    fn eq(&self,other:&Node<T>)->bool{
        if self.val==other.val{
            return true;
        }
        false
    }
}

#[derive(Debug,Clone)]
pub struct BinaryTree<T:Eq+Clone+Debug>{
    root:Option<Rc<RefCell<Node<T>>>>
}

impl<T:Eq+Clone+Debug> BinaryTree<T>{
    pub fn root<'a>(&'a self)->&'a Option<Rc<RefCell<Node<T>>>>{
        return &self.root;
    }
    pub fn root_mut<'a>(&'a mut self)->&'a mut Option<Rc<RefCell<Node<T>>>>{
        return &mut self.root;
    }
    fn get<'b>(&'b mut self,i:&'b usize)-> &'b mut Option<Rc<RefCell<Node<T>>>>{
        let closure = move |x:&Option<Rc<RefCell<Node<T>>>>|->bool{x.unwrap().borrow().index==*i};
        let answ = DFS( self.root_mut(),& closure);
        match answ{
            Ok(v)=>return v,
            Err(e)=> return &mut Option::None,
        }
    }
}

fn DFS<'a,T:Clone+std::fmt::Debug+std::cmp::PartialEq>(tree:&'a mut Option<Rc<RefCell<Node<T>>>>,feature:&dyn Fn(&Option<Rc<RefCell<Node<T>>>>) -> bool)->Result<&'a mut Option<Rc<RefCell<Node<T>>>>,&'static str>{
    if let Some(_) = tree{
     if feature(&tree.clone()){
        return Ok(tree);
     }
    }
          DFS(&mut tree.as_ref().unwrap().borrow_mut().left,feature);
          DFS(  &mut tree.as_ref().unwrap().borrow_mut().right,feature);
    
        return  Err("There is no node with the given index");
    }``
4

Consider returning Option<&mut ...> instead of &mut Option<...>.

3 Likes
5

Wow, this really worked out! Thank you a lot!

6

(2e71828 already gave the answer here, but to explore this a bit more.)

Note that this is a good time to think about the type in use and ponder whether it's what you actually meant. For example, what can you do with a &mut Option<...>? Is that what you wanted people to do for this case?

In particular, if get returns me a &mut Option<...>, that means I can write a Some(...) into it. But it doesn't really make sense to write anywhere if the lookup failed, so that's probably not the type you wanted. (And this logic is indepedent of the fact that you got a borrowck error.)

And if you're in general unsure where to go, following what std does can often help: [T]::get_mut returns an Option<&mut ...>, not a &mut Option<...>.

1 Like
7

Yes, this is literally what i needed

8

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.