ps4 - rust traduccion

Prestamos mutables múltiples durante una búsqueda de árbol en profundidad

Question

¿Cómo se podría reestructurar esta función que realiza una búsqueda en profundidad y devuelve el elemento primario del nodo coincidente?

Sé que las variaciones de este problema han surgido muy a menudo (por ejemplo, múltiples préstamos mutables al generar una estructura de árbol con una función recursiva en Rust , préstamo mutuo que no termina donde se esperaba ), pero todavía no puedo encontrar la forma de modificarlo. trabajo. He intentado variaciones usando slices, std::mem::drop , y agregando parámetros de por vida where ''a: ''b pero aún no he descifrado escribirlo sin tomar prestado de forma mutable una variable en una rama y luego usar la variable en otra rama

#[derive(Clone, Debug)]
struct TreeNode {
    id: i32,
    children: Vec<TreeNode>,
}

// Returns a mutable reference to the parent of the node that matches the given id.
fn find_parent_mut<''a>(root: &''a mut TreeNode, id: i32) -> Option<&''a mut TreeNode> {
    for child in root.children.iter_mut() {
        if child.id == id {
            return Some(root);
        } else {
            let descendent_result = find_parent_mut(child, id);
            if descendent_result.is_some() {
                return descendent_result;
            }
        }
    }
    None
}

fn main() {
    let mut tree = TreeNode {
        id: 1,
        children: vec![TreeNode {
                           id: 2,
                           children: vec![TreeNode {
                                              id: 3,
                                              children: vec![],
                                          }],
                       }],
    };
    let a: Option<&mut TreeNode> = find_parent_mut(&mut tree, 3);
    assert_eq!(a.unwrap().id, 2);
}

error[E0499]: cannot borrow `*root` as mutable more than once at a time
  --> src/main.rs:11:25
   |
9  |     for child in root.children.iter_mut() {
   |                  ------------- first mutable borrow occurs here
10 |         if child.id == id {
11 |             return Some(root);
   |                         ^^^^ second mutable borrow occurs here
...
20 | }
   | - first borrow ends here

Aquí está con las sugerencias de @huon y los errores continuos del compilador:

fn find_parent_mut<''a>(root: &''a mut TreeNode, id: i32) -> Option<&''a mut TreeNode> {
    for child in root.children {
        if child.id == id {
            return Some(root);
        }
    }
    for i in 0..root.children.len() {
        let child: &''a mut TreeNode = &mut root.children[i];
        let descendent_result = find_parent_mut(child, id);
        if descendent_result.is_some() {
            return descendent_result;
        }
    }
    None
}

error[E0507]: cannot move out of borrowed content
 --> src/main.rs:9:18
  |
9 |     for child in root.children {
  |                  ^^^^ cannot move out of borrowed content

error[E0499]: cannot borrow `root.children` as mutable more than once at a time
  --> src/main.rs:15:44
   |
15 |         let child: &''a mut TreeNode = &mut root.children[i];
   |                                            ^^^^^^^^^^^^^
   |                                            |
   |                                            second mutable borrow occurs here
   |                                            first mutable borrow occurs here
...
22 | }
   | - first borrow ends here

Answer 1

Logré que funcionara de esta manera:

fn find_parent_mut<''a>(root: &''a mut TreeNode, id: i32)
        -> Option<&''a mut TreeNode> {
    if root.children.iter().any(|child| {child.id == id}) {
        return Some(root); 
    }
    for child in &mut root.children {
        match find_parent_mut(child, id) {
            Some(result) => return Some(result),
            None => {}
        }
    }
    None
}

Primero en su segundo intento, escribió for child in root.children lugar de for child in &mut root.children (tenga en cuenta el missing &mut ), que causó que root.children fuera consumido por el bucle en lugar de iterar, por lo tanto cannot move out of borrowed content error de cannot move out of borrowed content .

También lo doblé de una manera más iterativa, usando la función any(..) .

Para el segundo ciclo, no estoy exactamente seguro de lo que estaba pasando, al parecer vinculante las referencias a las variables era confuso el prestamista. Eliminé cualquier variable temporal, y ahora compila.

Answer 2

Uno puede hacer esto en un solo paso haciendo la búsqueda, registrando algunos datos y luego calculando el valor de retorno de manera eficiente fuera del ciclo:

let mut found = Err(());
for (i, child) in root.children.iter_mut().enumerate() {
    if child.id == id {
        found = Ok(None);
        break;
    }  else find_parent_mut(child, id).is_some() {
        found = Ok(Some(i));
        break;
    }
}
match found {
    Ok(Some(i)) => Some(&mut root.children[i]),
    Ok(None) => Some(root),
    Err(()) => None,
}

Esto evita los problemas causados ​​por la devolución condicional de variables mutables (que son los problemas que usted y mi respuesta a continuación se encontraron) evitando por completo las devoluciones dentro del ciclo interno.

Respuesta antigua / incorrecta:

No puedo probar mis sugerencias en este momento, pero creo que la mejor manera de resolver esto es regresar a la root fuera del ciclo.

for child in &mut root.children {
    if child.id == id {
        found = true;
        break
    } ...
}
if found {
    Some(root)
} else {
    None
}

Esto (con suerte) garantiza que la root no se preste a través de los children cuando se manipula.

Sin embargo, sospecho que el retorno temprano dentro del ciclo principal puede interferir, en cuyo caso uno podría tener que volver a enteros e indexar:

for i in 0..root.children.len() {
    if root.children[i].id == id {
        return Some(root)
    ...
}