Что я делаю неправильно в этом коде, чтобы реализовать функцию `dequeue` для очереди?

Я пытаюсь реализовать функцию dequeue для очереди, но не понимаю, как работает средство проверки заимствования. Что я делаю неправильно в этом коде?

use std::cell::RefCell;
use std::rc::Rc;
use std::mem::replace;

type Link<T> = Option<Rc<RefCell<Node<T>>>>;

struct Node<T>{
    item: T,
    next: Link<T>
}
pub struct Queue<T>{
    first: Link<T>,
    last: Link<T>,
    length: usize
}

impl<T> Queue<T>{
    pub fn new() -> Queue<T> {
        Queue {
            first: None,
            last: None,
            length: 0
        }
    }
    pub fn is_empty(&self) -> bool {
        self.length == 0
    }
    pub fn size(&self) -> usize {
        self.length
    }
    pub fn enqueue(&mut self, item: T) {
        let temp = self.last.take();
        self.last = Some(Rc::new(RefCell::new(Node{
            item,
            next: None
        })));
        if self.is_empty() {
            self.first = self.last.clone();
        } else {
            let temp = temp.unwrap();
            temp.borrow_mut().next = self.last.clone();
        }
        self.length += 1;
    }
    pub fn dequeue(&mut self) -> Result<T, String>{
        if let Some(ref mut value) = self.first.take() {
            let mut temp = *(value.borrow_mut());
            let next = *(temp.next.unwrap().borrow_mut());
            let old_value = replace(&mut temp, next);
            return Ok(old_value.item);
        }
        Err("Queue is empty".to_owned())
    }
}

Получив изменяемую ссылку на значение внутри Some, я хочу заменить его узлом, на который ссылается поле next узла. Нужно ли мне владеть значением внутри Some? Могу ли я сделать это?


queue rust ownership borrow-checker
person codeNoob    schedule 06.08.2017    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Вот реализация dequeue:

pub fn dequeue(&mut self) -> Result<T, String> {
    // First, disconnect `self.last` from the element it is pointing,
    // since it will have to be updated anyway. If there is no elemen in the
    // queue, we're done.
    let first = try!(self.first.take().ok_or("Queue is empty".to_owned()));
    // if there are two Rc's pointing to this node, then this must be the
    // only node, so `self.last` has to go
    if Rc::strong_count(&first) == 2 {
        self.last = None;
    }
    let first_node = Rc::try_unwrap(first).ok().expect(
        "This should be the only owner of the node"
    ).into_inner();
    self.first = first_node.next;
    self.length -= 1;
    Ok(first_node.item)
}

Вот полный код. Я также добавил dequeue_back, чтобы сделать эту очередь почти двусторонней, и несколько тестов.

person Victor Savu    schedule 06.08.2017