Come modellare strutture dati ricorsive complesse (grafici)?

Question

Sono molto interessato a Rust e sto iniziando il mio primo progetto non banale nella lingua. Ho ancora un po 'di problemi a comprendere appieno i concetti di prestito e durata.

L'applicazione è un simulatore di porte logiche in cui i componenti sono definiti in modo ricorsivo (in termini di altri componenti e relative interconnessioni).

mio piano attuale è di attuare questo simile come farebbe in C++ avendo una struttura di componenti possedere un vettore di componenti (sue sottocomponenti) e un vettore di reti che descrivono le interconnessioni tra i componenti:

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>> ?? 
     .... 
    } 
} 

In C++, la rete sarebbe facile da implementare come una serie di puntatori ai componenti ma non sono sicuro del modo migliore per farlo in Rust, suppongo che dovrei usare i puntatori presi in prestito? O c'è un modo migliore?

Si consideri il seguente principale:

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... 
} 

Come posso configurare circuito di creare una rete tra i sub1 e sub2? Devo aggiungere add_subcomponent a un puntatore preso in prestito per il componente aggiunto? o la scatola?

Sarebbe bello se qualcuno potesse indicarmi la giusta direzione.

Grazie mille.

Answer 1

Non è possibile rappresentare una struttura arbitraria del grafico in condizioni di ruggine sicura.

Il modo migliore per attuare questo modello è quello di utilizzare il codice pericoloso e puntatori prime o l'astrazione esistente che avvolge questa funzionalità in un api sicuro, per esempio http://static.rust-lang.org/doc/master/std/cell/struct.RefCell.html

Ad esempio, l'elenco tipico direzionale collegata bi sarebbe BE:

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

ci sono stati un certo numero di implementazioni di 'sicuro' in giro, dove si ha qualcosa di simile:

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

Questo è "tecnicamente" sicuro, ma è uno schema terribile; rompe tutte le regole di sicurezza semplicemente implementando manualmente i puntatori grezzi. Vi consiglio vivamente di non farlo.

Si potrebbe provare a utilizzare i riferimenti, ad esempio:

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

struct Node { 
    children:Vec<Node> 
} 

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

... ma sarete inciampare quasi subito in prestito checker inferno. Ad esempio, quando si rimuove un nodo, come fa il correttore di prestiti a sapere che i collegamenti associati in "spigoli" non sono più validi?

Sebbene sia possibile definire le strutture, la loro compilazione sarà estremamente problematica.

So che probabilmente è una risposta abbastanza insoddisfacente; potresti trovare utile cercare github per 'ruggine grafico' e 'ruggine albero' e guardare le implementazioni che altre persone hanno fatto.

In genere applicano la proprietà singola di un sottoalbero a un oggetto padre.