rust - programacion - ¿Cómo modelar estructuras de datos recursivas complejas(gráficos)?

recursividad estructura de datos ejemplos

Question

Estoy muy interesado en Rust y ahora estoy empezando mi primer proyecto no trivial en el idioma. Todavía estoy teniendo algunos problemas para entender completamente los conceptos de préstamo y de por vida.

La aplicación es un simulador de compuerta lógica en el cual los componentes se definen recursivamente (en términos de otros componentes y sus interconexiones).

Mi plan actual es implementar esto de manera similar a como lo haría en C ++ al tener una estructura de componentes que posee un vector de componentes (sus subcomponentes) y un vector de redes que describen las interconexiones entre esos componentes:

pub struct Pin {
    name: String
}

pub struct Net<''a> {
    nodes: Vec<(&''a Component<''a>,&''a Pin)>
}

pub struct Component<''a> {
    sub_components: Vec<Box<Component<''a>>>,
    in_pins: Vec<Pin>,
    out_pins: Vec<Pin>,
    netlist: Vec<Net<''a>>
}

impl<''a> Component<''a> {
    pub fn new() -> Component<''a> {
        ...
    }

    pub fn add_subcomponent( & mut self, comp: Component<''a> ) {
        // -> &Box<Component<''a>> ??
        ....
    }
}

En C ++, Net sería fácil de implementar como una serie de punteros a Componentes, pero no estoy seguro de cuál es la mejor manera de hacerlo en Rust. Supongo que debería usar punteros prestados. ¿O hay un mejor camino?

Considera lo siguiente principal:

fn main() {
    let sub1 = Component::new();
    let sub2 = Component::new();
    let circuit = Component::new();

    circuit.add_subcomponent( sub1 );
    circuit.add_subcomponent( sub2 );
    // sub1 and sub2 are now empty...
}

¿Cómo puedo configurar el circuito para crear una red entre sub1 y sub2? ¿Debo tener add_subcomponent devuelve un puntero prestado al Componente agregado? o la caja?

Sería genial si alguien pudiera apuntarme en la dirección correcta.

Muchas gracias.

Answer 1

No se puede representar una estructura de gráfico arbitraria en un óxido seguro.

La mejor manera de implementar este patrón es usar código inseguro y punteros sin procesar, o una abstracción existente que envuelva esta funcionalidad en una api segura, por ejemplo, http://static.rust-lang.org/doc/master/std/cell/struct.RefCell.html

Por ejemplo, la lista enlazada bidireccional típica sería:

struct Node {
  next: Option<Node>, // Each node ''owns'' the next one
  prev: *mut Node     // Backrefs are unsafe
}

Ha habido una serie de implementaciones ''seguras'' flotando alrededor, donde tienes algo como:

struct Node {
    id: u32,
    next: u32,
    prev: u32
}
struct Nodes {
  all:Vec<Node>,
  root:Option<Node>
}

Esto es "técnicamente" seguro, pero es un patrón terrible; rompe todas las reglas de seguridad simplemente implementando manualmente los punteros en bruto. Aconsejo fuertemente no hacerlo.

Puedes intentar usar referencias, por ejemplo:

struct Container<''a> {
  edges:Vec<Edge<''a>>,
  pub root: Node
}

struct Node {
  children:Vec<Node>  
}

struct Edge<''a> {
  n1: &''a Node,
  n2: &''a Node
}

... pero te tropezarás casi de inmediato en el infierno del verificador de préstamos. Por ejemplo, cuando elimina un nodo, ¿cómo sabe el verificador de préstamos que los enlaces asociados en ''bordes'' ya no son válidos?

Aunque es posible que puedas definir las estructuras, poblarlas será extremadamente problemático.

Sé que esa es probablemente una respuesta bastante insatisfactoria; Puede que le resulte útil buscar "gráfico de óxido" y "árbol de óxido" en github y ver las implementaciones que otras personas han hecho.

Por lo general, imponen la propiedad única de un subárbol a un objeto principal.