Как реализовать метод добавления связанного списка?

Question

Я хочу создать простой связанный список и добавить в него значение. Каким образом должен быть реализован метод add для вывода этого кода 100 50 10 5 в строке 42, второй вызов root.print()?

use std::rc::Rc; 

struct Node { 
    value: i32, 
    next: Option<Box<Node>>, 
} 

impl Node { 
    fn print(&self) { 
     let mut current = self; 
     loop { 
      println!("{}", current.value); 
      match current.next { 
       Some(ref next) => { 
        current = &**next; 
       } 
       None => break, 
      } 
     } 
    } 

    fn add(&mut self, node: Node) { 
     let item = Some(Box::new(node)); 
     let mut current = self; 
     loop { 
      match current.next { 
       None => current.next = item, 
       _ => {} 
       //Some(next) => { current = next; } 
      } 
     } 
    } 
} 

fn main() { 
    let leaf = Node { 
     value: 10, 
     next: None, 
    }; 
    let branch = Node { 
     value: 50, 
     next: Some(Box::new(leaf)), 
    }; 
    let mut root = Node { 
     value: 100, 
     next: Some(Box::new(branch)), 
    }; 
    root.print(); 

    let new_leaf = Node { 
     value: 5, 
     next: None, 
    }; 
    root.add(new_leaf); 
    root.print(); 
} 

(Playground)

Я переписал функцию:

fn add(&mut self, node: Node) { 
    let item = Some(Box::new(node)); 
    let mut current = self; 
    loop { 
     match current { 
      &mut Node { 
        value: _, 
        next: None, 
       } => current.next = item, 
      _ => {} 
      //Some(next) => { current = next; } 
     } 
    } 
} 

но компилятор говорит

error[E0382]: use of moved value: `item` 
    --> <anon>:28:40 
    | 
28 |     None => current.next = item, 
    |          ^^^^ value moved here in previous iteration of loop 
    | 
    = note: move occurs because `item` has type `std::option::Option<std::boxed::Box<Node>>`, which does not implement the `Copy` trait 

Я не понимаю, почему он говорит, что пункт был ранее перемещен если он используется только один раз, и как следует использовать филиал Some(_) чтобы перебирать список?

Answer 1

Это, как вам нужно написать это (playpen link)

fn add(&mut self, node: Node) 
{ 
    /// Identity function. Move the input to output. 
    fn moving<T>(x: T) -> T { x } 

    let item = Some(Box::new(node)); 
    let mut current = self; 
    loop { 
     match moving(current).next { 
      ref mut slot @ None => { *slot = item; return }, 
      Some(ref mut next) => current = next, 
     }; 
    } 
} 

Итак, что же это?

Шаг 1, нам необходимо return сразу же после использования значения item. Затем компилятор правильно видит, что он перемещается только один раз.

=> { *slot = item; return } 

Шаг 2, чтобы петли с &mut указателем, что мы обновляем длинный путь сложнее.

По умолчанию Rust будет reborrow a &mut который разыменовывается. Он не употребляет ссылку, она просто считает, что она заимствована, пока продукт позаимства все еще жив.

Очевидно, что здесь не очень хорошо. Мы хотим «отменить» от старого current до нового current. Мы можем заставить указатель &mut подчиняться вместо семантике перемещения.

Нам нужна эта (функция тождественность силы двигаться!):

match moving(current).next 

мы также можем написать так:

let tmp = current; 
match tmp.next 

или это:

match {current}.next 

Шаг 3, у нас нет текущего указателя после того, как мы посмотрели внутрь, поэтому адаптируем код к что.

• Используйте ref mut slot, чтобы окупить местоположение следующего значения.
• next от Some(ref mut next) до вне матча, так что другая ветка с None уже возвращена и ее заимствование не противоречит обновлению current на последней строке цикла. Это было необязательно.