Understanding ownership

help
#1

So, I was writing Binary Search tree as below

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    left: Link<T>,
    right: Link<T>,
}

impl<T: Ord> Node<T> {
    pub fn new(elem: T) -> Self {
        Node { elem, left: None, right: None }
    }

   pub fn push(&mut self, elem: T) {
        if self.elem < elem {
            self.right = self.right.take().map_or(
                Option::Some(Box::new(Node::new(elem))),
                |mut node| {
                    node.push(elem);
                    Option::Some(node)
                }
            );
        } else {
             self.left = self.left.take().map_or(
                 Option::Some(Box::new(Node::new(elem))),
                 |mut node| {
                     node.push(elem);
                     Option::Some(node)
                 }
             );
        }
    }
}

but the compiler threw me an error. So I wrote like this

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    left: Link<T>,
    right: Link<T>,
}

impl<T: Ord> Node<T> {
    pub fn new(elem: T) -> Self {
        Node { elem, left: None, right: None }
    }

    pub fn push(&mut self, elem: T) {
        if self.elem < elem {
            self.right = match self.right.take() {
                Some(mut node) => {node.push(elem); Option::Some(node)},
                None => Option::Some(Box::new(Node::new(elem)))
            }
        } else {
             self.left = match self.left.take() {
                 Some(mut node) => {node.push(elem); Option::Some(node)},
                 None => Option::Some(Box::new(Node::new(elem)))
             }
        }
    }
}

It successfully compiled. Based on the semantics both are exactly same thing. How couldn't it resolve ownership in the first one but successfully resolved in latter?
And can we write code like in the first one without breaking any ownership rules? If so how?
And lastly this is the code I tried to write completely on my own after learning about rust with too many linked list. Can you give me suggestions like what be made better?

#2

They don't have the same semantics. The first version unconditionally moves elem into the new Node as the first argument to map_or, before you know whether the left/right field is None. Thus elem is no longer available to also try to use in the closure. The second directs elem dynamically once you know whether you have Some or None.

FWIW, there's a lazy map_or_else too, but it wouldn't have helped this case. Then it would be trying to capture elem in both closures, again before knowing which path will actually be used.

1 Like
#3

So, there's no way to write it like the first one?. Is the second code is only way to implement it?

#4

One possible improvement -- you don't actually need to take() the options:

            if let Some(ref mut node) = self.right {
                node.push(elem);
            } else {
                self.right = Some(Box::new(Node::new(elem)));
            }

You can write that as a match too, but I find that less convenient when you want statements.

#5

Thanks for the suggestion. :smile: